V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
996bujiaban
V2EX  ›  Python

求解, python3,当数据大的时候,怎么列出全部排序可能?

  •  
  •   996bujiaban · 2021-05-06 05:25:42 +08:00 · 2805 次点击
    这是一个创建于 1057 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有 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)
    
    21 条回复    2021-05-08 10:57:06 +08:00
    clockwise9
        1
    clockwise9  
       2021-05-06 05:36:46 +08:00 via Android
    IgniteWhite
        2
    IgniteWhite  
       2021-05-06 06:12:35 +08:00
    numpy 更好些?回答不来
    不过[000, 001, ... , 999]应该是 1000 个数,应该写成 range(0, 1000)或者 range(1000)
    aijam
        3
    aijam  
       2021-05-06 06:24:28 +08:00
    400 个一组有 C(999, 400)种组合,10 的几百次方,比宇宙所有原子总数还多。。。
    raysonx
        4
    raysonx  
       2021-05-06 06:46:55 +08:00 via iPad
    000-999 是 1000 个数。。。
    xuanbg
        5
    xuanbg  
       2021-05-06 06:49:13 +08:00
    申请超算
    IgniteWhite
        6
    IgniteWhite  
       2021-05-06 08:09:44 +08:00
    @aijam 楼主实际上一共有 1000 个数,用一楼的链接算出来 C(1000, 400) = 496527238625422886115073562889623132621341353659827604662932184012645905732096457382164964136575507417172339042089778751904887857092411910579077412408539948204974129778390437393954251676800524680653478266662364352619244180931154020701111982328000776980305955525649501369943202079996789539150
    gstqc
        7
    gstqc  
       2021-05-06 08:12:35 +08:00 via Android
    4.965272386 E+290 种组合
    你需要重新学下高中数学
    popil1987
        8
    popil1987  
       2021-05-06 09:40:59 +08:00
    python itertools combinations
    pandas combine
    都是这个功能,肯定比 for 循环要快
    Vegetable
        9
    Vegetable  
       2021-05-06 09:41:52 +08:00
    首先这个是可以通过数学计算的,不要这么穷举。

    其次如果你有什么特别的需求要列出所有的组合,那你说这个数量级,建议你还是立刻冬眠等待人类走过几次科技革命好一点。
    necomancer
        10
    necomancer  
       2021-05-06 10:16:00 +08:00
    这种情况是做一个生成器,itertools,pandas 之类的都是这么干的,然后每次操作是从生成器里取出下一个
    necomancer
        11
    necomancer  
       2021-05-06 10:16:26 +08:00
    不会先全放在内存里再做什么操作。
    DCELL
        12
    DCELL  
       2021-05-06 14:46:43 +08:00
    1.如果只是输出一共多少种可能,应该是有公式的
    2.如果要输出全部组合,一般都是用回溯算法
    no1xsyzy
        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 都快几百个数量级。
    比特币暴跌,然后我能买到显卡了。
    no1xsyzy
        14
    no1xsyzy  
       2021-05-06 15:43:50 +08:00   ❤️ 3
    再脑洞下

    处理大量信息时,根据 Landauer's principle,必然产生热量,随便地瞎估一下,应远大于
    2.805zJ*4e290 相当于 2.682×10^260 吨 TNT 当量
    你这不是 CPU,这是 1e250 吨的质量弹
    ch2
        15
    ch2  
       2021-05-06 19:40:39 +08:00
    你想计算的是一个天文数字
    ZRS
        16
    ZRS  
       2021-05-06 20:14:22 +08:00 via iPhone
    我想说的楼上老哥们都说完了
    lizytalk
        17
    lizytalk  
       2021-05-06 20:59:52 +08:00
    高中排列组合?
    NeezerGu
        18
    NeezerGu  
       2021-05-06 21:07:47 +08:00
    @no1xsyzy
    那么能毁灭地球多少次咧?
    gstqc
        19
    gstqc  
       2021-05-06 23:09:57 +08:00
    @NeezerGu 2.682e260 吨 大约等于 2.09707e222 个银河系重量
    等于 4.490958e238 个地球重量
    yucongo
        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)
    julyclyde
        21
    julyclyde  
       2021-05-08 10:57:06 +08:00
    我觉得关键是你不应该先把它括起来然后再循环
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3236 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 61ms · UTC 12:10 · PVG 20:10 · LAX 05:10 · JFK 08:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.