Python: записать 1 000 000 дюймов в файл

Question

Какой самый компактный способ записи 1 000 000 целых (0, 1, 2 ...) в файл с использованием Python без архивирования и т. Д.? Мой ответ: 1 000 000 * 3 байта с использованием модуля struct, но кажется, что интервьюер ожидал другого ответа ...

Edit. Числа от 1 до 1 000 000 в случайном порядке (таким образом, преобразование как 5, 6, 7 -> 5-7 может применяться в редких случаях). Вы можете использовать любой метод записи, который вам известен, но полученный файл должен иметь минимальный размер.

Answer 1

На самом деле, вы можете сделать ОЧЕНЬ лучше, чем 2,5 МБ, так как не все заказы возможны. Можно утверждать, что избиение 5% будет включать сжатие, поскольку не хранится сама последовательность. По сути, вы хотели бы сохранить канонический порядковый номер. 8 чисел из 0-7 в случайном порядке обычно занимают 24 бита (log(8^8)/log(2)), но с каноническим порядковым номером это займет 16 бит (log(8!)/log(2)).

По сути, это предполагает создание алгоритма, который может преобразовать любую последовательность целых чисел в гигантское число. Примером возможной нумерации для последовательности из 8 чисел будет упорядочение по значению:

01234567 : 0  
01234576 : 1  
01234657 : 2  
01234675 : 3  
01234756 : 4  
01234765 : 5  
...

Стоимость этой стратегии log(1000000!)/log(2) (т. Е. log_2(1000000!)).
Стандартное решение обычно стоит около log(1000000^1000000)/log(2).

Вы также можете сжать немного больше места, обрабатывая 0000 0000 1111 1111 и 1111 1111 по-разному, но объем сэкономленного пространства невероятно мал.

Редактировать: Быстрое и грязное вычисление указывает, что эта оптимизация снижает размер примерно до 2,204 МБ.

Из-за принципа голубиных ям, я не верю, что можно добиться большего успеха, чем эта стратегия, независимо от того, используете ли вы сжатие или какую-то другую технику.

Answer 2

Предполагая, что вам нужно запомнить их порядок и что числа находятся в диапазоне от 1 до 1000000, для записи каждого из них потребуется всего 20 бит или 2,5 байта, поскольку значение 1,000,000 равно 0xF4240 в шестнадцатеричном формате.Вы должны были бы собрать их вместе, чтобы не тратить место на этом подходе, но при этом это займет всего 2,5 * 1 000 000 байт.

Answer 3

Ну, ваше решение занимает три байта (= 24 бита) на целое число.Теоретически, достаточно 20 бит (так как 2 ^ 19 <1.000.000 <2 ^ 20). </p>

РЕДАКТИРОВАТЬ: Ой, только что заметил комментарий Нила о том же.Я делаю этот ответ CW, так как он действительно принадлежит ему.

Answer 4

вопрос явно неполный.вот моя очень компактная попытка:

f = open('numbers.dat', 'w')
f.write('list(range(1,1000000))')
f.close()

загрузка файла:

f = open('numbers.dat', 'r')
numbers = eval(f.read().strip())
f.close()

, который должен это сделать.понять, почему здесь важен «питон»если интервьюер обеспокоен размером получаемого файла, решение может быть написано на любом языке.вопрос не определяет, хочет ли интервьюер компактный вывод или компактный код ...

Answer 5

Может, они имели в виду что-то подобное pythonic-way-to-convert-a-list-of-integer-in-a-string-of-string-отделенный-range-range но затем вы сказали, что последовательные последовательности редки, поэтому, возможно, нет

Answer 6

What is the most compact way to write 1,000,000 ints (0, 1, 2...) to file using Python without zipping etc

Если вы интерпретируете значения 1,000,000 как «Я не указал, что они должны быть разными», вы можете просто использовать цикл for для записи 0 миллион раз.

Answer 7

Я бы написал только начало и конец данного диапазона, в данном случае 1 и 1 000 000, потому что нигде интервьюер не упоминал, что порядок важен.