Хочу представить публике утилиту 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
