相关疑难解决方法(0)

这是一个面试问题:

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

我的分析:

文件大小为4×10 ⁹ ×4字节= 16 GB.

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

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

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

情况1:我们有1 GB = 1*10 ⁹*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内存= …

我有一个图表,包含大约35,000个以纯文本表示的节点:

node1 -> node35000
node29420 -> node35000
node2334 -> node4116
...

我想通过删除不属于链的节点至少三个长来修剪它.所以,如果我只有

1 -> 2;
2 -> 3;
3 -> 4;
0 -> 4;

我想保留1,2,3和4(因为1 -> 2 -> 3 -> 4四个节点长)但丢弃0,即删除0 -> 4.

有没有想过这样做的好方法？我尝试了Perl和shell函数的组合,但我认为我需要一个更好的方法.除非有工具可以做到这一点？数据采用graphviz格式,但我没有看到该套件中的任何工具与手头的任务相关.

哦,如果有一种简单的方法可以做这样的事情,我会接受建议 - 它不一定是我建议的任务.我只是想找到一种方法来消除大块周围的大部分噪音(这种情况很少见,而且大部分只是一些相交的链条).