关于数据结构和算法:如何在单台8G内存机器上实现1TB日志排序

24次阅读

共计 1074 个字符,预计需要花费 3 分钟才能阅读完成。

当初有一批日志数据,大小为 1TB,数据是某一天的生产的日志数据,当初只有一台单 CPU 及 8G 内存的机器,请应用算法对此日志数据按工夫的先后顺序进行排序。

解决方案 1:桶排序

它的原理是利用分区字段的特点,将数据别离写入到多个桶文件中,再针对每个桶文件应用内存排序算法(如疾速排序),将文件内容进行排序输入到有序桶文件中。最初将这些文件按分桶的程序组合起来,造成最终有序的文件。

  • 划分桶,在问题中,咱们须要排序的是日志中的工夫,而工夫是很容易划分出桶的,而工夫应用哪个维度来划分桶是咱们所面临的问题?如果抉择分钟可失去 1440 个桶,每个桶均匀就是 0.7G 左右,但像日志中数据可能有数据集中的问题,尤其是像 1TB 这么大的日志,顶峰时间段可能是均匀的 10 倍,分桶可能十分的不均匀;这样倡议再升高维度应用秒,一天可最多失去 86400 个分桶。均匀每个文件只有 12M 左右,顶峰也不过才 120M,所以抉择秒是比拟适合的分桶。
  • 再将数据按秒划分到各个桶即可。
  • 再将各个桶内的数据进行排序。
  • 最初按桶的先后顺序,合并到一个文件中,就失去了 1TB 日志的排序后果。

桶排序的特点:

  1. 桶排序的工夫复杂度为 O(n), 如果有 N 个数据,划分出 M 个桶。每个桶内元素 (T=N/M),如果桶内排序算法采纳疾速排序,工夫复杂度 O(TlogT),M 个桶的工夫复杂度就是 O(MTlogT), 再加上 T =N/M, 即可失去 N log(N/M),当 M 与 N 靠近时,工夫复杂度为常量级,这时候桶排序工夫复杂度靠近 O(N)
  2. 对排序的数据要求很刻薄,数据必须很容易的划分出 M 个桶,桶与桶之前有着人造的大小程序。对每个桶内的数据排序实现后,桶与桶之前无需再进行排序。
  3. 桶内的数据在各个桶内须必较均匀。如果通过桶的划分。桶内的数据十分不均匀,有的十分多,有的非常少,工夫复杂度将不再是 O(N),可能进化为 (N*logN)。
  4. 桶排序比拟适宜内部排序。即为对磁盘文件进行排序,因为个别磁盘文件数据量较大,无奈一次全副加载到内存中

解决方案 2:归并排序

它的核心思想:分而治之,具原本说就是将大数据分解成一个一个小数据,将小数据进行排序,而后再将这些小数据合并排序成终最终有序的数据。

  • 将 1TB 的文件按固定大小进行切分,比方大小 256M,读取时可按行读取,限度大小在 256M 以内,需保障残缺的行,这样能够切出大概 4096 个文件。
  • 将这 4096 个文件,应用疾速排序算法对这每个文件进行排序操作,可失去 4096 个排序的文件
  • 将这 4096 个文件进行合并输入,合并的逻辑就是从每个文件中顺次获取数据,排序,输入,就像示例中的那样。就能够失去一个最终有序的文件。
正文完
 0