Black-White Array: новая структура данных с O(log N) аллокаций / forpes.ru

Главная
Black-White Array: новая структура данных с O(log N) аллокаций

Black-White Array: новая структура данных с O(log N) аллокаций +56

14.01.2026 06:27

dronnix 41 14000 Источник

Кратко

Black-White Array (BWA) — это упорядоченная структура данных с амортизированным временем операций вставки/поиска/удаления $O(\log N)$ и $O(\log N)$ используемых участков памяти. Пример реализации и оригинальная научная публикация.

Преимущества

Амортизированное время вставки/удаления/поиска $O(\log N)$ - сравнимое с BTree от Google;
Количество аллокаций памяти при операциях вставки так же $O(\log N)$ - меньше давления на сборщик мусора, ниже фрагментация памяти;
Массивы под капотом: данные лежат рядом, что улучшает кэшируемость процессором и скорость обхода/доступа к данным;
Позволяет хранить элементы с одинаковыми ключами - не нужно использовать дополнительные структуры для группировки таких элементов;
Низкий оверхед на хранение служебной информации - экономия памяти по сравнению с другими структурами данных;
Удобен для вставки батчами;
Простая сериализация и десериализация;

Компромиссы

Время вставки варьируется от - каждая вторая вставка, до - один раз на N операций, но амортизированное время $O(\log N)$ . Для near-real-time систем это может быть критично. Эффект может быть нивелирован вставкой батчами, или асинхронной вставкой в фоне.
При редких паттернах операций массового удаления, возможна деградация производительности поиска до . Эффект может быть предотвращен вызовом метода Compact().

Подробности

Основная идея

Как известно, любое число N можно представить в двоичной системе счисления, или, говоря языком математики, как сумму степеней двойки.Например, число $5_{10}$ можно представить как , что в двоичной системе будет . Соответственно, для хранения N элементов можно использовать набор массивов, где размер каждого массива будет степенью двойки (1, 2, 4). Таким образом, для хранения 5 элементов нам понадобятся массивы размером 4 и 1. Обобщая, для хранения N элементов нам понадобятся $\log_2 N$ массивов, размер каждого из которых будет степенью двойки.

Чтобы поддерживать упорядоченность элементов, каждый массив должен быть отсортирован внутри. Сортировка между массивами не требуется: элементы из
массива размером 4 могут быть меньше, больше или равны элементу из массива размером 1.

Поиск

Для поиска элемента с ключом K, мы просто последовательно перебираем массивы, выполняя бинарный поиск в каждом из них:

for arrNum := 0; arrNum < len(arrays); arrNum++ {
  index := binarySearch(arrays[arrNum], K) 
    if index != -1 {
        return arrays[arrNum][index]
    }
}

Оптимизация: не нужно искать во всех массивах, только в тех, где сейчас хранятся элементы. Для 5 элементов это будут массивы размером 4 и 1, массив размера 2 можно пропустить. Количество хранимых элементов N в двоичной системе является битовой маской для выбора массивов, в которых нужно искать элементы:

for arrNum := 0; arrNum < len(arrays); arrNum++ {
    if N & (1 << arrNum) == 0 { // Skip unused arrays
        continue
    }
    index := binarySearch(arrays[arrNum], K)
    if index != -1 {
        return arrays[arrNum][index]
    }
}

Оценка трудоёмкости: в худшем случае нам нужно будет искать во всех $\log_2 N$ массивах:

$T_{search} = O(\log_2(N/2)) + O(\log_2(N/4)) + \cdots + O(\log_2 1) = O((\log_2 N)^2)$

В среднем случае, количество операций поиска зависит от вероятности нахождения элемента в каждом массиве. При равномерном распределении вероятностей искомый элемент будет найден в самом большом массиве с вероятностью 1/2, во втором по размеру с вероятностью 1/4 и т.д. Таким образом, среднее количество операций поиска будет: $O(\log_2 N)$ . За подробным доказательством оценки трудоёмкости поиска можно обратиться к оригинальной научной публикации, §4.1, Theorem 5. Мы же посмотрим на бенчмарки. За эталон был взят BTree от Google, с degree равным 32.

В бенчмарке производится вставка нескольких миллионов значений int64 с последующим поиском каждого из них. Как видно из графика, BWA показывает производительность, сравнимую с BTree. При этом BWA аллоцирует значительно меньше участков памяти и потребляет меньше памяти в целом. Но об этом в следующем разделе.

Вставка

Если при вставке нового элемента массив размера 1 свободен -- мы просто вставляем элемент туда за . Нетрудно заметить, что каждая вторая вставка будет такой - для каждого четного N. Рассмотрим случай, когда массив размера 1 уже занят для N=5. Если массив для вставки элемента занят, он помещается во временный массив. Основные массивы называются "белыми", а временные -- "черными". Отсюда и название структуры данных - Black-White Array. Черный массив объединяется с белым того же размера и помещается в следующий по размеру белый массив (он как раз в два раза больше).
Объединение массивов происходит при помощи слияния (механизм, похожий на merge sort), что обеспечивает сохранение упорядоченности элементов внутри массива, дальше рассмотрим это подробнее.

Пример для N=5, вставляем элемент со значением 11:

Вставляем 11 во временный массив размера 1 (черный);
Объединяем черный массив размера 1 с белым массивом размера 1, получаем массив [11,23];
Помещаем полученный массив в белый массив размера 2 (он был пуст);
Помечаем белый массив размера 1 как свободный.

Если белый массив большего размера занят, то запись результата объединения происходит в черный массив соответствующего размера, и процесс повторяется рекурсивно, пока не найдется (или не будет создан) свободный белый массив.

Слияние массивов

Для объединения двух массивов используется классический алгоритм слияния из сортировки слиянием (merge sort). Так как оба массива уже отсортированы, мы просто
последовательно сравниваем элементы каждого массива, выбирая меньший из них и помещаем его в результирующий массив:

func MergeArrays(arr1, arr2 []Element) []Element {
    merged := make([]Element, len(arr1)+len(arr2))
    src1, src2, dst := 0, 0, 0
    for src1 < len(arr1) && src2 < len(arr2) {
        if arr1[src1].Key <= arr2[src2].Key {
            merged[dst] = arr1[src1]
            src1++
        } else {
            merged[dst] = arr2[src2]
            src2++
        }
        dst++
    }
    // Copy remaining elements: one of sources will be empty  
    copy(merged[dst:], arr1[src1:])
    copy(merged[dst:], arr2[src2:])
    return merged
}

Особый случай вставки

Рассмотрим наиболее интересный случай, когда все массивы заняты, при N=7, вставляем элемент со значением 13:

Так как белый массив размером 1 занят, вставляем 13 во временный массив размера 1 (черный);
Объединяем черный массив размера 1 с белым массивом размера 1, получаем массив [13, 16] (черный, так как белый массив размера 2 занят);
Объединяем черный массив размера 2 [13, 16] с белым массивом размера 2 [11, 23], получаем массив [11, 13, 16, 23] (черный, так как белый массив размера 4 занят);
Так как белый массив размера 8 отсутствует, создаем его.
Объединяем черный массив размера 4 с белым массивом размера 4, записывая результат в только что созданный, белый массив размера 8.

Таким образом эта вставка элемента потребовала перемещения всех 7 элементов, что занимает времени. Однако, такая ситуация возникает только один раз на N вставок.
Нетрудно видеть, что последующая вставки займут , затем , затем снова и т.д. Тогда амортизированное время вставки будет:

$T_{insert} = \frac{O(1) + O(2) + O(1) + O(4) + \cdots + O(N)}{N} = O(\log_2 N)$

За подробным доказательством оценки трудоёмкости вставки можно обратиться к оригинальной научной публикации, §4.1, Corollary 3.
Мы же снова посмотрим на бенчмарки:

Видим, что BWA показывает производительность вставки, даже лучше, чем BTree, несмотря на худший случай для вставки одного элемента. Насколько же плох этот худший случай на практике? На современных процессорах(AMD64 и ARM64) наихудший случай вставки в BWA с ~1M элементов int64 занимает около 10 миллисекунд.
Это может быть проблемой для near-real-time систем с жесткими требованиями по времени отклика. В остальных случаях, амортизированное время вставки $O(\log N)$ показывает себя отлично. Для уменьшения влияния худшего случая вставки, можно использовать вставку батчами, или асинхронную вставку в фоне.

Аллокации памяти - почему это важно?

Меньше аллокаций - меньше давления на сборщик мусора, что особенно важно для языков с GC (Go, Java, Python и т.д.). Сборщик мусора как правило запускается каждые несколько миллисекунд и обходит все "живые" объекты в памяти, затрачивая на это процессорное время, даже если приложение в это время ничего не вычисляет. Если объектов миллионы, то потребление CPU может быть заметным.
Рассмотрим график меньшего масштаба, так как на предыдущем не видны изменения для BWA:

Количество аллокаций памяти при вставке элемента в BWA порядка $O(\log N)$ .

Обратите внимание, что при вставке BWA не производит поиск и позволяет вставлять элементы с одинаковыми ключами без дополнительных приёмов. Среди одинаковых ключей сохраняется порядок вставки (стабильность): более новые элементы будут в более коротких массивах.

Удаление

Для удаления элемента его нужно сначала найти (см. поиск). Далее профессор Моу (автор оригинальной публикации) предлагает заменить значение элемента на специальное void.
В некоторых языках программирования такой подход вполне работает: можно использовать None в Python, undefined в JavaScript и т.д. В Go, C, C++ такой подход не работает, так как эти языки не поддерживают nullable значения для примитивных типов (int, float, etc). Использовать указатели и их значения nil/null не эффективно: дополнительный уровень косвенности и нагрузка на сборщик мусора.
В своей реализации BWA для Go я использую массив битов, где каждый бит соответствует элементу в массивах BWA. Таким образом, при удалении элемента нужно просто установить соответствующий бит в 1 (удален).

Но что, если удаленных элементов становится слишком много? Когда удалённых элементов в каком-либо массиве накапливается половина от общего количества, нужно выполнить процедуру demote (понижение) для него. Суть процедуры: перемещаем все n/2 "живых" элементов из массива размера n в предыдуший по размеру массив (n/2). Если предыдущий массив занят, то выполняем слияние с ним, как при вставке и помещаем результат в текущий массив размером n.

func DemoteArray(arr []Element, deleted []bool) []Element {
	result := make([]Element, 0, len(arr)/2)
	for i := range arr {
        if !deleted[i] {
            result = append(result, arr[i])
        }
    }
	return result
}

Рассмотрим сначала пример удаления и понижения сегмента без объединения с предыдущим (он свободен):

Удаляем элемент со значением 17, из сегмента размера 4, помечая соответствующий бит в массиве удаленных элементов (не приведен на иллюстрации для упрощения);
Удаляем элемент со значением 42, из сегмента размера 4. Теперь в сегменте размера 4 удалено 2 из 4 элементов, что составляет половину. Выполняем понижение:
Перемещаем "живые" элементы [8, 33] в предыдущий сегмент размера 2;
Помечаем сегмент размера 4 как свободный.

Теперь рассмотрим пример удаления и понижения сегмента с объединением с предыдущим (он занят):

Здесь шаги 1 и 2 аналогичны предыдущему примеру. Далее:
3. Перемещаем "живые" элементы [8, 33] в черный сегмент размера 2 (так как белый занят);
4. Объединяем черный сегмент размера 2 с белым сегментом размера 2 [19, 23], получаем [8, 19, 23, 33] и помещаем его в белый сегмент размера 4, который был освобожден процедурой demote.

Таким образом структура данных поддерживает заполнённость сегментов на уровне не менее 50%. Что касается трудоёмкости операции удаления, то интуитивно понятно,
что амортизированное время удаления будет $O(\log N)$ . Понижение самого большого сегмента (размера N/2) происходит не чаще одного раза на N/4 удалений. Понижение меньших сегментов, требует меньше времени и в среднем менее вероятно. Подробное доказательство смотрите в оригинальной научной публикации, §4.1, Theorem 7.

Необходимо отметить, что использование массива битов для пометки удаленных элементов требует модификации процедуры поиска: при поиске нужно пропускать элементы, помеченные как удалённые. Подробнее можно посмотреть в исходном коде реализации BWA.

Об авторе оригинальной публикации

Идея BWA принадлежит профессору Йельского университета Джорджу Моу (Z. George Mou), я отправил ему реализацию BWA на Go, и он её одобрил. Сейчас профессор Моу работает над публикацией алгоритма пространственного поиска и его открытой реализации на C++.

Заключение

Black-White Array представляет собой интересную структуру данных, которая сочетает в себе преимущества массивов (последовательное хранение данных, низкий оверхед) и сбалансированных деревьев (логарифмическое время операций).
Однако нужно учитывать компромиссы, такие как вариативное время вставки и возможная деградация производительности поиска при определённых паттернах операций удаления.
Типичная область применения BWA - индексы в памяти, особенно с повторяющимися ключами, где важна скорость вставки и поиска, а также низкое потребление памяти и давление на сборщик мусора.

В статье я намеренно опустил некоторые детали реализации и оптимизации, чтобы сосредоточиться на основных концепциях. Детали и оптимизации можно найти в моей реализации.
Ваши звёзды ★ на GitHub будут для меня лучшей благодарностью! Так же смело присылайте пулл-реквесты с оптимизациями и улучшениями. С вопросами - добро пожаловать в комменты.

Комментарии (41)

hydra_13
14.01.2026 07:52
#29381604
Очень классная статья! Благодарю!

wataru
14.01.2026 07:52
#29382960
Если основное достоинство этой структуры в малом количестве аллокаций и компактности, то чем оно лучше любого дерева поиска, реализованного поверх массива - где вместо указателей используются индексы в массиве, и все элементы лежат в одном массиве? Удаленные элементы можно добавить в список пустых используя, допустим, левые "указатели".

Естественно, массив, как любой динамический массив в любом языке, при переполнении перевыделяется сразу в 2 раза больше чем надо, поэтому выделений будет O(log n) и каждый элемент будет перемещаться O(1) раз в среднем.

Тут тоже используется не более чем в 2 раза больше памяти, чем надо под элементы. Тут тоже будет log(n) аллокаций при вставке n элементов. Ассимптотика лучше - вместо O(log^2 n) тут O(log n).

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

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

А еще я не совсем уверен в асимптотике вставки/удаления. Казалось бы, если вставлять и удалять элементы поочередно, может быть патологический случай.
1. dronnix Автор
  14.01.2026 07:52
  #29383324
  Ваше решение хоршее. Ключевые отличия на вскидку:
  
  1. У деревьев будет оверхед на хранение индексов соседних узлов. Если в качестве value - int64, как в бенчмарке, будет чувствительно.
  2. Вставка будет требовать не только реаллокаций, но и постоянной перебалансировки дерева с прыжками по памяти. BWA делает это последовательным слиянием.
  3. У BWA в любой момент можно вызвать метод Compact и удвалить все неиспользуемые сегменты, что обеспечит минимальный расход памяти.
  
  В целом было бы интересно сравнить на практике, хотя бы вставку. Если реализуете - обязательно присылайте, вставим сюда.
  1. wataru
    14.01.2026 07:52
    #29383732
    С первым пунктом согласен. Действительно, накладные расходы по памяти тут заметно меньше.
    
    Вставка будет требовать не только реаллокаций, но и постоянной перебалансировки дерева с прыжками по памяти. BWA делает это последовательным слиянием.
    
    Реаллокаций там не больше, чем надо для black-white array: вместо Log n массивов длиной cумароно n, тут log n раз выделяется массив, только старые освобождаются, а последний в 2 раза длиннее.
    
    Перебалансировка дерева - это перекинуть Log n указателей-индексов. Прыжков тут не боольше, чем в бинарном поиске.
    
    У BWA в любой момент можно вызвать метод Compact и удвалить все неиспользуемые сегменты, что обеспечит минимальный расход памяти.
    
    Ну это такое себе, оно за O(n) уменьшает потребление памяти максимум в 2 раза. В дереве тоже можно все пустые места перекинуть в конец и обрезать массив (с переаллокацией и memcopy, конечно).
    
    dronnix Автор
    14.01.2026 07:52
    #29386106
    Перебалансировка дерева - это перекинуть Log n указателей-индексов. Прыжков тут не больше, чем в бинарном поиске.
    
    Верно, но BWA не делает этой перебалансировки при вставке. Только слияния. И эта перебалансировка в BTree от Google уже медленнее чем вставки в BWA. Если ещё добавить периодические перемещения при использовании реаллокации массива - будет еще медленнее. Но если нужен не `Insert`, а `ReplaceOrInsert`, тогда будет как вы написали.
    
    Ну это такое себе, оно за O(n) уменьшает потребление памяти максимум в 2 раза. В дереве тоже можно все пустые места перекинуть в конец и обрезать массив (с переаллокацией и memcopy, конечно).
    
    Виноват, здесь не имел в виду удаление. Приведу пример: приложение читает данные из потока, размер которого заранее не известен. После чтения последнего элемента можно вызвать метод Compact() и удалить неиспользуемые массивы и чёрные сегменты. Например, при 9 элементах в BWA будут массивы длиной 1,2,4,8. После компактификации останутся 1 и 8 (трудоёмкость логарифмическая). В дереве-в-массиве же будет 16 элементов в этом случае.
    Compact довольно удобен, когда нужно периодически обновлять данные - можно минимизировать потребление памяти до полезной + 1 бит(для признака удаления) между обновлениями.
    
    wataru
    14.01.2026 07:52
    #29386224
    Приведу пример: приложение читает данные из потока, размер которого заранее не известен
    
    Это весьма частный случай. Дерево в массиве тут тоже одним вызовом убирает всю лишнюю память: vector::shrink_to_fit в С++ например. Да, там будет 1 реаллокация и memcopy в отличии от Logn деаллокаций. Возможно чуть медленнее. Потому что в этом случае все вершины итак лежат в массиве подряд. Если бы в дереве были удаления, то могли остаться какие-то пустые места в середине массива, но так и в bwarray это так же. Compact() тоже не убирает их.
    
    В целом я бы посоветовал собрать сравнительную табличку. Эта структура действительно жрет меньше памяти, и имеет более быструю на практике вставку. Но при этом менее быстрый поиск. Особенно в худшем случае. Вполне можно представить сценарий, где большая часть запросов идет к последним добавленным элементам, которые как раз из 4% худших, попавших в самые короткие массивы (потому что количество элементов оказалось таким, что когда их добавляли, маленькие массивы были пусты).
    
    Так же более медленные поиск минимума, максимума (там линейная вообще сложность, по-моему. Ибо, а что если минимальные элементы все удалены? Вам надо по всему массиву пройтись в поиске первого не удаленного. Если вы это отдельно храните, то как их быстро пересчитывать? Плюс, тогда все еще не работает быстро поиск второго элемента с конца).
    
    Так же нельзя также быстро сделать всякие вещи на отрезках. В деревьях можно считать сумму/количество в поддеревьях и делать с этим классные вещи вроде узнать сумму или максимум из значений для всех элементов с ключами из отрезка [l..r] (тут у элементов есть ключ и значение). Вообще непонятно, как это сделать в BWarray. Можно было бы в каждом массиве держать частичные суммы и бинпоиском искать начало-конец, но что делать с удаленным элементами? И максимум из данных так уже не подсчитать вообще
    
    Нельзя делать структуру по неявному ключу. В деревьях можно хранить количество вершин в поддереве и за счет этого быстро вставить элемент в позицию k или удалить элемент с позиции k.
    
    Структура интересная, но надо четко понимать, что в лоб сравнивать с деревьями нельзя, потому что она может сильно меньше.
    
    dronnix Автор
    14.01.2026 07:52
    #29386354
    В целом я бы посоветовал собрать сравнительную табличку.
    
    Это можно, но для каждой структуры данных худшие, а для BWA ещё и довольно экзотические.
    
    Так же более медленные поиск минимума, максимума (там линейная вообще сложность, по-моему. Ибо, а что если минимальные элементы все удалены?
    
    Верно. Так как это случай был критичен для моего случая практического использования - оптимизировал его хранением позиций первого и последнего неудалённого элемента в массиве. Но со вторым элементом с конца всё будет так как вы написали.
    
    Так же нельзя также быстро сделать всякие вещи на отрезках.
    
    Можно, для этого даже отдельный метод есть! Сложность будет - квадрат логарифма. Медленнее чем у деревьев, но всё ещё достаточно быстро для многих случаев.
    
    Структура интересная, но надо четко понимать, что в лоб сравнивать с деревьями нельзя, потому что она может сильно меньше.
    
    Вот тут полностью согласен: структура требует знания её сильных и слабых сторон, B-Tree с правильным degree в этом плане более универсален.
    
    wataru
    14.01.2026 07:52
    #29386606
    Можно, для этого даже отдельный метод есть! Сложность будет - квадрат
    
    Нет, сложность линейная. Вы там все элементы обходите. В деревьях же обходится O(log n) вершин, даже если в отрезок попадает половина всех элементов. Потому что поддеревья агрегируются.
    
    dronnix Автор
    14.01.2026 07:52
    #29386694
    Верно, даже хуже, сложность будет при упорядоченном обходе - нужно каждый раз выбирать сегмент с наименьшим элементом.
    
    wataru
    14.01.2026 07:52
    #29386858
    Было бы быстрее обходить все элементы в интервале, возможно не по порядку. Тогда можно в каждом сегменте обойти все за линию.
    
    dronnix Автор
    14.01.2026 07:52
    #29386926
    Положил в бэклог.
    
    cpud47
    14.01.2026 07:52
    #29387598
    Верно. Так как это случай был критичен для моего случая практического использования - оптимизировал его хранением позиций первого и последнего неудалённого элемента в массиве. Но со вторым элементом с конца всё будет так как вы написали.
    
    Но там же пересчёт за линейное время. При удалении минимального элемента, нужно линейное время, чтобы найти следующий после него.
    
    dronnix Автор
    14.01.2026 07:52
    #29388128
    Вы имеете ввиду случай, когда после минимального элемента идёт серия удалённых? Да, этот минус описан в начале статьи и вот здесь обсуждали возможные оптимизации.
    
    cpud47
    14.01.2026 07:52
    #29388422
    Тогда это нужно явно говорить (типа "сложность поиска в худшем случае O(n), но при ряде условий $O(\log^2 n)$ ). Потому что пока это не очевидно и создаётся ошибочное представление.
    
    Понятное дело, что бывают ситуации, когда удаления редкие события. Но также есть много алгоритмов, которые активно добавляют и удаляют элементы. И для таких алгоритмов нарваться на подобную патологию довольно просто.
    
    dronnix Автор
    14.01.2026 07:52
    #29388802
    Линейный поиск ненулевого бита - это лишь деталь моей реализации. Планирую заменить на многоуровневый с логорифмической сложностью, хотя и жалко пары процентов производительности на вырожденный случай. На оценки из оригинальной публикации это не влияет, там этот механизм вообще не описан.
    
    cpud47
    14.01.2026 07:52
    #29388956
    А стоит ли? Кажется такое усложнение может устранить преимущество этой структуры данных. Всё же это такая, весьма специфичная структура данных. Поэтому эджкейсы в ней норм, если их документировать.
    
    Но вообще, хотелось бы понять, границы её применимости, где она лучше альтернатив работает. Может сделаете статью о конкретных её юзкейсах и сравнению с альтернативами (именно на этих юзкейсах). Тогда, кажется, будет меньше странных вопросов.
    
    cpud47
    14.01.2026 07:52
    #29388832
    Вообще непонятно, как это сделать в BWarray.
    
    Хранить деревья отрезков вместо сегментов. По идее должно быть достаточно быстро.
  1. cpud47
    14.01.2026 07:52
    #29383958
    Если в качестве value - int64, как в бенчмарке, будет чувствительно
    
    Кажется такой бенчмарк не очень репрезентативен. Не до конца понятна целевая ниша этой структуры данных, но обычно всё же у нас есть ещё какое-то (сравнительно большое) значение. И на фоне значения уже не так критично.
    
    Также стоит понимать, что использовать деревья просто как ассоциативные контейнеры чаще всего затея не самая удачная. Банальный хешмап на порядок быстрее деревьев или вот этих вот bwa. Деревья обычно берут чтобы на них строить всякие интересные статистики и прочее. Поэтому опять же вес узла там не так значителен.
    
    dronnix Автор
    14.01.2026 07:52
    #29385878
    Кажется такой бенчмарк не очень репрезентативен.Не до конца понятна целевая ниша этой структуры данных, но обычно всё же у нас есть ещё какое-то (сравнительно большое) значение.
    
    Типичный случай такого применения - вторичный индекс: основная структура лежит в массиве или map, a дерево/BWA хранит индекс в этом массиве или указатель и упорядочено по другому ключу.
    
    Также стоит понимать, что использовать деревья просто как ассоциативные контейнеры чаще всего затея не самая удачная.
    
    Это верно, если посмотрите на интерфейс библиотеки - у меня реализованы все типичные для деревьев методы, включая итераторы, Max/Min, etc. Так же реализованы некоторые методы, которые в деревьях не реализуемы, неупорядоченный обход с , например, по скорости близкий к обходу массива.
    
    cpud47
    14.01.2026 07:52
    #29387618
    у меня реализованы все типичные для деревьев методы
    
    Не, я говорил про всякие деревья отрезков, или более хитрые структуры. Вам wataru выше об этом тоже написал.
1. alkneu
  14.01.2026 07:52
  #29384860
  >Если основное достоинство этой структуры в малом количестве аллокаций и компактности, то чем оно лучше любого дерева поиска, реализованного поверх массива
  
  Прямо c языка сняли, причём под капотом может быть чуть ли не любой flavor двоичного- red-black, treap, splay, etc.
  
  В качестве бонуса - можно поддерживать оптимальное (вплоть до констатного множителя) использование памяти даже если элементы удаляются - скажем, уменьшать выделенный буфер памяти в 2 раза, если использовано менее 1/3 элементов.
1. jordiutrera
  14.01.2026 07:52
  #29392802
  Чем оно лучше любого дерева поиска, реализованного поверх массива - где вместо указателей используются индексы в массиве, и все элементы лежат в одном массиве
  
  Для меня, одна из основных прелестей этой структуры данных её проста в реализации и анализе сложности. Например, я, до сих пор не знаю как delete() в красно-чёрном дереве работает толком :(

cpud47
14.01.2026 07:52
#29383916
Про время поиска нужно аккуратно формулировать. Из статьи:

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.

Значения поисков редко распределены равномерно. Вообще распределение входных ключей может быть сильно разным. И есть основания полагать, что достаточно часто оно сильно перекошено (всякие правила Парето и прочее). Поэтому на практике результатами этой теоремы воспользоваться нельзя.

Реальная ассимптотика поиска будет как раз $O(\log^2 n)$ , что весьма неприятно. Даже на каком-то миллионе элементов константа вырастет в 20 раз.

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

И в целом, там амортизация внятно не доказана. Там только какие-то очень простые кейсы для последовательностей одинаковых операций.

P.S. Будьте аккуратнее с обработкой "одинаковых ключей", как Вы заявили. Потому что там очень легко все ассимптотики могут стать. Хотя глядя на код поиска, кажется он некорректен в присутствии одинаковых элементов.
1. dronnix Автор
  14.01.2026 07:52
  #29385994
  Во-первых, спасибо за внимательное прочтение, включая первоисточник. В современном мире это дорогого стоит!
  
  Значения поисков редко распределены равномерно. Вообще распределение входных ключей может быть сильно разным. И есть основания полагать, что достаточно часто оно сильно перекошено (всякие правила Парето и прочее). Поэтому на практике результатами этой теоремы воспользоваться нельзя.
  
  75% элементов расположено в первых двух массивах. ~94% в первых четырёх, что даёт или что хуже чистого логарифма, но всё ещё очень быстро.
  Случай, когда нам постоянно нужны только 6% элементов расположенных в младших массивах - довольно вырожденный.
  
  P.S. Будьте аккуратнее с обработкой "одинаковых ключей", как Вы заявили. Потому что там очень легко все ассимптотики могут стать. Хотя глядя на код поиска, кажется он некорректен в присутствии одинаковых элементов.
  
  Вот тут пожалуйста по-подробнее, у меня покрыты тестами этот и другой случаи. Буду признателен за конкретный пример, на котором код работает некорректно. Про деградацию по производительности - такая же просьба.
  1. wataru
    14.01.2026 07:52
    #29386108
    Можете объяснить, как по вашему работает вот эта вот функция 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) и держать их отсортированными. Но тогда код удаления и добавления надо тоже аккуратно допилить, чтобы инвариант поддерживался.
    
    dronnix Автор
    14.01.2026 07:52
    #29386220
    Вот представьте, что у вас все элементы с одинаковым ключом, и массив deleted: [true, false, true, true, true].
    
    Во первых, этот пример не корректен - удалённых элементов не может быть быть более половины, но в целом кейс верный. Я его сразу описал в начале статьи, в недостатках:
    
    При редких паттернах операций массового удаления, возможна деградация производительности поиска до
    
    Это случай поддаётся оптимизации - нужно эффективнее искать неудалённый элемент в битовой маске. Но он настолько вырожденный, что я не стал усложнять реализацию ради него.
    
    Тесты у вас слабые. Надо добавить побольше одинаковых элементов и кучу разных битовых масок deleted.
    
    Чтобы не перебирать разные битовые маски, существуют классы эквивалентности. Кажется я покрыл все, но если упустил - пожалуйста напишите какой конкрктно, или сделайте PR.
    
    wataru
    14.01.2026 07:52
    #29386296
    Чтобы не перебирать разные битовые маски, существуют классы эквивалентности.
    
    У вас там ровно 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, то туда можно массово добавлять и удалять. В деревьях такого нет, там можно хоть все добавить, все удалить много раз и ничего не деградирует патологически.
    
    dronnix Автор
    14.01.2026 07:52
    #29386486
    У вас там похоже делается предположение, что раз в отрезке меньше половины удаленных и вы встретили удаленный, то слева точно что-то должно быть. Но ограничение-то на весь целый отрезок. Маленький его кусочек, рассматриваемый в бинпоиске, может нарушать это ограничение.
    
    Спасибо за подробности! Верно, всегда идём на лево, потому что всегда удаляем самый правый элемент среди равных, что и обеспечивает `findRightmostNotDeleted` (используется и при поиске и при удалении). Надеюсь, снял вопрос по корректности?
    
    Это O(N) даже с битовой магией. Ибо повторяющихся элементов может быть много
    
    С учётом вышесказанного - нужно найти первый ненулевой бит в серии. Для этого есть много разных подходов, но прийдётся городить структуру данных внутри структуры данных. В простейшем случае можно сначала проверять не биты, а машинные слова - по 64 бита сразу. Последовательно. В теории сложность всё ещё линейная, на практике очень быстро работает.
    
    wataru
    14.01.2026 07:52
    #29386668
    Верно, всегда идём на лево, потому что всегда удаляем самый правый элемент среди равных, что и обеспечивает
    
    Вот с этого и стоило начать! Это как раз то самое упорядочивание пар (element, deleted) о котором я говорил в начале. Но почему у вас тогда в тестах есть [true, false, true] для одного и того же 23?
    
    Также этот инвариант нарушается при слиянии отрезков: https://github.com/dronnix/bwarr/blob/5a25121cb0da85fe401dc81b5b046f376cae8638/segment.go#L35
    
    Так что вам надо этот инвариант поддерживать везде, убрать лишние тесты и еще и комментарии о нем в код вставить, тогда вопросов у читающих не будет.
    
    dronnix Автор
    14.01.2026 07:52
    #29386908
    Также этот инвариант нарушается при слиянии отрезков: https://github.com/dronnix/bwarr/blob/5a25121cb0da85fe401dc81b5b046f376cae8638/segment.go#L35
    
    А вот это - "nice catch", как говорится, посмотрю подробнее и поправлю чуть позже. Большое спасибо.
    
    wataru
    14.01.2026 07:52
    #29386300
    Ну и про деградацию. У вас там не деградация до O(N)/4, у вас там некорректная работа пока что.
    
    dronnix Автор
    14.01.2026 07:52
    #29386492
    Про корректность ответил выше.
  1. cpud47
    14.01.2026 07:52
    #29387686
    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-и), есть некоторая доля ключей $\alpha \approx 3-20%$ на которые приходятся почти все запросы - так называемые "горячие данные". И вот если Вам не повезёт, и эти горячие данные попадут в малые сегменты, то поиски будут систематически медленными. Поэтому и говорю, что на практике та теорема малоприменима.
  1. cpud47
    14.01.2026 07:52
    #29387758
    Вот тут пожалуйста по-подробнее, у меня покрыты тестами этот и другой случаи. Буду признателен за конкретный пример, на котором код работает некорректно. Про деградацию по производительности - такая же просьба.
    
    Перечитал тот код, конкретно там вроде ок. Но комментарии помогли бы.
    
    С одинаковыми ключами сложность например в том, что в них могут быть разные элементы (значения). В таком случае, нужно уметь указывать, а какой именно из них хочется удалить.
    
    Также, есть обратная сторона медали: если мне нужны только уникальные элементы(а этом, согласитесь, более частый кейс), то приходится делать Search||Insert - а это бъёт по перфу.
    
    Ассимптотическую деградацию я, наверное, сейчас не приведу. Вроде о простых проблемах Вам уже wataru рассказал (и возможно Вы их уже и так обрабатывали).
    
    dronnix Автор
    14.01.2026 07:52
    #29388368
    Также, есть обратная сторона медали: если мне нужны только уникальные элементы(а этом, согласитесь, более частый кейс), то приходится делать Search||Insert - а это бъёт по перфу.
    
    Не знаю на сколько частый, но да, бъёт. Мне нужны были именно вспомогательные индексы по неуникальному полю - timestamp, [S2CellID] (https://s2geometry.io/devguide/s2cell_hierarchy.html), etc, поэтому сразу делал упорядоченное мультимножество.
    
    Ещё раз спасибо вам за ваши коментарии.
    
    cpud47
    14.01.2026 07:52
    #29388456
    На самом деле, я не очень понял, почему Вы подаёте ниуникальность ключей, как какую-то особенность структуры. Ведь деревъя с неуникальными ключами точно также несложно делаются.
    
    Если постараться, можно даже сделать хешмап с неуникальными ключами. С ним уже сложнее и нужно аккуратно быть. Но если не нужен порядок, то хешмап должен быть гораздо быстрее.

diderevyagin
14.01.2026 07:52
#29385514
Очень интересный материал, спасибо !

lightln2
14.01.2026 07:52
#29387528
Интересно, оказывается, эта структура имеет название. Я думал, это "народный" трюк, чтобы делать "дешевый аналог" деревьев, если в вашем языке программирования нет их из коробки, и нет возможности использовать дополнительные библиотеки. Я похожий трюк даже один раз использовал для какой-то задачи с литкода, потому что не знал, есть ли в питоне sorted set)
Основное ее преимущество перед деревьями - простота реализации. Если не гнаться за излишней оптимизацией, реализация [на питоне] занимает буквально десяток строчек!
Она, кажется, позволяет делать большую часть того, что могут и обычные деревья, за счет дополнительного log-фактора. Этот лог фактор можно убить с помощью эзотерической техники fractional cascading (но непонятно, нафига, так как это уже сложнее, чем "вращать деревья").
Этот подход, если я правильно понимаю, является частным случаем log-structure merge tree, на котором основаны поисковые движки типа lucene, и многие nosql базы данных (cassandra, rocksdb)
1. lightln2
  14.01.2026 07:52
  #29387748
  вот, если кому интересно, реализация на питоне (поиск и вставки, без удаления), получилось 9 строчек.
  Вставка O(1) амортизированная, поиск O(log^2(n)). На практике, перед вставкой надо тоже делать поиск, чтобы избежать дубликатов, но для этого можно добавить простой хешсет, чтобы вставка осталась O(1).
  1. lightln2
    14.01.2026 07:52
    #29389592
    Хочу поправить себя, я тут неправду написал, конечно, вставка O*log(n)) амортизированная.
    Тут еще кажется, что сортировка массива добавляет еще один лог-фактор, но в Питоне, как и в Яве, сортировка является вариантом TimSort, который работает за линейное время, если сортируемый массив состоит из небольщого количества уже отсортированных кусков (так как внутри он использует merge sort).
    Поэтому полезный трюк на питоне или Яве (но не на C++ или C#) - если надо сделать merge sort, можно просто слить массивы в один массив, и использовать стандартный сорт!
1. jordiutrera
  14.01.2026 07:52
  #29392484
  Идею вы уловили, но дьявол, как обычно, кроется в деталях ...

Black-White Array: новая структура данных с O(log N) аллокаций +56

Кратко

Преимущества

Компромиссы

Подробности

Основная идея

Поиск

Вставка

Слияние массивов

Особый случай вставки

Аллокации памяти - почему это важно?

Удаление

Об авторе оригинальной публикации

Заключение

Комментарии (41)

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор

dronnix Автор