Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 41
Очень классная статья! Благодарю!
Если основное достоинство этой структуры в малом количестве аллокаций и компактности, то чем оно лучше любого дерева поиска, реализованного поверх массива - где вместо указателей используются индексы в массиве, и все элементы лежат в одном массиве? Удаленные элементы можно добавить в список пустых используя, допустим, левые "указатели".
Естественно, массив, как любой динамический массив в любом языке, при переполнении перевыделяется сразу в 2 раза больше чем надо, поэтому выделений будет O(log n) и каждый элемент будет перемещаться O(1) раз в среднем.
Тут тоже используется не более чем в 2 раза больше памяти, чем надо под элементы. Тут тоже будет log(n) аллокаций при вставке n элементов. Ассимптотика лучше - вместо O(log^2 n) тут O(log n).
При этом и в этих массивах и в дереве будут не линейные доступы, что у вас бинпоиск, что прыжки по указателям.
А еще есть хеш-таблицы с линейной адресацией. Там кроме хранения всего одним куском еще и доступ будет линейный почти всегда.
А еще я не совсем уверен в асимптотике вставки/удаления. Казалось бы, если вставлять и удалять элементы поочередно, может быть патологический случай.
Ваше решение хоршее. Ключевые отличия на вскидку:
1. У деревьев будет оверхед на хранение индексов соседних узлов. Если в качестве value - int64, как в бенчмарке, будет чувствительно.
2. Вставка будет требовать не только реаллокаций, но и постоянной перебалансировки дерева с прыжками по памяти. BWA делает это последовательным слиянием.
3. У BWA в любой момент можно вызвать метод Compact и удвалить все неиспользуемые сегменты, что обеспечит минимальный расход памяти.
В целом было бы интересно сравнить на практике, хотя бы вставку. Если реализуете - обязательно присылайте, вставим сюда.
С первым пунктом согласен. Действительно, накладные расходы по памяти тут заметно меньше.
Вставка будет требовать не только реаллокаций, но и постоянной перебалансировки дерева с прыжками по памяти. BWA делает это последовательным слиянием.
Реаллокаций там не больше, чем надо для black-white array: вместо Log n массивов длиной cумароно n, тут log n раз выделяется массив, только старые освобождаются, а последний в 2 раза длиннее.
Перебалансировка дерева - это перекинуть Log n указателей-индексов. Прыжков тут не боольше, чем в бинарном поиске.
У BWA в любой момент можно вызвать метод Compact и удвалить все неиспользуемые сегменты, что обеспечит минимальный расход памяти.
Ну это такое себе, оно за O(n) уменьшает потребление памяти максимум в 2 раза. В дереве тоже можно все пустые места перекинуть в конец и обрезать массив (с переаллокацией и memcopy, конечно).
Перебалансировка дерева - это перекинуть Log n указателей-индексов. Прыжков тут не больше, чем в бинарном поиске.
Верно, но BWA не делает этой перебалансировки при вставке. Только слияния. И эта перебалансировка в BTree от Google уже медленнее чем вставки в BWA. Если ещё добавить периодические перемещения при использовании реаллокации массива - будет еще медленнее. Но если нужен не `Insert`, а `ReplaceOrInsert`, тогда будет как вы написали.
Ну это такое себе, оно за O(n) уменьшает потребление памяти максимум в 2 раза. В дереве тоже можно все пустые места перекинуть в конец и обрезать массив (с переаллокацией и memcopy, конечно).
Виноват, здесь не имел в виду удаление. Приведу пример: приложение читает данные из потока, размер которого заранее не известен. После чтения последнего элемента можно вызвать метод Compact() и удалить неиспользуемые массивы и чёрные сегменты. Например, при 9 элементах в BWA будут массивы длиной 1,2,4,8. После компактификации останутся 1 и 8 (трудоёмкость логарифмическая). В дереве-в-массиве же будет 16 элементов в этом случае. Compact довольно удобен, когда нужно периодически обновлять данные - можно минимизировать потребление памяти до полезной + 1 бит(для признака удаления) между обновлениями.
Приведу пример: приложение читает данные из потока, размер которого заранее не известен
Это весьма частный случай. Дерево в массиве тут тоже одним вызовом убирает всю лишнюю память: vector::shrink_to_fit в С++ например. Да, там будет 1 реаллокация и memcopy в отличии от Logn деаллокаций. Возможно чуть медленнее. Потому что в этом случае все вершины итак лежат в массиве подряд. Если бы в дереве были удаления, то могли остаться какие-то пустые места в середине массива, но так и в bwarray это так же. Compact() тоже не убирает их.
В целом я бы посоветовал собрать сравнительную табличку. Эта структура действительно жрет меньше памяти, и имеет более быструю на практике вставку. Но при этом менее быстрый поиск. Особенно в худшем случае. Вполне можно представить сценарий, где большая часть запросов идет к последним добавленным элементам, которые как раз из 4% худших, попавших в самые короткие массивы (потому что количество элементов оказалось таким, что когда их добавляли, маленькие массивы были пусты).
Так же более медленные поиск минимума, максимума (там линейная вообще сложность, по-моему. Ибо, а что если минимальные элементы все удалены? Вам надо по всему массиву пройтись в поиске первого не удаленного. Если вы это отдельно храните, то как их быстро пересчитывать? Плюс, тогда все еще не работает быстро поиск второго элемента с конца).
Так же нельзя также быстро сделать всякие вещи на отрезках. В деревьях можно считать сумму/количество в поддеревьях и делать с этим классные вещи вроде узнать сумму или максимум из значений для всех элементов с ключами из отрезка [l..r] (тут у элементов есть ключ и значение). Вообще непонятно, как это сделать в BWarray. Можно было бы в каждом массиве держать частичные суммы и бинпоиском искать начало-конец, но что делать с удаленным элементами? И максимум из данных так уже не подсчитать вообще
Нельзя делать структуру по неявному ключу. В деревьях можно хранить количество вершин в поддереве и за счет этого быстро вставить элемент в позицию k или удалить элемент с позиции k.
Структура интересная, но надо четко понимать, что в лоб сравнивать с деревьями нельзя, потому что она может сильно меньше.
В целом я бы посоветовал собрать сравнительную табличку.
Это можно, но для каждой структуры данных худшие, а для BWA ещё и довольно экзотические.
Так же более медленные поиск минимума, максимума (там линейная вообще сложность, по-моему. Ибо, а что если минимальные элементы все удалены?
Верно. Так как это случай был критичен для моего случая практического использования - оптимизировал его хранением позиций первого и последнего неудалённого элемента в массиве. Но со вторым элементом с конца всё будет так как вы написали.
Так же нельзя также быстро сделать всякие вещи на отрезках.
Можно, для этого даже отдельный метод есть! Сложность будет - квадрат логарифма. Медленнее чем у деревьев, но всё ещё достаточно быстро для многих случаев.
Структура интересная, но надо четко понимать, что в лоб сравнивать с деревьями нельзя, потому что она может сильно меньше.
Вот тут полностью согласен: структура требует знания её сильных и слабых сторон, B-Tree с правильным degree в этом плане более универсален.
Можно, для этого даже отдельный метод есть! Сложность будет - квадрат
Нет, сложность линейная. Вы там все элементы обходите. В деревьях же обходится O(log n) вершин, даже если в отрезок попадает половина всех элементов. Потому что поддеревья агрегируются.
при упорядоченном обходе - нужно каждый раз выбирать сегмент с наименьшим элементом. 
Верно. Так как это случай был критичен для моего случая практического использования - оптимизировал его хранением позиций первого и последнего неудалённого элемента в массиве. Но со вторым элементом с конца всё будет так как вы написали.
Но там же пересчёт за линейное время. При удалении минимального элемента, нужно линейное время, чтобы найти следующий после него.
Вы имеете ввиду случай, когда после минимального элемента идёт серия удалённых? Да, этот минус описан в начале статьи и вот здесь обсуждали возможные оптимизации.
Тогда это нужно явно говорить (типа "сложность поиска в худшем случае O(n), но при ряде условий
). Потому что пока это не очевидно и создаётся ошибочное представление.
Понятное дело, что бывают ситуации, когда удаления редкие события. Но также есть много алгоритмов, которые активно добавляют и удаляют элементы. И для таких алгоритмов нарваться на подобную патологию довольно просто.
Линейный поиск ненулевого бита - это лишь деталь моей реализации. Планирую заменить на многоуровневый с логорифмической сложностью, хотя и жалко пары процентов производительности на вырожденный случай. На оценки из оригинальной публикации это не влияет, там этот механизм вообще не описан.
А стоит ли? Кажется такое усложнение может устранить преимущество этой структуры данных. Всё же это такая, весьма специфичная структура данных. Поэтому эджкейсы в ней норм, если их документировать.
Но вообще, хотелось бы понять, границы её применимости, где она лучше альтернатив работает. Может сделаете статью о конкретных её юзкейсах и сравнению с альтернативами (именно на этих юзкейсах). Тогда, кажется, будет меньше странных вопросов.
Вообще непонятно, как это сделать в BWarray.
Хранить деревья отрезков вместо сегментов. По идее должно быть достаточно быстро.
Если в качестве value - int64, как в бенчмарке, будет чувствительно
Кажется такой бенчмарк не очень репрезентативен. Не до конца понятна целевая ниша этой структуры данных, но обычно всё же у нас есть ещё какое-то (сравнительно большое) значение. И на фоне значения уже не так критично.
Также стоит понимать, что использовать деревья просто как ассоциативные контейнеры чаще всего затея не самая удачная. Банальный хешмап на порядок быстрее деревьев или вот этих вот bwa. Деревья обычно берут чтобы на них строить всякие интересные статистики и прочее. Поэтому опять же вес узла там не так значителен.
Кажется такой бенчмарк не очень репрезентативен.Не до конца понятна целевая ниша этой структуры данных, но обычно всё же у нас есть ещё какое-то (сравнительно большое) значение.
Типичный случай такого применения - вторичный индекс: основная структура лежит в массиве или map, a дерево/BWA хранит индекс в этом массиве или указатель и упорядочено по другому ключу.
Также стоит понимать, что использовать деревья просто как ассоциативные контейнеры чаще всего затея не самая удачная.
Это верно, если посмотрите на интерфейс библиотеки - у меня реализованы все типичные для деревьев методы, включая итераторы, Max/Min, etc. Так же реализованы некоторые методы, которые в деревьях не реализуемы, неупорядоченный обход с 
, например, по скорости близкий к обходу массива.
>Если основное достоинство этой структуры в малом количестве аллокаций и компактности, то чем оно лучше любого дерева поиска, реализованного поверх массива
Прямо c языка сняли, причём под капотом может быть чуть ли не любой flavor двоичного- red-black, treap, splay, etc.
В качестве бонуса - можно поддерживать оптимальное (вплоть до констатного множителя) использование памяти даже если элементы удаляются - скажем, уменьшать выделенный буфер памяти в 2 раза, если использовано менее 1/3 элементов.
Чем оно лучше любого дерева поиска, реализованного поверх массива - где вместо указателей используются индексы в массиве, и все элементы лежат в одном массиве
Для меня, одна из основных прелестей этой структуры данных её проста в реализации и анализе сложности. Например, я, до сих пор не знаю как delete() в красно-чёрном дереве работает толком :(
Про время поиска нужно аккуратно формулировать. Из статьи:
Theorem 5 (Search Time (Hit)). For a BWA with up to n = 2^m values, the amortized time of a
hit search is O(log n) , provided that the values are uniformly distributed.
Значения поисков редко распределены равномерно. Вообще распределение входных ключей может быть сильно разным. И есть основания полагать, что достаточно часто оно сильно перекошено (всякие правила Парето и прочее). Поэтому на практике результатами этой теоремы воспользоваться нельзя.
Реальная ассимптотика поиска будет как раз, что весьма неприятно. Даже на каком-то миллионе элементов константа вырастет в 20 раз.
Ну и отдельный вопрос к формулировке. Не очень понятно, почему автор здесь говорит про аммортизированное время, если доказал он только среднее время (матожидание). Это, как никак, сильно разные понятия.
И в целом, там амортизация внятно не доказана. Там только какие-то очень простые кейсы для последовательностей одинаковых операций.
P.S. Будьте аккуратнее с обработкой "одинаковых ключей", как Вы заявили. Потому что там очень легко все ассимптотики могут стать
. Хотя глядя на код поиска, кажется он некорректен в присутствии одинаковых элементов.
Во-первых, спасибо за внимательное прочтение, включая первоисточник. В современном мире это дорогого стоит!
Значения поисков редко распределены равномерно. Вообще распределение входных ключей может быть сильно разным. И есть основания полагать, что достаточно часто оно сильно перекошено (всякие правила Парето и прочее). Поэтому на практике результатами этой теоремы воспользоваться нельзя.
75% элементов расположено в первых двух массивах. ~94% в первых четырёх, что даёт 
или 
что хуже чистого логарифма, но всё ещё очень быстро.
Случай, когда нам постоянно нужны только 6% элементов расположенных в младших массивах - довольно вырожденный.
P.S. Будьте аккуратнее с обработкой "одинаковых ключей", как Вы заявили. Потому что там очень легко все ассимптотики могут стать
Вот тут пожалуйста по-подробнее, у меня покрыты тестами этот и другой случаи. Буду признателен за конкретный пример, на котором код работает некорректно. Про деградацию по производительности - такая же просьба.
Можете объяснить, как по вашему работает вот эта вот функция findRightmostNotDeleted: https://github.com/dronnix/bwarr/blob/5a25121cb0da85fe401dc81b5b046f376cae8638/segment.go#L69?
Какие у вас там инварианты на deleted? Судя по тестам из комментария выше, там может быть вообще что угодно - удаленные и в конце, и в начале? Вот представьте, что у вас все элементы с одинаковым ключом, и массив deleted: [true, false, true, true, true]. Вот смотрите вы в бинпоиске в середину, видите там true, и решаете куда идти - влево или вправо. Но массив мог бы быть и [true, true, true, false, true]. Там правильное решение противоположное. Но элемент в середине точно такой же и вы никак не можете сделать из него два разных вывода о том, в какую половину идти.
Тесты у вас слабые. Надо добавить побольше одинаковых элементов и кучу разных битовых масок deleted.
Это еще можно исправить, если вы будете в каждом отрезке одинаковых элементов удаленные держать, например, только в конеце. Грубо говоря, сравнивать пары (element, deleted) и держать их отсортированными. Но тогда код удаления и добавления надо тоже аккуратно допилить, чтобы инвариант поддерживался.
Вот представьте, что у вас все элементы с одинаковым ключом, и массив deleted: [true, false, true, true, true].
Во первых, этот пример не корректен - удалённых элементов не может быть быть более половины, но в целом кейс верный. Я его сразу описал в начале статьи, в недостатках:
При редких паттернах операций массового удаления, возможна деградация производительности поиска до
Это случай поддаётся оптимизации - нужно эффективнее искать неудалённый элемент в битовой маске. Но он настолько вырожденный, что я не стал усложнять реализацию ради него.
Тесты у вас слабые. Надо добавить побольше одинаковых элементов и кучу разных битовых масок deleted.
Чтобы не перебирать разные битовые маски, существуют классы эквивалентности. Кажется я покрыл все, но если упустил - пожалуйста напишите какой конкрктно, или сделайте PR.
Чтобы не перебирать разные битовые маски, существуют классы эквивалентности.
У вас там ровно 3 повторения одного элемента. Для больших длин больше классов.
Вот вам пример с мелким количеством удаленных элементов:
[false, true, true, true, false, false, false] vs
[true, true, false, true, false, false, false]
Сначала вы найдете удаленный в середине и пойдете налево. Потом посмотрите в отрезке [true/false, true, false/true] на удаленный на позиции 2. И там опять надо или идти влево или вправо, но элемент точно такой же. Если вы возразите, что тут половина удалена, а должно быть строго меньше, то расширьте пример. Допишите [true, false, false, false, false, false, false, false]. Тогда ваш алгоритм сломается на третьем шаге.
У вас там похоже делается предположение, что раз в отрезке меньше половины удаленных и вы встретили удаленный, то слева точно что-то должно быть. Но ограничение-то на весь целый отрезок. Маленький его кусочек, рассматриваемый в бинпоиске, может нарушать это ограничение.
Это случай поддаётся оптимизации - нужно эффективнее искать неудалённый элемент в битовой маске.
Это O(N) даже с битовой магией. Ибо повторяющихся элементов может быть много
Но он настолько вырожденный, что я не стал усложнять реализацию ради него.
У вас не в оптимизации проблема, а в некорректности работы. Если какой-то элемент повторяется много раз при вставках и удалениях, то вы можете его в вашей структуре ошибочно не найти, хоть он там и есть.
При редких паттернах операций массового удаления, возможна деградация производительности поиска до
Т.е. у вашей структуры данных оценка сложности O(N) а не O(log n). Что значит редкий случай массового удаления? На практике если структура поддерживает add и delete, то туда можно массово добавлять и удалять. В деревьях такого нет, там можно хоть все добавить, все удалить много раз и ничего не деградирует патологически.
У вас там похоже делается предположение, что раз в отрезке меньше половины удаленных и вы встретили удаленный, то слева точно что-то должно быть. Но ограничение-то на весь целый отрезок. Маленький его кусочек, рассматриваемый в бинпоиске, может нарушать это ограничение.
Спасибо за подробности! Верно, всегда идём на лево, потому что всегда удаляем самый правый элемент среди равных, что и обеспечивает `findRightmostNotDeleted` (используется и при поиске и при удалении). Надеюсь, снял вопрос по корректности?
Это O(N) даже с битовой магией. Ибо повторяющихся элементов может быть много
С учётом вышесказанного - нужно найти первый ненулевой бит в серии. Для этого есть много разных подходов, но прийдётся городить структуру данных внутри структуры данных. В простейшем случае можно сначала проверять не биты, а машинные слова - по 64 бита сразу. Последовательно. В теории сложность всё ещё линейная, на практике очень быстро работает.
Верно, всегда идём на лево, потому что всегда удаляем самый правый элемент среди равных, что и обеспечивает
Вот с этого и стоило начать! Это как раз то самое упорядочивание пар (element, deleted) о котором я говорил в начале. Но почему у вас тогда в тестах есть [true, false, true] для одного и того же 23?
Также этот инвариант нарушается при слиянии отрезков: https://github.com/dronnix/bwarr/blob/5a25121cb0da85fe401dc81b5b046f376cae8638/segment.go#L35
Так что вам надо этот инвариант поддерживать везде, убрать лишние тесты и еще и комментарии о нем в код вставить, тогда вопросов у читающих не будет.
Также этот инвариант нарушается при слиянии отрезков: https://github.com/dronnix/bwarr/blob/5a25121cb0da85fe401dc81b5b046f376cae8638/segment.go#L35
А вот это - "nice catch", как говорится, посмотрю подробнее и поправлю чуть позже. Большое спасибо.
Ну и про деградацию. У вас там не деградация до O(N)/4, у вас там некорректная работа пока что.
Про корректность ответил выше.
75% элементов расположено в первых двух массивах
Это не сильно важно. Суть в том, что пусть у нас есть последовательность поисковых запросов Search(x1), Search(x2), ..., Search(xm). Каждый из этих запросов найдёт элемент по индексу Index(x1), Index(x2), ..., Index(xm). Вопрос в том, из какого распределения берутся x1, .., xm.
Автор, в этой теореме, предполагает, что x1, ..., xm берутся из такого распределения, что Index(xk) распределены равномерно на U[1, .., n] (где n - количество элементов в массиве). Это вообще говоря, очень нетривиальное условие. Мало того, что из этого условия не очень понятно, как должны быть распределены сами x1, .., xm (оно зависит от распределения вставок!), так ещё распределение запросов редко кто готов предсказать. Но, допустим, для простоты, что нам достаточно того, чтобы x1, ..., xm были распределены равномерно.
На практике, равномерные распределения редко встречаются. Вообще, распределение запросов в реальных задачах - вопрос очень сложный и неоднозначный. Но если пытаться на него ответить, то я бы сказал, что для статических задач поиска (где сначала все insert-ы, а потом все search-и), есть некоторая доля ключей
на которые приходятся почти все запросы - так называемые "горячие данные". И вот если Вам не повезёт, и эти горячие данные попадут в малые сегменты, то поиски будут систематически медленными. Поэтому и говорю, что на практике та теорема малоприменима.
Вот тут пожалуйста по-подробнее, у меня покрыты тестами этот и другой случаи. Буду признателен за конкретный пример, на котором код работает некорректно. Про деградацию по производительности - такая же просьба.
Перечитал тот код, конкретно там вроде ок. Но комментарии помогли бы.
С одинаковыми ключами сложность например в том, что в них могут быть разные элементы (значения). В таком случае, нужно уметь указывать, а какой именно из них хочется удалить.
Также, есть обратная сторона медали: если мне нужны только уникальные элементы(а этом, согласитесь, более частый кейс), то приходится делать Search||Insert - а это бъёт по перфу.
Ассимптотическую деградацию я, наверное, сейчас не приведу. Вроде о простых проблемах Вам уже wataru рассказал (и возможно Вы их уже и так обрабатывали).
Также, есть обратная сторона медали: если мне нужны только уникальные элементы(а этом, согласитесь, более частый кейс), то приходится делать Search||Insert - а это бъёт по перфу.
Не знаю на сколько частый, но да, бъёт. Мне нужны были именно вспомогательные индексы по неуникальному полю - timestamp, [S2CellID] (https://s2geometry.io/devguide/s2cell_hierarchy.html), etc, поэтому сразу делал упорядоченное мультимножество.
Ещё раз спасибо вам за ваши коментарии.
На самом деле, я не очень понял, почему Вы подаёте ниуникальность ключей, как какую-то особенность структуры. Ведь деревъя с неуникальными ключами точно также несложно делаются.
Если постараться, можно даже сделать хешмап с неуникальными ключами. С ним уже сложнее и нужно аккуратно быть. Но если не нужен порядок, то хешмап должен быть гораздо быстрее.
Очень интересный материал, спасибо !
Интересно, оказывается, эта структура имеет название. Я думал, это "народный" трюк, чтобы делать "дешевый аналог" деревьев, если в вашем языке программирования нет их из коробки, и нет возможности использовать дополнительные библиотеки. Я похожий трюк даже один раз использовал для какой-то задачи с литкода, потому что не знал, есть ли в питоне sorted set)
Основное ее преимущество перед деревьями - простота реализации. Если не гнаться за излишней оптимизацией, реализация [на питоне] занимает буквально десяток строчек!
Она, кажется, позволяет делать большую часть того, что могут и обычные деревья, за счет дополнительного log-фактора. Этот лог фактор можно убить с помощью эзотерической техники fractional cascading (но непонятно, нафига, так как это уже сложнее, чем "вращать деревья").
Этот подход, если я правильно понимаю, является частным случаем log-structure merge tree, на котором основаны поисковые движки типа lucene, и многие nosql базы данных (cassandra, rocksdb)
вот, если кому интересно, реализация на питоне (поиск и вставки, без удаления), получилось 9 строчек.
Вставка O(1) амортизированная, поиск O(log^2(n)). На практике, перед вставкой надо тоже делать поиск, чтобы избежать дубликатов, но для этого можно добавить простой хешсет, чтобы вставка осталась O(1).
Хочу поправить себя, я тут неправду написал, конечно, вставка O*log(n)) амортизированная.
Тут еще кажется, что сортировка массива добавляет еще один лог-фактор, но в Питоне, как и в Яве, сортировка является вариантом TimSort, который работает за линейное время, если сортируемый массив состоит из небольщого количества уже отсортированных кусков (так как внутри он использует merge sort).
Поэтому полезный трюк на питоне или Яве (но не на C++ или C#) - если надо сделать merge sort, можно просто слить массивы в один массив, и использовать стандартный сорт!
Идею вы уловили, но дьявол, как обычно, кроется в деталях ...
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Black-White Array: новая структура данных с O(log N) аллокаций