¿Resumen Big-O para implementaciones de Java Collections Framework? [cerrado]

164

Puede que enseñe un "curso intensivo de Java" pronto. Si bien es seguro asumir que los miembros de la audiencia conocerán la notación Big-O, probablemente no sea seguro suponer que sabrán cuál es el orden de las diversas operaciones en diversas implementaciones de colecciones.

Podría tomarme el tiempo para generar una matriz de resumen, pero si ya está en el dominio público en algún lugar, seguro que me gustaría volver a usarla (con el crédito adecuado, por supuesto).

Alguien tiene algún puntero?

java collections big-o Jared
fuente
Aquí hay un enlace que encontré útil al analizar algunos objetos Java muy comunes y cuánto cuestan sus operaciones usando la notación Big-O. objectissues.blogspot.com/2006/11/…
Nick
Aunque no es de dominio público, los excelentes Java Generics and Collections de Maurice Naftalin y Philip Wadler enumeran descripciones generales de información de tiempo de ejecución en sus capítulos sobre las diferentes clases de colección.
Fabian Steeg
1
¿Sería útil este punto de referencia de rendimiento ?
ThreaT

Respuestas:

149

Este sitio web es bastante bueno pero no específico de Java: http://bigocheatsheet.com/ Aquí hay una imagen en caso de que este enlace no funcione

Ben J
fuente
27
Y es por eso que no usamos las URL como respuestas. Ese documento / servidor, por lo que puedo decir, ¡ya no está disponible!
Jason Mock
1
@Ben J Los enlaces ya no funcionan
Vikas V el
Los enlaces del archivo web ahora también están rotos.
MikeFHay
Parece nuevas URL de trabajo agregadas. Gracias por tomar el esfuerzo, es muy útil.
Tejas C
1
@AndreaZilio LinkedList.remove (Object) es un tiempo constante, suponiendo que ya conozca al vecino. Si no conoce al vecino, es hora lineal de encontrarlo primero.
Paul Evans
217

El libro Java Generics and Collections tiene esta información (páginas: 188, 211, 222, 240).

Lista de implementaciones:

                      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)

Establecer implementaciones:

                      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)

Implementaciones 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)

Implementaciones de cola:

                      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)

La parte inferior de javadoc para el paquete java.util contiene algunos enlaces buenos:

kit de herramientas
fuente
3
Debe especificar para qué escenario de caso son esas cifras, por ejemplo, eliminar de Arraylist podría tomar O (n), si elimina el elemento en el medio o al final de la matriz.
Popeye
@popeye no es O generalmente el peor de los casos?
Yassin Hajaj
Como mencionó @Popeye, debe haber una descripción clara sobre el caso de la respuesta. El caso puede ser promedio / peor para la complejidad del tiempo. Parece que la respuesta se refiere a un caso "promedio" para todos los DS.
Yashwin Munsadwala
12

Los Javadocs de Sun para cada clase de colección generalmente le indicarán exactamente lo que desea. HashMap , por ejemplo:

Esta implementación proporciona un rendimiento de tiempo constante para las operaciones básicas (get y put), suponiendo que la función hash dispersa los elementos correctamente entre los cubos. La iteración sobre las vistas de recopilación requiere un tiempo proporcional a la "capacidad" de la instancia de HashMap (el número de depósitos) más su tamaño (el número de asignaciones de valores clave).

TreeMap :

Esta implementación proporciona un costo de tiempo de registro (n) garantizado para las operaciones contenedoras KeyKey, get, put y remove.

TreeSet :

Esta implementación proporciona un costo de tiempo de registro (n) garantizado para las operaciones básicas (agregar, eliminar y contiene).

(énfasis mío)

mate b
fuente
No estoy de acuerdo con la parte de HashMap. Sé la posición de Sun, pero ... get, por ejemplo, debe llamar a obj.equals (key), que podría ser lineal en el tamaño de los objetos contenidos. Tenga en cuenta que normalmente tiene que leer los campos para esta comparación. Las excepciones serían enteros o cadenas (internados) ???
Desbordado
En primer lugar, si estaban equivocados, ¿no debería ser demasiado difícil para usted crear un caso de prueba que refuta el rendimiento de tiempo constante? En segundo lugar, si observa el código fuente de HashMap, no llama a equals () contra cada tecla del mapa, solo cuando los códigos hash son iguales.
mate b
55
Si lee la cita anterior, dice que es en tiempo constante "suponiendo que la función hash dispersa los elementos correctamente entre los cubos". Según la teoría de CS, las tablas hash tienen operaciones de tiempo constante cuando la función hash es "buena" (lo que ocurre en promedio), pero puede tomar tiempo lineal en el peor de los casos.
newacct
44
@Overflown: técnicamente, no importa cuánto tiempo tome obj.equals () desde una perspectiva de complejidad, ya que eso es solo parte de la "constante" en relación con el número de elementos en la colección.
mikera
6

El chico de arriba dio una comparación para HashMap / HashSet vs. TreeMap / TreeSet.

Hablaré sobre ArrayList vs. LinkedList:

Lista de arreglo:

  • O (1) get()
  • O amortizado (1) add()
  • si inserta o elimina un elemento en el medio usando ListIterator.add()o Iterator.remove(), será O (n) para cambiar todos los elementos siguientes

Lista enlazada:

  • En) get()
  • O (1) add()
  • si inserta o elimina un elemento en el medio usando ListIterator.add()o Iterator.remove(), será O (1)
newacct
fuente
1
if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1) ¿por qué? primero necesitamos encontrar un elemento en el medio, entonces ¿por qué no O (n)?
MyTitle
@ MyTitle: léelo de nuevo. "utilizando ListIterator.add()o Iterator.remove()" Tenemos un iterador.
newacct