Las listas enlazadas son terribles y no deben usarse excepto en casos muy especiales. Usted toma una gran penalización de rendimiento porque los nodos generalmente no se almacenan consecutivamente en la memoria, lo que destruye el rendimiento de su caché. En teoría, la inserción y eliminación son rápidas, pero en la práctica generalmente tiene que buscar la ubicación donde ocurrirá la inserción o eliminación, ¡y tal búsqueda lleva tiempo lineal! Entonces, a menos que tenga una situación especial (por ejemplo, puede conocer la ubicación de inserción / eliminación sin buscarla), las listas vinculadas son una muy mala opción.
¿Sabes qué más tiene tiempo de inserción y eliminación lineal? Vectores Sin embargo, a diferencia de una lista vinculada, tienen un excelente rendimiento de caché, lo que significa que en la práctica sus inserciones y eliminaciones son generalmente más rápidas. Además, puedes acceder a ellos al azar. Son fáciles de ordenar, y cuando se ordenan, puede usar la búsqueda binaria para buscar elementos. La mayoría de las veces, el código escrito con una lista vinculada funcionaría mejor y sería más fácil de escribir si utilizara un vector.
Una vez que el conjunto de datos es lo suficientemente grande como para la inserción y eliminación lineal para matar el rendimiento, debe pasar a un árbol binario equilibrado. Son difíciles de escribir, y la implementación adecuada de una puede llevar una semana o más, especialmente si no lo ha hecho antes. Tienen excelentes características de rendimiento, aunque no tan buenas como un vector para búsquedas o recorridos (debido tanto a la complejidad como al rendimiento de la memoria caché).
- ¿Qué libro sería mejor para aprender la estructura de datos para principiantes?
- ¿Cuál es el enfoque algorítmico para este problema de hackerrank?
- ¿Cuál es una explicación fácil de entender del algoritmo de Reddit?
- ¿Qué algoritmo se usa para escanear?
- ¿Hay alguna manera / hay algoritmos para dividir los caracteres chinos en radicales?
Si desea búsquedas rápidas utilizando múltiples criterios, debe considerar mantener los “datos” en un lugar y un “índice” en una estructura de datos diferente. Cada elemento en el índice se refiere a una entrada en la estructura de datos principal (con un puntero, referencia, iterador o índice, dependiendo de cómo almacene los datos principales; si es un vector C ++, los índices son el único método seguro). Luego puede ordenar cada índice de una manera diferente; por ejemplo, uno de ellos podría ordenarse por el nombre de sus datos de host, otro podría clasificarse por edad, otro por dirección, etc. Esto le permite obtener tiempos de búsqueda de inicio de sesión para múltiples tipos de búsqueda .
Tenga en cuenta que el uso de un índice también significa que su almacenamiento de datos centrales no necesita ser ordenado en absoluto, lo que hace que sea más fácil almacenar sus datos principales en un vector. Puede que tenga que ser creativo para permitir eliminaciones rápidas de este vector; considere cambiar el elemento para eliminarlo con la entrada final y luego abrir la parte posterior; si mantener la posición igual es importante (para preservar la validez del índice), considere agregar una lista de elementos “eliminados” que estén disponibles para su reutilización, y permita que el vector tenga “agujeros” en él.
Sobre el tema del vector frente al árbol binario, es bastante obvio que el vector ganará en pequeñas cantidades de datos (porque es muy simple y el rendimiento de la memoria caché tan bueno), pero el árbol ganará si tiene grandes cantidades de datos. Mi experiencia con C ++ es que el punto de equilibrio es de aproximadamente 5 kilobytes; más que eso, y deberías usar un árbol. Menos, y el vector normalmente será más rápido . Si el número de estudiantes en el índice será de alrededor de 1300 o menos, y si necesita 4 bytes en cada entrada de índice para referirse nuevamente al registro de datos principal, entonces mantener el índice como un vector superará a un árbol binario . Si tiene significativamente más estudiantes que eso, es probable que deba cambiar a un árbol para obtener el máximo rendimiento.
