首页 > 其它语言 > 【算法思想】位图排序算法

【算法思想】位图排序算法

问题的提出

一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7。假设最多只有1M的内存空间可用,在考虑空间和时间的优化的情况下,请问如何对其进行排序?


常规思想

我们假设这些整数都是用整型存储(一般整型的大小为4个字节),那么1M字节可以存储250 000个数据。由于输入文件最大可能有10^7个数据,因此可以通过遍历输入文件40次来完成排序。第一次将在[0,249 999]范围内的整数读入到内存中,第二次将在[250 000,499 999]范围内的整数读入到内存中,依此类推。每读入一次数据,就对这些数据进行排序(可以采用一些排序算法)并输出。显然,我们要对文件进行反复的读写,这不是我们所期望的。下面我们提出一种更加合理的算法—位图排序算法


位图排序算法

如果我们想一次读取文件的全部内容(最大可能有1000万个整数),问题在于如何用1M的内存来表示这些数。我们可以用位图表示集合。我们可以用一个长度为20的字符数组来表示小于20的所有正整数的集合。举例说明:下面的字符串可以表示集合{1,2,3,5,8,13}: 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 集合中有数值的位置都置为1,其它所有位置为0.

这样我们就用一个具有1000万个位的字符串表示了这个文件,其中,当且仅当整数i在文件中存在时,第i位为1。因此我们可以分下面三步来解决这一问题:

  1. 将字符串的所有位置为0即初始化
  2. 逐一读取文件中的每个整数,并将以该整数为下标的对应为置为1
  3. 逐一检查字符串的每一位,如果为1,则输出这一元素的下标

时间、空间的折中与双赢

我们在很多问题中,都遇到着时间和空间的折中,毛泽东在论持久战中也说过以空间换时间(据说是蒋介石先提出来的)。但是上面的程序是:减少程序空间需求的同时也减少了其运行时间。因为需要处理的数据变少了,从而处理数据所需要的时间变少了,同时没有反复的读取文件,进一步避免了磁盘的访问时间。当然,只有当原始设计非最佳方案时,才有可能时空双赢。


奥卡姆的剃刀

    设计者确定其设计已经达到完美的标准不是不能再添加任何东西,而是不能再减少任何东西。

本文固定链接: http://www.devba.com/index.php/archives/6243.html | 开发吧

报歉!评论已关闭.