> > 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 -- To UNSUBSCRIBE, email to [email protected] with a subject of "unsubscribe". Trouble? Contact [email protected] Archive: http://lists.debian.org/87lio6ohtx.wl%[email protected]
