Skip to content

Latest commit

 

History

History
31 lines (18 loc) · 1.29 KB

File metadata and controls

31 lines (18 loc) · 1.29 KB

其他问题

海量数据

100Mb的内存对1Gb的数据进行排序

面对海量数据,即数据不可能一次全部载入内存,需要用到外排序的方法,外排序采用分块的方法

  • 将文件分成10个100M,并依次载入内存中进行排序,最后结果存入硬盘,得到的是10个分别排序的文件
  • 接着从每个文件载入9M的数据到输入缓存区,输出缓存区大小为10M
  • 对输入缓存区的数据进行归并排序,输出缓存区写满之后写在硬盘上,缓存区清空继续写接下来的数据
  • 对于输入缓存区,当一个块的9M数据全部使用完,载入该块接下来的9M数据,一直到所有的块的所有数据都已经被载入到内存中被处理过

10亿个数中找出最大的前1万个数

1、小根堆

  • 创建一个小根堆,将前K个元素存入堆
  • 后面的元素与堆顶元素相比,比堆顶元素大,就替换堆顶元素,并且重新调整小根堆

2、分治法

先把10亿个数分成100份,每份1000w个数。

对于每一份数组,再分成100份小分区,每份10万个数

计算每个小分区的最大的1万个数

合并大分区中的小分区,100*1万,找到每个大分区的前1万个数

合并大分区,将100*1万个数合并,找到前1万个数