Путаница при расчете размера между байтами и мегабайтами
Это решаемая проблема, когда мы должны найти пропущенное целое число из входных данных в форме файла, содержащего 4 миллиарда несортированных целых чисел без знака. Подвох в том, что можно использовать только 10 МБ памяти.
Автор дает решение, где мы делаем 2 прохода. На первом этапе мы создаем массив "блоков" некоторого размера. Например. Блок 0 представляет 0 to 9991 представляет 1000 to 1999, скоро. Таким образом мы знаем, сколько значений должно присутствовать в каждом блоке.
Теперь мы просматриваем файл и подсчитываем, сколько значений фактически присутствует в каждом блоке, что приведет нас к отсутствующему целому числу.
Я понимаю подход. Тем не менее, для расчета соответствующего размера блока начинается с этого:
Массив в первом проходе может занимать 10 МБ или примерно 2 23 байта памяти.
Как 10 МБ такой же как 2^23? Я не могу понять, где 2^23 номер пришел.
Так 2^24 16MBytes, так что, вероятно, он принимает 2^23 что является ближайшим значением, которое составляет 10 МБ или меньше. Если это так, то почему он не может использовать все 10 МБ? то есть, почему он должен использовать степень 2, чтобы получить размер здесь?
3 ответа
Не указано, но я предполагаю, что проблема заключается в том, чтобы найти одно отсутствующее целое число из файла с набором 2^32 (4294967296) уникальных 32-битных целых чисел без знака со значениями от 0 до 4294967295. Файл занимает 17179869184 байта.
Использование 2^23 = 8388608 места в памяти позволяет хранить в памяти 2^21 = 2097152 32-разрядных целых числа без знака. Каждая группа представляет (2^32)/(2^21) = 2^11 = 2048 значений. Таким образом, count[0] для значений от 0 до 2047, count[1] для значений от 2048 до 4095, ..., count[2097151] для значений от 4294965248 до 4294967295. Основная строка во внутренней части цикла будет count [значение >>21] += 1. Все значения будут 2048, кроме числа, соответствующего отсутствующему целому числу, которое будет иметь счет 2047. Для второго прохода нужно только прочитать значения 2047 в нужном диапазоне, чтобы найти пропущенное целое число.
В качестве альтернативы можно использовать 4194304 16-разрядных отсчетов, при этом каждая группа представляет 1024 значения (максимальное значение отсчета - 1024), но существенной разницы во времени нет.
Если предположить, что 10 МБ = 10 * 2 ^ 20 = 10485760, то тогда можно использовать 32-разрядные числа 10 * 2 ^ 18 = 2621440, каждое из которых рассчитано на диапазон 1639 значений (последний счет для небольшой группы), что неудобно. Если используется 16-битный отсчет, то диапазон 3278 значений также неудобен.
Это не.
1 МБ составляет 2^20 байт (1024 X 1024) = 1048576, затем 10 МБ - 10485760.
2 ^ 23 = 8388608
Конечно, на этом веб-сайте говорится, что 10 МБ - это "примерно 2^23", что может быть точным в зависимости от того, что подразумевается под "примерно".
Я считаю, что это должно быть 10*2^23 или 5*2^24 в битах. Попробуй посмотреть, в байтах или битах
10 MB = 2*5*2^20*2^3
M=2^20
B=2^3b
10=2*5