不同质因数函数的速度

Question

我有这 3 个素因子函数，但我不明白它们的时间复杂度差异。

这是我开始使用的第一个功能，希望能做得更快。我已经有了一个相当快的素数函数，但我认为 Sieve 会更快。

def is_prime(i):
    if i <= 1: return False
    if i <= 3: return True
    if i%3 == 0 or i%2 == 0: return False
    return sum((1 for y in xrange(5, int(i**0.5)+1, 6) if i%y == 0 or i%(y+2) == 0)) == 0

prime_factors_1 = lambda x: [i for i in range(1,x) if x%i == 0 and is_prime(i)]

这是我在这个人的博客上找到的埃拉托色尼筛法实现：http://www.drmaciver.com/2012/08/sieving-out-prime-factorizations/

def prime_factorizations(n):
   sieve = [[] for x in xrange(0, n+1)]
   for i in xrange(2, n+1):
      if not sieve[i]:
         q = i
         while q < n:
             for r in xrange(q, n+1, q):
                 sieve[r].append(i)
             q *= i
   return sieve[-1]

我喜欢尝试改进我找到的示例，并且我喜欢尝试减少行数，同时保留功能和 time/space 效率。我可能对这个列表的理解有点过头了。

def prime_factors_2(n):
    factors = [[] for n in xrange(0,n+1)]
    [[[factors[r].append(i) for r in xrange(q, n+1, q)] for q in range(i,n,i)] for i in (y for y in xrange(2,n+1) if not factors[y])]   
    return factors[-1]

我计时并得到了这个输出：

prime_factorizations: 1.11333088677
prime_factors_1:      0.0737618142745
prime_factors_2:     10.7310789671

关于这些时间，有几点我不明白：

为什么非筛法最快？
- 是不是因为它只产生不同的素因子？
为什么带有列表推导的筛子这么慢？
- （分层）列表理解本身就比较慢吗？
什么算法会比我原来的非筛法更快？

Answer 1

Why is the non-sieve far fastest?

其他函数做了大量工作来生成您不关心的数字因子。

Why is the sieve with list comprehension so much slower?

因为你搞砸了。这部分：

[[[factors[r].append(i) for r in xrange(q, n+1, q)] for q in range(i,n,i)] for i in (y for y in xrange(2,n+1) if not factors[y])]
#                                                   ^^^^^^^^^^^^^^^^^^^^^

不等同于原始代码中的 while 循环，后者将 q 乘以 i 而不是添加 i。但是，即使您做对了，使用列表推导式来处理副作用也会造成混淆，这与列表推导式的目的背道而驰，并且会浪费 space 用于您构建的巨大嵌套 Nones 列表。

What algorithm will be faster than my original non-sieve?

您可以除掉已发现的质因数，以消除检查后续因数是否为质性的需要，并减少需要检查的因数：

def prime_factors(n):
    factors = []
    if n % 2 == 0:
        factors.append(2)
        while n % 2 == 0:
            n //= 2
    candidate = 3
    while candidate * candidate <= n:
        if n % candidate == 0:
            factors.append(candidate)
            while n % candidate == 0:
                n //= candidate
        candidate += 2
    if n != 1:
        factors.append(n)
    return factors

不同质因数函数的速度

Speed of different prime factor functions

python

performance

list-comprehension

prime-factoring