V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
main1234
V2EX  ›  程序员

[求问] 在内存限制下如何对数组排序

  •  
  •   main1234 · 86 天前 · 1632 次点击
    这是一个创建于 86 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如给定无序数组 arr ,长度为 100w ,但是机器可用内存只有 5w 数组长度,如何排序并写入文件 我的思路是类似归并排序 1.每次取数组 2.5w 长度排序,写入文件 file1 2.循环步骤 1 ,此时会有排序好的文件为 file1 至 fileN 3.合并 file$i 和 file$(i+1),此时会有一个 5w 长度的排序数组

    问题是第 3 步后,如果处理接下来的文件??因为内存只能容纳 5w 长度的数组,怎么将 10w 长度数组合并呢

    17 条回复    2024-01-18 19:28:04 +08:00
    julyclyde
        1
    julyclyde  
       86 天前
    用交换类排序呗,对内存(几乎)没需求
    liuhan907
        2
    liuhan907  
       86 天前
    这不就是外部排序+多路归并排序么
    Tanix2
        3
    Tanix2  
       86 天前
    如果每次取 2.5w 长度形成一个有序的 chunk 的话,共有 100w/2.5w=40 个 chunk ,之后使用 40 路归并排序,40 个 chunk 里每个先取比如说 0.5k 个元素(减少 I/O ,最好能达到一个 page 的大小,但是这里应该达不到),每次选出其中最大的一个元素放到缓冲区(大小为一个 page )。如果某个 chunk 在内存里没有元素了,那么从磁盘里再取 0.5k 个;如果输出缓冲区满了,写到磁盘里。
    以上是二阶段多路归并排序,如果第一阶段形成的 chunk 数过多(比如大于 2.5w 了),可以考虑更多阶段。
    changnet
        4
    changnet  
       86 天前   ❤️ 1
    交换类排序冒泡排序这种,只需要一个原始数组,在原始数组上交换排序,不需要额外的内存。但 op 这明显原始数组都加载不进来,所以是不行的。

    你用文件来排序是对的,但你排序好的 file1 和 file2 合并后并不是按顺序的啊,比如 file1 中最大的那个比 file2 中的那个还大。

    要先把 100w 数据读出来,按排序因子分成 20 段写入 20 个文件,比如文件 1 只写入大小为 1~50000 ,文件 2 只写入 50001~100000 ,然后分别对这些文件进行排序,再把文件拼起来就行。

    当然如果无法预估排序因子的大小,拆分不会那么顺利。因为是无序的,没法预知该拆成多少个文件,那就先拆成 2 个,对大于 5W 的文件继续拆分,直到所有文件都小于 5w 再排序
    Tanix2
        5
    Tanix2  
       86 天前
    有数据库的话,也可以考虑存到数据库里,让数据库给你排
    BBCCBB
        6
    BBCCBB  
       86 天前
    比如每 1000 个数字加载出来, 排序, 写到一个小文件里, 然后每次合并两个有序文件. 归并排序这种思想. 比较两个文件的队头数字, 小的写到新的文件里.

    最后比如留下了 20 个 5w 数字的有序文件..

    然后继续 merge.. 得到 10 个 10w 有序的.
    ...
    以此类推.
    ...
    得到 2 个 50w 数字的有序文件,

    最后

    得到了 1 个 100w 数字的有序文件.

    每次只读文件的第一个数字, 需要的内存很低的.
    iOCZS
        7
    iOCZS  
       86 天前
    既然不能整体读取到内存,为何要合并呢?
    直接每 5W 存一个文件得了,虽然说追加写入也是可以,但你又不能整体读取。。。。
    zhuangzhuang1988
        8
    zhuangzhuang1988  
       86 天前
    直接 sqlite 就可以了
    darling19961030
        10
    darling19961030  
       86 天前
    1. 将 100w 数据以 5w 大小分 20 组写入文件
    2. 将这 20 组数据分别读到内存中排序
    3. 读取 20 组数据的最小值到内存,比较出最小值写入文件,再从最小值所在组读入一个新数据
    4. 再比较出最小值写入文件,再从最小值所在组读入新值
    5. 直到读完 20 组数据,那写入的文件也是 100w 排序后的数据了
    verrickt
        11
    verrickt  
       86 天前 via Android
    外部排序+流式处理
    nuk
        12
    nuk  
       86 天前
    随机从数组中取出 5w 个元素,排序后塞回原来的位置。当随机足够多次,排序稳定后,再检查一遍,如果没排序完,就接着循环。
    hefish
        13
    hefish  
       86 天前
    大学课本 《数据结构》 里面有详细描述。
    LindsayZhou
        14
    LindsayZhou  
       86 天前
    桶排序,每个桶做成一个文件。
    LGA1150
        15
    LGA1150  
       86 天前 via Android
    mmap 然后原地排序,剩下的交给操作系统
    liguangsheng
        16
    liguangsheng  
       85 天前
    归并的时候被归并的两个文件都是有序状态的,不需要全部读到内存里再合并,两个文件指针,每次至少读一个数字就可以归并了
    NASK
        17
    NASK  
       85 天前
    外部排序+归并排序,也许是这样
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2752 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 05:57 · PVG 13:57 · LAX 22:57 · JFK 01:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.