猿问
下载APP

找到一个不是40亿个给定值的整数

这是一个面试问题:


给定一个包含40亿个整数的输入文件,提供一个算法来生成一个未包含在文件中的整数。假设您有1 GB内存。如果您只有10 MB内存,请跟进您的操作。


我的分析:


文件大小为4×10 9 ×4字节= 16 GB。


我们可以进行外部排序,因此我们可以了解整数的范围。我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么?


我的理解(阅读完所有答案后):


假设我们正在讨论32位整数。有2 ^ 32 = 4 * 10 9个不同的整数。


情况1:我们有1 GB = 1 * 10 9 * 8位= 80亿位内存。

解决方案:如果我们使用一个代表一个不同整数的位,那就足够了。我们不需要排序。执行:


int radix = 8;

byte[] bitfield = new byte[0xffffffff/radix];

void F() throws FileNotFoundException{

    Scanner in = new Scanner(new FileReader("a.txt"));

    while(in.hasNextInt()){

        int n = in.nextInt();

        bitfield[n/radix] |= (1 << (n%radix));

    }


    for(int i = 0; i< bitfield.lenght; i++){

        for(int j =0; j<radix; j++){

            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);

        }

    }

}

情况2:10 MB内存= 10 * 10 6 * 8位= 8000万位

解决方案:对于所有可能的16位前缀,有2 ^ 16个整数= 65536,我们需要2 ^ 16 * 4 * 8 = 2百万位。我们需要构建65536个桶。对于每个桶,我们需要4个字节来保存所有可能性,因为最坏的情况是所有40亿个整数属于同一个桶。


通过第一次通过文件构建每个桶的计数器。

扫描存储桶,找到第一个命中率低于65536的存储桶。

构建新的存储桶,我们在第二步中通过文件的第二次传递找到了高16位前缀

扫描步骤3中构建的存储桶,找到第一个没有命中的存储桶。

代码与上面的代码非常相似。


结论:我们通过增加文件传递来减少内存。


对那些迟到的人的澄清:问题,并不是说文件中没有包含一个完整的整数 - 至少不是大多数人解释它的方式。但是,评论主题中的许多评论都是关于任务的变化。不幸的是,将其引入评论主题的评论后来被其作者删除了,所以现在看起来孤立的回复只是误解了一切。这很令人困惑。抱歉。


跃然一笑
浏览 363回答 3
3回答

ITMISS

假设“整数”表示32位:具有10 MB的空间足以让您计算输入文件中具有任何给定的16位前缀的数量,对于所有可能的16位前缀,一次通过输入文件。至少有一个桶的击中次数不会超过2 ^ 16次。执行第二遍以查找已使用该存储桶中的哪些可能数字。如果它意味着超过32位,但仍然是有限大小:如上所述,忽略恰好落在(有符号或无符号;您选择的)32位范围之外的所有输入数字。如果“整数”表示数学整数:读取输入一次并跟踪您所见过的最长数字的最大数字长度。完成后,输出最大加一个随机数,该数字还有一个数字。(文件中的一个数字可能是一个超过10 MB的bignum来准确表示,但如果输入是一个文件,那么你至少可以表示适合它的任何东西的长度)。

翻过高山走不出你

统计通知算法使用比确定性方法更少的通过来解决此问题。如果允许非常大的整数,则可以生成在O(1)时间内可能唯一的数字。像GUID这样的伪随机128位整数只会与集合中现有的40亿个整数中的一个冲突,而不是每640亿亿个案例中只有一个。如果整数限制为32位,则可以使用远小于10 MB的单次传递生成一个可能唯一的数字。伪随机32位整数将与40亿现有整数中的一个冲突的几率约为93%(4e9 / 2 ^ 32)。1000个伪随机整数将全部碰撞的几率小于12,000亿亿(1个碰撞的概率^ 1000)。因此,如果程序维护包含1000个伪随机候选者的数据结构并迭代已知整数,从候选者中消除匹配,则几乎肯定会找到至少一个不在文件中的整数。

萧十郎

关于这个问题的详细讨论已经在Jon Bentley “Column 1. Cracking the Oyster” 编程中讨论了Pearls Addison-Wesley pp.3-10Bentley讨论了几种方法,包括外部排序,使用多个外部文件进行合并排序等。但Bentley建议的最佳方法是使用位字段的单程算法,他幽默地称之为“Wonder Sort”:)问题,40亿数字可以表示为:4 billion bits = (4000000000 / 8) bytes = about 0.466 GB实现bitset的代码很简单:(取自解决方案页面)#define BITSPERWORD 32#define SHIFT 5#define MASK 0x1F#define N 10000000int a[1 + N/BITSPERWORD];void set(int i) {&nbsp; &nbsp; &nbsp; &nbsp; a[i>>SHIFT] |=&nbsp; (1<<(i & MASK)); }void clr(int i) {&nbsp; &nbsp; &nbsp; &nbsp; a[i>>SHIFT] &= ~(1<<(i & MASK)); }int&nbsp; test(int i){ return a[i>>SHIFT] &&nbsp; &nbsp;(1<<(i & MASK)); }Bentley的算法对文件进行单次传递set,将数组中的相应位调整,然后使用test上面的宏检查此数组以查找缺少的数字。如果可用内存小于0.466 GB,Bentley建议使用k-pass算法,该算法根据可用内存将输入划分为范围。举一个非常简单的例子,如果只有1个字节(即处理8个数字的存储器)可用且范围从0到31,我们将其分为0到7,8-15,16-22的范围等等。并在每个32/8 = 4通行证中处理此范围。HTH。
打开App,查看更多内容
随时随地看视频慕课网APP
我要回答