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

查看 138|回复 12
作者:main1234   
如给定无序数组 arr ,长度为 100w ,但是机器可用内存只有 5w 数组长度,如何排序并写入文件
我的思路是类似归并排序
1.每次取数组 2.5w 长度排序,写入文件 file1
2.循环步骤 1 ,此时会有排序好的文件为 file1 至 fileN
3.合并 file$i 和 file$(i+1),此时会有一个 5w 长度的排序数组
问题是第 3 步后,如果处理接下来的文件??因为内存只能容纳 5w 长度的数组,怎么将 10w 长度数组合并呢

数组, 排序, 长度, file1

julyclyde   
用交换类排序呗,对内存(几乎)没需求
liuhan907   
这不就是外部排序+多路归并排序么
Tanix2   
如果每次取 2.5w 长度形成一个有序的 chunk 的话,共有 100w/2.5w=40 个 chunk ,之后使用 40 路归并排序,40 个 chunk 里每个先取比如说 0.5k 个元素(减少 I/O ,最好能达到一个 page 的大小,但是这里应该达不到),每次选出其中最大的一个元素放到缓冲区(大小为一个 page )。如果某个 chunk 在内存里没有元素了,那么从磁盘里再取 0.5k 个;如果输出缓冲区满了,写到磁盘里。
以上是二阶段多路归并排序,如果第一阶段形成的 chunk 数过多(比如大于 2.5w 了),可以考虑更多阶段。
changnet   
交换类排序冒泡排序这种,只需要一个原始数组,在原始数组上交换排序,不需要额外的内存。但 op 这明显原始数组都加载不进来,所以是不行的。
你用文件来排序是对的,但你排序好的 file1 和 file2 合并后并不是按顺序的啊,比如 file1 中最大的那个比 file2 中的那个还大。
要先把 100w 数据读出来,按排序因子分成 20 段写入 20 个文件,比如文件 1 只写入大小为 1~50000 ,文件 2 只写入 50001~100000 ,然后分别对这些文件进行排序,再把文件拼起来就行。
当然如果无法预估排序因子的大小,拆分不会那么顺利。因为是无序的,没法预知该拆成多少个文件,那就先拆成 2 个,对大于 5W 的文件继续拆分,直到所有文件都小于 5w 再排序
Tanix2   
有数据库的话,也可以考虑存到数据库里,让数据库给你排
BBCCBB   
比如每 1000 个数字加载出来, 排序, 写到一个小文件里, 然后每次合并两个有序文件. 归并排序这种思想. 比较两个文件的队头数字, 小的写到新的文件里.
最后比如留下了 20 个 5w 数字的有序文件..
然后继续 merge.. 得到 10 个 10w 有序的.
...
以此类推.
...
得到 2 个 50w 数字的有序文件,
最后
得到了 1 个 100w 数字的有序文件.
每次只读文件的第一个数字, 需要的内存很低的.
iOCZS   
既然不能整体读取到内存,为何要合并呢?
直接每 5W 存一个文件得了,虽然说追加写入也是可以,但你又不能整体读取。。。。
eote   
直接 sqlite 就可以了
darling19961030   
https://en.wikipedia.org/wiki/Memory-mapped_I/O_and_port-mapped_I/O
https://stackoverflow.com/questions/45972/mmap-vs-reading-blocks
c 的 mmap 直接把文件映射成内存
您需要登录后才可以回帖 登录 | 立即注册

返回顶部