Java PriorityQueue удаление произвольных элементов производительности - PullRequest
Новая
       15

Java PriorityQueue удаление произвольных элементов производительности

7 голосов
/ 16 апреля 2009

Скажем, у меня есть java PriorityQueue (которую java реализует как кучу), который я повторяю для удаления элементов на основе некоторых критериев: 

PriorityQueue q = new PriorityQueue();
...
Iterator it = q.iterator();
while(it.hasNext()){
    if( someCriterion(it.next()) )
        it.remove();
}

Сколько времени занимает каждая операция удаления ()? Я не уверен, что это O (log (n)) или O (1).

1 Ответ

10 голосов
/ 16 апреля 2009

Если вы используете реализацию Sun, это O(log(n)). Из Javadocs :

Примечание о реализации: эта реализация обеспечивает O (log (n)) время для методов enqueing и dequeing (offer, poll, remove() и add); линейное время для remove(Object) и contains(Object) методы; и постоянное время для методов поиска (peek, element и size).

Другие реализации могут иметь различную сложность.

Редактировать: Javadocs не покрывают производительность удаления элемента с помощью итератора, поэтому мне пришлось искать исходный код. Все это относится к реализации Sun и может отличаться версией Apple, GNU Classpath и т. Д. Источник Sun доступен здесь ; он также включен в JDK, так что, возможно, он уже установлен.

В итераторе PriorityQueue по умолчанию для remove() используется вызов PriorityQueue.removeAt(lastRet), где lastRet - индекс, который последний раз был возвращен next(). removeAt() представляется O(log(n)) наихудшим случаем (возможно, придется просеять очередь, но не нужно повторять).

Однако иногда случаются плохие вещи. Из комментариев removeAt(): 

/**
 * Removes the ith element from queue.
 *
 * Normally this method leaves the elements at up to i-1,
 * inclusive, untouched.  Under these circumstances, it returns
 * null.  Occasionally, in order to maintain the heap invariant,
 * it must swap a later element of the list with one earlier than
 * i.  Under these circumstances, this method returns the element
 * that was previously at the end of the list and is now at some
 * position before i. This fact is used by iterator.remove so as to
 * avoid missing traversing elements.
 */

Когда ненулевой элемент возвращается removeAt(), итератор добавляет его в специальную очередь для последующего использования: когда у итератора заканчиваются элементы в очереди, он затем повторяет эту специальную очередь. Когда во время этой второй фазы итерации вызывается remove(), итератор вызывает PriorityQueue.removeEq(lastRetElt), где lastRetElt - последний элемент, возвращаемый из специальной очереди. removeEq вынужден использовать линейный поиск, чтобы найти правильный элемент для удаления, что делает его O(n). НО он может проверять элементы, используя == вместо .equals(), поэтому его постоянный коэффициент ниже, чем PriorityQueue.remove(Object).

То есть, другими словами, удаление с помощью итератора технически O(n), но на практике это должно быть немного быстрее, чем remove(Object).

...