Большая-O сводка для реализаций Платформы Наборов Java? [закрытый]

Question

Большая-O сводка для реализаций Платформы Наборов Java? [закрытый]

При поиске файлов, которые можно добавить. Результат из git show делает это, но он также включает в себя много других вещей. Следующая команда полезна для получения одного и того же списка файлов, но без всех других вещей.

 git status --porcelain | grep "^?? " | sed -e 's/^[?]* //'

Это полезно, если в конвейере скомбинировано найти файлы, соответствующие определенному шаблону, а затем git add.

git status --porcelain | grep "^?? "  | sed -e 's/^[?]* //' | \
egrep "\.project$|\.settings$\.classfile$" | xargs -n1 git add

152

java collections big-o

задан Jared 20 February 2009 в 05:01

3 ответа

Другие вопросы по тегам:

java collections big-o

Похожие вопросы:

score 196 · Answer 1

Книжные Дженерики Java и Наборы имеют эту информацию (страницы: 188, 211, 222, 240).

Реализации списка:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

реализации Набора:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Реализации Map:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

реализации Очереди:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

нижняя часть javadoc для пакет java.util содержит некоторые хорошие ссылки:

Обзор Наборов имеет хорошую сводную таблицу.
Аннотируемая Схема списки все реализации на одной странице.

score 12 · Answer 2

Javadoc от Sun для каждого класса набора будут обычно говорить Вам точно, что Вы хотите. HashMap, например:

Эта реализация обеспечивает постоянно-разовая производительность для основных операций (получите и поместите), принятие хеш-функции рассеивает элементы правильно среди блоков. Повторение по представлениям набора требует время, пропорциональное "способности" экземпляра HashMap (количество блоков) плюс его размер (количество отображений значения ключа).

TreeMap:

Эта реализация обеспечивает гарантируемый журнал (n), время стоило за containsKey, получает, поместило и удаляет операции.

TreeSet:

Эта реализация обеспечивает гарантируемый журнал (n), время, стоившее за основные операции (добавьте, удалите, и содержит).

(шахта акцента)

score 6 · Answer 3

Приведенный выше парень сравнивал HashMap / HashSet с TreeMap / TreeSet.

Я расскажу о ArrayList и LinkedList:

ArrayList:

O (1) get ()
амортизируется O (1) add ()
, если вы вставляете или удаляете элемент посередине, используя ListIterator.add () или Iterator. remove () , это будет O (n) для сдвига всех следующих элементов

LinkedList:

O (n) get ()
O (1) add ( )
, если вы вставляете или удаляете элемент посередине, используя ListIterator.add () или Iterator.remove () , это будет O (1)