izvolov/burst

То, чего нет в Бусте

burst's Issues

Провести испытания разных алгоритмов пересечения

Сейчас в итераторе пересечения используется частный случай алгоритма WAND.
В упорядоченном списке диапазонов берётся наименьший по первому элементу диапазон, и если его первый элемент не совпадает с первым элементом последнего диапазона, то он — наименьший диапазон — прокручивается до тех пор, пока его первый элемент меньше первого элемента последнего диапазона, а затем ставится в отсортированный массив диапазонов на своё новое место.

Есть мнение, что можно сделать по-другому, а именно — продвинуть все диапазоны, которые по первому элементу меньше последнего, а затем отсортировать массив диапазонов заново.

Нужно выяснить (аналитически и замерами), не будет ли это эффективнее.

Научить итератор склейки работать с rvalue

1. Всегда принимает строго диапазон диапазонов.
2. Копирует этот диапазон диапазонов себе внутрь.

Разность множеств

Добавить итератор разности множеств и функцию для получения диапазона такой разности.

Функции для создания стандартных контейнеров из диапазонов

У контейнеров (например, std::vector) есть конструктор, принимающий два итератора, но нет конструктора, принимающего диапазон. Из-за этого бывает проблематично сконструировать rvalue такого контейнера.

Необходимо реализовать такую функциональность.

Поиск галопом

Написать алгоритм поиска галопом.
Поиск начинается с первого элемента последовательности.
Искомый элемент сравнивается с текущим элементом. Если текущий элемент меньше, то делается единичный шаг, снова сравнивается и т.д. При каждом несовпадении шаг удваивается.
Когда текущий элемент становится не меньше искомого, в диапазоне от элемента на предыдущем шаге до текущего элемента искомое значение доискивается простым двоичным поиском.

Реализовать функции

1. galloping_lower_bound
2. galloping_upper_bound

Установка проекта

Завести команду в make для установки заголовков проекта.

Вынести целочисленные логарифмы в отдельные файлы

Сейчас в разных частях программы используются функции (logip, log2ip), вычисляющие целую часть логарифма. Эти функции могут пригодиться и в других местах, поэтому следует вынести их в отдельные файлы и написать к ним отдельные тесты.

Инфраструктура для измерений

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

Добавить сортировку подсчётом

Стандартный алгоритм сортировки подсчётом.
Интерфейс:
counting_cort(first, last, result, map).
first, last — итераторы на начало и конец сортируемой последовательности.
result — итератор на начало результирующей отсортированной последовательности.
map — отображение входной последовательности в целые числа.

Структура для K-ичного поиска

Разработать структуру, соответствующую интерфейсу стандартных std::множеств (std::set, std::unordered_set и т.п.), основанную на поиске в k-ичном дереве поиска.
Основные идеи изложены в статье "Schlegel, Gemulla, Lehner — k-Ary Search on Modern Processors".
http://www.ins.cwi.nl/projects/damon09/DaMoN09-KarySearch.pdf

Новый принцип работы с множествами

Итераторы слияния, пересечения, объединения и т.п. нуждаются в переработке:

1. Владеть принимаемым внешним диапазоном.
2. Не копировать внутрь себя внутренние диапазоны.
3. Внешний диапазон должен быть иметь такую категорию, чтобы итератор-алгоритм мог модифицировать его так, как ему нужно (например, для итератора слияния это произвольный доступ).
4. Контейнеры и список инициализации не рассматривается как входной аргумент.

Аллокатор для динамического кортежа

Подумать о том, чтобы параметризовать ДК аллокатором.

Вопрос: нужен ли аллокатор для массива менеджеров? Если нужен, то как их обобщить? Ведь для хранилища нужен байтовый аллокатор, а для массива менеджеров — аллокатор, параметризованный типом менеджера.

Вытащить функции-обёртки для диапазонов из итераторов

В настоящий момент в файлах, где определены итераторы слияния и пересечения, реализованы ещё и функции-обёртки, которые создают диапазоны этих итераторов — это функции thrust::merge(ranges) и thrust::intersect(ranges).

Эти функции нужно вынести в отдельные файлы в thrust/range/merge.hpp и thrust/range/intersect.hpp соответственно.

Подумать о более лёгком копировании итераторов

Сейчас в проекте есть три итератора — слияния, пересечения и склеивания.
Все они хранят обрабатываемые диапазоны внутри себя по значению.
Соответственно, при копировании происходит копирование этих внутренних массивов диапазонов.

Нужно подумать, возможно ли реорганизовать код и облегчить копирование этих итераторов, то есть чтобы копирование итераторов не влекло за собой копирование больших внутренних объектов.

Поразрядная сортировка с пользовательским буфером

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

Адапторы для диапазонов

Для механизмов работы с диапазонами "на лету" создать аналогию бустовым адапторам.

Пример (псевдокод):

std::vector<std::vector<int>> items
{
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

auto to_range =
    [] (const auto & container)
    {
        return boost::make_iterator_range(container);
    };

auto flattened_items =
    items
        | boost::adaptors::transformed(to_range)
        | burst::adaptors::joined;

assert(flattened_items == {1, 2, 3, 4, 5, 6, 7, 8, 9});

Подумать об эффективном вычислении расстояния между итераторами слияния

Сейчас итератор слияния не умеет за константу выяснять расстояние до другого итератора слияния.
Однако, итератор слияния мог бы при инициализации выяснять суммарную длину входных диапазонов, запоминать это число, а затем, при продвижении, уменьшать его.
Это дало бы возможность вычислять за O(1) расстояние между двумя итераторами слияния просто посчитав разницу этой остаточной длины и, как следствие, выяснять за константу размер диапазона слияния.

Проблема тут в том, что если входной диапазон не имеет метода size(), то и вычислить суммарную длину быстро не удастся.
Поэтому надо либо пробегать по таким диапазонам от начала до конца и считать размер за линию, либо по-особому обрабатывать такие диапазоны — создавать для них другую специализацию(?) итератора слияния.

Добавить итератор объединения

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

Сделать итератор склейки более эффективным

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

Для этого нужно внутри итератора склейки хранить два индекса — индекс текущего диапазона в массиве диапазонов и индекс элемента в текущем диапазоне.
Также можно завести переменную — количество элементов до конца склеенного диапазона. Тогда можно будет за O(1) вычислять расстояние между итераторами.

Обобщённый алгоритм прокрутки

В первом приближении интерфейс такой.

Для диапазонов:

burst::skip_to_lower_bound(range, goal);
burst::skip_to_upper_bound(range, goal);

Для итераторов:

burst::advance_to_lower_bound(iterator, goal);
burst::advance_to_upper_bound(iterator, goal);

burst::advance_to_lower_bound(iterator, limit, goal[, compare]);
burst::advance_to_upper_bound(iterator, limit, goal[, compare]);

goal — элемент типа value_type, до которого нужно прокрутить диапазон или итератор.
limit — итератор, представляющий предел, дальше которого прокручивать не нужно.
compare — отношения порядка.

Предел и отношение порядка задаются только в том случае, если прокручиваемый итератор не имеет встроенного метода advance_to_lower(upper)_bound.

Операции сдвига без неявных преобразований

Стандартные операции битового сдвига >> и << в общем случае не сохраняют тип числа, которое было подвергнуто этим операциям. Это приводит к избыточному коду.
Необходимо решить эту проблему при помощи соответствующих функций right_shift и left_shift.

Разработать алгоритм перебора подмножеств

На вход подаётся некое множество. Требуется последовательно пройти по его подмножествам.
Нужно придумать, как представлять подмножество и интерфейс работы с ним.

Снизить требования к итератору в битапе

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

Нужно изменить алгоритм так, чтобы он требовал только однонаправленного итератора.

Кэширующий итератор

Существуют итераторы, которые возвращают результат своего разыменования по значению. Например, таким может быть итератор преобразования (boost::transform_iterator). Иногда требуется запоминать результат такого преобразования, чтобы не производить вычисление заново каждый раз при обращении к итератору.

Требуется разработать кэширующий итератор со следующей логикой:

1. Кэширующий итератор присасывается к произвольному итератору Iter.
2. Если результат разыменования Iter — ссылка, то кэширующий итератор ничего не делает.
3. Если результат разыменования возвращается по значению, то при первом разыменовании кэширующий итератор переносит к себе этот результат и возвращает его по ссылке, а при последующих разыменованиях возвращает уже вычисленное значение.
4. При продвижении вычисленный результат выбрасывается.

Добавить итератор симметрической разности

Итератор, который пробегает по всем элементам, которые присутствуют в нечётном числе входных множеств.

Не копировать элементы в процессе поразрядной сортировки

Сейчас элементы копируются при перекладывании между буферами. Лучше их переносить.

Свойства типов

Создать раздел type_traits и реализовать метафункции для проверки некоторых свойств типов.
В настоящий момент требуются:

1. is_equality_comparable
2. is_less_than_comparable

Сделать итератор по битапу

В библиотеке реализован двоичный алгоритм поиска подстроки (он же "bitap", от же "shift-or").
В настоящий момент его интерфейс позволяет только производить поиск с нужного места в тексте.
То есть, если образец был найден где-то, то чтобы найти следующий, нужно начинать поиск с позиции после начала предыдущего вхождения.
На самом деле алгоритм позволяет этого не делать, и находить все вхождения ровно за один проход.
Для этого удобно было бы создать итератор по вхождениям, который проходил бы их всех, и при этом делал это эффективно.

Упрощение описания функций

У всех старых функций, создающих разнообразные итераторы и диапазоны (например, make_bitap_iterator или intersect), явно выписан тип возвращаемого значения.

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

Попробовать другой алгоритм для итератора слияния

Сейчас итератор слияния работает при помощи пирамиды.
Можно попробовать другой алгоритм, похожий на алгоритм в итераторе пересечения:

1. Хранить диапазоны в массиве упорядоченными по первым элементам.
2. При разыменовывании наружу выдаётся первый элемент первого диапазона.
3. При переходе к следующему элементу продвигается первый диапазон, а затем ставится на своё место в упорядоченном массиве (как в п.1).

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

Комментарии к итераторам

Нужно написать исчерпывающие комментарии к итераторам слияния и пересечения:

1. Описать алгоритм работы.
2. Описать требования к шаблонным параметрам.
3. Прокомментировать непонятные места.

Поразрядная сортировка

Стандартный алгоритм поразрядной сортировки.
Интерфейс:
radix_cort(first, last, map, radix).
first, last — итераторы на начало и конец сортируемой последовательности.
map — отображение входной последовательности в целые числа.
radix — функция взятия разряда из целого числа.

Функции типа make_<container> не только от диапазонов

Например, у класса std::vector есть конструктор вида vector(size, value). Значит, можно создать функцию

template <typename Value>
auto make_vector (std::vector<Value>::size_type, const Value & value);

которая выведет тип элементов вектора из передаваемого значения.

Добавить итератор полупересечения

M-полупересечение (нечёткое пересечение) N диапазонов — это элементы, каждый из которых есть не менее, чем в M из этих диапазонов, 1 <= M <= N. При M = 1 полупересечение вырождается в объединение, при M = N — в строгое пересечение.

Уважать ADL в функциях, создающих контейнеры

Существуют объекты, которые не являются массивами, но и методов x.{begin, end}() у них тоже нет. Зато для них определены внешние функции {begin, end}(x). Пример — boost::directory_iterator.

Для поддержки таких объектов, возможно, стоит в функциях make_{vector, list, set, ...}(r) вызывать не std::{begin, end}, а использовать ADL:

using std::begin;
using std::end;

... begin(x) ...
... end(x) ...

Добавить возможность узнавать тип (RTTI) объекта в ДК по индексу

По аналогии с boost/std::any.

Прокручивать диапазоны по-разному в зависимости от вида

Алгоритм skip_to в настоящий момент использует boost::lower_bound для поиска нужного элемента в диапазоне для любого вида диапазона: и произвольного доступа, и однонаправленного и пр.

Нужно в зависимости от вида диапазона реализовывать алгоритм по-разному.
Для диапазона произвольного доступа нужно использовать двоичный поиск, а для всех остальных — последовательный.

Написать функции для удобного создания итераторов

Сейчас для создания итераторов слияния и пересечения нужно явно прописывать их тип, а именно — сложные шаблонные параметры.

Нужно написать интерфейс для удобного создания этих итераторов.
Стандартная схема для этого — функции make_my_iterator.
К примеру:
auto merged_begin = thrust::make_merge_iterator(ranges);

Для итератора на конец, видимо, придётся либо воспользоваться специальным дополнительным аргументом функции, например,
auto merged_end = thrust::make_merge_iterator(ranges, thrust::iterator::end_tag);
либо использовать отдельную функцию вроде
auto merged_end = thrust::make_merge_iterator_end(ranges);

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

Компромисс в сортировке подсчётом

В сортировке подсчётом существует выбор:

1. Потребовать от входных итераторов однонаправленность, и тогда придётся в массив счётчиков добавлять один дополнительный элемент.
2. Потребовать от входных итераторов двунаправленность, и тогда дополнительный элемент в массив счётчиков добавлять не нужно.

Нужно взвесить все "за" и "против" данных подходов и выбрать лучший.
В данный момент выбран первый вариант.

Осовременить код

1. Все псевдонимы типов заводить через using.
2. Использовать полиморфные лямбды, где нужно.

Обдумать введение "допустимого, но неоговорённого" состояния для ДК

Согласно пункту стандарта 17.6.5.15 Moved-from state of library types, классы стандартной библиотеки после переноса переходят в допустимое, но неоговорённое состояние (valid but unspecified state).

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

Интерфейс поразрядной сортировки

Подумать над тем, нужен ли интерфейс, похожий на std::sort с предикатом по-умолчанию. То есть такой интерфейс, вызов которого приводит к тому, что сортированный диапазон оказывается на месте входного несорированного.

Поразрядная сортировка обязательно требует наличия дополнительного буфера. Возможно, стоит потребовать от пользователя предоставить этот буфер явно, а не создавать его в динамической памяти внутри алгоритма?

Операции с кортежами для использования в цепочках преобразователей

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

Нужно разработать наиболее часто применяющиеся функции:

1. Взять n-й элемент кортежа.
2. Преобразовать n-й элемент кортежа.
3. Применить функцию к кортежу

и т.д.

Также нужно предусмотреть возможность композиции этих преобразователей.

Облегчить копирование объекта битапа

thrust::algorithm::bitap хранит таблицу битовых масок для элементов искомого образца. При копировании объекта таблица копируется вместе с ним. Это довольно тяжёлый объект (по-умолчанию — std::map).

Однако, замечено, что объект, однажды проинициализированный образцом, больше никогда не меняется. Кроме того, очевидно, что для одинаковых образцов таблицы будут также одинаковые.
Это значит, что можно хранить таблицу не по значению, а по указателю, что упростит копирование всего объекта.

Вывод: в классе thrust::algorithm::bitap хранить таблицу битовых масок образца по указателю.

Внешние функции front(container) и back(container)

В стандартной библиотеке уже есть функции std::{c}begin() и std::{c}end(), которые возвращают соответствующие итераторы на тот объект, от которого они вызываются. Если это контейнер, то у него просто вызываются нужные методы. Если массив, то возвращаются указатели.

Нужно сделать аналогичные функции front(), back(), cfront(), cback().

Гетерогенный контейнер (динамический кортеж)

Массово внедрить функции типа make_<container>

По аналогии с уже существующей функцией burst::make_vector создать соответствующие функции, требующиеся в проекте, и заменить на них код явного создания этих контейнеров.

Обновить описание проекта.

Порядок включений от частного к общему

Сейчас заголовки включаются в порядке:

1. STL
2. Сторонние библиотеки.
3. Свои заголовки.

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

Итераторы побитового ввода-вывода

Создать аналогию стандартным итераторам std::{istream/ostream}_iterator, но которые работают не с текстовым представлением объектов, а бинарным.

Инструменты для взятия из диапазона нескольких первых элементов

1. Итератор со счётчиком оставшихся элементов.
2. Функции для работы с диапазонами:
   1. Если на входе диапазон произвольного доступа, то просто вернуть boost::make_iterator_range(begin, begin + n).
   2. Для любого другого диапазона создать boost::iterator_range<take_n_iterator<...>>.
3. Адаптор для работы с диапазонами.