data-structures - ordered - merge two singly linked list in c++
Lista vinculada vs Vector (5)
En los últimos días me he estado preparando para mi primera entrevista telefónica para un trabajo de desarrollo de software. En la investigación de preguntas he llegado a este artículo.
Todo fue genial hasta que llegué a este pasaje.
"¿Cuándo usarías una lista vinculada contra un vector?"
Ahora, desde la experiencia y la investigación, se trata de dos estructuras de datos muy diferentes, una lista vinculada que es una matriz dinámica y un vector que es un punto 2d en el espacio. La única correlación que puedo ver entre los dos es si utiliza un vector como una lista vinculada, diga myVector(my value, pointer to neighbor)
¿Pensamientos?
Como una corrección en el tiempo Big O de inserción y eliminación dentro de una lista vinculada, si tiene un puntero que mantiene la posición del elemento actual y los métodos utilizados para moverlo por la lista, (como .moveToStart() , .moveToEnd() , .next() etc.), puede eliminar e insertar en tiempo constante.
No me gusta la respuesta número uno aquí, así que pensé en compartir una investigación real sobre esto realizada por Herb Sutter de Microsoft. Los resultados de la prueba fueron con hasta 100k elementos en un contenedor, pero también afirmaron que continuaría realizando una lista enlazada incluso en medio millón de entidades. A menos que planee que su contenedor tenga millones de entidades, su contenedor predeterminado para un contenedor dinámico debe ser el vector. Resumí más o menos lo que dice, pero también vincularé la referencia en la parte inferior:
"[Incluso si] preasigna los nodos dentro de una lista vinculada, eso le devuelve la mitad del rendimiento, pero sigue siendo peor [que un vector]. ¿Por qué? En primer lugar, es más espacio: la sobrecarga por elemento (es parte de la razón) - los punteros hacia adelante y hacia atrás involucrados dentro de una lista enlazada - pero también (y más importante) el orden de acceso. La lista enlazada tiene que atravesar para encontrar un punto de inserción, haciendo todo este puntero persiguiendo, que es el mismo Lo que el vector estaba haciendo, pero lo que realmente está ocurriendo es que los captadores previos son tan rápidos . Realizar recorridos lineales con datos que se asignan de manera eficiente dentro de la memoria (asignar y usar, por ejemplo, un vector de punteros que se define y se presenta), se superará Listas enlazadas en casi todos los escenarios ".
Sé que es un poco tarde para este interrogador, pero este es un video muy perspicaz de Bjarne Stroustrup (el inventor de C ++) sobre por qué debes evitar las listas enlazadas con hardware moderno. https://www.youtube.com/watch?v=YQs6IC-vgmo
Use vector a menos que "el tamaño de los datos sea grande" o "una garantía de seguridad fuerte es esencial".
el tamaño de los datos es grande : - la inserción del vector en el tiempo lineal medio toma (debido a la necesidad de barajar las cosas), pero otras son operaciones de tiempo constante (como atravesar el nodo n). Por lo tanto, no hay mucha sobrecarga si el tamaño de los datos es pequeño.
Según el "Libro de normas de codificación C ++ de Andrei Alexandrescu y Herb Sutter"
"El uso de un vector para listas pequeñas es casi siempre superior al uso de la lista. Aunque la inserción en la mitad de la secuencia es una operación de tiempo lineal para el vector y una operación de tiempo constante para la lista, el vector generalmente supera a la lista cuando los contenedores son relativamente pequeños debido a su mejor factor constante, y la ventaja Big-Oh de la lista no se activa hasta que el tamaño de los datos aumenta ".
La lista de garantía de seguridad sólida proporciona una garantía de seguridad sólida. http://www.cplusplus.com/reference/list/list/insert/
Vector es otro nombre para matrices dinámicas . Es el nombre utilizado para la estructura de datos de matriz dinámica en C ++ . Si tienes experiencia en Java puedes conocerlos con el nombre ArrayList . (Java también tiene una clase de colección antigua llamada Vector que no se usa hoy en día debido a problemas en la forma en que se diseñó).
Los vectores son buenos para el acceso de lectura aleatoria y para la inserción y eliminación en la parte posterior (lleva tiempo constante amortizado), pero son malos para las inserciones y eliminaciones en la parte frontal o en cualquier otra posición (tiempo lineal, según los elementos deben moverse). Los vectores generalmente se distribuyen de forma contigua en la memoria, por lo que atravesar uno es eficiente porque la memoria caché de la CPU se usa de manera efectiva.
Las listas enlazadas, por otro lado, son buenas para insertar y eliminar elementos en la parte delantera o trasera (tiempo constante), pero no son particularmente buenas para muchas otras cosas: por ejemplo, eliminar un elemento en un índice arbitrario en la mitad de la lista requiere tiempo lineal porque Primero debes encontrar el nodo. Por otro lado, una vez que haya encontrado un nodo en particular, puede eliminarlo o insertar un nuevo elemento después de él en un tiempo constante, algo que no puede hacer con un vector. Las listas enlazadas también son muy simples de implementar, lo que las convierte en una estructura de datos popular.