Выпустил релиз 1.0.2 с дополнительными комментариями реализации. Спасибо хабробропользователям: - @wataru - за ревью, найденный баг в реализации и интересную дискуссию; - @jordiutrera - за ревью, PR с оптимизациями; - @cpud47 - за продуктивное обсуждение трудоёмкости;
Это верно, но и представить режим работы, при котором каждый вызов Min будет довольно сложно: нужно изменить довольно много данных между его вызовами. На фоне этих изменений вклад Min будет не заметен.
то при удалении это надо будет пересчитывать за O(n).
Я решил пересчитывать не при удалении, а при вызове Max/Min чтобы не портить производительность удаления. Верно, что в худшем случае это будет , но при последовательном вызове DeleteMin() для N элеметов потребуется сумммарно пропустить не более N элементов. Т.е. для серии вызовов это амортизируется в . Такая же история с упорядоченным обходом.
Линейный поиск ненулевого бита - это лишь деталь моей реализации. Планирую заменить на многоуровневый с логорифмической сложностью, хотя и жалко пары процентов производительности на вырожденный случай. На оценки из оригинальной публикации это не влияет, там этот механизм вообще не описан.
Также, есть обратная сторона медали: если мне нужны только уникальные элементы(а этом, согласитесь, более частый кейс), то приходится делать Search||Insert - а это бъёт по перфу.
Не знаю на сколько частый, но да, бъёт. Мне нужны были именно вспомогательные индексы по неуникальному полю - timestamp, [S2CellID] (https://s2geometry.io/devguide/s2cell_hierarchy.html), etc, поэтому сразу делал упорядоченное мультимножество.
Вы имеете ввиду случай, когда после минимального элемента идёт серия удалённых? Да, этот минус описан в начале статьи и вот здесь обсуждали возможные оптимизации.
У вас там похоже делается предположение, что раз в отрезке меньше половины удаленных и вы встретили удаленный, то слева точно что-то должно быть. Но ограничение-то на весь целый отрезок. Маленький его кусочек, рассматриваемый в бинпоиске, может нарушать это ограничение.
Спасибо за подробности! Верно, всегда идём на лево, потому что всегда удаляем самый правый элемент среди равных, что и обеспечивает `findRightmostNotDeleted` (используется и при поиске и при удалении). Надеюсь, снял вопрос по корректности?
Это O(N) даже с битовой магией. Ибо повторяющихся элементов может быть много
С учётом вышесказанного - нужно найти первый ненулевой бит в серии. Для этого есть много разных подходов, но прийдётся городить структуру данных внутри структуры данных. В простейшем случае можно сначала проверять не биты, а машинные слова - по 64 бита сразу. Последовательно. В теории сложность всё ещё линейная, на практике очень быстро работает.
В целом я бы посоветовал собрать сравнительную табличку.
Это можно, но для каждой структуры данных худшие, а для BWA ещё и довольно экзотические.
Так же более медленные поиск минимума, максимума (там линейная вообще сложность, по-моему. Ибо, а что если минимальные элементы все удалены?
Верно. Так как это случай был критичен для моего случая практического использования - оптимизировал его хранением позиций первого и последнего неудалённого элемента в массиве. Но со вторым элементом с конца всё будет так как вы написали.
Так же нельзя также быстро сделать всякие вещи на отрезках.
Можно, для этого даже отдельный метод есть! Сложность будет - квадрат логарифма. Медленнее чем у деревьев, но всё ещё достаточно быстро для многих случаев.
Структура интересная, но надо четко понимать, что в лоб сравнивать с деревьями нельзя, потому что она может сильно меньше.
Вот тут полностью согласен: структура требует знания её сильных и слабых сторон, B-Tree с правильным degree в этом плане более универсален.
Вот представьте, что у вас все элементы с одинаковым ключом, и массив deleted: [true, false, true, true, true].
Во первых, этот пример не корректен - удалённых элементов не может быть быть более половины, но в целом кейс верный. Я его сразу описал в начале статьи, в недостатках:
При редких паттернах операций массового удаления, возможна деградация производительности поиска до
Это случай поддаётся оптимизации - нужно эффективнее искать неудалённый элемент в битовой маске. Но он настолько вырожденный, что я не стал усложнять реализацию ради него.
Тесты у вас слабые. Надо добавить побольше одинаковых элементов и кучу разных битовых масок deleted.
Чтобы не перебирать разные битовые маски, существуют классы эквивалентности. Кажется я покрыл все, но если упустил - пожалуйста напишите какой конкрктно, или сделайте PR.
Перебалансировка дерева - это перекинуть Log n указателей-индексов. Прыжков тут не больше, чем в бинарном поиске.
Верно, но BWA не делает этой перебалансировки при вставке. Только слияния. И эта перебалансировка в BTree от Google уже медленнее чем вставки в BWA. Если ещё добавить периодические перемещения при использовании реаллокации массива - будет еще медленнее. Но если нужен не `Insert`, а `ReplaceOrInsert`, тогда будет как вы написали.
Ну это такое себе, оно за O(n) уменьшает потребление памяти максимум в 2 раза. В дереве тоже можно все пустые места перекинуть в конец и обрезать массив (с переаллокацией и memcopy, конечно).
Виноват, здесь не имел в виду удаление. Приведу пример: приложение читает данные из потока, размер которого заранее не известен. После чтения последнего элемента можно вызвать метод Compact() и удалить неиспользуемые массивы и чёрные сегменты. Например, при 9 элементах в BWA будут массивы длиной 1,2,4,8. После компактификации останутся 1 и 8 (трудоёмкость логарифмическая). В дереве-в-массиве же будет 16 элементов в этом случае. Compact довольно удобен, когда нужно периодически обновлять данные - можно минимизировать потребление памяти до полезной + 1 бит(для признака удаления) между обновлениями.
Во-первых, спасибо за внимательное прочтение, включая первоисточник. В современном мире это дорогого стоит!
Значения поисков редко распределены равномерно. Вообще распределение входных ключей может быть сильно разным. И есть основания полагать, что достаточно часто оно сильно перекошено (всякие правила Парето и прочее). Поэтому на практике результатами этой теоремы воспользоваться нельзя.
75% элементов расположено в первых двух массивах. ~94% в первых четырёх, что даёт или что хуже чистого логарифма, но всё ещё очень быстро. Случай, когда нам постоянно нужны только 6% элементов расположенных в младших массивах - довольно вырожденный.
P.S. Будьте аккуратнее с обработкой "одинаковых ключей", как Вы заявили. Потому что там очень легко все ассимптотики могут стать. Хотя глядя на код поиска, кажется он некорректен в присутствии одинаковых элементов.
Вот тут пожалуйста по-подробнее, у меня покрыты тестами этот и другой случаи. Буду признателен за конкретный пример, на котором код работает некорректно. Про деградацию по производительности - такая же просьба.
Кажется такой бенчмарк не очень репрезентативен.Не до конца понятна целевая ниша этой структуры данных, но обычно всё же у нас есть ещё какое-то (сравнительно большое) значение.
Типичный случай такого применения - вторичный индекс: основная структура лежит в массиве или map, a дерево/BWA хранит индекс в этом массиве или указатель и упорядочено по другому ключу.
Также стоит понимать, что использовать деревья просто как ассоциативные контейнеры чаще всего затея не самая удачная.
Это верно, если посмотрите на интерфейс библиотеки - у меня реализованы все типичные для деревьев методы, включая итераторы, Max/Min, etc. Так же реализованы некоторые методы, которые в деревьях не реализуемы, неупорядоченный обход с , например, по скорости близкий к обходу массива.
1. У деревьев будет оверхед на хранение индексов соседних узлов. Если в качестве value - int64, как в бенчмарке, будет чувствительно. 2. Вставка будет требовать не только реаллокаций, но и постоянной перебалансировки дерева с прыжками по памяти. BWA делает это последовательным слиянием. 3. У BWA в любой момент можно вызвать метод Compact и удвалить все неиспользуемые сегменты, что обеспечит минимальный расход памяти.
В целом было бы интересно сравнить на практике, хотя бы вставку. Если реализуете - обязательно присылайте, вставим сюда.
Спасибо, классная статья!
Как шутил одни профессор - "оптимизация загрузки кластера задачами может занимать больше чем сами задачи".
Выпустил релиз 1.0.2 с дополнительными комментариями реализации.
Спасибо хабробропользователям:
- @wataru - за ревью, найденный баг в реализации и интересную дискуссию;
- @jordiutrera - за ревью, PR с оптимизациями;
- @cpud47 - за продуктивное обсуждение трудоёмкости;
Отличный вопрос. Действительно, черные сегменты нужны каждую вторую вставку. Поэтому в своей реализации я держу их наготове. Но! более опытный в алгоритмах @jordiutrera предложил использовать старший белый массив как целевой: https://github.com/dronnix/bwarr/pull/23
Это верно, но и представить режим работы, при котором каждый вызов
довольно сложно: нужно изменить довольно много данных между его вызовами. На фоне этих изменений вклад
MinбудетMinбудет не заметен.Я решил пересчитывать не при удалении, а при вызове Max/Min чтобы не портить производительность удаления.
, но при последовательном вызове 
. Такая же история с упорядоченным обходом.
Верно, что в худшем случае это будет
DeleteMin()для N элеметов потребуется сумммарно пропустить не более N элементов. Т.е. для серии вызовов это амортизируется вВ оригинальной статье - "clever code", ближе к "заумный" чем к "продуманный" в этом контексте.
Линейный поиск ненулевого бита - это лишь деталь моей реализации. Планирую заменить на многоуровневый с логорифмической сложностью, хотя и жалко пары процентов производительности на вырожденный случай. На оценки из оригинальной публикации это не влияет, там этот механизм вообще не описан.
Не знаю на сколько частый, но да, бъёт. Мне нужны были именно вспомогательные индексы по неуникальному полю - timestamp, [S2CellID] (https://s2geometry.io/devguide/s2cell_hierarchy.html), etc, поэтому сразу делал упорядоченное мультимножество.
Ещё раз спасибо вам за ваши коментарии.
Вы имеете ввиду случай, когда после минимального элемента идёт серия удалённых? Да, этот минус описан в начале статьи и вот здесь обсуждали возможные оптимизации.
Положил в бэклог.
А вот это - "nice catch", как говорится, посмотрю подробнее и поправлю чуть позже. Большое спасибо.
Верно, даже хуже, сложность будет
при упорядоченном обходе - нужно каждый раз выбирать сегмент с наименьшим элементом.
Про корректность ответил выше.
Спасибо за подробности! Верно, всегда идём на лево, потому что всегда удаляем самый правый элемент среди равных, что и обеспечивает `findRightmostNotDeleted` (используется и при поиске и при удалении). Надеюсь, снял вопрос по корректности?
С учётом вышесказанного - нужно найти первый ненулевой бит в серии. Для этого есть много разных подходов, но прийдётся городить структуру данных внутри структуры данных. В простейшем случае можно сначала проверять не биты, а машинные слова - по 64 бита сразу. Последовательно. В теории сложность всё ещё линейная, на практике очень быстро работает.
Это можно, но для каждой структуры данных худшие, а для BWA ещё и довольно экзотические.
Верно. Так как это случай был критичен для моего случая практического использования - оптимизировал его хранением позиций первого и последнего неудалённого элемента в массиве. Но со вторым элементом с конца всё будет так как вы написали.
Можно, для этого даже отдельный метод есть! Сложность будет - квадрат логарифма. Медленнее чем у деревьев, но всё ещё достаточно быстро для многих случаев.
Вот тут полностью согласен: структура требует знания её сильных и слабых сторон, B-Tree с правильным degree в этом плане более универсален.
Во первых, этот пример не корректен - удалённых элементов не может быть быть более половины, но в целом кейс верный. Я его сразу описал в начале статьи, в недостатках:
Это случай поддаётся оптимизации - нужно эффективнее искать неудалённый элемент в битовой маске. Но он настолько вырожденный, что я не стал усложнять реализацию ради него.
Чтобы не перебирать разные битовые маски, существуют классы эквивалентности. Кажется я покрыл все, но если упустил - пожалуйста напишите какой конкрктно, или сделайте PR.
Верно, но BWA не делает этой перебалансировки при вставке. Только слияния. И эта перебалансировка в BTree от Google уже медленнее чем вставки в BWA. Если ещё добавить периодические перемещения при использовании реаллокации массива - будет еще медленнее. Но если нужен не `Insert`, а `ReplaceOrInsert`, тогда будет как вы написали.
Виноват, здесь не имел в виду удаление. Приведу пример: приложение читает данные из потока, размер которого заранее не известен. После чтения последнего элемента можно вызвать метод
Compact()и удалить неиспользуемые массивы и чёрные сегменты. Например, при 9 элементах в BWA будут массивы длиной 1,2,4,8. После компактификации останутся 1 и 8 (трудоёмкость логарифмическая). В дереве-в-массиве же будет 16 элементов в этом случае.Compactдовольно удобен, когда нужно периодически обновлять данные - можно минимизировать потребление памяти до полезной + 1 бит(для признака удаления) между обновлениями.Во-первых, спасибо за внимательное прочтение, включая первоисточник. В современном мире это дорогого стоит!
75% элементов расположено в первых двух массивах. ~94% в первых четырёх, что даёт
или 
что хуже чистого логарифма, но всё ещё очень быстро.
Случай, когда нам постоянно нужны только 6% элементов расположенных в младших массивах - довольно вырожденный.
Вот тут пожалуйста по-подробнее, у меня покрыты тестами этот и другой случаи. Буду признателен за конкретный пример, на котором код работает некорректно. Про деградацию по производительности - такая же просьба.
Типичный случай такого применения - вторичный индекс: основная структура лежит в массиве или map, a дерево/BWA хранит индекс в этом массиве или указатель и упорядочено по другому ключу.
Это верно, если посмотрите на интерфейс библиотеки - у меня реализованы все типичные для деревьев методы, включая итераторы, Max/Min, etc. Так же реализованы некоторые методы, которые в деревьях не реализуемы, неупорядоченный обход с
, например, по скорости близкий к обходу массива.
Ваше решение хоршее. Ключевые отличия на вскидку:
1. У деревьев будет оверхед на хранение индексов соседних узлов. Если в качестве value - int64, как в бенчмарке, будет чувствительно.
2. Вставка будет требовать не только реаллокаций, но и постоянной перебалансировки дерева с прыжками по памяти. BWA делает это последовательным слиянием.
3. У BWA в любой момент можно вызвать метод Compact и удвалить все неиспользуемые сегменты, что обеспечит минимальный расход памяти.
В целом было бы интересно сравнить на практике, хотя бы вставку. Если реализуете - обязательно присылайте, вставим сюда.