java - 使用有限的内存查找丢失的号码

Question

问题是，给定一个包含 40 亿个唯一整数的输入文件，提供一种算法来生成文件中不包含的整数，假设只有 10 MB 的内存。

搜索了一些解决方案并在下面发布了代码，其中之一是将整数存储到位 vector block 中(每个 block 代表 40 亿范围内的特定整数范围， block 中的每个位代表一个整数)，以及为每个 block 使用另一个计数器，以计算每个 block 中整数的数量。因此，如果整数的数量小于整数的 block 容量，则扫描 block 的位 vector 以查找缺少的整数。

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

第一遍中的数组可以容纳 10 兆字节或大约 2^23 字节的内存。由于数组中的每个元素都是一个 int，而一个 int 是 4 个字节，我们最多可以容纳大约 2^21 个元素的数组。因此，我们可以推断出以下内容:

因此，我们可以得出以下结论: 2^10< rangeSize <2^26，这些条件给了我们很大的“Swing 空间”，但我们选择的越接近中间，在任何给定时间使用的内存就越少。

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();
    }

}

Answer 1

如果您形成 M 个 block ，每个 block 的大小为 2^32/M，则所需的总内存为 M+2^27/M 字(32 位)。当 M=√2^27，即 1 和 2^27 block 之间的一半时，该函数达到最小值。最小为 2^14.5 字，约 92 KBytes。

这在双对数图上非常清楚。