Comments 9
Deque это общее название двухсторонней очереди. Можно сделать на двусвязном списке (тогда нет возможности быстро доставать элементы по индексу и соответственно бинарного поиска) или на циклической очереди (тогда нет возможности быстро вставлять/удалять в середину).
Есть ещё возможность использоать SkipList, там получше с этим.
Но основная особенность в том, что у меня элементы не отсортированы. Это видно даже на примере с [“q”, “w”, “e”, “r”, “t”, “y”, “u”].
В таком случае я бы делал по классической схеме БД — «хранилище» + индекс.
В качестве хранилища обычный двусвязный список, куда заносятся элементы по мере их поступления, в качестве индекса — ну скажем, SkipList где ключ — параметр, по которому вы этот элемент будете искать, а данные — указатель на элемент двусвязного списка, где хранится информация.
Тогда проходом по двусвязному списку мы может получить элементы в том порядке, в котором они к нам пришли, а по скиплисту всегда может быстро найти элемент по ключу.
Не успел утром ответить Вам на комментарий ниже, отвечу здесь.
Мне было важно 3 вещи:
- Вставлять/удалять элементы в середину: list.add(42, "Forty two")
- Доставать по индексу: list.get(42) -> "Forty two"
- Находить индекс по элементу: list.indexOf("Forty two") -> 42
На SkipList + любая таблица можно сделать. Но не совсем так, как Вы написали в этом камменте. В качестве хранилища обычный двусвязный список не подойдет. Найдя узел из него нельзя получить его индекс. А если вместо двусвязного списка использовать SkipList, то можно посчитать количество элементов до конца списка и на основании этого вычислить индекс.
В целом, не удивительно, что такой подход сработает. Ведь SkipList и дерево очень похожи по возможностям, хоть и сильно отличаются в реализации. SkipList даже проще, т.к. предоставляет из коробки возможность узнавать количество элементов до конца.
Другое дело, что SkipList по памяти хуже чем дерево, т.к. каждый узел требует дополнительный массив или даже два. И скорее всего по производительности тоже будет хуже. Было бы интересно протестировать.
Другое дело, что это не ваш случай т.к. при добавлении элемента в список «положить» его в нужную позицию не получится — он будет размещен там, где ему положено быть по порядку сортировки относительно остальных элементов.
Не зная всех подробностей вашей задачи, мне сложно что-либо предполагать относитльно ее решения, но складывается впечатление, что вам подошел бы массив + индекс к нему. Ибо операция list.add(42, «Forty two») подразумевает что у вас в списке уже есть как минимум 41 элемент. А если у вас их на момент добавления, скажем, всего 10? что будет между последним (10-м) элементов массива и 42-м (добавляемым)? Пустые узлы?
С производительностью там не так просто. Деревья требуют постоянной перебалансировки иначе они могу выродиться в обычный список (представьте, что вы в двоичное дерево добавляете последовательно 50 узлов со значениями от 1 до 50-ти — как оно будет выглядеть в конце, если его не перестраивать?)
SkipList дает небольшой проигрыш по времени поиска (ибо поиск по дереву, при условии что оно сбалансировано, является двоичным, т.е. самым быстрым из возможных), но выигрывает в добавлении и удалении элементов т.к. не требует никаких дополнительных действий по оптимизации дерева.
list.add(42, «Forty two») подразумевает что у вас в списке уже есть как минимум 41 элемент
Верно. При этом все элементы, которые с индексом большим, чем 41 смещаются. Массив не подходит, т.к. надо будет переместить все элементы, что в общем случае выливается в O(n).
Структура на основе дерева работает за O(log(n)). Гарантировано. Алгоритмы перебалансировки не такие страшные. AVL и красно-черное дерево как раз про это. Они поддерживают дерево (почти) сбалансированым, с определенными гарантиями, в том числе и по скорости.
SkipList тоже работает за O(log(n)), но это в среднем. Может и дольше. Как мне кажется, в среднем он может быть медленнее дерева, но это не точно, надо мерять.
В целом, в случае когда содержимое списка постоянно меняется (элементы постоянно добавляются-удаляются) 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 есть двусвязный сортированный список с возможностью быстрого поиска по ключу или положению элемента в списке.
Я для подобных задач пользую SkipList, расширенный виртуальным индексом. Неплохой баланс скорости на всем спектре операций — добавление, удаление, поиск.
На нем у меня реализовано:
индексированный список пар «ключ-данные»
сортированный список (когда данные одновременно являются ключом)
набор — множество однотипных элементов с возможностью таких операций над набором как пересечение, объединение, разность наборов.
О том, как добавить в балансирующееся двоичное дерево поиска возможность получать индекс по элементу и элемент по индексу, написано, например, во втором издании классической книги Кормена (вышло в 2001 году), в 14-й главе. Более того, реализации set с подобными возможностями уже можно найти в g++.
То, как добавить в коллекцию возможность искать элемент по значению, сделав обратный индекс «значение → его индекс или указатель в коллекции», эксплуатируется в ряде известных задач: «как сделать двоичную кучу с возможностью удаления элемента», «как реализовать LRU-кеш».
Действительно, если мы возьмём балансирующееся дерево поиска (с явными или неявными ключами), добавим в узлы ссылки на родителей, а также будем поддерживать мап «значение → указатель в дереве», то мы сможем за O(logN) добавлять элемент, удалять элемент, искать элемент по индексу (если поддерживаем размеры поддеревьев в вершинах) и определять индекс по значению. Более того, в такой структуре мы можем за логарифмическое время выполнять немутирующие запросы на отрезках (например, сумму всех элементов с ключами в данном диапазоне). Если используются неявные ключи, то мы можем ещё и переставлять местами различные участки коллекции, тоже за логарифмическое время.
Если не ошибаюсь, в 2016 году на Чемпионате Урала по программированию я задал Сергею Владимировичу Копелиовичу, который вёл алгоритмы и структуры данных в Санкт-Петербургском АУ, два вопроса касаемо данной идеи:
1) встречалась ли она в каких-либо известных источниках;
2) насколько она концептуально сложна, стоит ли, например, писать статью.
Ответы были примерно такими:
1) вроде бы нет, статей на явно данную тему не было;
2) идею нельзя назвать сложной, хороший студент должен додуматься до неё за 10-20 минут.
Год назад я давал задачу на реализацию подобной структуры на одной из олимпиад ПФО. После тура некоторые команды выразили своё недовольство задачей — «зачем спрашивать настолько очевидные вещи».
Структуры данных: список, который умеет всё*