* Под всё имеется в виду относительно быстрое выполнение операций над единичным элементом массива.

Структур данных, которые реализуют список полно. У всех есть свои достоинства и недостатки. Например в мире Java — в зависимости от необходимых операций — можно использовать:

• add(obj), get(obj), set(index, obj): базовый набор почти всех списков, например ArrayList.
• add(index, obj): структуры в виде дерева, например TreeList из apache common-collections.
• remove(index): то же, что и выше.
• contains(obj), indexOf(obj): можно использовать связку ArrayList и HashMap.
• remove(obj): … затрудняюсь ответить. В некоторых случаях можно обойтись LinkedHashSet. Решается тривиально при наличии предыдущих двух пунктов, но какие структуры могут и то и другое быстро?

Когда мне понадобилась структура с быстрыми add(obj), get(index), remove(index) и indexOf(obj), то google не дал ответа. Ни примеров кода, ни описания подобных структур я не нашел. Возможно не там искал, пришлось выдумывать самому. Но если кто-то скинет ссылку в комментариях, то буду весьма признателен.

Возможно, кто-то догадался, что можно взять TreeList, который умеет быстро вставлять/удалять элементы в середине списка и добавить к нему HashMap из объекта в индекс в TreeList для быстрого выполнения indexOf(obj). И это будет простое, изящное, но неверное решение. Ведь при добавлении в середину или удалении из середины нужно будет пересчитать индексы, в среднем, для половины элементов. Это ухудшит производительность до O(n).

Дальше я расскажу о структуре данных, которая может всё из перечисленного выше. Которая выполняет любую операцию над одним элементом за O(log(n)) времени. Ну почти — за логарифм выполняется в том случае, когда все объекты в списке различны. Если в списке есть одинаковые объекты, то возможно проседание производительности вплоть до O(log(n) ^ 2).

Предупрежу сразу, что я не буду здесь расписывать код. Он может быть достаточно сложен для статьи. Но он есть, написан на Java. За основу взят класс TreeList из apache common-collections. Pull request уже есть, но на момент написания статьи ещё не влит.

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

Ссылки будут в конце.

Зачем это нужно

В самом деле, не так-то просто придумать ситуации, когда от списка нужно вот прям вообще всё. Вряд ли это какая-то супер необходимая структура, иначе о ней знали бы все. Однако несколько примеров, где такой список мог быть полезен можно привести.

Я осознаю, что многие из примеров надуманные. Всё или почти всё можно решить другим способом.

Кэширование и сжатие

Моя первоначальная задача, из-за которой я начал исследовать вопрос. Игрался со сжатием специфических данных и понадобился список для кэша объектов.

Идея следующая: при обработке очередного объекта ищем его в списке. Если не нашли — сохраняем объект и добавляем его в начало списка. Если нашли, то берём его индекс в списке и вместо объекта сохраняем только его индекс, после чего перемещаем объект в начало списка. Таким образом, объекты, которые встречаются часто будут получать маленькие индексы, а объекты, которые встретились всего один раз, со временем перемещаются в конец списка и удаляются.

Очередь

Если вместо обычной FIFO очереди для каких-то задач использовать подобную структуру, то можно делать следующие операции:

• Отвечать на вопрос: сколько задач в очереди перед данной задачей.
• Удалять задачи из очереди.

Примерно как в супермаркете. Если вы пришли за шоколадкой, но видите, что очередь двигается медленно, то, может, шоколадка не так уж сильно и нужна? :)

Таблица рекордов

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

• Перемещать игроков выше по списку, если они показали лучший результат, чем раньше.
• Удалять игроков из списка, например, в случае бана за читерство.
• Показывать каждому игроку на каком он месте.
• Постранично показывать таблицу рекордов.
• Показывать разреженную таблицу по местам, например время 1, 2, 3, 5, 10, 20, 50, 100, 1000, 10000 места.

Структура данных

Структура основана на дереве с неявным ключом. Именно на этом подходе основан, например, TreeList в apache common-collections. Для того чтобы двигаться дальше, надо понять как работает эта структура.

Дерево с неявным ключом

Дерево состоит из узлов (Nodes). Каждый узел содержит ссылку на объект, который хранится в узле и 2 ссылки на другие узлы: левый и правый. Самый верхний узел называется корневым. В самом простом случае узел выглядит примерно так:

class Node<T> {
  obj: T
  left: Node<T>
  right: Node<T>
}

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

                             [ element: 25 ]
                           /                                           /                             [ element: 14 ]                       [ element: 45 ]
           /          \                           /                    /            \                         /            [ element: 10 ]    [ element: 22 ]     [ element: 27 ]    [ element: 90 ]
                    /          \                            /
                   /            \                          /
            [ element: 17 ] [ element: 23 ]         [ element: 80 ] 

Но для нашей цели такое дерево не подходит. Нам не надо хранить объекты отсортированными, но надо иметь к ним доступ по индексу, как в массиве.

Как можно поместить массив в дерево? Давайте выберем элемент с индексом i из середины массива. Поместим в корневой узел i-й элемент из массива. Из корневого узла выходят 2 поддерева. В левое поддерево помещаем половину массива с индексом < i, а в правую с индексом > i. Как это сделать? Точно так же: выбираем в подмассиве какой-то элемент из середины, помещаем этот элемент в узел, получаем еще 2 подмассива поменьше. И так пока не поместим все элементы массива в узлы дерева.

Например, так может выглядеть массив с элементами [“q”, “w”, “e”, “r”, “t”, “y”, “u”]:

                            [el: r,  size: 7]
                           /        :                                  /         :                  [el: w, size: 3]           :           [el: y, size: 3]
           /     :    \             :             /    :               /      :     \            :            /     :      [el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]
        :        :         :        :         :        :         :
        :        :         :        :         :        :         :
       [q]      [w]       [e]      [r]       [t]      [y]       [u]

Index:  0        1         2        3         4        5         6

Средний элемент в массиве “r”, его помещаем в корневой узел. Два подмассива [“q”, “w”, “e”] и [“t”, “y”, “u”] помещаются в левое и правое поддерево. Для этого из подмассивов выбираются центральные элементы, в нашем случае это “w” и “y”, они и попадают в узлы следующего уровня. И т. д.

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

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

Давайте посмотрим, как в таком дереве найти, например, элемент с index = 4.
Мы начинаем обход с корневого узла (root, в нашем случае с элементом “r”). У нас есть 3 варианта: мы уже находимся на нужном узле, нужный узел слева, нужный узел справа. Для того чтобы понять, где искать нужный элемент, нужно сравнить размер левого поддерева (в нашем случае left.size = 3) и текущий индекс (в нашем случае 4). Если эти 2 числа равны, то мы нашли необходимый узел и искомый элемент в нём. Если размер левого поддерева больше, то необходимый узел в левом поддереве. Если меньше, то надо искать в правом поддереве, но нужно уменьшить искомый индекс: index = index — left.size — 1.

Поскольку в нашем случае left.size < index, то мы ищем в правом поддереве элемент с новым индексом 4 — 3 — 1 = 0. Перемещаемся к узлу с элементом “y”.

Дальше делаем то же самое, что делали в корневом узле. Сравниваем left.size и index. Поскольку 1 > 0 то ищем в левом поддереве, перемещаемся к узлу с элементом “t”.

В этом узле нет левого поддерева, и его размер равен 0. index = left.size, а значит мы нашли узел с индексом 4 и можем достать из него искомый элемент “t”.

В псевдокоде это выглядит примерно так:

function get(node: Node<T>, index: int): T {
  val leftSize: int = (node.left == null) ? 0 : node.left.size;
  if (leftSize == index) {
    return node.obj;
  } else if (leftSize > index) {
    return get(node.left, index);
  } else {
    return get(node.right, index — leftSize — 1);
  }
}

Я постарался описать ключевой принцип как поместить массив в дерево. Работает такая структура, конечно, медленнее классического массива, за O(log(n)) против O(1). Но у неё есть важное преимущество: добавление элемента в середину или удаление из середины работает тоже за O(log(n)) против O(n) у массива. Конечно, при условии, что дерево более-менее сбалансировано. Существует много алгоритмов поддержания дерева в почти сбалансированном виде. Например, красно-чёрное дерево, AVL дерево, Декартово дерево. Я не буду расписывать подробности балансировки дерева, для нас подойдёт любой алгоритм. Давайте просто считать, что дерево в среднем сбалансировано и его максимальная глубина не сильно отличается от минимальной.

Небольшая оптимизация

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

                             [el: r, pos: 3]
                           /        :                                  /         :                  [el: w, pos: -2]           :           [el: y, pos: +2]
           /     :    \             :             /    :               /      :     \            :            /     :      [el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]
        :        :         :        :         :        :         :
        :        :         :        :         :        :         :
       [q]      [w]       [e]      [r]       [t]      [y]       [u]

Index:  0        1         2        3         4        5         6

Например, корневой узел “r” имеет позицию 3. Узел “w” имеет позицию -2 относительно родительского узла или абсолютную позицию 3 + (-2) = 1. Аналогично можно спуститься ещё на один уровень, например узел “e” имеет позицию 3 + (-2) + (+1) = 2. Т.е. индекс узла — это сумма позиций от корня дерева до этого узла.

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

Добавляем индексирование

Итак, в дереве мы умеем брать элемент по индексу, менять его значение, добавлять элементы в середину и удалять. По сути, нам осталось добавить быстрый поиск индекса по значению, indexOf(obj). Тогда contains(obj) и remove(obj) будут решаться тривиально.

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

Для того чтобы что-то быстро искать обычно используют таблицу. В мире Java таблицы называются Map, у неё есть 2 основные реализации: HashMap и TreeMap. Ключом таблицы будет ссылка на объект, а значением ссылка на его узел:

class IndexedTreeListSet<T> {
  root: Node<T>
  indexMap: Map<T, Node<T>>
}

Т.е. структура состоит из двух частей: само дерево-список и таблица со ссылками на объекты и узлы этого дерева. При обновлении дерева надо обновлять и таблицу. Детально расписывать процесс не буду. Интуитивно он должен быть понятен: добавили узел — положили его же в таблицу, удалили узел — удалили из таблицы. На практике же есть нюансы с балансировкой дерева: алгоритм должен менять ссылки между узлами, а не перемещать объекты между узлами. Иначе придётся делать много обновлений в таблице и упадёт производительность.

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

class Node<T> {
  obj: T
  left: Node<T>
  right: Node<T>
  parent: Node<T>
  pos: int
}

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

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

Правда, у нас появилась небольшая проблемка. Допустим, мы вызываем set(index, obj). Мы можем легко заменить один элемент в узле на другой, но только в том случае, если нового элемента в списке еще нет. А если есть, то что делать? Удалить лишний элемент из старой позиции и положить в новую? Или наоборот, сначала добавить, а потом удалить? Результат может быть разным. А можно вообще ничего не делать или бросать исключение. Идеального решения нет.

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

Убираем уникальность

Ок, усложняем ещё, разрешим хранить одинаковые объекты. Очевидно, что надо что-то делать с таблицей. Первая идея хранить в ней список узлов кажется не очень хорошей: с увеличением длины списка будет ухудшаться производительность. Вплоть до O(n), если все элементы списка будут одинаковыми.

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

class IndexedTreeList<T> {
  root: Node<T>
  indexMap: Map<T, TreeSet<Node<T>>>
}

Тогда вставка/удаление в/из TreeSet<Node> размера m будет происходить за log(m) сравнений позиций узлов, а каждое сравнение будет происходить за log(n) времени. Итоговая сложность вставки или удаления в подобную структуру будет происходить за O(log(n) * (1 + log(m))), где n это общее количество элементов в списке, а m это количество элементов в списке равных вставляемому/удаляемому. В худшем случае, когда все элементы равны друг другу, получим сложность O(log(n) ^ 2).

Внимательный читатель наверняка возразит: а как же иммутабельность? Мы ведь не можем изменять объекты, если они являются ключами таблицы? В общем случае так и есть. Однако для дерева, которое хранит в ключах отсортированные объекты, помимо стандартных правил для сравнений, достаточно сохранять инвариант: если a < b, то это свойство не должно изменяться со временем. Это как раз наш случай: если позиция одного узла меньше позиции другого узла, то это свойство будет сохраняться независимо от того, сколько узлов между ними было добавлено или удалено.

Можно ли сделать структуру персистентной?

Короткий ответ: нет, нельзя. Из-за двусвязности дерева, от корня к листьям и обратно, у нас каждый узел дерева связан с каждым. Персистентность таким образом не сделать, придётся пересоздавать всю структуру при любом изменении.

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

Если вам будет интересно, то я постараюсь написать статью об этой структуре. Возможно, даже реализую её на Java, Kotlin или Scala. Но, скорее всего, это будет не скоро.

Немного особенностей реализации

Тут я хочу описать некоторые особенности, с которыми пришлось столкнуться.
Про одну из оптимизаций про хранение позиции узла в списке я писал выше. Тут проявляется сила Open Source: я взял готовый код TreeList и не вникал в детали AVL дерева, поворотов узлов, обновления позиций и т. п.

Другая особенность, доставшаяся от TreeList, это ссылки на поддеревья в листах деревьев. Каждый узел хранит boolean leftIsPrevious и rightIsNext. Эти переменные обозначают наличие или отсутствие левого/правого поддерева. Если поддерева нет, то в left/right вместо ссылки на поддерево хранится ссылка на узел, который соответствует предыдущему или следующему элементу. В нашем примере [“q”, “w”, “e”, “r”, “t”, “y”, “u”] узел “e” листовой, у него нет поддеревьев. Соответственно leftIsPrevious и rightIsNext у него true, а left и right указывают на узлы “w” и “r” соответственно. Подобный подход помогает быстрее итерироваться по списку. И мешает при программировании новых фичей :)

Немного о работе с таблицей объект > узел. В идеале, в таблицу нужно один раз класть элемент при добавлении его в структуру и один раз удалять при удалении из структуры. На практике мне этого достичь не удалось. При добавлении элемента он добавляется в таблицу, всё как положено. Однако при удалении элемента алгоритм балансировки иногда перемещает элементы между узлами. В результате получается два удаления и одна запись в таблицу вместо одного удаления. Это можно исправить если убрать оптимизацию с leftIsPrevious и rightIsNext. И даже получить небольшой выигрыш производительности, причём не только при удалении. В некоторых тестах прирост был 10-20%. Но скорость итерирования падает существенно, раза в 1.5-2.5 на моих тестах. Оптимизацию решил пока оставить.

В Java основные типы таблиц HashMap и TreeMap. Для таблицы объект > узел по умолчанию используется HashMap. Однако можно использовать и TreeMap со специфическим для задачи Comparator’ом. В этом случае indexOf(obj) и remove(obj) будет искать/удалять тот объект, который равен указанному объекту согласно коду Comparator’а. Например, мы храним список пользователей, а компаратор сравнивает пользователей только по имени. Тогда мы можем ответить на вопрос “В каких позициях списка находятся пользователи с именем ‘Наполеон?’”. Или удалить из списка всех Наполеонов :).

Структура не поддерживает null. Исправить можно, но нет ощущения того, что это необходимо.

Касаемо того, что структура «умеет всё» я, конечно, немного слукавил. Конечно, при работе с единичными элементами всё хорошо и при определенных условиях даже за логарифм. Однако она не умеет некоторых вещей, которые умеют другие структуры. Например, Декартово дерево с неявным ключом, о нём были статьи на хабре. Оно не умеет быстро делать indexOf, но умеет за логарифм (в среднем, не гарантировано) делать sublist и конкатенировать два списка в один, плюс его можно сделать персистентным.

Производительность

В джаве производительность принято измерять с помощью фреймворка jmh. Тесты проводились на MacBook Pro 2017 года под Java11.

Я сравнил производительность стандартного ArrayList, TreeList из apache common-collections, и два своих класса IndexedTreeList и IndexedTreeListSet на нескольких сценариях. В каждом сценарии выполнялось 1000 однотипных операций, поэтому результат надо умножать на 1000.


Для начала я сравнил скорость доставания случайного элемента из списка. Предупрежу сразу, что в данном тесте накладные расходы очень существенны. Результаты, приближающиеся к 100000 * 1000 операций в секунду сильно искажены.


Тут, как ни странно, самый большой интерес вызывает стандартный ArrayList. Теоретически скорость доставания из него должна быть константой и не зависеть от количество элементов. На практике производительность сначала держится около 90000 * 1000 операций в секунду (помним про накладные расходы), но при длине списка в несколько тысяч элементов начинает проседать. Виной тому всё более частый cache miss: в кэше процессора не оказывается нужных данных и нужно всё чаще ходить за данными в оперативную память. При миллионе элементов скорость прохождения теста ниже в 10 раз, но на практике проседание производительности еще больше.

TreeList, IndexedTreeList и IndexedTreeListSet ожидаемо показывают схожий результат. Ожидаемо сильно медленнее, чем ArrayList. Даже при маленьком количестве элементов TreeList в несколько раз медленнее, чем ArrayList, хотя тест показывает разницу всего в 2 раза.

Следующий тест addRemoveRandom. Здесь в каждом тесте я вставляю в случайную позицию элемент и удаляю из случайной позиции элемент.


Можно было предположить, что ArrayList работает быстрее на маленьких списках. Однако то, что он выигрывает в этом тесте на списках вплоть до 10000 элементов выглядит интересно. Видимо, System.arrayCopy очень хорошо оптимизирован и использует все возможности современных процессоров. Начиная с 10000 элементов специализированные структуры данных начинают выигрывать. При 1000000 элементов разница скорости в 30-50 раз.

IndexedTreeList и IndexedTreeListSet ожидаемо медленнее, чем TreeList. Примерно в 1.5 — 2 раза.

Оставшиеся 2 теста indexOfKnown и indexOfUnknown как раз должны продемонстрировать основную особенность данной структуры. Различие тестов в том, что в одном случае мы ищем элемент, который есть в списке, а в другом случае ищем элемент, которого в списке нет.


Здесь у ArrayList и TreeList почти без сюрпризов. С увеличением размера скорость падает практически линейно. Поиск элемента не из списка ожидаемо в 2 раза медленнее, чем поиск элемента из списка, т.к. надо пройти весь массив вместо половины в среднем.

А вот IndexedTreeList и IndexedTreeListSet здесь показывают ожидаемо хороший результат. Эти структуры данных показывают сравнимую с ArrayList скорость выполнения indexOf даже при 10 элементах. При 1000 элементах эти структуры быстрее в 10 раз, при 1000000 быстрее в 1000 раз. При поиске элемента, которого нет в списке они ожидаемо дают лучшую скорость, чем при поиске элемента из списка.

На что еще интересно обратить внимание, так это на проседание производительности у IndexedTreeList и IndexedTreeListSet в тесте indexOfUnknown. Тут ситуация аналогичная той, что была в тесте с ArrayList.get. Теоретически мы не должны были получить падение производительности, а на практике, из-за cache miss получили, причём существенно.

Вместо заключения

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

Но даже если это ещё один велосипед, то я постарался сделать его полезным. Pull request в common-collections создан, но на момент написания статьи ещё не влит. Зная, как медленно всё может происходить в open source, не удивлюсь, если процесс затянется на месяцы.

Несколько удивил результат сравнения производительности ArrayList и TreeList. Тесты показали, что TreeList нет смысла использовать на размерах списка до 10000 элементов. Было бы интересно попробовать b-tree вместо бинарного дерева. Эта структура должна более бережно использовать память и, скорее всего, быстрее работать. И под неё можно адаптировать идею с индексированием.

В любом случае, прикольно иметь в арсенале инструмент, который может (почти) всё с предсказуемой сложностью.

Ссылки

Оригинальный проект
Pull request в apache common-collections
Тикет в Jira