Структуры данных: список, который умеет всё*

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

    Структур данных, которые реализуют список полно. У всех есть свои достоинства и недостатки. Например в мире 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.

    Код под спойлером
    @Fork(1)
    @Warmup(iterations = 3)
    @Measurement(iterations = 5)
    public class PerformanceCompare {
    
        public static final Map<String, Class> CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,
                ArrayList.class)
                .collect(Collectors.toMap(c -> c.getSimpleName(), c -> c));
    
        public static final int ITERATIONS = 1000;
    
        @State(Scope.Benchmark)
        public static class Plan {
    
            @Param({"10", "100", "1000", "10000", "100000", "1000000"/*, "10000000"*/})
            public int size;
    
            @Param({"ArrayList", "TreeList", "IndexedTreeList", "IndexedTreeListSet"})
            public String className;
    
            private Random random;
            private List<Integer> list;
    
            @Setup
            public void init() throws IllegalAccessException, InstantiationException {
                random = new Random();
                list = (List<Integer>) CLASSES.get(className).newInstance();
    
                for (int i = 0; i < size; i++) {
                    list.add(i);
                }
            }
        }
    
    
        @Benchmark
        public void indexOfKnown(Plan plan, Blackhole blackhole) {
            List<Integer> list = plan.list;
            Random random = plan.random;
            int value = 0;
            for (int i = 0; i < ITERATIONS; i++) {
                value = list.indexOf(random.nextInt(plan.size));
            }
            blackhole.consume(value);
        }
    
        @Benchmark
        public void indexOfUnknown(Plan plan, Blackhole blackhole) {
            List<Integer> list = plan.list;
            Random random = plan.random;
            int value = 0;
            for (int i = 0; i < ITERATIONS; i++) {
                value += list.indexOf(random.nextInt());
            }
            blackhole.consume(value);
        }
    
        @Benchmark
        public void addRemoveRandom(Plan plan, Blackhole blackhole) {
            List<Integer> list = plan.list;
            Random random = plan.random;
            int value = 0;
            for (int i = 0; i < ITERATIONS; i++) {
                list.add(random.nextInt(list.size() + 1), random.nextInt());
                value += list.remove(random.nextInt(list.size()));
            }
            blackhole.consume(value);
        }
    
        @Benchmark
        public void get(Plan plan, Blackhole blackhole) {
            List<Integer> list = plan.list;
            Random random = plan.random;
            int value = 0;
            for (int i = 0; i < ITERATIONS; i++) {
                value += list.get(random.nextInt(list.size()));
            }
            blackhole.consume(value);
        }
    
        @Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)
        public static void main(String[] args) throws RunnerException {
            Options opt = new OptionsBuilder()
                    .include(PerformanceCompare.class.getSimpleName())
                    .forks(1)
    //                .jvmArgs("-Xms2048m", "-Xmx2048m", "-XX:MaxDirectMemorySize=512M")
                    .build();
    
            new Runner(opt).run();
        }
    }


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

    Результат теста get
    PerformanceCompare.get                       ArrayList       10  thrpt    5  79865.412 ± 10145.202  ops/s
    PerformanceCompare.get                       ArrayList      100  thrpt    5  81862.243 ±   983.727  ops/s
    PerformanceCompare.get                       ArrayList     1000  thrpt    5  81033.507 ±  4540.206  ops/s
    PerformanceCompare.get                       ArrayList    10000  thrpt    5  64096.123 ±  1430.361  ops/s
    PerformanceCompare.get                       ArrayList   100000  thrpt    5  41289.491 ± 11286.114  ops/s
    PerformanceCompare.get                       ArrayList  1000000  thrpt    5   8598.944 ±  2048.461  ops/s
    PerformanceCompare.get                        TreeList       10  thrpt    5  33912.275 ±  3754.284  ops/s
    PerformanceCompare.get                        TreeList      100  thrpt    5  21346.854 ±   863.588  ops/s
    PerformanceCompare.get                        TreeList     1000  thrpt    5  14808.414 ±   508.098  ops/s
    PerformanceCompare.get                        TreeList    10000  thrpt    5   8679.384 ±   109.250  ops/s
    PerformanceCompare.get                        TreeList   100000  thrpt    5   4605.998 ±  1028.945  ops/s
    PerformanceCompare.get                        TreeList  1000000  thrpt    5   2241.381 ±   768.147  ops/s
    PerformanceCompare.get                 IndexedTreeList       10  thrpt    5  34054.357 ±  3682.829  ops/s
    PerformanceCompare.get                 IndexedTreeList      100  thrpt    5  21934.002 ±  2339.947  ops/s
    PerformanceCompare.get                 IndexedTreeList     1000  thrpt    5  14626.691 ±   369.893  ops/s
    PerformanceCompare.get                 IndexedTreeList    10000  thrpt    5   7386.863 ±   342.150  ops/s
    PerformanceCompare.get                 IndexedTreeList   100000  thrpt    5   4562.126 ±   352.772  ops/s
    PerformanceCompare.get                 IndexedTreeList  1000000  thrpt    5   2105.718 ±   702.064  ops/s
    PerformanceCompare.get              IndexedTreeListSet       10  thrpt    5  33317.503 ±  2307.829  ops/s
    PerformanceCompare.get              IndexedTreeListSet      100  thrpt    5  21247.440 ±  1253.386  ops/s
    PerformanceCompare.get              IndexedTreeListSet     1000  thrpt    5  14665.557 ±   487.833  ops/s
    PerformanceCompare.get              IndexedTreeListSet    10000  thrpt    5   7667.214 ±    80.093  ops/s
    PerformanceCompare.get              IndexedTreeListSet   100000  thrpt    5   3454.023 ±    82.994  ops/s
    PerformanceCompare.get              IndexedTreeListSet  1000000  thrpt    5   1768.701 ±    35.878  ops/s
    


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

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

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

    Результат теста addRemoveRandom
    PerformanceCompare.addRemoveRandom           ArrayList       10  thrpt    5  12440.764 ±   485.642  ops/s
    PerformanceCompare.addRemoveRandom           ArrayList      100  thrpt    5   9880.123 ±   464.014  ops/s
    PerformanceCompare.addRemoveRandom           ArrayList     1000  thrpt    5   5288.905 ±  1219.055  ops/s
    PerformanceCompare.addRemoveRandom           ArrayList    10000  thrpt    5   1024.942 ±   179.366  ops/s
    PerformanceCompare.addRemoveRandom           ArrayList   100000  thrpt    5     91.219 ±    25.380  ops/s
    PerformanceCompare.addRemoveRandom           ArrayList  1000000  thrpt    5      5.499 ±     0.400  ops/s
    PerformanceCompare.addRemoveRandom            TreeList       10  thrpt    5   6242.607 ±   350.290  ops/s
    PerformanceCompare.addRemoveRandom            TreeList      100  thrpt    5   3117.945 ±   116.066  ops/s
    PerformanceCompare.addRemoveRandom            TreeList     1000  thrpt    5   1829.778 ±    80.516  ops/s
    PerformanceCompare.addRemoveRandom            TreeList    10000  thrpt    5   1230.077 ±    53.381  ops/s
    PerformanceCompare.addRemoveRandom            TreeList   100000  thrpt    5    443.571 ±    69.207  ops/s
    PerformanceCompare.addRemoveRandom            TreeList  1000000  thrpt    5    308.963 ±    84.077  ops/s
    PerformanceCompare.addRemoveRandom     IndexedTreeList       10  thrpt    5   3556.511 ±   144.596  ops/s
    PerformanceCompare.addRemoveRandom     IndexedTreeList      100  thrpt    5   2120.777 ±    83.848  ops/s
    PerformanceCompare.addRemoveRandom     IndexedTreeList     1000  thrpt    5   1211.112 ±    92.288  ops/s
    PerformanceCompare.addRemoveRandom     IndexedTreeList    10000  thrpt    5    789.458 ±    19.450  ops/s
    PerformanceCompare.addRemoveRandom     IndexedTreeList   100000  thrpt    5    302.989 ±    40.030  ops/s
    PerformanceCompare.addRemoveRandom     IndexedTreeList  1000000  thrpt    5    178.822 ±    92.853  ops/s
    PerformanceCompare.addRemoveRandom  IndexedTreeListSet       10  thrpt    5   4138.007 ±   119.943  ops/s
    PerformanceCompare.addRemoveRandom  IndexedTreeListSet      100  thrpt    5   2435.803 ±    20.276  ops/s
    PerformanceCompare.addRemoveRandom  IndexedTreeListSet     1000  thrpt    5   1445.054 ±   276.909  ops/s
    PerformanceCompare.addRemoveRandom  IndexedTreeListSet    10000  thrpt    5    972.256 ±    19.987  ops/s
    PerformanceCompare.addRemoveRandom  IndexedTreeListSet   100000  thrpt    5    366.608 ±    94.487  ops/s
    PerformanceCompare.addRemoveRandom  IndexedTreeListSet  1000000  thrpt    5    227.677 ±    48.276  ops/s
    


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

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

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

    Результат тестов indexOfKnown и indexOfUnknown
    PerformanceCompare.indexOfKnown              ArrayList       10  thrpt    5  41424.356 ±   549.047  ops/s
    PerformanceCompare.indexOfKnown              ArrayList      100  thrpt    5  17216.477 ±  1444.744  ops/s
    PerformanceCompare.indexOfKnown              ArrayList     1000  thrpt    5   2296.306 ±    76.372  ops/s
    PerformanceCompare.indexOfKnown              ArrayList    10000  thrpt    5    233.863 ±    26.926  ops/s
    PerformanceCompare.indexOfKnown              ArrayList   100000  thrpt    5     23.208 ±     2.776  ops/s
    PerformanceCompare.indexOfKnown              ArrayList  1000000  thrpt    5      0.919 ±     0.455  ops/s
    PerformanceCompare.indexOfKnown               TreeList       10  thrpt    5  26740.708 ±  1323.125  ops/s
    PerformanceCompare.indexOfKnown               TreeList      100  thrpt    5   5670.923 ±    99.638  ops/s
    PerformanceCompare.indexOfKnown               TreeList     1000  thrpt    5    745.408 ±    26.827  ops/s
    PerformanceCompare.indexOfKnown               TreeList    10000  thrpt    5     52.288 ±     1.362  ops/s
    PerformanceCompare.indexOfKnown               TreeList   100000  thrpt    5      4.224 ±     0.855  ops/s
    PerformanceCompare.indexOfKnown               TreeList  1000000  thrpt    5      0.193 ±     0.052  ops/s
    PerformanceCompare.indexOfKnown        IndexedTreeList       10  thrpt    5  34485.128 ±  1582.703  ops/s
    PerformanceCompare.indexOfKnown        IndexedTreeList      100  thrpt    5  29209.412 ±  1544.268  ops/s
    PerformanceCompare.indexOfKnown        IndexedTreeList     1000  thrpt    5  21139.584 ±  1442.867  ops/s
    PerformanceCompare.indexOfKnown        IndexedTreeList    10000  thrpt    5  12544.306 ±   312.097  ops/s
    PerformanceCompare.indexOfKnown        IndexedTreeList   100000  thrpt    5   3538.201 ±   272.537  ops/s
    PerformanceCompare.indexOfKnown        IndexedTreeList  1000000  thrpt    5   1420.119 ±   538.476  ops/s
    PerformanceCompare.indexOfKnown     IndexedTreeListSet       10  thrpt    5  39201.995 ±  1887.065  ops/s
    PerformanceCompare.indexOfKnown     IndexedTreeListSet      100  thrpt    5  34204.112 ±  1122.517  ops/s
    PerformanceCompare.indexOfKnown     IndexedTreeListSet     1000  thrpt    5  25374.557 ±  1596.746  ops/s
    PerformanceCompare.indexOfKnown     IndexedTreeListSet    10000  thrpt    5  14291.317 ±   391.180  ops/s
    PerformanceCompare.indexOfKnown     IndexedTreeListSet   100000  thrpt    5   4215.898 ±   283.680  ops/s
    PerformanceCompare.indexOfKnown     IndexedTreeListSet  1000000  thrpt    5   1729.100 ±  1260.815  ops/s
    PerformanceCompare.indexOfUnknown            ArrayList       10  thrpt    5  59053.313 ±  1845.665  ops/s
    PerformanceCompare.indexOfUnknown            ArrayList      100  thrpt    5  10867.572 ±   142.823  ops/s
    PerformanceCompare.indexOfUnknown            ArrayList     1000  thrpt    5   1186.583 ±    28.003  ops/s
    PerformanceCompare.indexOfUnknown            ArrayList    10000  thrpt    5    120.953 ±     4.146  ops/s
    PerformanceCompare.indexOfUnknown            ArrayList   100000  thrpt    5     11.936 ±     0.320  ops/s
    PerformanceCompare.indexOfUnknown            ArrayList  1000000  thrpt    5      0.566 ±     0.335  ops/s
    PerformanceCompare.indexOfUnknown             TreeList       10  thrpt    5  28134.237 ±  2291.670  ops/s
    PerformanceCompare.indexOfUnknown             TreeList      100  thrpt    5   3153.930 ±   158.734  ops/s
    PerformanceCompare.indexOfUnknown             TreeList     1000  thrpt    5    322.383 ±    44.245  ops/s
    PerformanceCompare.indexOfUnknown             TreeList    10000  thrpt    5     25.674 ±     1.787  ops/s
    PerformanceCompare.indexOfUnknown             TreeList   100000  thrpt    5      1.867 ±     0.291  ops/s
    PerformanceCompare.indexOfUnknown             TreeList  1000000  thrpt    5      0.093 ±     0.008  ops/s
    PerformanceCompare.indexOfUnknown      IndexedTreeList       10  thrpt    5  66625.126 ±  5232.668  ops/s
    PerformanceCompare.indexOfUnknown      IndexedTreeList      100  thrpt    5  70038.055 ±  5803.848  ops/s
    PerformanceCompare.indexOfUnknown      IndexedTreeList     1000  thrpt    5  63240.467 ±   885.956  ops/s
    PerformanceCompare.indexOfUnknown      IndexedTreeList    10000  thrpt    5  54731.988 ±  3950.150  ops/s
    PerformanceCompare.indexOfUnknown      IndexedTreeList   100000  thrpt    5  22049.476 ±   821.924  ops/s
    PerformanceCompare.indexOfUnknown      IndexedTreeList  1000000  thrpt    5   9459.862 ±   804.738  ops/s
    PerformanceCompare.indexOfUnknown   IndexedTreeListSet       10  thrpt    5  70274.968 ± 15830.355  ops/s
    PerformanceCompare.indexOfUnknown   IndexedTreeListSet      100  thrpt    5  71017.685 ±  6920.447  ops/s
    PerformanceCompare.indexOfUnknown   IndexedTreeListSet     1000  thrpt    5  66405.960 ±  1127.231  ops/s
    PerformanceCompare.indexOfUnknown   IndexedTreeListSet    10000  thrpt    5  57983.963 ±  3276.142  ops/s
    PerformanceCompare.indexOfUnknown   IndexedTreeListSet   100000  thrpt    5  41277.110 ±  9919.893  ops/s
    PerformanceCompare.indexOfUnknown   IndexedTreeListSet  1000000  thrpt    5   9840.185 ±  2159.352  ops/s
    


    Здесь у 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
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

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

      0
      Для похожей задачи использовал deque, вставка в «середину» через бинарный поиск. По итогу всегда имеем отсортированый deque со всеми его прелестями.
        +1

        Deque это общее название двухсторонней очереди. Можно сделать на двусвязном списке (тогда нет возможности быстро доставать элементы по индексу и соответственно бинарного поиска) или на циклической очереди (тогда нет возможности быстро вставлять/удалять в середину).
        Есть ещё возможность использоать SkipList, там получше с этим.
        Но основная особенность в том, что у меня элементы не отсортированы. Это видно даже на примере с [“q”, “w”, “e”, “r”, “t”, “y”, “u”].

          0
          Я правильно понимаю, что вам важен порядок следования элементов?
          В таком случае я бы делал по классической схеме БД — «хранилище» + индекс.
          В качестве хранилища обычный двусвязный список, куда заносятся элементы по мере их поступления, в качестве индекса — ну скажем, SkipList где ключ — параметр, по которому вы этот элемент будете искать, а данные — указатель на элемент двусвязного списка, где хранится информация.

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

            Не успел утром ответить Вам на комментарий ниже, отвечу здесь.
            Мне было важно 3 вещи:


            1. Вставлять/удалять элементы в середину: list.add(42, "Forty two")
            2. Доставать по индексу: list.get(42) -> "Forty two"
            3. Находить индекс по элементу: list.indexOf("Forty two") -> 42

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


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

              0
              У SkipList есть расширение, описанное в статье A SkipList Cookbook — 3.4 Linear List Operations — фактически это виртуальный индекс, позволяющий быстро искать элемент не только по ключу, но и по его положению в списке.
              Другое дело, что это не ваш случай т.к. при добавлении элемента в список «положить» его в нужную позицию не получится — он будет размещен там, где ему положено быть по порядку сортировки относительно остальных элементов.
              Не зная всех подробностей вашей задачи, мне сложно что-либо предполагать относитльно ее решения, но складывается впечатление, что вам подошел бы массив + индекс к нему. Ибо операция list.add(42, «Forty two») подразумевает что у вас в списке уже есть как минимум 41 элемент. А если у вас их на момент добавления, скажем, всего 10? что будет между последним (10-м) элементов массива и 42-м (добавляемым)? Пустые узлы?

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

              SkipList дает небольшой проигрыш по времени поиска (ибо поиск по дереву, при условии что оно сбалансировано, является двоичным, т.е. самым быстрым из возможных), но выигрывает в добавлении и удалении элементов т.к. не требует никаких дополнительных действий по оптимизации дерева.
                0
                list.add(42, «Forty two») подразумевает что у вас в списке уже есть как минимум 41 элемент

                Верно. При этом все элементы, которые с индексом большим, чем 41 смещаются. Массив не подходит, т.к. надо будет переместить все элементы, что в общем случае выливается в O(n).


                Структура на основе дерева работает за O(log(n)). Гарантировано. Алгоритмы перебалансировки не такие страшные. AVL и красно-черное дерево как раз про это. Они поддерживают дерево (почти) сбалансированым, с определенными гарантиями, в том числе и по скорости.


                SkipList тоже работает за O(log(n)), но это в среднем. Может и дольше. Как мне кажется, в среднем он может быть медленнее дерева, но это не точно, надо мерять.

                  +1
                  В статье Skip Lists: A Probabilistic Alternative to Balanced Trees автор приводит сравнения с деревьями. Время поиска на уровне деревьев, время добавления и удаления кратно меньше.
                  В целом, в случае когда содержимое списка постоянно меняется (элементы постоянно добавляются-удаляются) SkipList будет предпочтительнее, особенно на больших объемах (я тестировал на полутора-двух миллионах элементов, правда, без сравнения с деревьями и абсолютные цифры не будут показательны т.к. тест проходил на 18-ядерном SMT8 IBM PowerS 924 с 1800 Гб RAM)

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

                  list.add(42, «Forty two»)

                  а потом

                  list.add(42, «another Forty two»)

                  и предыдущий уже будет ни разу не 42, а уже 43…

                  У меня задачи обычно связаны с кешированием данных — если с каким-то справочником (на 10-20-30 тысяч записей) приходится работать многократно, то эффективнее один раз втянуть его в память, а потом уже работать с памятью.

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

                  Выборка без сортировки с занесением результатов в SkipList с ключом по набору нужных полей и последующей обработкой по списку от начала к концу оказалось быстрее в 5-6 раз.

                  Фактически, SkipList есть двусвязный сортированный список с возможностью быстрого поиска по ключу или положению элемента в списке.
        0
        Недостаток деревьев в необходимости их балансировки.
        Я для подобных задач пользую SkipList, расширенный виртуальным индексом. Неплохой баланс скорости на всем спектре операций — добавление, удаление, поиск.

        На нем у меня реализовано:
        индексированный список пар «ключ-данные»
        сортированный список (когда данные одновременно являются ключом)
        набор — множество однотипных элементов с возможностью таких операций над набором как пересечение, объединение, разность наборов.
          +3
          Описанные идеи важны, но их вряд ли можно назвать новыми.

          О том, как добавить в балансирующееся двоичное дерево поиска возможность получать индекс по элементу и элемент по индексу, написано, например, во втором издании классической книги Кормена (вышло в 2001 году), в 14-й главе. Более того, реализации set с подобными возможностями уже можно найти в g++.

          То, как добавить в коллекцию возможность искать элемент по значению, сделав обратный индекс «значение → его индекс или указатель в коллекции», эксплуатируется в ряде известных задач: «как сделать двоичную кучу с возможностью удаления элемента», «как реализовать LRU-кеш».

          Действительно, если мы возьмём балансирующееся дерево поиска (с явными или неявными ключами), добавим в узлы ссылки на родителей, а также будем поддерживать мап «значение → указатель в дереве», то мы сможем за O(logN) добавлять элемент, удалять элемент, искать элемент по индексу (если поддерживаем размеры поддеревьев в вершинах) и определять индекс по значению. Более того, в такой структуре мы можем за логарифмическое время выполнять немутирующие запросы на отрезках (например, сумму всех элементов с ключами в данном диапазоне). Если используются неявные ключи, то мы можем ещё и переставлять местами различные участки коллекции, тоже за логарифмическое время.

          Если не ошибаюсь, в 2016 году на Чемпионате Урала по программированию я задал Сергею Владимировичу Копелиовичу, который вёл алгоритмы и структуры данных в Санкт-Петербургском АУ, два вопроса касаемо данной идеи:
          1) встречалась ли она в каких-либо известных источниках;
          2) насколько она концептуально сложна, стоит ли, например, писать статью.
          Ответы были примерно такими:
          1) вроде бы нет, статей на явно данную тему не было;
          2) идею нельзя назвать сложной, хороший студент должен додуматься до неё за 10-20 минут.

          Год назад я давал задачу на реализацию подобной структуры на одной из олимпиад ПФО. После тура некоторые команды выразили своё недовольство задачей — «зачем спрашивать настолько очевидные вещи».

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

          Самое читаемое