python - 如何在 python 中高效地多线程或多进程处理大型 itertools.combinations？

Question

目标(较大问题的最简单概述)

我正在反复搜索一个大整数的最接近幂和的列表。

一些背景
我是多线程的新手。我的理解是，我目前的瓶颈可能会通过多线程得到缓解。但是，我不确定是否有其他方法更适合做进一步的改进。

代码

from itertools import combinations
from math import log, ceil

num = 26115155829

pwr = {n**p:str(n)+'^'+str(p) for n in range(9999,1,-1) for p in range(2,ceil(log(num,n)))}
pk = tuple(sorted(pwr.keys()))

sum2 = [(abs(num-(a+b)),' + '.join((pwr[a],pwr[b]))) for a,b in combinations(pk,2) if abs(num-(a+b)) < 99999]
sum3 = [(abs(num-(a+b+c)),' + '.join((pwr[a],pwr[b],pwr[c]))) for a,b,c in combinations(pk,3) if abs(num-(a+b+c)) < 99999]

_ 描述 _

 num: Example of a large integer (usually 10 to 18 digits long)
 pwr: Dictionary comprehension of possible base^exponent power pairs; 4 to 1 digits Base start as decreasing so as to overwrite duplicates with smaller base representation, Power is limited to be lower than target large integer
 sumN: Filtered list comprehension of the sum of N powers having a distance lower than ~100000 to the target

---

示例输出
>>> print(*sorted(sum2)[:100],sep='\n')

(57, '4774^2 + 2966^3')
(1052, '969^3 + 2932^3')
(3654, '2052^3 + 2595^3')
(5004, '8691^2 + 2964^3')
(5560, '7012^2 + 2965^3')
(8465, '7013^2 + 2965^3')
(9492, '4775^2 + 2966^3')
(9604, '4773^2 + 2966^3')
(12379, '8692^2 + 2964^3')
(13680, '1486^3 + 2837^3')
(19043, '4776^2 + 2966^3')
(19149, '4772^2 + 2966^3')
(19583, '7011^2 + 2965^3')
(22385, '8690^2 + 2964^3')
(22492, '7014^2 + 2965^3')
(24445, '1518^3 + 2828^3')
(28596, '4777^2 + 2966^3')
(28692, '4771^2 + 2966^3')
(29764, '8693^2 + 2964^3')
(30338, '843^3 + 2944^3')
(30347, '1976^3 + 2640^3')
(30581, '1072^3 + 120^5')
(33604, '7010^2 + 2965^3')
(36521, '7015^2 + 2965^3')
(37919, '467^3 + 2963^3')
(38151, '4778^2 + 2966^3')
(38233, '4770^2 + 2966^3')
(39764, '8689^2 + 2964^3')
(46766, '791^3 + 2948^3')
(47151, '8694^2 + 2964^3')
(47623, '7009^2 + 2965^3')
(47708, '4779^2 + 2966^3')
(47772, '4769^2 + 2966^3')
(50552, '7016^2 + 2965^3')
(55208, '1021^3 + 2926^3')
(57141, '8688^2 + 2964^3')
(57267, '4780^2 + 2966^3')
(57309, '4768^2 + 2966^3')
(58112, '2157^3 + 2524^3')
(59445, '1694^3 + 2770^3')
(60912, '1748^3 + 2749^3')
(61640, '7008^2 + 2965^3')
(62883, '1733^3 + 2755^3')
(64540, '8695^2 + 2964^3')
(64585, '7017^2 + 2965^3')
(66828, '4781^2 + 2966^3')
(66844, '4767^2 + 2966^3')
(73647, '855^3 + 2943^3')
(74516, '8687^2 + 2964^3')
(75655, '7007^2 + 2965^3')
(76377, '4766^2 + 2966^3')
(76391, '4782^2 + 2966^3')
(78620, '7018^2 + 2965^3')
(81931, '8696^2 + 2964^3')
(85237, '1045^3 + 2923^3')
(85268, '280^4 + 2713^3')
(85908, '4765^2 + 2966^3')
(85956, '4783^2 + 2966^3')
(87470, '731^3 + 2952^3')
(89668, '7006^2 + 2965^3')
(91889, '8686^2 + 2964^3')
(91936, '2328^3 + 2381^3')
(92657, '7019^2 + 2965^3')
(95437, '4764^2 + 2966^3')
(95523, '4784^2 + 2966^3')
(99324, '8697^2 + 2964^3')
(99736, '638^3 + 2957^3')

>>> print(*sorted(sum3)[:100],sep='\n')

(0, '1724^3 + 1893^3 + 2422^3')
(0, '2798^2 + 6430^2 + 2965^3')
(0, '462^2 + 8679^2 + 2964^3')
(0, '5577^2 + 6666^2 + 2964^3')
(0, '98^2 + 4773^2 + 2966^3')
(1, '1485^2 + 9984^2 + 2963^3')
(1, '1932^2 + 6741^2 + 2965^3')
(1, '2499^2 + 6552^2 + 2965^3')
(1, '2709^2 + 6468^2 + 2965^3')
(1, '3549^2 + 6048^2 + 2965^3')
(1, '5571^2 + 1510^3 + 2829^3')
(2, '4454^2 + 9058^2 + 2963^3')
(2, '4574^2 + 8998^2 + 2963^3')
(3, '2133^2 + 4271^2 + 2966^3')
(3, '2137^2 + 4269^2 + 2966^3')
(3, '2682^2 + 9731^2 + 2963^3')
(3, '295^3 + 127^4 + 2956^3')
(3, '3693^2 + 9394^2 + 2963^3')
(3, '4969^2 + 2095^3 + 2566^3')
(3, '7022^2 + 7251^2 + 2963^3')
(4, '1692^2 + 8525^2 + 2964^3')
(4, '1717^2 + 8520^2 + 2964^3')
(4, '2410^2 + 2302^3 + 2405^3')
(4, '3148^2 + 217^4 + 2880^3')
(4, '3533^2 + 2225^3 + 2471^3')
(4, '3746^2 + 5928^2 + 2965^3')
(4, '4642^2 + 5256^2 + 2965^3')
(4, '560^2 + 6990^2 + 2965^3')
(4, '5684^2 + 6575^2 + 2964^3')
(4, '5901^2 + 9664^2 + 2962^3')
(4, '6095^2 + 1318^3 + 2876^3')
(4, '6100^2 + 6191^2 + 2964^3')
(4, '6651^2 + 9164^2 + 2962^3')
(4, '6892^2 + 2200^3 + 2489^3')
(4, '7949^2 + 8064^2 + 2962^3')
(5, '2397^2 + 6590^2 + 2965^3')
(5, '2685^2 + 6478^2 + 2965^3')
(5, '322^2 + 7005^2 + 2965^3')
(5, '4031^2 + 9254^2 + 2963^3')
(5, '4525^2 + 1006^3 + 2927^3')
(5, '4947^2 + 4970^2 + 2965^3')
(5, '6199^2 + 2335^3 + 2372^3')
(5, '7441^2 + 8535^2 + 2962^3')
(5, '8003^2 + 9512^2 + 2961^3')
(5, '8932^2 + 9897^2 + 11^10')
(6, '3^13 + 4604^2 + 2966^3')
(6, '790^2 + 1211^3 + 2898^3')
(7, '2192^2 + 531^3 + 2961^3')
(7, '2858^2 + 3824^2 + 2966^3')
(7, '2^6 + 4774^2 + 2966^3')
(7, '346^2 + 318^4 + 2514^3')
(7, '4135^2 + 9208^2 + 2963^3')
(7, '4523^2 + 794^3 + 2947^3')
(7, '543^3 + 2036^3 + 2597^3')
(8, '1330^2 + 4585^2 + 2966^3')
(8, '1687^2 + 4466^2 + 2966^3')
(8, '209^3 + 9631^2 + 2963^3')
(8, '2135^2 + 4270^2 + 2966^3')
(8, '2422^2 + 8347^2 + 2964^3')
(8, '2454^2 + 4095^2 + 2966^3')
(8, '2870^2 + 3815^2 + 2966^3')
(8, '4138^2 + 7643^2 + 2964^3')
(8, '5357^2 + 8555^2 + 2963^3')
(8, '5893^2 + 8195^2 + 2963^3')
(8, '7743^2 + 8262^2 + 2962^3')
(8, '7^2 + 4774^2 + 2966^3')
(8, '854^2 + 4697^2 + 2966^3')
(9, '2314^2 + 1623^3 + 2795^3')
(9, '4739^2 + 2203^3 + 2488^3')
(9, '4812^2 + 8873^2 + 2963^3')
(9, '564^2 + 1301^3 + 2881^3')
(9, '6318^2 + 2217^3 + 351^4')
(10, '3376^2 + 2099^3 + 2564^3')
(10, '7913^2 + 9587^2 + 2961^3')
(10, '9748^2 + 1859^3 + 2696^3')
(11, '8520^2 + 332^4 + 2404^3')
(11, '8951^2 + 147^4 + 2946^3')
(12, '1364^2 + 4575^2 + 2966^3')
(12, '1454^2 + 6860^2 + 2965^3')
(12, '18^4 + 4763^2 + 2966^3')
(12, '2131^2 + 4272^2 + 2966^3')
(12, '2139^2 + 4268^2 + 2966^3')
(12, '2277^2 + 4196^2 + 2966^3')
(12, '2335^2 + 4164^2 + 2966^3')
(12, '2459^2 + 4092^2 + 2966^3')
(12, '2505^2 + 4064^2 + 2966^3')
(12, '3117^2 + 3616^2 + 2966^3')
(12, '3336^2 + 3415^2 + 2966^3')
(12, '455^2 + 130^4 + 2956^3')
(12, '488^2 + 4749^2 + 2966^3')
(12, '696^2 + 4723^2 + 2966^3')
(12, '9139^2 + 9864^2 + 2960^3')
(12, '9427^2 + 1308^3 + 2876^3')
(13, '1646^2 + 8534^2 + 2964^3')
(13, '273^2 + 8687^2 + 2964^3')
(13, '5152^2 + 1400^3 + 2858^3')
(13, '533^2 + 1228^3 + 2895^3')
(13, '6728^2 + 62^5 + 2930^3')
(13, '7160^2 + 506^3 + 2960^3')
(14, '4088^2 + 2211^3 + 2482^3')

Answer 1

多线程有用吗？

正如@Blckknght 指出的那样，CPython 的多线程受到 GIL (Global Interpreter Lock) 的限制。 .由于一次只能运行一个线程，线程化对提高 CPU 绑定(bind)代码的性能没有帮助吗？

多处理有帮助吗？

是的，multi-processing module非常适合提高 CPU 绑定(bind)代码的性能，但仅适用于以下问题:

1) 可以分割成独立的子问题

2)没有抵消并行处理优势的通信开销

可以将组合划分为子问题吗？

combinations 迭代器的单次运行不容易分区(它无法从迭代序列​​的中间开始)。

但是，您可以在单独的进程中运行 combinations(pk, 2) 和 combinations(pk, 3)。