MiddleКодРедкоЕщё не отвечали
Отсортировать огромный файл байтов, не помещающийся в память
Очень большой файл содержит элементы типа байт (значения 0..255) и не помещается в RAM. Запишите его отсортированное содержимое в другой файл.
Требования:
- Не загружайте весь файл в память.
- Используйте то, что различных значений байта всего 256.
def sort_bytes(in_path, out_path):
# ваш код здесьДопишите реализацию.
Раз диапазон значений ограничен (256 значений байта), используйте сортировку подсчётом: читайте файл порциями, считайте частоту каждого байта в массиве из 256 ячеек, затем запишите каждое значение повторённым по его счётчику. Это O(n) время и O(1) доп. память (фиксированная таблица на 256 записей). Общий неограниченный случай потребовал бы внешней сортировки слиянием: разбить на отсортированные блоки на диске, затем слить.
- ✗Пытаться загрузить весь файл в память вопреки ограничению размера
- ✗Упускать, что 256 ограниченных значений дают сортировку подсчётом за O(n)
- ✗Считать, что порядок вставки в dict совпадает с сортировкой по ключу
- →Почему ограниченный диапазон байта превращает задачу в O(n)?
- →Как сортировать файл, если значения — неограниченные 64-битные целые?
Оглавление
Задача
Реализуйте sort_bytes: запишите отсортированное содержимое огромного файла байтов в другой файл, не загружая его целиком.
Решение
def sort_bytes(in_path, out_path, chunk=1 << 20):
counts = [0] * 256
with open(in_path, "rb") as f:
while True:
block = f.read(chunk)
if not block:
break
for b in block: # 0..255
counts[b] += 1
with open(out_path, "wb") as out:
for value, n in enumerate(counts):
if n:
out.write(bytes([value]) * n)Ключевые моменты
- Диапазон ограничен 256 значениями → сортировка подсчётом за O(n), память O(1).
- Файл читается порциями — в RAM одновременно лишь один блок и таблица из 256 счётчиков.
- Без ограничения диапазона понадобилась бы внешняя сортировка слиянием (блоки + k-путёвое слияние).
Оглавление
