Re: Аналог утилиты tac для сжатого файла
> > n^2 это в данном случае бесконечность. Понятно, что надо сохранять вектор отступов
> > блоков на первом проходе..
>
> Тут на интересную задачку можно накопать, если не знать про входные данные более
> ничего :)
>
> Если хранить вектор отступов, то памяти при работе потребуется M =
> (N/K)*sizeof(off_t)+K, где N — размер файла, K — размер блока, который мы можем
> распаковываем единовременно. При этом M может оказаться больше, чем размер
> доступной памяти.
Ну, в тяжелом случае (файл состоит из одних переводов строки или чего-то очень
близкого, что можно сжать в один блок) нам все равно придется разжать весь
файл, если пользоваться zlib, а не лезть в структуру уже блока грязными
ногами. А в типичном нам нужно хранить не полный вектор отступов, а только
те, которые еще нужны, а их вряд ли много - один, ну, два.
--
If a `religion' is defined to be a system of ideas that contains
unprovable statements, then Godel taught us that mathematics is not
only a religion, it is the only religion that can prove itself to be
one.
-- John Barrow
Reply to: