Resumo do Big-O para implementações do Java Collections Framework? [fechadas]

164

Eu posso estar ensinando um "curso intensivo de Java" em breve. Embora seja provavelmente seguro assumir que os membros do público conhecerão a notação Big-O, provavelmente não é seguro assumir que eles saberão qual é a ordem das várias operações nas várias implementações de coleção.

Eu poderia dedicar algum tempo para gerar uma matriz de resumo, mas se ela já estiver disponível em algum lugar público, gostaria de reutilizá-la (com o devido crédito, é claro).

Alguém tem alguma dica?

java collections big-o Jared
fonte
Aqui está um link que eu achei útil quando discutimos alguns objetos Java muito comuns e quanto custam suas operações usando a notação Big-O. objectissues.blogspot.com/2006/11/…
Nick
Embora não sejam de domínio público, os excelentes Java Generics and Collections de Maurice Naftalin e Philip Wadler listam visões gerais de informações de tempo de execução em seus capítulos sobre as diferentes classes de coleções.
Fabian Steeg
1
Esse benchmark de desempenho teria alguma utilidade?
Ameaça

Respostas:

149

Este site é muito bom, mas não específico para Java: http://bigocheatsheet.com/ Aqui está uma imagem, caso este link não funcione

Ben J
fonte
27
E é por isso que não usamos URLs como respostas. Esse documento / servidor, pelo que sei, não está mais disponível!
Jason Mock
1
@ Ben J Ligações não mais estão trabalhando
Vikas V
Os links do arquivo da web agora também estão quebrados.
MikeFHay
Parece que foram adicionados novos URLs de trabalho. Obrigado por se esforçar, é muito útil.
precisa
1
@AndreaZilio LinkedList.remove (Object) é tempo constante, supondo que você já conheça o vizinho. Se você não conhece o vizinho, é hora linear de encontrá-lo primeiro.
Paul Evans
217

O livro Java Generics and Collections possui essas informações (páginas: 188, 211, 222, 240).

Listar implementações:

                      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)

Defina implementações:

                      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)

Implementações de mapas:

                      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)

Implementações da fila:

                      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)

A parte inferior do javadoc para o pacote java.util contém alguns bons links:

kit de ferramentas
fonte
3
É necessário especificar para qual cenário de caso são esses números; por exemplo, excluir da matriz pode levar O (n), se você excluir o elemento no meio ou no final da matriz.
Popeye
@popeye normalmente não é o pior caso?
Yassin Hajaj
Conforme mencionado por @Popeye, deve haver uma descrição clara sobre qual é o caso da resposta. O caso pode ser médio / pior para a complexidade do tempo. Parece que a resposta está se referindo a um caso "médio" para todo o DS.
Yashwin Munsadwala
12

Os Javadocs da Sun para cada classe de coleção geralmente informam exatamente o que você deseja. HashMap , por exemplo:

Essa implementação fornece desempenho em tempo constante para as operações básicas (obter e colocar), assumindo que a função hash disperse os elementos adequadamente entre os buckets. A iteração nas visualizações de coleção requer um tempo proporcional à "capacidade" da instância do HashMap (o número de buckets) mais seu tamanho (o número de mapeamentos de valores-chave).

TreeMap :

Essa implementação fornece o tempo de log (n) garantido para as operações containsKey, get, put e remove.

TreeSet :

Essa implementação fornece o tempo de log (n) garantido para as operações básicas (adicionar, remover e conter).

(ênfase minha)

matt b
fonte
Eu discordo da parte do HashMap. Eu sei a posição da Sun, mas ... get, por exemplo, deve chamar obj.equals (key), que pode ser linear no tamanho dos objetos contidos. Considere que você normalmente precisa ler os campos para esta comparação. As exceções seriam números inteiros ou seqüências de caracteres (internadas) ???
Transbordou
Antes de tudo, se eles estavam errados, não seria muito difícil criar um caso de teste que refute o desempenho em tempo constante? Segundo, se você olhar para o código-fonte do HashMap, ele não chamará igual () contra cada tecla do mapa - somente quando os códigos de hash forem iguais.
mate b
5
Se você leu a citação acima, diz que é de tempo constante "assumindo que a função hash dispersa os elementos adequadamente entre os buckets". Da teoria CS, as tabelas de hash têm operações de tempo constante quando a função de hash é "boa" (o que acontece em média), mas pode levar tempo linear no pior dos casos.
Newacct
4
@ Overflown - tecnicamente, não importa quanto tempo obj.equals () leva a partir de uma perspectiva de complexidade, pois isso é apenas parte da "constante" em relação ao número de itens na coleção.
mikera 12/09/10
6

O cara acima deu comparação para HashMap / HashSet vs. TreeMap / TreeSet.

Vou falar sobre ArrayList vs. LinkedList:

ArrayList:

  • O (1) get()
  • O amortizado (1) add()
  • se você inserir ou excluir um elemento no meio usando ListIterator.add()ou Iterator.remove(), será O (n) para mudar todos os seguintes elementos

LinkedList:

  • Em) get()
  • O (1) add()
  • se você inserir ou excluir um elemento no meio usando ListIterator.add()or Iterator.remove(), será O (1)
newacct
fonte
1
if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1) porque? primeiro precisamos encontrar um elemento no meio, então por que não O (n)?
MyTitle
@ MyTitle: leia novamente. "using ListIterator.add()ou Iterator.remove()" Temos um iterador.
precisa saber é o seguinte