并行化第 n 个阶乘 python 程序的更好方法？

Question

我有这个 python 代码来计算连续 n 个“1”的第 n 个阶乘。我已经能够很好地优化它，包括使用多处理模块在所有内核上将其调整为运行。但是我注意到第 7 个进程（这是我从上到下的值的下限）比其余线程快得多。当 n=11 时，线程 0-6 平均耗时 32 秒，而线程 7 仅耗时 12 秒。我本以为数字本身会有所不同，但我不希望立即出现如此明显差异的墙。

我的代码中是否遗漏了导致这堵大墙的计算？我已经验证了输出并且每个段的长度几乎相同（线程 7 通过几十次计算略长，但在宏伟的计划中这没什么，线程 7 是最短的运行ning 无论如何）

是否有更好的并行化方法以提高效率？使线程不完全相同会有帮助吗？

编辑：添加python版本信息

Python 3.8.5（tags/v3.8.5:580fbb0，2020 年 7 月 20 日，15:57:54）[MSC v.1924 64 位 (AMD64)] on win32

（我对n=11做了25次测试，都和这个很相似运行）

import multiprocessing
import argparse
from datetime import datetime
from math import log10

parser = argparse.ArgumentParser(
    formatter_class=argparse.HelpFormatter,
    description="Calcs n factorial",
    usage=""
)

parser.add_argument("-n", "--number", type=int, default=2)

args = parser.parse_args()

def getlog(send_end, i, threads, num, n, inc):
    begin = datetime.now()
    start = num-inc*i
    end = num-inc*(i+1) if i < threads-1 else 0
    output = sum(map(log10, range(start, end, -n)))
    send_end.send(output)
    final = datetime.now()
    duration = final-begin
    print("{},{},{},{}".format(i, duration, start, end))

def main():
    n = args.number
    num = int('1'*n)
    threads = multiprocessing.cpu_count() if num/multiprocessing.cpu_count() > multiprocessing.cpu_count() else 1
    inc = int(num/threads)
    inc -= inc%n
    jobs = []
    pipe_list = []
    for i in range(threads):
        recv_end, send_end = multiprocessing.Pipe(False)
        p = multiprocessing.Process(target=getlog, args=(send_end, i, threads, num, n, inc))
        jobs.append(p)
        pipe_list.append(recv_end)
        p.start()
    for proc in jobs:
        proc.join()
    e = sum([output.recv() for output in pipe_list])

    print('%.2fe%d' % (10**(e % 1), e // 1))
    
if __name__ == '__main__':
    start = datetime.now()
    main()
    end = datetime.now()
    print(end-start)

Answer 1

迭代一百万个不同量级的数字的次数：

from timeit import repeat
from collections import deque

for e in range(26, 36):
    n = 2**e
    t = min(repeat(lambda: deque(range(n, n+10**6), 0), number=1))
    print(e, t)

我在 32 位 Python 在 64 位 Windows 上的输出，请注意从 2³⁰ 到 2³¹:

26 0.020830399999999916
27 0.020713199999999987
28 0.02067260000000004
29 0.021565000000000056
30 0.021966000000000152
31 0.16404839999999998
32 0.16630840000000013
33 0.16394810000000026
34 0.16302989999999973
35 0.1655395999999998

范围内的映射 log10 仍然显示大致相同的（绝对）增加：

26 0.14502039999999994
27 0.1435571
28 0.14378349999999962
29 0.14398270000000002
30 0.14687919999999988
31 0.29700239999999933
32 0.29499730000000035
33 0.2949491999999996
34 0.2964432000000006
35 0.2918921999999995

代码：

from timeit import repeat
from collections import deque
from math import log10

for e in range(26, 36):
    n = 2**e
    t = min(repeat(lambda: deque(map(log10, range(n, n+10**6)), 0), number=1))
    print(e, t)

~~并且您在线程 7 中的数字都是快速量级，而 most/all 其他线程中的数字是慢速量级。~~

~~你可以改变你的范围，让它们都经过所有星等。更简单的例子：使用范围 range(0, 10) 和 range(10, 20)，而不是范围 range(0, 20, 2) 和 range(1, 20, 2).~~

顺便说一句，当从 2³⁰ 到 2[=44 时，我看到 64 位 Python 在 64 位 Windows 上有类似的增长=]31。但是在 Linux 上的 64 位 Python 上，从 2³⁰ 到 2³¹ 时我没有看到任何增加，但是从 2⁶² 到 2⁶³.

更新：

以上striked-through段不正确。正如所示，并不是因为“数字”很慢（我曾想过），而是因为有两个完全独立的 range 实现。并且只有您的线程 7 使用快速线程（用于小数字的线程）。因此，我上面提出的让所有 threads/ranges 经历所有量级的建议实际上是 counter-productive。它不会让慢的更快，它只会让快的和其他的一样慢。无赖。

所以备选建议：不要像您那样给每个线程一个范围，而是给每个线程一部分 long 范围和一部分非 long 范围。这应该使所有线程同样快，并减少总时间。但是影响会很小，n越大影响越小，我怀疑这是否值得复杂化。

Answer 2

range 如果需要处理超出 C long 范围的值，则使用较慢的实现 - 请参阅 source.

您在 Windows，其中 C long 是 32 位的（甚至在 64 位 Python 版本上）。过程 7 是唯一一个范围元素在 C long.

范围内的过程

并行化第 n 个阶乘 python 程序的更好方法？

Better way to parallelize my nth factorial python program?

python

python-multithreading

python-3.x