FastBWT

FastBWT это сортировщик BWT, использующий мой новый алгоритм сортировки путем склеивания частично сортированных отрезков. Метод требует примерно в 2 раза больше памяти по сравнению с обычной прямой сортировкой блока, но зато имеет гарантированную сложность O(n*logn*logn) вместо O(n*n*logn). Поскольку BWT обычно сортирует большие блоки данных, скорость на блоках с длиными одинаковыми последовательностями может падать в сотни и даже тысячи раз по сравнению с "удачными" блоками того же размера, что вынуждает отказываться от применения BWT в областях, где он мог бы быть полезен. Данный алгоритм не имеет "катастрофически неудачных данных", когда скорость обработки некоторых блоков заметно падает. Более того, его можно использовать для повторной сортировки и эта сортировка будет проходить даже быстрее первого прохода. Обычно

FastBWT можно запускать как обычное консольное приложение или как подключаемую .Net библиотеку.

Текущая версия библиотеки (0.3) включает две версии сортировщика и одну версию десортировщика. При запуске FastBWT как консольное приложение, используется сортировщик BWT_Medium_Sorter.

Изменения

Версия 0.3 (Загрузить)

Первая опубликованная версия.

BWT_Medium_Sorter получил параллельную инициализацию и двубайтовую корзиночную сортировку, что сократило время обработки на 15%-20%.

Работа с FastBWT как с подключаемой библиотекой

Файл FastBWT.exe можно подключить к своему проекту как обычную библиотеку через раздел References. FastBWT имеет следующие открытые классы:

FastBWT.ASorter

Абстрактный суперкласс для всех сортировщиков. Также содержит статические методы для применения сортированного индекса.

FastBWT.BWT_Small_Sorter

Сортировщик для маленьких блоков. Позволяет сортировать блоки размером до 2Г, но эффективен только для очень маленьких блоков, где оптимизации приносят вред. Имеет смысл использовать этот сортировщик, если размер блока не превышает нескольких сотен килобайт.

FastBWT.BWT_Medium_Sorter

Сортировщик для средних блоков. Позволяет сортировать блоки размером до 2Г. Для сортировки блоков большего размера необходимо применять более сложные конструкции, поскольку .Net не позволяет создавать обычные массивы длиной более 2Г элементов.

FastBWT.ADesorter

Абстрактный класс для всех десортировщиков.

FastBWT.BWT_Small_Desorter

Десортировщик для маленьких блоков. Позволяет десортировать блоки размером до 2Г. В настоящий момент работает в одном потоке.

FastBWT.StatisticStep

Структура, содержащая отчет одного рабочего потока об одной итерации.

Объекты сортировщиков могут использоваться повторно, но только после окончания предыдущей сортировки. Если необходима одновременная обработка нескольких блоков, создайте несколько объектов. Сортировщик достаточно интенсивно распараллеливает свою работу, так что запуск более двух сортировщиков одновременно будет лишь замедлять работу при любом количестве процессорных ядер. Объем используемой памяти обычно равен 9-11 размерам блока и зависит от типа данных. Например, видео и другие сжатые данные могут вызывать временный, но очень резкий скачок используемой памяти. При 16Г памяти видео файл размера 1,4Г обычно уже не удается отсортировать. 

Работа с FastBWT как с консольным приложением

FastBWT можно запускать вручную, из скриптов или из "не .Net" приложений. Если не указывать входящий или исходящий файл, программа соответственно читает или записывает в стандартный поток консоли. В этом случае нельзя использовать параметры, выводящие что-то на экран. Не пытайтесь пока сортировать файлы больше 2Г: программа, скорее всего выдаст ошибку или отсортирует его неверно.

Программа требует при запуске несколько типов параметров:

• Команда -bwt или -ubwt. Для сортировки нужно указать ключ -bwt, для десортировки ключ -ubwt.
• Входной и выходной файл -i и -o. Через пробел после ключа нужно указать путь к файлу. В скриптах путь лучше заключить в двойные кавычки: так решаются проблемы с пробелами в пути. Если программа должна читать или писать данные в стандартный поток, просто не указывайте этот ключ.
• Способ кодирования индекса -ip, -in, -ii, -id. Стартовым индексом называется индекс первоначального блока в отсортированной матрице. Этот индекс необходим для правильного поворота десортированного блока. Если его указать неверно, ошибки не произойдет, но получившийся файл будет "провернут". То есть, его начало будет где-то в середине.
  • Ключ -ip означает вывод индекса на экран. Разумеется, этот ключ запрещен, если выводной файл не указан. Этот ключ используется только при сортировке.
  • Ключ -in означает запись/чтение индекса из имени файла. Перед расширением файла вставляется индекс в десятичной форме и в квадратных скобках. При десортировке программа сама извлекает этот индекс. Обратите внимание, что при сортировке имя выходного файла отличается от указанного. Например, если индекс равен 12345, а имя файа указанно как file.bwt, программа создаст файл file[12345].bwt. При десортировке надо указывать имя файла с индексом.
  • Ключ -ii означает запись/чтение индекса непосредственно в файл. В выходной файл записывается отсортированный блок и 4 байта, содержащие индекс в порядке Big Endian (первый байт - старший). Десортировщик читает файл и использует последние 4 байта как индекс.
  • Ключ -id служит для непосредственного указания индекса. Через пробел после него следует указать индекс в десятичной форме. Этот ключ используется только при десортировке.
• Необязательная команда вывода статистики выполнения -stat. Каждый рабочий поток сортировщика отчитывается о количестве проделанной работы на каждой итерации сортировщика. Эту статистику можно затем использовать для оценки "сортируемости" файла и для подгонки параметров сортировщика.

Формат статистики

Статистика разбита на блоки Step по итерациям сортировщика. Каждая итерация сортирует индексы до определенной глубины. После сортировки неотличимые индексы группируются.

Большие группы (big) содержат больше 65536 индексов. Такие группы могут серьезно замедлить следующий шаг.

Мелкие группы (small) содержат от 2 до 65535 индексов. Такие группы быстро сортируются и обрабатываются пакетно.

Точки (points) содержат 1 индекс и больше не будут требовать обработки.

Длительность (Duration) - количество секунд, затраченных потоком на обработку шага.

Суммарная статистика итерации указывает общие затраты на итерацию. Суммарная длительность (Total Duration)указывает время обработки шага одним потоком. Максимальная длительность (Max Duration) указывает реальное время обработки шага. Потоки не могут переходить к следующему шагу, пока все соседи не закончат работу, поэтому каждый шаг может приводить к потере до нескольких секунд.

Строчка Полное Время (Total Time) указывает время, прошедшее с начала инициализации сортировки до получения сортированного блока. Время чтения и записи не учитывается.

Примеры команд сортировки файла

FastBWT.exe -bwt -ip -i d:\abc\file.txt -o file.bwt

Сортировать файл d:\abc\file.txt, сохранить результат в файл file.bwt в текущем каталоге и вывести индекс на экран.

FastBWT.exe -bwtt -in -stat -i d:\abc\file.txt -o d:\abc\file.bw

Сортировать файл d:\abc\file.txt, вписать в имя файла стартовый индекс и сохранить результат в файл с получившимся именем. Например, если стартовый индекс равен 12345, то результат сохранится в файл d:\abc\file[12345].bwt. После сортировки вывести статистику.

MyProg.exe | FastBWT.exe -bwt -ii > d:\abc\out.bwt

Отсортировать данные из программы MyProg.exe, сохранить результат и индекс в файл d:\abc\out.bwt.

Примеры команд десортировки файла

FastBWT.exe -ubwt -i d:\abc\file.bwt -o file.txt -id 12345

Десортировать файл d:\abc\file.bwt в файл d:\abc\file.txt используя стартовый индекс 12345.

FastBWT.exe -ubwt -i d:\abc\file[12345].bwt -o file.txt -in

Десортировать файл d:\abc\file[12345].bwt, взяв индекс из имени файла и сохранить результат в файл file.txt в текущем каталоге.

FastBWT.exe -ubwt -ii < d:\abc\in.bwt | MyProg.exe

Десортировать файл d:\abc\in.bwt, взяв индекс из последних четырех байтов файла и отправить результат программе MyProg.exe