Re: Аналог утилиты tac для сжатого файла
On Thu, 16 Feb 2012 09:32:05 +0200 Serhiy Storchaka storch...@gmail.com wrote: 15.02.12 21:32, Alexander Galanin написав(ла): Это смотря как распаковывать… Не подходит по условию. Раз для топикстартера даже простой внешний индекс выглядит «некрасиво», то разбирать бинарный CentralDir и создавать индекс в памяти уж совсем чёрная низкоуровневая магия. Грязная работа по разбору уже сделана авторами libzip, а индекс в памяти — лично мной в fuse-zip. Осталось только смонтировать архив. -- Alexander Galanin -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120216143943.d841dd959376f0c97f785...@galanin.nnov.ru
Re: Аналог утилиты tac для сжатого файла
16.02.12 12:39, Alexander Galanin написав(ла): Грязная работа по разбору уже сделана авторами libzip, а индекс в памяти — лично мной в fuse-zip. Осталось только смонтировать архив. Тогда да, распаковка очень проста (если не нужно реверсить строки пока ещё идёт добавление). Упаковка сложнее. А вот уже предлагавшийся вариант с монтируемой в память ФС с поблочным сжатием будет самым простым с пользовательской стороны и для вывода, и для ввода (по сравнению с zip может проиграть только в степени сжатия). -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/jhirem$5mb$1...@dough.gmane.org
Re: Аналог утилиты tac для сжатого файла
13.02.12 21:34, Alexey Pechnikov написав(ла): Кажется, стоит дополнить - разумеется, сжимаются строки ненулевой длины, но достаточно малые для того, чтобы имело смысл применить построчное сжатие; скажем, длина строк от 100 до 1000 байт. Подойдет и вариант поблочного сжатия (например, блоками по 16...256 килобайт). Как очень простой вариант, можно сжимать по N строк и в хексе их записывать построчно на диск... итоговый файл легко пропустить через tac и далее построчно читать, распаковывая и делая реверс строки. При правильно выбранном N получим и выигрыш от сжатия и простую распаковку. При наличии достаточного объема ОЗУ аналогичное легко проделывается в памяти (без перекодировки в хекс). Наверняка есть готовые библиотеки и утилиты, реализующие данный алгоритм (как минимум, подобное делается во множестве СУБД с поколоночным хранением). Что такое хекс? В остальном мысль правильная. -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/jhgi12$mnj$1...@dough.gmane.org
Re: Аналог утилиты tac для сжатого файла
13.02.12 23:01, Alexey Pechnikov написав(ла): 14 февраля 2012 г. 0:01 пользователь Alexander Galanin a...@galanin.nnov.ru написал: Раз уж допустимо менять формат входных данных, то почему бы не хранить информацию в виде россыпи из гзипнутых файлов по N строк? Чтобы за просто так порвать диск? Очень сильно думаю, что в любом скриптовом языке fsync зовется после записи каждого файла... так что никак не вариант. А вообще хватило бы и двух файлов - с блоками и со смещениями блоков, но это некрасиво. Чем же некрасиво? Вполне по делу — данные и индекс. Легко реализовать даже на шелле. tac index | while read range; do cut -b $range data | gunzip | tac; done Пришло в голову, что zip архив позволяет добавлять файлы к архиву, и утилитка для этого дела есть, любезно написанная когда-то Anton Kovalenko: | zipput archive.zip file-name Интересно, какая производительность такого решения, если туда поблочно/построчно данные пихать, может, и сойдет. Если добавление O(1), то извлечение O(N). Без индекса в любом случае O(N^2) в сумме будет. -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/jhgihm$rcs$1...@dough.gmane.org
Re: Аналог утилиты tac для сжатого файла
On Wed, 15 Feb 2012 17:21:20 +0200 Serhiy Storchaka storch...@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 -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120215233206.404b87531a30b10f838b9...@galanin.nnov.ru
Re: Аналог утилиты tac для сжатого файла
15.02.12 21:32, Alexander Galanin написав(ла): Это смотря как распаковывать. Если распаковщик будет читать Central Directory, то там в худшем случае надо пробегаться по списку всех файлов, размер которого линейно зависит от N (по условию). Однако если считать CentralDir и положить хотя бы в map (как в fuse-zip сделано), то распаковка уже за O(N*log N) будет работать (с константой 1). Не подходит по условию. Раз для топикстартера даже простой внешний индекс выглядит «некрасиво», то разбирать бинарный CentralDir и создавать индекс в памяти уж совсем чёрная низкоуровневая магия. -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/jhibdq$diq$1...@dough.gmane.org
Re: Аналог утилиты tac для сжатого файла
автор, я правильно понимаю. что текстовый файл - это некий очень большой лог, генерируемый в постоянном режиме некой coolprog? по-моему, имеет смысл натравить на него logrotate, конфиги для него пишутся просто, в мане все расписано. настроить его, чтобы при достижении определенного размера (500M, допустим), он жал файл в очередной бэкап. бжкапы нумеруются, можно настроить, сколько штук их хранить, также перед сжатием файла на его месте тут же создается пустой, так что прога ничего не заподозрит. а можно при желании прикрутить к нему скрипт, который будет смотреть содержимое и вытаскивать из него. допустим, даты первой и последней записи, по которым именовать файл вроде coolprog.log_20120125-20120208.gz, чтобы при необходимости легко было найти нужный файл. по-моему, куда более оптимальный вариант. ибо coolprog может и полгода работать, так фигли хранить устаревшую информацию? 2012-044 16:30 Alexey Pechnikov pechni...@mobigroup.ru wrote: Большой файл (больше размера ОЗУ и свободного дискового пространства) сжат, например, с помощью gzip или любого другого потокового упаковщика. Надо его разжать, причем с реверсом строк на лету, не читая весь файл в память и не сохраняя на диск. Понятно, что задача выполнима, вопрос, существует ли стандартное решение или надо свою утилиту писать? Примечание: конвейер zcat + tac может выполнить операцию, но увы, файл в процессе разжимается целиком. -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120214123133.1e86c...@ulf.tvoe.tv
Re: Аналог утилиты tac для сжатого файла
Re: Аналог утилиты tac для сжатого файла dimas Tue, 14 Feb 2012 00:32:02 -0800 автор, я правильно понимаю. что текстовый файл - это некий очень большой лог, генерируемый в постоянном режиме некой coolprog? Не хотел никого провоцировать, потому не давал описания задачи, но раз возник вопрос, уточню. Это система потокового анализа, берущая из БД, скажем, несколько гиг информации и создающая результат аналогичного объема, который передается на дальнейшую обработку или построителю отчетов. Обработчик написан как потоковый и памяти практически не ест (реверс строк возникает для того, чтобы группировку делать - последняя обработанная запись в группе становится первой, остальные после реверса можно игнорировать, так получаем любые итоги с накоплением в рамках модели потоковой обработки). Понятно, что при запуске уже десятка потоков обработки никакой памяти не хватит (учитывая реверс строк - уже два экземпляра данных получается, и т.п.). При сбросе данных на диск, скажем, на виртуалке с 0,5 Гб памяти все отлично обрабатывается (нет, память я не экономлю... экономить - это в 640 кБ уместить... возможно, кстати, только бесполезно практически), но это явно неэффективно делать без сжатия (сжатие уменьшает размер временных файлов ~100 раз), да и о SSD дисках стоит подумать с их ограниченным числом циклов перезаписи. Так вот, прежде чем делать очевидную вещь - создавать связный список, в вершине которого несжатый буфер, а далее сжатые блоки, и оперировать этой структурой, решил уточнить, неужели нет готовых решений для задачи (была кстати, когда-то идея сделать модуль для эскулайт с реализацией эффективного поколоночного хранения данных, да надобности тогда не было, а оказывается, такая вещь с функцией реверса записей может быть очень полезна). -- Best regards, Alexey Pechnikov. http://pechnikov.tel/
Re: Аналог утилиты tac для сжатого файла
On Tue, Feb 14, 2012 at 05:29:08PM +0400, Alexander wrote: а может стоит посмотреть в сторону свойств файловых систем? например, zfs умеет сжимать прозрачно Уже предлагали. -- WBR, wRAR signature.asc Description: Digital signature
Аналог утилиты tac для сжатого файла
Большой файл (больше размера ОЗУ и свободного дискового пространства) сжат, например, с помощью gzip или любого другого потокового упаковщика. Надо его разжать, причем с реверсом строк на лету, не читая весь файл в память и не сохраняя на диск. Понятно, что задача выполнима, вопрос, существует ли стандартное решение или надо свою утилиту писать? Примечание: конвейер zcat + tac может выполнить операцию, но увы, файл в процессе разжимается целиком. -- Best regards, Alexey Pechnikov. http://pechnikov.tel/
Re: Аналог утилиты tac для сжатого файла
On Mon, Feb 13, 2012 at 04:30:12PM +0400, Alexey Pechnikov wrote: Большой файл (больше размера ОЗУ и свободного дискового пространства) сжат, например, с помощью gzip или любого другого потокового упаковщика. Надо его разжать, причем с реверсом строк на лету, не читая весь файл в память и не сохраняя на диск. Понятно, что задача выполнима, Нет, непонятно. Обоснуйте. -- WBR, wRAR signature.asc Description: Digital signature
Re: Аналог утилиты tac для сжатого файла
On Mon, Feb 13, 2012 at 06:51:48PM +0600, Andrey Rahmatullin wrote: On Mon, Feb 13, 2012 at 04:30:12PM +0400, Alexey Pechnikov wrote: Большой файл (больше размера ОЗУ и свободного дискового пространства) сжат, например, с помощью gzip или любого другого потокового упаковщика. Надо его разжать, причем с реверсом строк на лету, не читая весь файл в память и не сохраняя на диск. Понятно, что задача выполнима, Нет, непонятно. Обоснуйте. Раз в zlib есть gzseek на чтение, то она теоретически выполнима. Практически, это идиотизм, конечно. -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120213125653.ga23...@nano.ioffe.rssi.ru
Re: Аналог утилиты tac для сжатого файла
13.02.2012 16:56, Иван Лох пишет: On Mon, Feb 13, 2012 at 06:51:48PM +0600, Andrey Rahmatullin wrote: On Mon, Feb 13, 2012 at 04:30:12PM +0400, Alexey Pechnikov wrote: Большой файл (больше размера ОЗУ и свободного дискового пространства) сжат, например, с помощью gzip или любого другого потокового упаковщика. Надо его разжать, причем с реверсом строк на лету, не читая весь файл в память и не сохраняя на диск. Понятно, что задача выполнима, Нет, непонятно. Обоснуйте. Раз в zlib есть gzseek на чтение, то она теоретически выполнима. Практически, это идиотизм, конечно. Всего-то n^2 вместо n. В случае, когда памяти мало, это может быть неплохим результатом. -- Alexander Galanin -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/4f39099c.3070...@galanin.nnov.ru
Re: Аналог утилиты tac для сжатого файла
On Mon, Feb 13, 2012 at 04:56:53PM +0400, Иван Лох wrote: Большой файл (больше размера ОЗУ и свободного дискового пространства) сжат, например, с помощью gzip или любого другого потокового упаковщика. Надо его разжать, причем с реверсом строк на лету, не читая весь файл в память и не сохраняя на диск. Понятно, что задача выполнима, Нет, непонятно. Обоснуйте. Раз в zlib есть gzseek на чтение, то она теоретически выполнима. If the file is opened for reading, this function is emulated but can be extremely slow. -- WBR, wRAR signature.asc Description: Digital signature
Re: Аналог утилиты tac для сжатого файла
On Mon, Feb 13, 2012 at 05:01:16PM +0400, Alexander Galanin wrote: 13.02.2012 16:56, Иван Лох пишет: On Mon, Feb 13, 2012 at 06:51:48PM +0600, Andrey Rahmatullin wrote: On Mon, Feb 13, 2012 at 04:30:12PM +0400, Alexey Pechnikov wrote: Большой файл (больше размера ОЗУ и свободного дискового пространства) сжат, например, с помощью gzip или любого другого потокового упаковщика. Надо его разжать, причем с реверсом строк на лету, не читая весь файл в память и не сохраняя на диск. Понятно, что задача выполнима, Нет, непонятно. Обоснуйте. Раз в zlib есть gzseek на чтение, то она теоретически выполнима. Практически, это идиотизм, конечно. Всего-то n^2 вместо n. В случае, когда памяти мало, это может быть неплохим результатом. n^2 это в данном случае бесконечность. Понятно, что надо сохранять вектор отступов блоков на первом проходе.. -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120213131259.gb23...@nano.ioffe.rssi.ru
Re: Аналог утилиты tac для сжатого файла
13.02.2012 17:12, Иван Лох пишет: n^2 это в данном случае бесконечность. Понятно, что надо сохранять вектор отступов блоков на первом проходе.. Тут на интересную задачку можно накопать, если не знать про входные данные более ничего :) Если хранить вектор отступов, то памяти при работе потребуется M = (N/K)*sizeof(off_t)+K, где N — размер файла, K — размер блока, который мы можем распаковываем единовременно. При этом M может оказаться больше, чем размер доступной памяти. -- Alexander Galanin -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/4f391269.1080...@galanin.nnov.ru
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 -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/87lio6ohtx.wl%...@ran.pp.ru
Re: Аналог утилиты tac для сжатого файла
On Mon, 13 Feb 2012 19:48:10 +0400 Artem Chuprina r...@ran.pp.ru wrote: Ну, в тяжелом случае (файл состоит из одних переводов строки или чего-то очень близкого, что можно сжать в один блок) нам все равно придется разжать весь файл, если пользоваться zlib, а не лезть в структуру уже блока грязными ногами. Да уж, тут все хитрости окажутся бесполезны. А в типичном нам нужно хранить не полный вектор отступов, а только те, которые еще нужны, а их вряд ли много - один, ну, два. Так файл-то надо задом наперёд пройти. Так что сначала дойти до конца, расставив контрольные точки, а потом идти с конца, когда их можно будет исключать. -- Alexander Galanin -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120213210345.bfb61690bfcfbe215b59e...@galanin.nnov.ru
Re: Аналог утилиты tac для сжатого файла
А в типичном нам нужно хранить не полный вектор отступов, а только те, которые еще нужны, а их вряд ли много - один, ну, два. Так файл-то надо задом наперёд пройти. Так что сначала дойти до конца, расставив контрольные точки, а потом идти с конца, когда их можно будет исключать. Насколько я понимаю, у гзипнутого файла вполне есть структура, которую можно распознать. Он на блоки поделен. Так что не надо будет идти до конца. Как делает tac? Делает seek на глазок поближе к концу, читает блок вперед, ищет концы строк. Целые строки выводит, запоминает только начало блока до первой \n. Задействует, конечно, память под найденные позиции концов, но только в пределах одного прочитанного блока, после вывода смело их забывает. Так же можно делать и тут, только искать надо будет начало гзип-блока, и запоминать его смещение первого из найденных, и начало раззипованного куска до первой \n. Хотя вообще у меня было такое ощущение, что zlib жмет блоки ограниченного размера. Не сжатый блок делает ограниченного размера, а исходный. 32K по умолчанию. Так что если есть уверенность, что файл сжат zlib'ом, то и файла из одних концов строк бояться не надо - там максимальный размер разжатого куска 32K. А вот четкой уверенности в том, что можно, начав с любого места, уверенно найти начало блока, у меня нет, но есть ощущение, что структура у него такова, что да, можно. -- /dev/null-транспортировка -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/87ipjaoa3k.wl%...@ran.pp.ru
Re: Аналог утилиты tac для сжатого файла
Кажется, стоит дополнить - разумеется, сжимаются строки ненулевой длины, но достаточно малые для того, чтобы имело смысл применить построчное сжатие; скажем, длина строк от 100 до 1000 байт. Подойдет и вариант поблочного сжатия (например, блоками по 16...256 килобайт). Как очень простой вариант, можно сжимать по N строк и в хексе их записывать построчно на диск... итоговый файл легко пропустить через tac и далее построчно читать, распаковывая и делая реверс строки. При правильно выбранном N получим и выигрыш от сжатия и простую распаковку. При наличии достаточного объема ОЗУ аналогичное легко проделывается в памяти (без перекодировки в хекс). Наверняка есть готовые библиотеки и утилиты, реализующие данный алгоритм (как минимум, подобное делается во множестве СУБД с поколоночным хранением). -- Best regards, Alexey Pechnikov. http://pechnikov.tel/
Re: Аналог утилиты tac для сжатого файла
On Mon, 13 Feb 2012 23:34:30 +0400 Alexey Pechnikov pechni...@mobigroup.ru wrote: Кажется, стоит дополнить - разумеется, сжимаются строки ненулевой длины, но достаточно малые для того, чтобы имело смысл применить построчное сжатие; скажем, длина строк от 100 до 1000 байт. Раз уж допустимо менять формат входных данных, то почему бы не хранить информацию в виде россыпи из гзипнутых файлов по N строк? P.S. пардон за «личку» -- Alexander Galanin -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120214000140.d929299a68e57c7322e5f...@galanin.nnov.ru
Re: Аналог утилиты tac для сжатого файла
14 февраля 2012 г. 0:01 пользователь Alexander Galanin a...@galanin.nnov.ru написал: Раз уж допустимо менять формат входных данных, то почему бы не хранить информацию в виде россыпи из гзипнутых файлов по N строк? Чтобы за просто так порвать диск? Очень сильно думаю, что в любом скриптовом языке fsync зовется после записи каждого файла... так что никак не вариант. А вообще хватило бы и двух файлов - с блоками и со смещениями блоков, но это некрасиво. Пришло в голову, что zip архив позволяет добавлять файлы к архиву, и утилитка для этого дела есть, любезно написанная когда-то Anton Kovalenko: | zipput archive.zip file-name Интересно, какая производительность такого решения, если туда поблочно/построчно данные пихать, может, и сойдет. P.S. В личку это как раз хорошо, чтобы ответить на это сообщение рассылку читаю в вебе. -- Best regards, Alexey Pechnikov. http://pechnikov.tel/
Re: Аналог утилиты tac для сжатого файла
On Tue, Feb 14, 2012 at 01:01:04AM +0400, Alexey Pechnikov wrote: Чтобы за просто так порвать диск? Очень сильно думаю, что в любом скриптовом языке fsync зовется после записи каждого файла... так что никак не вариант. А вообще хватило бы и двух файлов - с блоками и со смещениями блоков, но это некрасиво. Еще вариант, файловая система поддерживающая компрессию. Это самое простое и, думаю, быстродействующее решение, но не слишком переносимое. -- Иван Лох -- To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120213213118.gd23...@nano.ioffe.rssi.ru
