Существует ли известная реализация индексируемого связанного списка?
Это - перевод версии Ruby Mike's в язык Common LISP:
(defun perms (x y original-string)
(loop with all = (list "")
with current-array = (list "")
for iteration from 1 to y
do (loop with next-array = nil
for string in current-array
do (loop for c across original-string
for value = (concatenate 'string string (string c))
do (push value next-array)
(push value all))
(setf current-array (reverse next-array)))
finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))
И другая версия, немного короче и использующий больше функций средства цикла:
(defun perms (x y original-string)
(loop repeat y
collect (loop for string in (or (car (last sets)) (list ""))
append (loop for c across original-string
collect (concatenate 'string string (string c)))) into sets
finally (return (loop for set in sets
append (loop for el in set when (>= (length el) x) collect el)))))
8 ответов
Я не верю, что можно будет получить O (1) как для вставки, так и для поиска. В ту минуту, когда вы добавляете массив (или даже причудливые, разделяемые векторы), вставка становится O (n) .
Есть способы уменьшить ущерб в зависимости от ожидаемого поведения вашего списка. Если поисков будет намного больше, чем вставок / удалений, может быть лучше просто использовать векторы (массивы переменного размера) - они достаточно эффективны, не совсем как массивы, но лучше, чем обход списков (поскольку это, как правило, списки массивов, технически он все еще проходит по списку, но каждый элемент в списке обычно имеет свой размер, что делает его более эффективным).
Если вставки и удаления происходят чаще, вы можете сделать построение индекса ленивым, чтобы это делается только при необходимости. Например, вставки и удаления изменят только часть связанного списка (и пометят индекс как грязный) - только когда кто-то попытается использовать индекс, он будет перестроен и помечен как чистый.
Вы даже можете оптимизировать перестроение, сохранив запись о первой грязной записи. Это будет означать, что если вы вставляете или удаляете только последнюю половину списка, вам не нужно перестраивать весь индекс, когда кто-то хочет его использовать.
Решение, которое я когда-то реализовал, было 2D-списком. Под этим я имею в виду:
+-----------+ +-----------+ +-----------+
List -> | count = 7 | -> | Count = 4 | -> | Count = 6 | -> null
+-----------+ +-----------+ +-----------+
| | |
V V V
+-----------+ +-----------+ +-----------+
| [0] | | [7] | | [11] |
+-----------+ +-----------+ +-----------+
| | |
V V V
+-----------+ +-----------+ +-----------+
| [1] | | [8] | | [12] |
+-----------+ +-----------+ +-----------+
| | |
: : :
: : :
| | |
V V V
+-----------+ +-----------+ +-----------+
| [6] | | [10] | | [16] |
+-----------+ +-----------+ +-----------+
| | |
V V V
null null null
Хотя при этом и вставка, и поиск выполнялись O (n), баланс был правильным. В решении с чистым массивом поиск - O (1) , а вставка - O (n) . Для чисто связанного списка вставка будет O (1) (как только вы найдете точку вставки, конечно, операция, которая сама по себе является O (n) ), а поиск - O (n) .
Двумерный список равен O (n) для обоих, но с меньшим коэффициентом. Если вы хотите вставить, вы можете найти нужный столбец, просто изучив первую строку каждого столбца. Затем вы просматриваете сам столбец в поисках нужной строки. Затем элемент вставляется, и счетчик для этого столбца увеличивается. Аналогично для удалений, хотя в этом случае счетчик уменьшается, и весь столбец удаляется, когда его счетчик достигает нуля.
Для поиска по индексу вы просматриваете столбцы, чтобы найти правильный столбец, а затем перемещаете элементы в столбце, чтобы получить нужный элемент.
И он может даже автоматически настраиваться, пытаясь сохранить максимальную высоту и ширину примерно одинаковыми.
Двумерный список равен O (n) для обоих, но с меньшим коэффициентом. Если вы хотите вставить, вы можете найти нужный столбец, просто изучив первую строку каждого столбца. Затем вы просматриваете сам столбец в поисках нужной строки. Затем элемент вставляется, и счетчик для этого столбца увеличивается. Аналогично для удалений, хотя в этом случае счетчик уменьшается, и весь столбец удаляется, когда его счетчик достигает нуля.
Для поиска по индексу вы просматриваете столбцы, чтобы найти правильный столбец, а затем перемещаете элементы в столбце, чтобы получить нужный элемент.
И он может даже автоматически настраиваться, пытаясь сохранить максимальную высоту и ширину примерно одинаковыми.
Двумерный список равен O (n) для обоих, но с меньшим коэффициентом. Если вы хотите вставить, вы можете найти нужный столбец, просто изучив первую строку каждого столбца. Затем вы просматриваете сам столбец в поисках нужной строки. Затем элемент вставляется, и счетчик для этого столбца увеличивается. Аналогично для удалений, хотя в этом случае счетчик уменьшается, и весь столбец удаляется, когда его счетчик достигает нуля.
Для поиска по индексу вы просматриваете столбцы, чтобы найти правильный столбец, а затем перемещаете элементы в столбце, чтобы получить нужный элемент.
И он может даже автоматически настраиваться, пытаясь сохранить максимальную высоту и ширину примерно одинаковыми.
Затем вы проходите по самому столбцу в поисках нужной строки. Затем элемент вставляется, и счетчик для этого столбца увеличивается. Аналогично для удалений, хотя в этом случае счетчик уменьшается, и весь столбец удаляется, когда его счетчик достигает нуля.Для поиска по индексу вы просматриваете столбцы, чтобы найти правильный столбец, а затем перемещаете элементы в столбце, чтобы получить нужный элемент.
И он может даже автоматически настраиваться, пытаясь сохранить максимальную высоту и ширину примерно одинаковыми.
Затем вы просматриваете сам столбец в поисках нужной строки. Затем элемент вставляется, и счетчик для этого столбца увеличивается. Аналогично для удалений, хотя в этом случае счетчик уменьшается, и весь столбец удаляется, когда его счетчик достигает нуля.Для поиска по индексу вы просматриваете столбцы, чтобы найти правильный столбец, а затем перемещаете элементы в столбце, чтобы получить нужный элемент.
И он может даже автоматически настраиваться, пытаясь сохранить максимальную высоту и ширину примерно одинаковыми.
Если вы считаете, что O (log N) == O (1) ,
проверка:
- Красно-черное дерево , O (logN) при каждой операции
- Список пропусков , O (logN) при каждой операции
Вы правы в этом.
Связанные списки - это O (1) вставка / удаление, потому что операция, которую вы выполняете, чтобы вставить или удалить что-то, просто переключает пару указателей (один или два на объекте, который вы вставляете, и один или два на одном или двух других объектах). Очевидно, это не зависит от размера списка.
Список пропуска даст вам поиск O (logn), но, поскольку вы поддерживаете индекс, это также означает вставку / удаление O (logn), потому что это индекс необходимо поддерживать в актуальном состоянии.
Любая параллельная структура данных, которую вы используете для поиска, должна быть сохранена, поэтому ваша сложность будет масштабироваться в зависимости от сложности этого индекса.
У вас есть конкретная проблема в уме? пытаетесь решить?
Например, вы можете получить O (n) вставку, удаление и поиск, если вы можете гарантировать идеальный хэш.
Когда я реализовывал связанный список в классе, я думал об оптимизации времени доступа, сохраняя 3 дополнительных поля: узел в середине списка, индекс самого последнего доступного узла и последний обращался к самому узлу.
Чтобы получить узел по индексу, я бы сначала посмотрел на все доступные пути для достижения узла по заданному индексу, а затем выбрал бы самый дешевый способ сделать это. Способы были бы просто:
- Переход от начала к желаемому индексу
- Переход от последнего доступного узла к желаемому индексу (вперед)
- Переход от самого последнего доступного узла к желаемому индексу (назад)
- Переход от средний узел к желаемому индексу (вперед)
- Переход от среднего узла к желаемому индексу (назад)
- Переход от конца узла к желаемому индексу
Путь с наименьшей разницей в нашем желаемый индекс, и наш начальный индекс будет самым дешевым вариантом. Если доступ к узлу еще не осуществлялся, узел, к которому недавно осуществлялся доступ, может быть установлен как средний узел. Конечно, с четным числом элементов нет реальной середины, поэтому я бы просто выбрал нижний предел n / 2.
В любом случае, я никогда не удосужился реализовать эту оптимизацию или даже на самом деле проанализировать его,
Как насчет хеш-таблицы? Вы получаете O (1) произвольный доступ по ключу и O (1) вставку / удаление. Загвоздка в том, что записи неупорядочены.
Для эффективной реализации упорядоченных последовательностей ознакомьтесь с деревьями пальцев . Они дают вам O (1) доступ к head и last и O (log n) произвольный доступ к внутренним узлам. Вставить или удалить с любого конца в O (1). Примечательно, что изменение направления дерева пальцев занимает постоянное время.
Я не знаю точного BigO при вставке (так как это будет зависеть от размера выборки и роста), но Java java.util.LinkedList сразу приходит на ум .
http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html
РЕДАКТИРОВАТЬ: да, очевидно, что внизу это все еще настоящий связанный список и как такое индексированное получение может быть O (n / 2), что, конечно, формально O (n).
Вы всегда можете потратить целую кучу места и реализовать реализацию List, которая хранит параллельный связанный список и массив с отложенными вставка / удаление.
Хотя я не думаю, что вы можете получить целочисленное индексирование, резервная хеш-таблица может работать, если вы используете «ссылочные» типы.
Java LinkedList имеет O (n) доступ для индексированных получает. LinkedList расширяет AbstractSequentialList , чтобы показать, что он не предлагает индексированных значений O (1).
Я бы посоветовал взглянуть на TreeList Apache . Он предлагает O (log n) вставок / удалений и O (1) индексированных поисков.