有 999 个数,[000,001,002,...,999]
每 2 个组合成一对,
如
('000', '001')
('000', '002')
('000', '003')
('001', '002')
('001', '003')
('002', '003')
.............
当 2 个一组时,有 498501 种组合,显示打印出来耗费:3.6621711 秒
当 3 个一组时,有 165668499 种组合,显示打印出来耗费:20.6741886 秒
.............
请问当 400 个一组时,有多少种组合?怎么在 10 秒完成?
我需要对每组数据进行统计编号,
如
1:('000', '001')
2:('000', '002')
3:('000', '003')
这岂不是非常占用内存空间?有什么更快速,更优雅的写法吗
import itertools
import time
z=[]
for i in range(0,999):
if i<10:
i = '00'+str(i)
elif 10<=i and i<100:
i ='0'+str(i)
else:
i=str(i)
z.append(str(i))
# 计时开始
start = time.perf_counter()
# 排序全部组合
z2 =(itertools.combinations((z), 3))
end = time.perf_counter()
print('排序组合耗费:',end-start)
c=0
for i in z2:
c+=1
print('组合数:',c)
# 计时结束
end = time.perf_counter()
print('一共耗费:',end-start)
1
clockwise9 2021-05-06 05:36:46 +08:00 via Android
|
2
IgniteWhite 2021-05-06 06:12:35 +08:00
numpy 更好些?回答不来
不过[000, 001, ... , 999]应该是 1000 个数,应该写成 range(0, 1000)或者 range(1000) |
3
aijam 2021-05-06 06:24:28 +08:00
400 个一组有 C(999, 400)种组合,10 的几百次方,比宇宙所有原子总数还多。。。
|
4
raysonx 2021-05-06 06:46:55 +08:00 via iPad
000-999 是 1000 个数。。。
|
5
xuanbg 2021-05-06 06:49:13 +08:00
申请超算
|
6
IgniteWhite 2021-05-06 08:09:44 +08:00
@aijam 楼主实际上一共有 1000 个数,用一楼的链接算出来 C(1000, 400) = 496527238625422886115073562889623132621341353659827604662932184012645905732096457382164964136575507417172339042089778751904887857092411910579077412408539948204974129778390437393954251676800524680653478266662364352619244180931154020701111982328000776980305955525649501369943202079996789539150
|
7
0ZXYDDu796nVCFxq 2021-05-06 08:12:35 +08:00 via Android
4.965272386 E+290 种组合
你需要重新学下高中数学 |
8
popil1987 2021-05-06 09:40:59 +08:00
python itertools combinations
pandas combine 都是这个功能,肯定比 for 循环要快 |
9
Vegetable 2021-05-06 09:41:52 +08:00
首先这个是可以通过数学计算的,不要这么穷举。
其次如果你有什么特别的需求要列出所有的组合,那你说这个数量级,建议你还是立刻冬眠等待人类走过几次科技革命好一点。 |
10
necomancer 2021-05-06 10:16:00 +08:00
这种情况是做一个生成器,itertools,pandas 之类的都是这么干的,然后每次操作是从生成器里取出下一个
|
11
necomancer 2021-05-06 10:16:26 +08:00
不会先全放在内存里再做什么操作。
|
12
DCELL 2021-05-06 14:46:43 +08:00
1.如果只是输出一共多少种可能,应该是有公式的
2.如果要输出全部组合,一般都是用回溯算法 |
13
no1xsyzy 2021-05-06 15:33:31 +08:00 8
C(1000, 400) > 4e290
10 秒内打印,也就是说每秒打印 >4e289 种可能性。 要区分这 >4e290 种可能性,需要 > log_2 4e290 > 962 bit > 120 bytes 也就是说每秒需要传输 > 4e289*120 B > 4e291 B 的数据 作为比较:yes | pv > /dev/null 采用目前输出速率最高的 GNU yes,2.92GiB/s 即每秒输出 3.135e9 B 中间差了 282 个数量级。 —— @necomancer 让咱们再假定你流式进行处理,每个操作只需要占用一个 CPU 周期,并且你的 CPU 有 64 核,且所有核心超频到 10GHz 4e290 / 64 / 10e9 > 6e278 秒 > 1e271 年 好吧,再让我们用上 GPU 加速每个操作可以用一个 CUDA 核心的一个时钟周期完成,一块 RTX 3090 按照 10496 CUDA 核心,假设超频到 3GHz,需要花费 4e290 / 10496 / 3e9 > 1e277 秒 > 3e269 年 这个数据量太离谱,itertools 也根本没得作用。 —— 如果要把 C(1000, 400) 量级的数据在 10 秒内输出,不要说比特币 51% 攻击了,99% 攻击都能发动了。 直接把链算到底,连计算难度都来不及变更,变更了也没用;这 CPU 比当今所有的 GPU 都快几百个数量级。 比特币暴跌,然后我能买到显卡了。 |
14
no1xsyzy 2021-05-06 15:43:50 +08:00 3
再脑洞下
处理大量信息时,根据 Landauer's principle,必然产生热量,随便地瞎估一下,应远大于 2.805zJ*4e290 相当于 2.682×10^260 吨 TNT 当量 你这不是 CPU,这是 1e250 吨的质量弹 |
15
ch2 2021-05-06 19:40:39 +08:00
你想计算的是一个天文数字
|
16
ZRS 2021-05-06 20:14:22 +08:00 via iPhone
我想说的楼上老哥们都说完了
|
17
lizytalk 2021-05-06 20:59:52 +08:00
高中排列组合?
|
19
0ZXYDDu796nVCFxq 2021-05-06 23:09:57 +08:00
@NeezerGu 2.682e260 吨 大约等于 2.09707e222 个银河系重量
等于 4.490958e238 个地球重量 |
20
yucongo 2021-05-07 14:25:58 +08:00
import more_itertools as mit
%time mit.ilen(itertools.combinations([f'{i:02}' for i in range(0, 999)], 400)) 内存并不是问题,时间是个问题,直到天荒地老也不会完结…… 当然,上面已经有大佬说了可以用 C(999, 400) |
21
julyclyde 2021-05-08 10:57:06 +08:00
我觉得关键是你不应该先把它括起来然后再循环
|