使用有限的内存找到缺少的号码

问题在于，如果输入文件具有40亿个唯一整数，则会提供一种生成文件中未包含的整数的算法，假定只有10 MB的内存。

搜索下面的一些解决方案和发布的代码，其中之一是将整数存储到位向量块（每个块代表40亿范围内的整数的特定范围，块中的每个位表示一个整数），并使用另一个计数器为每个块计算每个块中的整数数量。 因此，如果整数的数量小于整数的块容量，则扫描该块的位向量以查找哪些缺失整数。

我对这个解决方案的问题是， 为什么“我们选择的中间越接近，在任何给定的时间内使用的内存就越少” ，这里有更多的上下文，

第一遍中的数组可以容纳10兆字节或大约2 ^ 23字节的内存。 由于数组中的每个元素都是一个int，并且int是4个字节，所以我们可以保存一个至多有大约2 ^ 21个元素的数组。 所以我们可以推导出以下几点：

因此，我们可以得出以下结论：2 ^ 10 <rangeSize <2 ^ 26，这些条件给了我们很大的“摆动空间”，但是我们选择的中间距离越近，所用的内存就越少给定的时间。

public class QuestionB {
    public static int bitsize = 1048576; // 2^20 bits (2^17 bytes)
    public static int blockNum = 4096; // 2^12
    public static byte[] bitfield = new byte[bitsize/8];
    public static int[] blocks = new int[blockNum];

    public static void findOpenNumber() throws FileNotFoundException {
        int starting = -1;
        Scanner in = new Scanner (new FileReader ("Chapter 10/Question10_3/input_file_q10_3.txt"));
        while (in.hasNextInt()) {
            int n = in.nextInt();
            blocks[n / (bitfield.length * 8)]++;
        }

        for (int i = 0; i < blocks.length; i++) {
            if (blocks[i] < bitfield.length * 8){
                /* if value < 2^20, then at least 1 number is missing in
                 * that section. */
                starting = i * bitfield.length * 8;
                break;
            }
        }

        in = new Scanner(new FileReader("Chapter 10/Question10_3/input_file_q10_3.txt"));
        while (in.hasNextInt()) {
            int n = in.nextInt();
            /* If the number is inside the block that’s missing 
             * numbers, we record it */
            if (n >= starting && n < starting + bitfield.length * 8) {
                bitfield [(n-starting) / 8] |= 1 << ((n - starting) % 8);
            }
        }

        for (int i = 0 ; i < bitfield.length; i++) {
            for (int j = 0; j < 8; j++) {
                /* Retrieves the individual bits of each byte. When 0 bit 
                 * is found, finds the corresponding value. */
                if ((bitfield[i] & (1 << j)) == 0) {
                    System.out.println(i * 8 + j + starting);
                    return;
                }
            }
        }       
    }

    public static void main(String[] args) throws FileNotFoundException {
        findOpenNumber();
    }

}

---

如果你形成每个大小为2 ^ 32 / M的M块，则所需的总内存为M + 2 ^ 27 / M个字（32位）。 当M =√2^ 27时，该函数达到最小值，这是1和2 ^ 27块之间的一半。 最小值为2 ^ 14.5字，约92千字节。

这在对数图上非常明显。

---

我喜欢这个问题。 我会给它额外的想法，但我认为如果磁盘空间和时间不是问题，您可以将数字分成100k块，并在每个文件中对它们进行排序。 任何没有100k条目的块都会有差距。 它根本不是优雅的，但它会让球滚动。

链接地址: http://www.djcxy.com/p/70795.html

上一篇: find a missing number using limited memory

下一篇: Write a program to find 100 largest numbers out of an array of 1 billion numbers