混淆计算字节和兆字节之间的大小
Confusion calculating size between Bytes and Megabytes
这是一个 solved problem，我们必须从输入数据中找到缺失的整数，该输入数据的形式是包含 40 亿个未排序的无符号整数的文件。问题是只能使用 10 MBytes 的内存。
作者给出了我们做2遍的解决方案。在第一遍中，我们创建了一个大小为 "blocks" 的数组。例如。块0代表0 to 999，1代表1000 to 1999，以此类推。因此我们知道每个块中应该存在多少个值。
现在我们扫描文件并计算每个块中实际存在的值数量 - 这将导致我们找到缺失的整数。
我理解这个方法。但是，要计算适当的块大小，请从以下开始：
The array in the first pass can fit in 10 MBytes, or roughly 2^23 bytes, of memory.
10 MB 与 2^23 有什么区别？我无法理解 2^23 号码从何而来。
所以 2^24 是 16MBytes，所以他可能正在使用 2^23，这是最接近的值，即 10MBytes 或更少。如果是这样，为什么他不能使用整个 10 MBytes？即为什么他必须使用 2 的幂来获得这里的大小？
我认为它应该是 10*2^23 或 5*2^24 位。
试试看是byte还是bit
10 MB = 2*5*2^20*2^3
M=2^20
B=2^3b
10=2*5
不是。
1 MB 是 2^20 字节 (1024 X 1024) = 1048576
那么 10 MB 就是 10485760。
2^23 = 8388608
当然该网站说 10 MB 是 "roughly 2^23"，这可能是准确的，具体取决于粗略的含义。
未说明，但我假设问题是从具有一组 2^32 (4294967296) 个唯一的 32 位无符号整数且值从 0 到 4294967295 的文件中找到一个丢失的整数。该文件采用space 的 17179869184 个字节。
使用 2^23 = 8388608 内存 space 允许 2^21 = 2097152 32 位无符号整数计数保存在内存中。每组代表 (2^32)/(2^21) = 2^11 = 2048 个值。所以 count[0] 用于值 0 到 2047，count[1] 用于值 2048 到 4095，...，count[2097151] 用于值 4294965248 到 4294967295。循环内部的主线是count[value>>21] += 1。所有计数都将为 2048，除了与缺失整数对应的计数为 2047。第二遍只需读取适当范围内的 2047 个值即可找到缺失的整数。
另一种方法是使用 4194304 16 位计数，每组代表 1024 个值（最大计数值为 1024），但时间上没有显着差异。
假设 10MB = 10 * 2^20 = 10485760，则可以使用 10 * 2^18 = 2621440 32 位计数，每个计数范围为 1639 个值（最后一个计数为较小的一组），这很尴尬。如果使用 16 位计数，则 3278 个值的范围，也很尴尬。
这是一个 solved problem，我们必须从输入数据中找到缺失的整数，该输入数据的形式是包含 40 亿个未排序的无符号整数的文件。问题是只能使用 10 MBytes 的内存。
作者给出了我们做2遍的解决方案。在第一遍中，我们创建了一个大小为 "blocks" 的数组。例如。块0代表0 to 999，1代表1000 to 1999，以此类推。因此我们知道每个块中应该存在多少个值。
现在我们扫描文件并计算每个块中实际存在的值数量 - 这将导致我们找到缺失的整数。
我理解这个方法。但是，要计算适当的块大小，请从以下开始：
The array in the first pass can fit in 10 MBytes, or roughly 2^23 bytes, of memory.
10 MB 与 2^23 有什么区别？我无法理解 2^23 号码从何而来。
所以 2^24 是 16MBytes，所以他可能正在使用 2^23，这是最接近的值，即 10MBytes 或更少。如果是这样，为什么他不能使用整个 10 MBytes？即为什么他必须使用 2 的幂来获得这里的大小？
我认为它应该是 10*2^23 或 5*2^24 位。 试试看是byte还是bit
10 MB = 2*5*2^20*2^3
M=2^20
B=2^3b
10=2*5
不是。
1 MB 是 2^20 字节 (1024 X 1024) = 1048576 那么 10 MB 就是 10485760。
2^23 = 8388608
当然该网站说 10 MB 是 "roughly 2^23"，这可能是准确的，具体取决于粗略的含义。
未说明，但我假设问题是从具有一组 2^32 (4294967296) 个唯一的 32 位无符号整数且值从 0 到 4294967295 的文件中找到一个丢失的整数。该文件采用space 的 17179869184 个字节。
使用 2^23 = 8388608 内存 space 允许 2^21 = 2097152 32 位无符号整数计数保存在内存中。每组代表 (2^32)/(2^21) = 2^11 = 2048 个值。所以 count[0] 用于值 0 到 2047，count[1] 用于值 2048 到 4095，...，count[2097151] 用于值 4294965248 到 4294967295。循环内部的主线是count[value>>21] += 1。所有计数都将为 2048，除了与缺失整数对应的计数为 2047。第二遍只需读取适当范围内的 2047 个值即可找到缺失的整数。
另一种方法是使用 4194304 16 位计数，每组代表 1024 个值（最大计数值为 1024），但时间上没有显着差异。
假设 10MB = 10 * 2^20 = 10485760，则可以使用 10 * 2^18 = 2621440 32 位计数，每个计数范围为 1639 个值（最后一个计数为较小的一组），这很尴尬。如果使用 16 位计数，则 3278 个值的范围，也很尴尬。