* Por todo, me refiero a la ejecución relativamente rápida de operaciones en un solo elemento de una matriz.Las estructuras de datos que implementan la lista están completas. Cada uno tiene sus propias ventajas y desventajas. Por ejemplo, en el mundo Java, dependiendo de las operaciones necesarias, puede usar:- add (obj), get (obj), set (index, obj): un conjunto básico de casi todas las listas, por ejemplo, ArrayList.
- add (index, obj): estructuras en forma de árbol, por ejemplo, TreeList de apache common-collections.
- eliminar (índice): igual que el anterior.
- contiene (obj), indexOf (obj): puede usar un montón de ArrayList y HashMap.
- remove (obj): ... me resulta difícil responder. En algunos casos, puede arreglárselas con LinkedHashSet. Se resuelve trivialmente en presencia de los dos puntos anteriores, pero ¿qué estructuras pueden ambos rápidamente?
Cuando necesitaba una estructura con rápida adición (obj), get (index), remove (index) e indexOf (obj), google no dio una respuesta. No encontré ningún código de ejemplos o descripciones de tales estructuras. Tal vez no estaba buscando allí, tuve que inventarlo yo mismo. Pero si alguien deja caer el enlace en los comentarios, lo agradeceré enormemente.Quizás alguien se dio cuenta de que puede tomar una TreeList, que puede insertar / eliminar rápidamente elementos en el medio de la lista y agregar un HashMap del objeto al índice en la TreeList para la ejecución rápida de indexOf (obj). Y será una decisión simple, elegante, pero incorrecta. Después de todo, cuando se agrega al medio o se elimina del medio, será necesario volver a calcular los índices, en promedio, para la mitad de los elementos. Esto degradará el rendimiento a O (n).A continuación hablaré sobre una estructura de datos que puede hacer todo lo anterior. Que realiza cualquier operación en un elemento en tiempo O (log (n)). Bueno, casi, porque el logaritmo se realiza en el caso en que todos los objetos de la lista son diferentes. Si la lista contiene los mismos objetos, entonces es posible reducir el rendimiento hasta O (log (n) ^ 2).Te advertiré de inmediato que no pintaré el código aquí. Puede ser bastante complicado para el artículo. Pero lo es, escrito en Java. Basado en la clase TreeList de apache common-collections. La solicitud de extracción ya existe, pero al momento de la redacción, el artículo aún no se ha vertido.Además, no describiré algoritmos bien conocidos. Por ejemplo, algoritmos de equilibrio de árboles. Para la mayoría, puede ser suficiente dar por sentado el hecho de que el árbol puede mantenerse equilibrado. Esto no afecta la comprensión de la idea general. Aquellos que quieran saber más pueden encontrar fácilmente información. Pero le contaré muy brevemente sobre algunas cosas básicas, porque sin el conocimiento de los conceptos básicos, muchos elementos clave no se pueden entender.Los enlaces estarán al final.Por qué es necesario
De hecho, no es tan fácil encontrar situaciones en las que todo se necesita directamente de la lista. Es poco probable que se trate de algún tipo de estructura súper necesaria, de lo contrario, todos lo sabrían. Sin embargo, se pueden dar algunos ejemplos donde dicha lista podría ser útil.Reconozco que muchos de los ejemplos son descabellados. Todo o casi todo se puede resolver de otra manera.Almacenamiento en caché y compresión
Mi tarea inicial, por lo que comencé a investigar el tema. Jugó con la compresión de datos específicos y necesitaba una lista para el caché de objetos.La idea es esta: cuando procesamos otro objeto, lo buscamos en la lista. Si no se encuentra, guarde el objeto y agréguelo al principio de la lista. Si se encuentra, tomamos su índice en la lista y, en lugar del objeto, guardamos solo su índice, después de lo cual movemos el objeto a la parte superior de la lista. Por lo tanto, los objetos que ocurren a menudo recibirán índices pequeños, y los objetos que ocurren solo una vez eventualmente se moverán al final de la lista y se eliminarán.Giro
Si en lugar de la cola FIFO habitual, para algunas tareas, se utiliza una estructura similar, se pueden realizar las siguientes operaciones:- Responda la pregunta: cuántas tareas hay en la cola antes de esta tarea.
- Eliminar tareas de la cola.
Es como en un supermercado. Si viniste por una barra de chocolate, pero ves que la línea se mueve lentamente, ¿tal vez la barra de chocolate no es tan necesaria? :)Tabla de puntaje alto
Supongamos que queremos almacenar el tiempo durante el cual los jugadores completan un nivel en un juego. Hay muchos jugadores y todos compiten, tratando de mostrar el tiempo mínimo. Los datos del jugador pueden colocarse en una matriz y ordenarse por tiempo. Usando esta estructura, puedes:- Mueve a los jugadores más arriba en la lista si muestran mejores resultados que antes.
- Eliminar jugadores de la lista, por ejemplo, en el caso de una prohibición de hacer trampa.
- Muestra a cada jugador dónde está.
- Mostrar la tabla de registros página por página.
- Mostrar una tabla dispersa en lugares, por ejemplo, tiempo 1, 2, 3, 5, 10, 20, 50, 100, 1000, 10000 lugares.
Estructura de datos
La estructura se basa en un árbol con una clave implícita. En este enfoque, por ejemplo, se basa TreeList en apache common-collections. Para seguir adelante, debe comprender cómo funciona esta estructura.Árbol de claves implícitas
Un árbol consta de nodos (nodos). Cada nodo contiene un enlace a un objeto que se almacena en el nodo y 2 enlaces a otros nodos: izquierdo y derecho. El nodo superior se llama nodo raíz. En el caso más simple, el nodo se ve así:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
}
En el árbol binario clásico para cada nodo en el subárbol izquierdo, todos los objetos son más pequeños que en el nodo actual, y en el derecho - grande. Por ejemplo: [ element: 25 ]
/ \
/ \
[ element: 14 ] [ element: 45 ]
/ \ / \
/ \ / \
[ element: 10 ] [ element: 22 ] [ element: 27 ] [ element: 90 ]
/ \ /
/ \ /
[ element: 17 ] [ element: 23 ] [ element: 80 ]
Pero para nuestro propósito, tal árbol no es adecuado. No necesitamos almacenar objetos ordenados, pero debemos tener acceso a ellos por índice, como en una matriz.¿Cómo puedo poner una matriz en un árbol? Seleccionemos un elemento con índice i desde el centro de la matriz. Coloque el elemento i-ésimo de la matriz en el nodo raíz. 2 subárboles salen del nodo raíz. En el subárbol izquierdo colocamos la mitad de la matriz con índice <i, y en el derecho con índice> i. ¿Cómo hacerlo? De la misma manera: seleccionamos un elemento del medio en un subconjunto, colocamos este elemento en un nodo, obtenemos 2 subconjuntos más pequeños. Y así hasta que coloquemos todos los elementos de la matriz en los nodos del árbol.Por ejemplo, una matriz con los elementos [“q”, “w”, “e”, “r”, “t”, “y”, “u”] podría verse así: [el: r, size: 7]
/ : \
/ : \
[el: w, size: 3] : [el: y, size: 3]
/ : \ : / : \
/ : \ : / : \
[el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
El elemento del medio en la matriz "r", lo colocamos en el nodo raíz. Dos submatrices ["q", "w", "e"] y ["t", "y", "u"] se colocan en los subárboles izquierdo y derecho. Para esto, los elementos centrales se seleccionan de las submatrices, en nuestro caso son "w" e "y", y caen en los nodos del siguiente nivel. Y así sucesivamente.En nuestro caso, el árbol está equilibrado, la profundidad de todos los subárboles es la misma. Pero esto no tiene por qué ser así.En la imagen de arriba, cada nodo, además del elemento y los enlaces a los nodos izquierdo y derecho, contiene el número de elementos de todo el subárbol. Esta información debe actualizarse correctamente cuando cambie el árbol.Veamos cómo encontrar, por ejemplo, un elemento con índice = 4 en dicho árbol.Comenzamos el rastreo desde el nodo raíz (raíz, en nuestro caso con el elemento "r"). Tenemos 3 opciones: ya estamos en el nodo derecho, el nodo derecho a la izquierda, el nodo derecho a la derecha. Para comprender dónde buscar el elemento deseado, debe comparar el tamaño del subárbol izquierdo (en nuestro caso left.size = 3) y el índice actual (en nuestro caso 4). Si estos 2 números son iguales, entonces encontramos el nodo necesario y el elemento deseado en él. Si el tamaño del subárbol izquierdo es mayor, entonces el nodo requerido en el subárbol izquierdo. Si es menor, entonces debe buscar en el subárbol correcto, pero debe reducir el índice deseado: index = index - left.size - 1.Dado que en nuestro caso left.size <index, estamos buscando en el subárbol derecho el elemento con el nuevo índice 4 - 3 - 1 = 0. Mover al nodo con el elemento "y".Luego hacemos lo mismo que hicimos en el nodo raíz. Compare left.size e index. Como 1> 0, miramos en el subárbol izquierdo, nos movemos al nodo con el elemento "t".No hay subárbol izquierdo en este nodo, y su tamaño es 0. index = left.size, lo que significa que encontramos un nodo con índice 4 y podemos obtener el elemento "t" requerido.En pseudocódigo, se ve más o menos así:function get(node: Node<T>, index: int): T {
val leftSize: int = (node.left == null) ? 0 : node.left.size;
if (leftSize == index) {
return node.obj;
} else if (leftSize > index) {
return get(node.left, index);
} else {
return get(node.right, index — leftSize — 1);
}
}
Traté de describir el principio clave de cómo poner una matriz en un árbol. Tal estructura funciona, por supuesto, más lenta que la matriz clásica, para O (log (n)) versus O (1). Pero tiene una ventaja importante: agregar un elemento al medio o eliminarlo del medio también funciona para O (log (n)) versus O (n) para la matriz. Por supuesto, siempre que el árbol esté más o menos equilibrado. Existen muchos algoritmos para mantener un árbol de forma casi equilibrada. Por ejemplo, árbol rojo-negro, árbol AVL, árbol cartesiano. No escribiré los detalles del equilibrio del árbol, cualquier algoritmo es adecuado para nosotros. Supongamos que el árbol está equilibrado en promedio y su profundidad máxima no es muy diferente de la mínima.Ligera optimización
El enfoque descrito anteriormente, con la comprobación del tamaño del árbol a la izquierda, es conveniente para la percepción, pero se puede hacer un poco más eficientemente. Para no mirar cada vez el subárbol izquierdo, en lugar del tamaño del árbol, se puede almacenar en el nodo su posición en relación con la posición de su nodo padre. El nodo raíz almacena una posición absoluta que coincide con el tamaño del subárbol izquierdo. [el: r, pos: 3]
/ : \
/ : \
[el: w, pos: -2] : [el: y, pos: +2]
/ : \ : / : \
/ : \ : / : \
[el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
Por ejemplo, el nodo raíz "r" tiene una posición de 3. El nodo "w" tiene una posición de -2 en relación con el nodo principal o la posición absoluta de 3 + (-2) = 1. Del mismo modo, puede bajar un nivel más, por ejemplo, el nodo "e" tiene una posición de 3 + (-2) + (+1) = 2. Es decir, El índice de nodo es la suma de las posiciones desde la raíz del árbol hasta este nodo.Esta optimización, además de una búsqueda más rápida de un elemento en la lista, proporcionará una búsqueda más rápida y fácil del índice en el nodo. Pero, por supuesto, actualizar la posición correctamente al cambiar el árbol se ha vuelto un poco más difícil.Agregar indexación
Entonces, en el árbol podemos tomar un elemento por índice, cambiar su valor, agregar elementos al medio y eliminar. Esencialmente, solo necesitamos agregar una búsqueda rápida de índice por valor, indexOf (obj). Luego contiene (obj) y eliminar (obj) se resolverá trivialmente.Pero primero, simplifiquemos un poco la tarea. Hagamos una estructura que almacene solo elementos únicos.Para buscar rápidamente algo, generalmente usan una tabla. En el mundo de Java, las tablas se llaman Map; tiene 2 implementaciones principales: HashMap y TreeMap. La clave de la tabla será un enlace al objeto, y el valor es un enlace a su nodo:class IndexedTreeListSet<T> {
root: Node<T>
indexMap: Map<T, Node<T>>
}
Aquellos. la estructura consta de dos partes: el árbol de la lista en sí y la tabla con enlaces a objetos y nodos de este árbol. Al actualizar el árbol, la tabla también debe actualizarse. No describiré el proceso en detalle. Intuitivamente, debería ser comprensible: agregue un nodo - póngalo en la tabla, elimine el nodo - elimínelo de la tabla. En la práctica, hay matices con el equilibrio del árbol: el algoritmo debe cambiar los enlaces entre nodos y no mover objetos entre nodos. De lo contrario, tendrá que hacer muchas actualizaciones en la tabla y el rendimiento disminuirá.Ok, asumiremos que podemos encontrar rápidamente el nodo por el elemento que contiene. ¿Y qué? Necesitamos encontrar su índice, pero esto aún no se puede hacer. Pero podemos complicar la clase de nodo para que contenga no solo enlaces a los nodos izquierdo y derecho, sino también a su padre:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
parent: Node<T>
pos: int
}
Por supuesto, actualizar el árbol es un poco más complicado, porque ahora necesitamos actualizar cuidadosamente el enlace al padre. Pero ahora, conociendo el nodo, podemos subir el árbol y calcular el índice de cualquier nodo. Si utilizamos la optimización del capítulo anterior, entonces solo tenemos que calcular la suma de las posiciones desde el nodo actual hasta la raíz.Para una lista que contiene elementos únicos, el problema puede considerarse resuelto.Es cierto que tenemos un pequeño problema. Supongamos que llamamos set (index, obj). Podemos reemplazar fácilmente un elemento en un nodo con otro, pero solo si todavía no hay un elemento nuevo en la lista. Y si es así, ¿qué debo hacer? ¿Eliminar el elemento sobrante de la posición anterior y colocar uno nuevo? O viceversa, ¿primero agregar y luego eliminar? El resultado puede ser diferente. Y no puede hacer nada en absoluto o lanzar una excepción. No hay una solucion perfecta.Ordenar por métodos estándar, tal lista, muy probablemente, tampoco funcionará. Después de todo, el algoritmo de clasificación no sabrá acerca de la necesidad de unicidad de los objetos y creará duplicados al mover elementos en la lista.Eliminamos la unicidad
Ok, complicando aún más las cosas, conservemos los mismos objetos. Obviamente, necesitas hacer algo con la mesa. La primera idea para almacenar una lista de nodos en ella no parece muy buena: con un aumento en la longitud de la lista, el rendimiento disminuirá. Hasta O (n) si todos los elementos de la lista son iguales.Luego, intentemos almacenar un árbol ordenado de nodos en una tabla en lugar de una lista. Ordenado por posición en la lista.class IndexedTreeList<T> {
root: Node<T>
indexMap: Map<T, TreeSet<Node<T>>>
}
Luego, la inserción / eliminación a / del TreeSet <Node> de tamaño m se producirá durante las comparaciones log (m) de las posiciones de los nodos, y cada comparación se producirá durante el tiempo log (n). La complejidad final de insertar o eliminar en una estructura similar ocurrirá en O (log (n) * (1 + log (m))), donde n es el número total de elementos en la lista ym es el número de elementos en la lista igual al insertado / eliminado. En el peor de los casos, cuando todos los elementos son iguales entre sí, obtenemos la complejidad O (log (n) ^ 2).Un lector atento probablemente objetará: pero ¿qué pasa con la inmutabilidad? Después de todo, ¿no podemos cambiar los objetos si son claves de tabla? En general lo es. Sin embargo, para un árbol que almacena objetos ordenados en claves, además de las reglas estándar para las comparaciones, es suficiente preservar la invariante: si a <b, entonces esta propiedad no debería cambiar con el tiempo. Este es solo nuestro caso: si la posición de un nodo es menor que la posición de otro nodo, esta propiedad se conservará independientemente de cuántos nodos se hayan agregado o eliminado entre ellos.¿Es posible hacer que la estructura sea persistente?
Respuesta corta: no, es imposible. Debido a la biconconexión del árbol, desde la raíz hasta las hojas y viceversa, tenemos cada nodo del árbol conectado a cada uno. La persistencia no se puede hacer de esta manera; hay que recrear toda la estructura con cualquier cambio.Pero entiendo cómo implementar una estructura persistente para los casos en los que no necesitamos insertar elementos en el medio de la lista. Puede agregar elementos al principio o al final, y puede eliminarlos del medio. Las propiedades restantes son las mismas.Si está interesado, intentaré escribir un artículo sobre esta estructura. Quizás incluso lo implemente en Java, Kotlin o Scala. Pero, lo más probable, no será pronto.Algunas características de implementación
Aquí quiero describir algunas características que tuve que enfrentar.Sobre una de las optimizaciones sobre el almacenamiento de la posición del nodo en la lista, escribí anteriormente. La fuerza del código abierto se manifiesta aquí: tomé el código TreeList listo y no profundicé en los detalles del árbol AVL, los giros de nodos, las actualizaciones de posición, etc.Otra característica heredada de TreeList son los enlaces a subárboles en las hojas de los árboles. Cada nodo almacena el valor booleano leftIsPrevious y rightIsNext. Estas variables indican la presencia o ausencia de un subárbol izquierdo / derecho. Si no hay un subárbol, entonces en izquierda / derecha, en lugar de un enlace al subárbol, se almacena un enlace al nodo que corresponde al elemento anterior o siguiente. En nuestro ejemplo, [“q”, “w”, “e”, “r”, “t”, “y”, “u”] el nodo “e” es frondoso, no tiene subárboles. En consecuencia, leftIsPrevious y rightIsNext son verdaderos, y los puntos left y right apuntan a los nodos "w" y "r", respectivamente. Este enfoque ayuda a recorrer la lista más rápido. E interfiere con la programación de nuevas características :)Un poco sobre trabajar con la tabla objeto → nodo. Idealmente, debe colocar un elemento en la tabla una vez al agregarlo a la estructura y eliminarlo una vez al eliminarlo de la estructura. En la práctica, no pude lograr esto. Cuando agrega un elemento, se agrega a la tabla, todo está como debería. Sin embargo, cuando elimina un elemento, el algoritmo de equilibrio a veces mueve elementos entre nodos. El resultado son dos eliminaciones y un registro en la tabla en lugar de una eliminación. Esto se puede solucionar si elimina la optimización de leftIsPrevious y rightIsNext. E incluso obtenga una pequeña ganancia de rendimiento, y no solo durante la eliminación. En algunas pruebas, el aumento fue del 10-20%. Pero la velocidad de iteración cae significativamente, 1.5-2.5 veces en mis pruebas. Decidí dejar la optimización por ahora.En Java, los principales tipos de tablas son HashMap y TreeMap. Para una tabla, un objeto → un nodo usa HashMap de forma predeterminada. Sin embargo, puede usar TreeMap con un comparador específico de tareas. En este caso, indexOf (obj) y remove (obj) buscarán / eliminarán el objeto que sea igual al objeto especificado de acuerdo con el código del comparador. Por ejemplo, almacenamos una lista de usuarios, y el comparador compara a los usuarios solo por su nombre. Entonces podemos responder a la pregunta "¿Qué posiciones de la lista son usuarios con el nombre 'Napoleón?'". O elimine todos los Napoleones de la lista :).La estructura no admite nulo. Puede arreglarlo, pero no se siente que sea necesario.En cuanto al hecho de que la estructura "lo sabe todo", yo, por supuesto, fui un poco engañoso. Por supuesto, cuando se trabaja con elementos individuales, todo está bien y bajo ciertas condiciones, incluso para el logaritmo. Sin embargo, ella no sabe algunas cosas que otras estructuras pueden. Por ejemplo, un árbol cartesiano con una clave implícita, había artículos sobre él en el centro No sabe cómo hacer indexOf rápidamente, pero sabe cómo hacer una sublista y concatenar dos listas en una para el logaritmo (en promedio, no garantizado), además puede hacerse persistente.Actuación
En Java, el rendimiento generalmente se mide utilizando el marco jmh. Las pruebas se realizaron en el MacBook Pro 2017 con Java11.Comparé el rendimiento de ArrayList estándar, TreeList de apache common-collections y mis dos clases IndexedTreeList e IndexedTreeListSet en varios escenarios. En cada escenario, se realizaron 1000 operaciones del mismo tipo, por lo que el resultado debería multiplicarse por 1000.Código bajo el spoiler@Fork(1)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public class PerformanceCompare {
public static final Map<String, Class> CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,
ArrayList.class)
.collect(Collectors.toMap(c -> c.getSimpleName(), c -> c));
public static final int ITERATIONS = 1000;
@State(Scope.Benchmark)
public static class Plan {
@Param({"10", "100", "1000", "10000", "100000", "1000000"/*, "10000000"*/})
public int size;
@Param({"ArrayList", "TreeList", "IndexedTreeList", "IndexedTreeListSet"})
public String className;
private Random random;
private List<Integer> list;
@Setup
public void init() throws IllegalAccessException, InstantiationException {
random = new Random();
list = (List<Integer>) CLASSES.get(className).newInstance();
for (int i = 0; i < size; i++) {
list.add(i);
}
}
}
@Benchmark
public void indexOfKnown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value = list.indexOf(random.nextInt(plan.size));
}
blackhole.consume(value);
}
@Benchmark
public void indexOfUnknown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.indexOf(random.nextInt());
}
blackhole.consume(value);
}
@Benchmark
public void addRemoveRandom(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
list.add(random.nextInt(list.size() + 1), random.nextInt());
value += list.remove(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Benchmark
public void get(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.get(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(PerformanceCompare.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
Para empezar, comparé la velocidad de obtener un elemento aleatorio de una lista. Te advertiré de inmediato que en esta prueba la sobrecarga es muy significativa. Los resultados que se aproximan a 100,000 * 1,000 operaciones por segundo están severamente distorsionados.Obtener resultado de la pruebaPerformanceCompare.get ArrayList 10 thrpt 5 79865.412 ± 10145.202 ops/s
PerformanceCompare.get ArrayList 100 thrpt 5 81862.243 ± 983.727 ops/s
PerformanceCompare.get ArrayList 1000 thrpt 5 81033.507 ± 4540.206 ops/s
PerformanceCompare.get ArrayList 10000 thrpt 5 64096.123 ± 1430.361 ops/s
PerformanceCompare.get ArrayList 100000 thrpt 5 41289.491 ± 11286.114 ops/s
PerformanceCompare.get ArrayList 1000000 thrpt 5 8598.944 ± 2048.461 ops/s
PerformanceCompare.get TreeList 10 thrpt 5 33912.275 ± 3754.284 ops/s
PerformanceCompare.get TreeList 100 thrpt 5 21346.854 ± 863.588 ops/s
PerformanceCompare.get TreeList 1000 thrpt 5 14808.414 ± 508.098 ops/s
PerformanceCompare.get TreeList 10000 thrpt 5 8679.384 ± 109.250 ops/s
PerformanceCompare.get TreeList 100000 thrpt 5 4605.998 ± 1028.945 ops/s
PerformanceCompare.get TreeList 1000000 thrpt 5 2241.381 ± 768.147 ops/s
PerformanceCompare.get IndexedTreeList 10 thrpt 5 34054.357 ± 3682.829 ops/s
PerformanceCompare.get IndexedTreeList 100 thrpt 5 21934.002 ± 2339.947 ops/s
PerformanceCompare.get IndexedTreeList 1000 thrpt 5 14626.691 ± 369.893 ops/s
PerformanceCompare.get IndexedTreeList 10000 thrpt 5 7386.863 ± 342.150 ops/s
PerformanceCompare.get IndexedTreeList 100000 thrpt 5 4562.126 ± 352.772 ops/s
PerformanceCompare.get IndexedTreeList 1000000 thrpt 5 2105.718 ± 702.064 ops/s
PerformanceCompare.get IndexedTreeListSet 10 thrpt 5 33317.503 ± 2307.829 ops/s
PerformanceCompare.get IndexedTreeListSet 100 thrpt 5 21247.440 ± 1253.386 ops/s
PerformanceCompare.get IndexedTreeListSet 1000 thrpt 5 14665.557 ± 487.833 ops/s
PerformanceCompare.get IndexedTreeListSet 10000 thrpt 5 7667.214 ± 80.093 ops/s
PerformanceCompare.get IndexedTreeListSet 100000 thrpt 5 3454.023 ± 82.994 ops/s
PerformanceCompare.get IndexedTreeListSet 1000000 thrpt 5 1768.701 ± 35.878 ops/s
Aquí, curiosamente, el mayor interés es la ArrayList estándar. Teóricamente, la velocidad de salida debe ser constante y no depender del número de elementos. En la práctica, el rendimiento inicialmente contiene alrededor de 90,000 * 1000 operaciones por segundo (recuerde la sobrecarga), pero con una longitud de lista de varios miles de elementos, comienza a ceder. Esto se debe a la falta de memoria caché cada vez más frecuente: la memoria caché del procesador no tiene los datos necesarios y, cada vez más, debe buscar datos en la RAM. Con un millón de elementos, la velocidad de la prueba es 10 veces menor, pero en la práctica, la reducción del rendimiento es aún mayor.TreeList, IndexedTreeList e IndexedTreeListSet esperan resultados similares. Se esperaba mucho más lento que ArrayList. Incluso con una pequeña cantidad de elementos, TreeList es varias veces más lento que ArrayList, aunque la prueba muestra la diferencia solo 2 veces.La siguiente prueba es addRemoveRandom. Aquí, en cada prueba, inserto un elemento en una posición aleatoria y elimino un elemento de una posición aleatoria.Resultado de la prueba AddRemoveRandomPerformanceCompare.addRemoveRandom ArrayList 10 thrpt 5 12440.764 ± 485.642 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100 thrpt 5 9880.123 ± 464.014 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000 thrpt 5 5288.905 ± 1219.055 ops/s
PerformanceCompare.addRemoveRandom ArrayList 10000 thrpt 5 1024.942 ± 179.366 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100000 thrpt 5 91.219 ± 25.380 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000000 thrpt 5 5.499 ± 0.400 ops/s
PerformanceCompare.addRemoveRandom TreeList 10 thrpt 5 6242.607 ± 350.290 ops/s
PerformanceCompare.addRemoveRandom TreeList 100 thrpt 5 3117.945 ± 116.066 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000 thrpt 5 1829.778 ± 80.516 ops/s
PerformanceCompare.addRemoveRandom TreeList 10000 thrpt 5 1230.077 ± 53.381 ops/s
PerformanceCompare.addRemoveRandom TreeList 100000 thrpt 5 443.571 ± 69.207 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000000 thrpt 5 308.963 ± 84.077 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10 thrpt 5 3556.511 ± 144.596 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100 thrpt 5 2120.777 ± 83.848 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000 thrpt 5 1211.112 ± 92.288 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10000 thrpt 5 789.458 ± 19.450 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100000 thrpt 5 302.989 ± 40.030 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000000 thrpt 5 178.822 ± 92.853 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10 thrpt 5 4138.007 ± 119.943 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100 thrpt 5 2435.803 ± 20.276 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000 thrpt 5 1445.054 ± 276.909 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10000 thrpt 5 972.256 ± 19.987 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100000 thrpt 5 366.608 ± 94.487 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000000 thrpt 5 227.677 ± 48.276 ops/s
Se podría suponer que ArrayList es más rápido en listas pequeñas. Sin embargo, el hecho de que gane en esta prueba en listas de hasta 10,000 elementos parece interesante. Aparentemente, System.arrayCopy está muy bien optimizado y utiliza todas las características de los procesadores modernos. A partir de 10.000 elementos, las estructuras de datos especializadas comienzan a ganar. Con 1,000,000 de elementos, la diferencia de velocidad es de 30-50 veces.Se espera que IndexedTreeList e IndexedTreeListSet sean más lentas que TreeList. Aproximadamente 1.5 - 2 veces.Las 2 pruebas restantes indexOfKnown e indexOfUnknown deberían demostrar la característica principal de esta estructura. La diferencia entre las pruebas es que en un caso estamos buscando un elemento que está en la lista, y en el otro caso estamos buscando un elemento que no esté en la lista.Resultado de la prueba indexOfKnown e indexOfUnknownPerformanceCompare.indexOfKnown ArrayList 10 thrpt 5 41424.356 ± 549.047 ops/s
PerformanceCompare.indexOfKnown ArrayList 100 thrpt 5 17216.477 ± 1444.744 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000 thrpt 5 2296.306 ± 76.372 ops/s
PerformanceCompare.indexOfKnown ArrayList 10000 thrpt 5 233.863 ± 26.926 ops/s
PerformanceCompare.indexOfKnown ArrayList 100000 thrpt 5 23.208 ± 2.776 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000000 thrpt 5 0.919 ± 0.455 ops/s
PerformanceCompare.indexOfKnown TreeList 10 thrpt 5 26740.708 ± 1323.125 ops/s
PerformanceCompare.indexOfKnown TreeList 100 thrpt 5 5670.923 ± 99.638 ops/s
PerformanceCompare.indexOfKnown TreeList 1000 thrpt 5 745.408 ± 26.827 ops/s
PerformanceCompare.indexOfKnown TreeList 10000 thrpt 5 52.288 ± 1.362 ops/s
PerformanceCompare.indexOfKnown TreeList 100000 thrpt 5 4.224 ± 0.855 ops/s
PerformanceCompare.indexOfKnown TreeList 1000000 thrpt 5 0.193 ± 0.052 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10 thrpt 5 34485.128 ± 1582.703 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100 thrpt 5 29209.412 ± 1544.268 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000 thrpt 5 21139.584 ± 1442.867 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10000 thrpt 5 12544.306 ± 312.097 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100000 thrpt 5 3538.201 ± 272.537 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000000 thrpt 5 1420.119 ± 538.476 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10 thrpt 5 39201.995 ± 1887.065 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100 thrpt 5 34204.112 ± 1122.517 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000 thrpt 5 25374.557 ± 1596.746 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10000 thrpt 5 14291.317 ± 391.180 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100000 thrpt 5 4215.898 ± 283.680 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000000 thrpt 5 1729.100 ± 1260.815 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10 thrpt 5 59053.313 ± 1845.665 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100 thrpt 5 10867.572 ± 142.823 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000 thrpt 5 1186.583 ± 28.003 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10000 thrpt 5 120.953 ± 4.146 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100000 thrpt 5 11.936 ± 0.320 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000000 thrpt 5 0.566 ± 0.335 ops/s
PerformanceCompare.indexOfUnknown TreeList 10 thrpt 5 28134.237 ± 2291.670 ops/s
PerformanceCompare.indexOfUnknown TreeList 100 thrpt 5 3153.930 ± 158.734 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000 thrpt 5 322.383 ± 44.245 ops/s
PerformanceCompare.indexOfUnknown TreeList 10000 thrpt 5 25.674 ± 1.787 ops/s
PerformanceCompare.indexOfUnknown TreeList 100000 thrpt 5 1.867 ± 0.291 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000000 thrpt 5 0.093 ± 0.008 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10 thrpt 5 66625.126 ± 5232.668 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100 thrpt 5 70038.055 ± 5803.848 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000 thrpt 5 63240.467 ± 885.956 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10000 thrpt 5 54731.988 ± 3950.150 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100000 thrpt 5 22049.476 ± 821.924 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000000 thrpt 5 9459.862 ± 804.738 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10 thrpt 5 70274.968 ± 15830.355 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100 thrpt 5 71017.685 ± 6920.447 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000 thrpt 5 66405.960 ± 1127.231 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10000 thrpt 5 57983.963 ± 3276.142 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100000 thrpt 5 41277.110 ± 9919.893 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000000 thrpt 5 9840.185 ± 2159.352 ops/s
Aquí, ArrayList y TreeList casi no tienen sorpresas. Con el aumento de tamaño, la velocidad disminuye casi linealmente. No se espera que la búsqueda de un elemento de una lista sea 2 veces más lenta que la búsqueda de un elemento de una lista, porque necesita pasar por toda la matriz en lugar de la mitad en promedio.Pero IndexedTreeList e IndexedTreeListSet aquí muestran el buen resultado esperado. Estas estructuras de datos muestran una velocidad de ejecución indexOf comparable a ArrayList incluso con 10 elementos. Con 1000 elementos, estas estructuras son 10 veces más rápidas, con 1,000,000 más rápidas 1000 veces. Al buscar un elemento que no está en la lista, se espera que den una mejor velocidad que cuando se busca un elemento de la lista.A lo que es interesante prestar atención es a la subsidencia del rendimiento de IndexedTreeList e IndexedTreeListSet en la prueba indexOfUnknown. Aquí la situación es similar a la de la prueba con ArrayList.get. Teóricamente, no deberíamos haber tenido una caída en el rendimiento, pero en la práctica, debido a la pérdida de caché, lo hemos conseguido, además, de manera significativa.En lugar de una conclusión
Todavía no sé si la estructura propuesta tiene una novedad o no. Por un lado, la idea no es complicada si sabes cómo funciona el árbol con una clave implícita. Por otro lado, no he visto una descripción de una estructura con tales propiedades. Y si es así, entonces tiene sentido hacer que la estructura sea más famosa, podría ser útil para alguien.Pero incluso si esta es otra bicicleta, traté de hacerla útil. Se ha creado una solicitud de extracción en colecciones comunes, pero al momento de escribir este artículo aún no se ha vertido. Sabiendo lo lento que puede pasar todo en código abierto, no me sorprenderá si el proceso se prolonga durante meses.Algo sorprendido por el resultado de comparar el rendimiento de ArrayList y TreeList. Las pruebas mostraron que TreeList no tiene sentido usar hasta 10,000 elementos en el tamaño de la lista. Sería interesante probar b-tree en lugar de un árbol binario. Esta estructura debería usar la memoria con más cuidado y, lo más probable, trabajar más rápido. Y para ello puedes adaptar la idea con indexación.En cualquier caso, es divertido tener un instrumento en el arsenal que pueda (casi) hacer todo con una complejidad predecible.Referencias
Proyecto original de
solicitud de extracción en Apache Common-CollectionsTicket en Jira