为什么在访问单个数字时，大整数除法比切片（数字）字符串更快？

Question

我正在做一项（典型的）寻找素数的作业。我认为我会很聪明，对于大数，用这个技巧跳过除法过程：

def div5(candidate):
    return str(candidate)[-1] == "5"

将 5 添加到自身几千次似乎是一种浪费（我只需要最后一个成员），但我想确定一下。

归功于unutbu Measure time elapsed in Python?

%>python -mtimeit -s"import intDiv" "intDiv.div5(2147483645)"
1000000 loops, best of 3: 0.272 usec per loop

%>python -mtimeit -s"import strDiv" "strDiv.str5(2147483645)"
1000000 loops, best of 3: 0.582 usec per loop

澄清一下，这是我定义的两个方法。

def div5(maxi): return not (maxi%5)

---

def str5(maxi): return str(maxi)[-1] == '5'

这太慢了。如何分析 str(maxi) 的最后一个成员，而不转换整个数字（不必要）？

感谢 @Claudiu 帮助清理了那些碍眼的东西。

Answer 1

% python -mtimeit "str(2147483645)"
1000000 loops, best of 3: 0.321 usec per loop

% python -mtimeit "2147483645 % 5"
10000000 loops, best of 3: 0.0351 usec per loop

% python -mtimeit "'2147483645'[-1]"
10000000 loops, best of 3: 0.0349 usec per loop

我想说瓶颈在于转换为字符串。

Answer 2

一个问题是将整数转换为字符串。这比整数除法要工作得多。
我不确定Python是如何做到这一点的，但大多数算法的工作原理都是这样的

def tostring(value):
    result = ""
    while True:
        digit = value % 10
        value = value / 10
        result = chr(digit + ord('0')) + result
        if value == 0: break

    return result

，即每个值有多个模运算。

Answer 3

将数字转换为字符串将如下所示：

digits = []
while x:
    digits.append(x % 10)
    x //= 10

您可以看到这将执行大量 % 操作（除了构建数字或字符串列表之外）。

除了这个优化问题之外，您的函数不正确。例如，10 不以 5 结尾，但可以被 5 整除。

Answer 4

您需要检查 5 和 0 是否能被 5 整除：

def str5(candidate):
    return str(candidate)[-1] in ["5","0"]

使用 6k±1 怎么样。如果该数字不能是素数，则返回 False。 2147483645%6 = 5 因此它可能是素数并且需要检查。此代码的运行时间比 div5 检查稍长一些，但您可以确定数字是否不能是素数。 3 以上的所有素数都符合序列 6k±1。所以 6(1)±1 = (5,7) 6(3)±1 = (17,19) 等等。模 6 都返回 5 或 1 作为余数。

def is6k(candidate):
    if candidate<=3: return candidate>1
    if candidate%5==0: return False
    return candidate%6 in [1,5]

我的 isPrime 适合小于 10**15 的数字。它还仅检查 sqrt(n) 并仅除以可能的素数。 for 循环将 p 和 q 设置为 5,7 11,13 17,19 23,25 29,31...

def isPrime(n):  
    if (n <= 3): return n > 1      
    if n%6 not in [1,5]: return False      
    for p,q in ((i,i+2) for i in range(5,int(n**.5)+1,6)): 
        if (n%p == 0 or n%q == 0):  return False          
    return True  

时间：

$ python -mtimeit -s"import prime" "prime.div5(2147483645)"
1000000 loops, best of 5: 145 nsec per loop


$ python -mtimeit -s"import prime" "prime.is6k(2147483645)"
1000000 loops, best of 5: 210 nsec per loop

整个素数测试需要更长的时间：

$ python -mtimeit -s"import prime" "prime.isPrime(2147483645)"
100000 loops, best of 5: 1.96 usec per loop