1

Есть бинарный файл, в ходе обработки которой требуется решить задачу:
произвольный отрезок (в произвольном месте файла) заменить заданным блоком данных, который может быть меньше или больше исходного отрезка файла.

SrcFile = { s1, s2, ... sn1, sn2, ... sni, ... sk }
Param =   { p1, p2, ... pj }    

k    ∈ { 10^3, ... 4 * 10^12 }
i, j ∈ { 10^3, ... 100 * 10^6 }
1 < i ⩽ k 
i < j или i > j, случай i == j не интересен

OutFile = { s1, s2, ... s(n1-1), p1, p2, ... pj, s(ni+1), ... sk } 
или можно, если |i - j| ≫ (k - (ni+1))
OutFile = { s1, s2, ... s(n1-1), s(ni+1), ... sk, p1, p2, ... pj }, 

Объем исходного файла от нескольких Кбайт до 4Гбайт, требуемый для замены отрезок и задаваемый блок для замены могут иметь объемы от пары Кбайт до сотен Мбайт.

На ум приходит способ простого сдвига данных по блокам. Но хочется иметь наиболее эффективное решение, т.к. данные могут быть очень большие. Было бы неплохо иметь различные реализации, оптимизированные под условия: приоритет максимальной скорости, минимальной нагрузки на ЦП, ОЗУ, минимальное количество перезаписей файла (нагрузка на внешнее запоминающее устройство).

У кого какие идеи?

2
  • 1
    Блочный файл, карта файла, в карте храним метки об удаленных блоках, при добавлении данных - проверяем есть ли необходимое кол-во свободных блоков(по карте) если есть - пишем туда, если нету - пишем в конец файла. надеюсь идею описал понятно.... из плюсов имеем хорошее быстродействие, возможность "сжимать" файл, из минусов - оверхед на карту файла =) 6 окт 2018 в 10:15
  • @ВладимирКлыков Не хотите перенести свой комментарий в ответы? Идея понятна, спасибо, будем пробовать.
    – Ildar
    6 окт 2018 в 10:39

1 ответ 1

4

Попробуйте использовать то, что за нас давно придумано (Файловые системы\Базы данных...).

  • Файл состоит из блоков(записей в БД\кластеров на винчестере).
  • В начале(средине\конце\любом произвольном месте, хоть в отдельном файле) - хранится карта свободного места
  • При добавлении записей мы в первую очередь ищем достаточный по размеру участок свободного места, если таковой имеет - пишем в него, если нет - пишем в конец файла.
  • При удалении записей мы просто модифицируем карту свободного места, помечая "блоки" пустыми(можно предусмотреть "критичное" удаление, когда данные затираются нулями помимо просто пометки об освобождении)
  • Из дополнительного можно предусмотреть сжатие файлов, при этом весь файл перезаписывается с минимально возможным свободным местом.

Из минусов реализации:

  • Небольшой оверхед на карту
  • При наличии большого числа "малых" записей - повышеный оверхед на "пустые" части блока
  • Небольшой оверхед на проверку удалена запись или нет, при считывании.

Из плюсов :

  • Достаточно быстрое удаление\добавление файлов.
  • Возможность при необходимости "сжимать" файл, а не делать это после каждого мелкого изменения
  • Небольшая нагрузка на устройство хранения и ОЗУ.

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

4
  • Удобный способ. Теперь нужно оптимально "сжать".
    – Ildar
    15 окт 2018 в 8:39
  • Если глубоко в теории - оптимально вам надо подбирать исходя из частоты и размера вставок, т.е. если часто новый блок будет меньше старого - оптимально сжимать всё что меньше среднего вставляемого блока и часто =) если часто новый блок больше старого - оптимально сжимать по мере некого "допустимого" кол-ва неиспользуемых блоков, и сжимать целиком(не оставляя пустых мест) 15 окт 2018 в 18:53
  • забыл отписаться, ваше решение подошло, спасибо!
    – Ildar
    2 мар 2022 в 7:02
  • 4 года :) Незачто 2 мар 2022 в 11:59

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.