LINUX.ORG.RU

Релиз shuf-t 1.2 — аналог shuf для файлов размером с RAM

 ,


2

12

Хочу представить публике утилиту shuf-t — аналог shuf (случайная перестановка строк файла) из GNU Core Utilities, предназначенный для работы с текстовыми файлами, размеры которых сравнимы или превышают доступную RAM.

Факты:

  • Shuf-t был написан с нуля на Qt5. Версия 1.2 перенесена на boost 1.5.8, без Qt. Но QtCreator \ qmake все еще используются для сборки.
  • Распространяется под лицензией Simplefied BSD.
  • Командный интерфейс совместим с shuf.
  • На данный момент доступен только deb пакет. Windows версия будет собрана позднее.
  • Для тасования строк использован алгоритм Фишера-Йетса

Кому мал shuf?

Основная сфера применения shuf-t — задачи машинного обучения. Конкретнее - подготовка данных для Vowpal Wabbit. Машинное обучение позволяет классифицировать (и не только) результаты на основе исторической выборки. Яркий пример — банковский скоринг (давать/не давать кредит). Чем больше результатов кредитования увидит классификатор — тем он точнее (обычно).

Столкнувшись с данными, объемом превосходящими RAM одного компьютера, экспериментатор вынужден обращаться к кластерам (MapReduce и т.п.) и облакам. Либо воспользоваться системами online machine learning, лучшей из которых сейчас является Vowpal Wabbit. Принцип VW — получил пример, обработал его и забыл. В памяти хранятся только коэффициенты результирующих уравнений, которые подгоняются по получаемым примерам. Т.о. VW может работать на одном ПК с наборами данных неограниченного размера.

У подобных систем есть минусы, и один из них — чувствительность к порядку предъявляемых для обучения классификатора данных. К примеру, если вы отсортируете ваш набор кредиторов по результату, и предъявите VW сначала 10000 неплательщиков, а затем 10000 исправно погасивших долг, то после обучения классификатор будет всех заносить в последнюю группу, т.к. о неплательщиках он давно «забыл». Выходом в данном случае является равномерное размазывание записей о плохих и хороших заемщиках по набору данных. Что и достигается рандомизацией порядка строк в текстовом файле размером в сотню гигабайт.

Как работает?

Очень просто - в RAM считываются не строки файла, а их адреса в нем. Их порядок рандомизируется. В соответствие с новым порядком строк исходный файл считывается в выделенный в RAM буфер и сохраняется, куда пожелал пользователь. Нюансом тут является то, что файл считывается в несколько проходов (т.к. буфер меньше его размера), а offset'ы строк сортируются так, что чтение всегда идет от начала файла к его концу. Т.е. не выполняется seek() адреса меньше текущей позиции чтения.

Скорость работы зависит от числа строк, их размера и меняется нелинейно. 4Гб файл с дефолтным буфером в 1Гб у меня обрабатывается 4 минуты.

>>> Проект на github



Проверено: Shaman007 ()

аналог shuf из GNU Core Utilities

написан на Qt5

Klymedy ★★★★★ ()
Ответ на: комментарий от Klymedy

Я весь софт для личного пользования пишу на Qt, в т.ч. консольные утилиты.

Truf ()
Ответ на: комментарий от sudopacman

Я может юмора вашего не понимаю?

QtCreator->New project->Qt Console Application. Потом при необходимости ненужные 3 строчки выпиливаются - остается чистый C++ проект. С QtCreator в качестве IDE и qmake для сборки. А вообще, я же написал, что

Версия 1.2 перенесена на boost 1.5.8, без Qt.

Т.к. от Qt там остался только QCommandLineParser.

Truf ()
Ответ на: комментарий от Truf

Понятно. Но просто вроде как qt графический тулкит, а тут консольное приложение.

sudopacman ★★★★★ ()
Ответ на: комментарий от sudopacman

вроде как qt графический тулкит

Уже давно нет. Без QtGui или QtOpenGL не будет графики, c одним QtCore вполне можно создавать консольные приложения или демоны.

Автору стоит задуматься о применении более лёгкой библиотеки. Boost-то еще ладно - может там что-то нетривиальное, которое кодить без подобной библиотеки - чистое самоубийство. Другое дело - зачем тащить целый QtCore ради QCommandLineParser?

Pinkbyte ★★★★★ ()
Последнее исправление: Pinkbyte (всего исправлений: 1)
Ответ на: комментарий от Pinkbyte

Да нету там уже QtCore. Я QCommandLineParser переделал на вызовы libboost_program_options. В честь этого и релиз v1.2.

Truf ()
Ответ на: комментарий от Truf

QCommandLineParser переделал на вызовы libboost_program_options

Пардон, значит не понял я тебя. Ну тогда всё правильно сделал.

Pinkbyte ★★★★★ ()
Ответ на: комментарий от sudopacman

Хе, я уже не помню, когда последний раз писал GUI приложение на Qt. И без WYSIWYG редактора уже вряд ли GUI соберу.

QtCreator и его toolchain у меня стандартный IDE. Я в него любые C\C++ проекты затаскиваю и спокойно работаю. Тот же Vowpal Wabbit собирается в нем на ура.

Truf ()

афффтор, ну ты и пейсатель: килобайты кода стройными рядами, покуда хватает глаз, уходят вдаль, к горизонту... а покороче точно нельзя?

1. есть sort -R, который может и подтормаживать, но по идее должен работать с большими файлами

2. а как насчет алгоритма попроще?

типа порезать большой файл на куски, влезающие в память, перетасовать каждый кусок по отдельности, записать в файл, а затем последовательно вычитывать по одной строке из случайно выбираемого одного из этих файлов и писать в результирующий файл?

и еще — как у тебя прога будет работать, если некоторые строки дикого размера, например, вообще в оперативку не помещаются целиком?

www_linux_org_ru ★★★★★ ()
Ответ на: комментарий от www_linux_org_ru

э-хе-хех

килобайты кода стройными рядами, покуда хватает глаз, уходят вдаль, к горизонту.. а покороче точно нельзя?

Мой код суммарно 33Кб. Я тут глянул - один shuf.c из GNU Core Utils 8.24 весит 17,6Кб. К нему еще 12 header'ов, которые шарятся между многими утилитами. Смею предположить, что shuf-t меньше shuf.

Нафига столько кода? А для обработки 10 параметров командной строки и пятака порожденных ими режимов работы. Все чтобы мимикрировать под командный интерфейс оригинального shuf. Он довольно богатый. Могу рассказать подробнее, но вам вряд ли это нужно.

1. есть sort -R, который может и подтормаживать, но по идее должен работать с большими файлами

sort (кстати, весит 144Кб один .c файл) сортирует по хешам. Хз насколько хорошо. В любом случае скорость его работы удручает. Попробуйте тасануть им 4-х гиговый файл. В моей практике был случай, когда строк было миллиард и тасование занимало больше суток. Сколько будет над такими данными пыхтеть sort? Неделю... месяц..?

2. а как насчет алгоритма попроще?
типа порезать большой файл на куски, влезающие в память, перетасовать каждый кусок по отдельности, записать в файл, а затем последовательно вычитывать по одной строке из случайно выбираемого одного из этих файлов и писать в результирующий файл?

Ну возьмите датасет из примера - 10000 плохих заемщиков, потом 10000 хороших. На какие куски вы будете резать такой файл и сколько проходов с тасованием вам понадобиться, чтобы гарантировать то, что он хорошо перемешан? Логично, что тасовать придется и сами куски и принцип разбиения на них. И не факт, что производительность будет выше shuf-t. Вообще, вопрос алгоритма «попроще» поднимался на kaggle, т.к. у каждого питонщика оказался свой костыль для тасовки больших файлов. Меня более-менее устроила как раз эта эвристика.

А в целом, т.к. речь идет об околонаучных областях применения, я бы не приветствовал подобные костыли.

как у тебя прога будет работать, если некоторые строки дикого размера, например, вообще в оперативку не помещаются целиком?

С такими данными shuf-t работать не сможет. Но трудно представить себе строку больше гигабайта (это дефолтный размер буфера, его можно и увеличить). В машинном обучении используются текстовые файлы, в которых одна строка соответствует одному историческому наблюдению (в 99% случаев). Речь идет о тысячах и миллиардах строк. У меня были максимум по 16Кб каждая. Датасет из строк в гигабайты мне трудно представить, т.к. для статистической достоверности их потребуется минимум пара сотен.

Truf ()
Ответ на: комментарий от www_linux_org_ru

2. а как насчет алгоритма попроще?

типа порезать большой файл на куски, влезающие в память, перетасовать каждый кусок по отдельности, записать в файл, а затем последовательно вычитывать по одной строке из случайно выбираемого одного из этих файлов и писать в результирующий файл?

Сори, я не дочитал цитату и контрпример был не верный. Но в любом случае - дерзайте, может догоните sort -R по скорости.

Truf ()

> Но QtCreator \ qmake все еще используются для сборки.

Люди, которые путают символы «/» и «\», не должны программировать.

poige ()

Написал программку уровня лабы первого курса, молодец, к тебе вопросов нет. Вопрос к Шоме: что это делает в новостях?

mix_mix ★★★★★ ()

Shuf-t был написан с нуля на Qt5. Версия 1.2 перенесена на boost 1.5.8

А IRL там нужен был всего-лишь патч строчек в 10 к оригинальному shuf

devl547 ★★★★★ ()
Ответ на: комментарий от mix_mix

Так оно же про бабки, кредиты тусует, а значит дико интерпрайзная штука!

Napilnik ★★★★★ ()

Не понимаю, чего вы взъелись на чувака. Написал полезный софт,обосновал его актуальность. Чувак молодец, а вы его пилите. Не надо так)

aarexer ()
Ответ на: комментарий от devl547

умиляет, как красноглазые эникеи считают нужным вбросить свое веское слово в теме разработки ПО. от наблюдения за процессом сборки и поглядывания на код с умным видом разработчиками не становятся.

tcler ()
Ответ на: комментарий от aarexer

Чувак молодец, а вы его пилите.

Суть любого форума же.

WARNING ★★★★ ()
Ответ на: комментарий от Truf

Давай.

Кстати, рекомендую почитать про sliding mmap и не изобретать велосипеды.

devl547 ★★★★★ ()
Ответ на: комментарий от tcler

Умиляет когда школьники фигачат здоровенные велосипеды вместо того, чтоб зайти в гугл.

devl547 ★★★★★ ()

банковский скоринг (давать/не давать кредит)

данными, объемом превосходящими RAM одного компьютера

Спуфинг зашел что ли?

buddhist ★★★★★ ()
Ответ на: комментарий от devl547

Умиляет когда школьники фигачат здоровенные велосипеды вместо того, чтоб зайти в гугл.

Так они стают взрослыми мужчинами, в отличие от девочек, которые жить не могут без гугля ^_^.

anonymous ()
Ответ на: комментарий от devl547

Вообще-то я не школьник и давно уже не студент, к сожалению. И я не думаю, что mmap даст выигрыш в производительности. Если вы быстренько накидаете свой shuf для 10Gb файла, мы сможем померятся скоростью тасовки.

Truf ()
Ответ на: комментарий от Truf

свой shuf для 10Gb файла

Где хранится исходный файл и куда писать результирующий? И какое у нас ограничение по размеру ОЗУ?

devl547 ★★★★★ ()
Ответ на: комментарий от Truf

Бэкслеш (\) и слеш (/) совершенно разные символы и использовать вместо второго первый - нехорошо :)

Dimez ★★★★★ ()
Ответ на: комментарий от devl547

Храниться на SSD и пишется на SSD. RAM не больше 4Gb.

Truf ()
Ответ на: комментарий от Dimez

Если уж на то пошло, бэкслеш вообще нельзя использовать в тексте на естественном языке. Это символ чисто синтетический и изобретён был для того, чтобы не тащить в ограниченное пространство таблицы ASCII символы ∧ и ∨.

Centaur ()
Ответ на: комментарий от devl547

Давай возьмем train.csv из датасета компании Criteo с их конкурса на Kaggle. Вот страничка конкурса. Вот линк на датасет. Датасет 4.3Gb в gzip. Думаю, train.csv в нем должен превышать 6Gb. У меня качаться 40 мин будет. Регистрации там нет - просят указать любое имя.

Truf ()
Ответ на: комментарий от Centaur

чтобы не тащить в ограниченное пространство таблицы ASCII символы ∧ и ∨.

Будто этот хлам из Алгола не синтетический.

devl547 ★★★★★ ()

уважаемый Вы все ещё в нокие? зачем вам машинное обучение?

anonymous ()
Ответ на: комментарий от Truf

Ограничиваем память до 4 гигов или меньше

Датасет 4.3Gb в gzip.

Читаем с SSD, шаффлим в нём строчки и пишем обратно на SSD.

Всё так?

4Гб файл с дефолтным буфером в 1Гб у меня обрабатывается 4 минуты.

Ок, учтём для сравнения

devl547 ★★★★★ ()
Ответ на: комментарий от anonymous

уже 1.5 года как нет. Хочу заниматься МО - нравится мне.

Truf ()
Ответ на: комментарий от devl547

Размер train.csv будет ясен, когда я его скачаю и распакую ) А так вроде все верно.

Truf ()
Ответ на: комментарий от devl547

Это оказался train.txt в формате tsv на 10.4Gb и 45840617 строк.

Truf ()

Раз написали, значит кому-то нужно. Хотя например чем дамп файлы баз данных открывать... самое оно. Буду знать.

weare ★★ ()
Ответ на: комментарий от Truf

Хорошо, вечером погоняю шаффл на этом файле.
Есть пара мыслей, как это сделать быстро не изобретая велосипедом.

devl547 ★★★★★ ()
Ответ на: комментарий от devl547

У меня получилось следующее: Буфер 1Гб (дефолтный) - 21.37 мин; Буфер 2Гб - 13.55 мин

http://pastebin.com/46SqcHMC

Следует отметить, что программа на почти 46 млн. строк дополнительно берет ~0.8Гб памяти на метаданные (offset'ы строки в исходном файле и файле результате). Так что пиковое потребление RAM было 1.7 и 2.8 Gb соответственно.

С большим буфером пробовать пока не буду - подожду результатов mmap().

Конфигурация у меня: Kubuntu 15.10, 16Gb RAM, 1Tb SSD, Intel i7 2.9GHz 4-core.

Truf ()

Запасаемся попкорном)

anonymous ()

Давайте так: побежденный рекламирует победителя среди тех кому уже отдал или отдаст программу

anonymous ()

Тред не читал, но за Коша респект! :D

pascal ★★ ()

У меня не скромный вопрос. Кому нужно отсосать чтобы такая новость попала на главную?

st4l1k ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.