On Wed, 15 Feb 2012 17:21:20 +0200 Serhiy Storchaka <[email protected]> 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 -- To UNSUBSCRIBE, email to [email protected] with a subject of "unsubscribe". Trouble? Contact [email protected] Archive: http://lists.debian.org/[email protected]
