海量数据处理之排序问题
网站首页 文章专栏 海量数据处理之排序问题
海量数据处理之排序问题
编辑时间:2019-05-06 18:10 作者:毛毛小妖 浏览量:103 评论数:0

    海量数据处理中一类常见的问题就是排序问题,即对海量数据进行排序。例如,一个文件中有9亿条不重复的9位整数,对这个文件中的数字进行排序。

    针对这个问题,最容易想到的方法是将所有数据导入内存中,然后使用常规排序方法比如快速排序,归并排序算法进行排序,最后将排序好的数据存入文件。但这些方法在此并不适用,由于数据量巨大,在32位机器中,一个整数占用4B,而9亿条数据总共占用9亿 x 4B,大约需要3.6G内存,对于32位机器来说,很难将这么多数据数据一次性载入内存,更不用说排序了,所以需要考虑其他方法。当然了,现在机器内存都比较大,也可以尝试这么做,但是效率却是很低下的,不建议这么做。我们来看看其他方法:

一、数据库排序法

    将文本文件导入数据库,让数据库进行索引排序后提取数据到文件。这种方法虽然简单,方便,但是运算速度较慢,而且对数据库设备要求比较高。

二、分治法

    通过hash法将9亿条数据分成20段,每段大约9000万条,大约占用5000万 x 4B = 200MB空间,在文件中一次搜索0~5000万,50000001~1亿,将排序的结果存入文件。该方法要装满9位整数,一共需要20次,所以总共进行20次排序,需要对文件进行20次读操作。该方法虽然缩小了每次使用的内存空间,但是编码复杂,速度也比较慢。

三、位图法

    考虑到9位整数最大为999999999,由于9亿条数据是不重复的,可以把这些数据组成一个队列或数组,让它有0~999999999(一共10亿个数)元素数组下标表示数值。每个数组的数字用0表示不存在这个数,1表示存在这个数,判断0或1只需要1bit存储就够了,而声明一个可以包含9位整数的bit数组,一共需要10亿/8,大约120MB内存。把数组中的数据全部初始化为0,读取文件中的数据,并将数据存入数组。比如读到32456这个数,就在数组中找到下标为32456的这个位,并将该位置为1。最终遍历整个数组,将值为1的下标存入文件,最终得到排序后的内容。
    此类排序问题的求解方法一般都是采用第三种方法。比如以下两个问题的求解也可以使用这种方法。
    1>一年的全国高考人数为900万,分数使用标准分,最低0分,最高900分,不存在成绩为小数的情况,把这900万考生成绩排序。
    2>一个包含n个正整数的文件,每个正整数小于等于1000万,并且文件内正整数没有重复数据,输出整数的升序排序。

来说两句吧
最新评论
    还没有人评论哦,快来坐沙发吧!