Amazon: сохранить LIST на диск — сложность и память

Условие

Дан LIST из чисел/строк. Нужно сохранить его на диск, чтобы потом восстановить. Предложите несколько вариантов и обсудите big-O сложность алгоритма и потребление памяти.

Решение

Варианты

1. pickle — двоичный, нативный для Python.
   • Время: O(n).
   • Память при записи: O(1) поверх потока (поток построчный) или O(n) при pickle.dumps.
2. json — текстовый, кросс-платформенный.
   • Время: O(n).
   • Чуть медленнее pickle и не сериализует кастомные классы.
3. Текстовый файл ('\n'.join) — для простых типов.
   • Очень компактно по коду, но требует осознанного парсинга при чтении.
4. numpy.save / np.savez — если элементы числовые и однотипные. Самый компактный для big data.
5. parquet / arrow — если list большой и нужна потоковая обработка.

Реализация

import pickle, json
data = [1, 2, 3, "four", 5.5]
 
# 1. pickle
with open("a.pkl", "wb") as f:
    pickle.dump(data, f)
 
# 2. json
with open("a.json", "w") as f:
    json.dump(data, f)
 
# 3. Через стрим — память O(1)
with open("a.txt", "w") as f:
    for x in data:
        f.write(f"{x}\n")

Сложность

• Все подходы линейны O(n) по числу элементов.
• Память: pickle.dumps / json.dumps создают всю строку сразу — O(n). Стримовая запись (pickle.dump/построчно) — O(1) поверх входа.
• Для огромных list-ов лучше numpy memmap или pyarrow chunked-write.

Подводные камни

1. pickle — небезопасно открывать чужой файл (выполнение произвольного кода).
2. json теряет типы (tuple → list, отсутствие set).
3. CSV для list-of-list-ов — но сложно с разделителями внутри строк.
4. Для миллиардов элементов — стрим, иначе MemoryError.

Эталонный ответ

pickle.dump или json.dump — O(n) время; стрим — O(1) память; для числовых данных — numpy.save.