Re: Аналог утилиты tac для сжатого файла
On Wed, 15 Feb 2012 17:21:20 +0200
Serhiy Storchaka <storchaka@gmail.com> wrote:
> > Пришло в голову, что zip архив позволяет добавлять файлы к архиву, и
> > утилитка для этого дела есть, любезно написанная когда-то Anton
> > Kovalenko:
> > | zipput archive.zip file-name
> > Интересно, какая производительность такого решения, если туда
> > поблочно/построчно данные пихать, может, и сойдет.
> Если добавление O(1), то извлечение O(N). Без индекса в любом случае
> O(N^2) в сумме будет.
Это смотря как распаковывать. Если распаковщик будет читать Central
Directory, то там в худшем случае надо пробегаться по списку всех
файлов, размер которого линейно зависит от N (по условию). Однако если
считать CentralDir и положить хотя бы в map (как в fuse-zip сделано), то
распаковка уже за O(N*log N) будет работать (с константой < 1).
--
Alexander Galanin
Reply to: