Big-O resumen de las implementaciones de Java Collections Framework?

124

Puedo estar enseñando un "curso acelerado de Java" pronto. Si bien es seguro suponer 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 varias implementaciones de colecciones.Big-O resumen de las implementaciones de Java Collections Framework?

que podría tomar tiempo para generar una matriz de resumen a mí mismo, pero si ya está ahí fuera en el dominio público en alguna parte, me Seguro gustaría volver a utilizarlo (con el crédito apropiado, por supuesto.)

Alguien tiene ¿Alguna sugerencia?

Fuente

2009-02-18 Jared

¿Sería útil este [punto de referencia de rendimiento] (https://github.com/ThreaT/Java-Collections-Benchmark)? – ThreaT

Aquí hay un enlace que encontré útil cuando debato algunos objetos Java muy comunes y cuánto cuestan sus operaciones usando la notación Big-O. http://objectissues.blogspot.com/2006/11/big-o-notation-and-java-constant-time.html – Nick

Aunque no es de dominio público, es excelente [Java Generics and Collections] (http: // oreilly.com/catalog/9780596527754/) por Maurice Naftalin y Philip Wadler enumera las descripciones de la información de tiempo de ejecución en sus capítulos sobre las diferentes clases de colecciones. –

114

Este sitio web es bastante bueno, pero no es específico de Java: http://bigocheatsheet.com/

Fuente

2010-10-29 07:41:28

+21

Y es por eso que no usamos las URL como respuestas. Ese documento/servidor, por lo que puedo ver, ¡ya no está disponible! –

@Ben J Los enlaces ya no funcionan –

Los enlaces del archivo web ahora también están rotos. – MikeFHay

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

Esta aplicación proporciona rendimiento en tiempo constante para las operaciones básicas (get y put), asumiendo la función hash se dispersa adecuadamente los elementos entre los cubos. La iteración sobre las vistas de recopilación requiere tiempo proporcional a la "capacidad" de la instancia de HashMap (el número de segmentos) más su tamaño (el número de asignaciones de valores-clave).

TreeMap:

Esta aplicación proporciona registro garantizado (n) cuestan tiempo para la containsKey, conseguir, de poner y quitar operaciones.

TreeSet:

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

(el énfasis es mío)

Fuente

2009-02-18 04:31:55

No estoy de acuerdo con la parte de HashMap. Conozco la posición de Sun, pero ... obtener, por ejemplo, debe llamar obj.equals (clave), que podría ser lineal en el tamaño de los objetos contenidos. Considere que, por lo general, tiene que leer los campos para esta comparación. Las excepciones serían enteros o cadenas (internados) ??? – Overflown

En primer lugar, si estaban equivocados, no debería ser demasiado difícil para usted crear un caso de prueba que refute el rendimiento de tiempo constante. En segundo lugar, si nos fijamos en el código fuente de HashMap, no llama a igual() contra cada tecla en el mapa, solo cuando los códigos hash son iguales. –

Si lee la cita anterior, dice que es de tiempo constante "suponiendo que la función hash dispersa los elementos correctamente entre los cubos". De la teoría 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

151

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

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

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

Mapa implementaciones:

     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 del Javadoc para el paquete java.util contiene algunos buenos enlaces:

Collections Overview tiene un buen cuadro resumen.
Annotated Outline enumera todas las implementaciones en una página.

Fuente

2009-02-18 04:35:20 toolkit

Debe especificar para qué caso de caso son esas cifras, por ejemplo, eliminar de Arraylist podría tomar O (n), si elimina elemento en medio o al final de la matriz. – Popeye

El tipo anterior dio una comparación para HashMap/HashSet vs. TreeMap/TreeSet.

voy a hablar de ArrayList LinkedList vs.:

ArrayList:

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

LinkedList:

O (n) get()
O (1) add()
si insertar o eliminar un elemento en el medio usando ListIterator.add() o Iterator.remove(), será O (1)

Fuente

2009-05-02 00:52:30 newacct

'si inserta o elimina un elemento en el medio usando ListIterator.add() o Iterator.remove(), será O (1)' ¿por qué? primero tenemos que encontrar un elemento en el medio, entonces ¿por qué no O (n)? – MyTitle

@MyTitle: léelo de nuevo. "usando' ListIterator.add() 'o' Iterator.remove() '" Tenemos un iterador. – newacct

Big-O resumen de las implementaciones de Java Collections Framework?

Respuesta

Cuestiones relacionadas