擅长:python、mysql、java
<p>在使用Python3.5.2时,<code>numpy.roots</code>内存不足,当我试图确定unity的第1200个根时,我的Chromebook崩溃了。崩溃发生在他们构造多项式的伴随矩阵时,所以我不认为他们使用的是稀疏表示。从文件中:</p>
<blockquote>
<p>The algorithm relies on computing the eigenvalues of the companion matrix</p>
</blockquote>
<p>如果您只需要计算单位根,三角法方法在时间和空间复杂性方面都是渐进式的更好:</p>
<pre><code>def nthRootsOfUnity1(n): # linear space, parallelizable
from numpy import arange, pi, exp
return exp(2j * pi / n * arange(n))
</code></pre>
<p>如果您愿意放弃并行化,可以使用生成器为每个额外的根实现恒定的空间和恒定的时间,而第一种方法必须在返回之前计算所有n个根:</p>
^{pr2}$
<p>在我的机器上,在不使用并行化的情况下,这些方法在<code>numpy.roots</code>计算第1000个根所需的时间内计算出第10000000个根:</p>
<pre><code>In [3]: n = 1000
In [4]: %time _ = sum(numpy.roots([1] + [0]*(n - 1) + [-1]))
CPU times: user 40.7 s, sys: 811 ms, total: 41.5 s
Wall time: 10.8 s
In [5]: n = 10000000
In [6]: %time _ = sum(nthRootsOfUnity1(n))
CPU times: user 4.98 s, sys: 256 ms, total: 5.23 s
Wall time: 5.23 s
In [7]: %time _ = sum(nthRootsOfUnity2(n))
CPU times: user 11.6 s, sys: 2 ms, total: 11.6 s
Wall time: 11.6 s
</code></pre>