如何优化我的 Sage 可还原性算法的速度？

Question

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

使用 Sage，我找到了这些可归约的 A 多项式的数量。例如，假设我设置了 n=5 和 A=10^7。这会告诉我这些 10^7 次 5 多项式中有多少是可约的。我使用循环完成了此操作，该循环适用于 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

一个很小但在这种情况下毫无意义的优化是用 xrange(A) 替换 range(A)。前者将创建一个包含从 0 到 A - 1 的所有整数的数组，这是浪费时间和 space。 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 但我倾向于发现它们在加速大范围值的小计算的情况下有点缺乏（它们可以用于此但它需要一些小心，例如手动批处理您的输入；我不喜欢它...)

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

如何优化我的 Sage 可还原性算法的速度？

How do I optimize the speed of my Sage reducibility algorithm?

sage