Java: эффективная вставка в LinkedList - PullRequest
Новая
       8

Java: эффективная вставка в LinkedList

2 голосов
/ 02 апреля 2012

Я оптимизирую реализацию отсортированного LinkedList.

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

Я хотел бы знать, есть ли какой-либо другой способ, которым я могу вставить элемент одновременно с обходом списка, чтобы уменьшить вставку с O (n + (n ограничено размером () / 2)) до O (п).

ListIterator - это почти , что Im после, из-за его метода add (), но, к сожалению, в случае, когда в списке есть элементы, равные вставке, вставка должна быть помещена после них в список. Для реализации этого ListIterator необходим метод peek (), которого у него нет.

edit: У меня есть свой ответ, но я все равно добавлю его, так как многие люди не поняли правильно: Я ищу точку вставки И вставка, которая в совокупности выше, чем O (n)

Ответы [ 3 ]

2 голосов
/ 02 апреля 2012

Вы можете рассмотреть пропустить список , который реализован с использованием нескольких связанных списков с различной степенью детализации.Например, связанный список на уровне 0 содержит все элементы, на уровне 1 - только ссылки на каждый 2-й элемент в среднем, на уровне 2 - только на каждый 4-й элемент в среднем и т. Д. ... Поиск начинается с верхнего уровня и постепенно снижается до нижних уровней доон находит точное совпадение.Эта логика похожа на бинарный поиск.Таким образом, поиск и вставка являются операцией O (log n ).

Конкретным примером в библиотеке классов Java является ConcurrentSkipListSet (хотя это может быть не напрямуюможно использовать здесь).

1 голос
/ 02 апреля 2012

Я бы предпочел предложение Петера Торока, но я все же хотел бы добавить кое-что для подхода итератора:

Обратите внимание, что ListIterator предоставляет метод previous() для перебора списка в обратном направлении.Поэтому сначала выполняйте итерацию, пока не найдете первый элемент, который больше, а затем перейдите к предыдущему элементу и вызовите add(...).Если вы дойдете до конца, то есть все элементы меньше, просто позвоните add(...), не возвращаясь.

0 голосов
/ 02 апреля 2012

У меня есть свой ответ, но я все равно добавлю его, так как многие люди не поняли правильно: я ищу точку вставки И вставка, которая в совокупности выше O(n).

Вы требуете поддерживать коллекцию (возможно) неуникальных элементов, которые могут повторяться в порядке, заданном функцией упорядочения. Это может быть достигнуто различными способами. (Далее я использую «общую стоимость вставки» для обозначения стоимости вставки ряда (N) элементов в изначально пустую структуру данных.)

  • Один или два связанных списка предлагают O(N^2) общую стоимость вставки (независимо от того, комбинируете ли вы шаги для нахождения позиции и выполнения вставки!) И O(N) стоимость итерации.

  • TreeSet предлагает O(NlogN) общую стоимость вставки и O(N) стоимость итерации. Но не имеет дубликатов.

  • Мультисет множества на основе дерева (например, TreeMultiset) имеет ту же сложность, что и TreeSet, но допускает дублирование.

  • Структура данных списка пропусков также имеет ту же сложность, что и предыдущие два.

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

Похоже, у вас также есть неправильное представление о том, как сочетаются меры "большого О". Если у меня есть один шаг алгоритма, равный O(N), и второй шаг, который также равен O(N), то объединенные два шага - STILL O(N) .... не "больше, чем O(N)". Вы можете вывести это из определения «большой О». (Я не буду утомлять вас деталями, но математика проста.)

...