我如何优化Sage约简算法的速度？

Question

假设我有多项式f(x) = x^n + x + a。我为n设置了一个值，并想要0 <= a <= A，其中A是我设置的其他值。这意味着我将总共拥有A个不同的多项式，因为a可以是0和A之间的任何值。

使用Sage，我找到了这些A多项式的可约数。例如，假设我设置了n=5和A=10^7。这将告诉我这些5级的10^7多项式中有多少是可约的。我使用循环完成此操作，该循环适用于A的低值。但是对于我需要的较大值（即A=10^7），这将花费非常长且不切实际的时间。代码如下。有人可以帮我有意义地优化吗？

x = polygen(QQ)
n = 5
A = 10^7
count = 0

for i in range(A):
    p_pol = x^n + x + i

    if not p_pol.is_irreducible():
        count = count + 1
        print(i)



print('Count:' + str(count))

Answer 1

一个很小的例子，但在这种情况下，毫无意义的优化是将range(A)替换为xrange(A)。前者将创建一个从0到A - 1的所有整数的数组，这是浪费时间和空间的。 xrange(A)只会一一生成整数，完成后将其丢弃。 Sage 9.0默认基于Python 3，其中range等效于xrange。

不过让我们做一点实验。另一个小的优化将是预定义您的多项式在每个循环中恒定的部分：

x = polygen(QQ)
n = 5
A = 10^7
base = x^n + x

现在作为一般测试，让我们看看在几种情况下将整数添加到多项式然后计算其不可约性需要多长时间：

sage: (base + 1).is_irreducible()
False
sage: %timeit (base + 1).is_irreducible()
1000 loops, best of 3: 744 µs per loop
sage: (base + 3).is_irreducible()
True
sage: %timeit (base + 3).is_irreducible()
1000 loops, best of 3: 387 µs per loop

因此，在不可约的情况下（似乎是大多数情况），它似乎要快一些，因此，平均而言，每个时间需要387µs。然后：

sage: 0.000387 * 10^7 / 60
64.5000000000000

因此，平均（在我的计算机上，这仍然需要花费一个多小时的时间。

如果您有许多CPU内核，可以加快速度的一件事就是并行化。例如：

x = polygen(QQ)
A = 10^7
def is_irreducible(i, base=(x^5 + x)):
    return (base + i).is_irreducible()

from multiprocessing import Pool
pool = Pool()
A - sum(pool.map(is_irreducible, xrange(A)))

原则上，您会得到相同的结果。虽然您获得的速度最多只能达到您最多拥有的CPU数量（通常少一些）。 Sage还附带了一些parallelization helpers，但是对于在较大值范围内加快小计算速度的情况，我倾向于发现它们有点缺乏（它们can可以用于此目的，但是它需要一些注意，例如手动批处理您的输入；我对此并不感到疯狂...）

除此之外，您可能需要使用一些数学直觉来尝试减少问题空间。