c++ - length - matriz vs vector vs lista

array.length c++ (7)

Estoy manteniendo una tabla de longitud fija de 10 entradas. Cada elemento es una estructura de 4 campos similares. Habrá operaciones de inserción, actualización y eliminación, especificadas por posición numérica. Me pregunto cuál es la mejor estructura de datos para usar para mantener esta tabla de información:

Según esta descripción, parece que la lista podría ser la mejor opción ya que es O (1) al insertar y eliminar en el medio de la estructura de datos. Lamentablemente, no puede utilizar las posiciones numéricas cuando utiliza listas para hacer inserciones y elimina como puede para matrices / vectores. Este dilema conduce a una gran cantidad de preguntas que se pueden utilizar para tomar una decisión inicial sobre qué estructura es la mejor para usar. Esta estructura puede cambiarse más adelante si las pruebas muestran claramente que es una elección incorrecta.

Las preguntas que debe hacer son tres veces. La primera es la frecuencia con la que planeas hacer eliminaciones / inserciones en el medio en relación con las lecturas aleatorias. El segundo es qué tan importante es usar una posición numérica en comparación con un iterador. Finalmente, es importante el orden en su estructura.

Si la respuesta a la primera pregunta es aleatoria, las lecturas serán más frecuentes que un vector / matriz probablemente funcione bien. Nota: iterar a través de una estructura de datos no se considera una lectura aleatoria, incluso si se usa la notación del operador []. Para la segunda pregunta, si requiere absolutamente una posición numérica, se necesitará un vector / matriz, aunque esto puede llevar a un golpe de rendimiento. Las pruebas posteriores pueden mostrar que este golpe de rendimiento es insignificante en relación con la codificación más fácil con posiciones numéricas. Finalmente, si el orden no es importante, puede insertar y eliminar en un vector / matriz con un algoritmo O (1). Un algoritmo de muestra se muestra a continuación.

template <class T> void erase(vector<T> & vect, int index) //note: vector cannot be const since you are changing vector { vect[index]= vect.back();//move the item in the back to the index vect.pop_back(); //delete the item in the back } template <class T> void insert(vector<T> & vect, int index, T value) //note: vector cannot be const since you are changing vector { vect.push_back(vect[index]);//insert the item at index to the back of the vector vect[index] = value; //replace the item at index with value }

Estoy manteniendo una tabla de longitud fija de 10 entradas. Cada elemento es una estructura de 4 campos similares. Habrá operaciones de inserción, actualización y eliminación, especificadas por posición numérica. Me pregunto cuál es la mejor estructura de datos para usar para mantener esta tabla de información:

array - insertar / eliminar toma tiempo lineal debido al desplazamiento; la actualización toma tiempo constante; no se usa espacio para punteros; acceder a un elemento usando [] es más rápido.
vector stl - insertar / eliminar toma tiempo lineal debido al desplazamiento; la actualización toma tiempo constante; no se usa espacio para punteros; el acceso a un elemento es más lento que una matriz, ya que es una llamada al operador [] y una lista vinculada.
stl list - insertar y eliminar lleva tiempo lineal ya que necesita iterar a una posición específica antes de aplicar la inserción / eliminación; se necesita espacio adicional para los punteros; el acceso a un elemento es más lento que una matriz, ya que es un recorrido lineal de la lista enlazada.

En este momento, mi elección es usar una matriz. ¿Es justificable? ¿O me perdí algo?

¿Qué es más rápido: atravesar una lista, luego insertar un nodo o desplazar elementos en una matriz para producir una posición vacía y luego insertar el elemento en esa posición?

¿Cuál es la mejor manera de medir este rendimiento? ¿Puedo mostrar la marca de tiempo antes y después de las operaciones?

Está haciendo suposiciones que no debería estar haciendo, como "el acceso a un elemento es más lento que una matriz, ya que es una llamada al operador []". Puedo entender la lógica detrás de esto, pero ni tú ni yo podemos saber hasta que lo perfilemos.

Si lo haces, verás que no hay gastos generales, cuando las optimizaciones están activadas. El compilador enumera las llamadas de función. Hay una diferencia en el rendimiento de la memoria. Una matriz está asignada estáticamente, mientras que un vector asigna dinámicamente. Una lista asigna por nodo, lo que puede acelerar el caché si no tiene cuidado.

Algunas soluciones son hacer que el vector asigne desde la pila, y tener un asignador de agrupaciones para una list , de modo que los nodos puedan caber en la memoria caché.

Por lo tanto, en lugar de preocuparse por reclamos no admitidos, debe preocuparse por hacer que su diseño sea lo más limpio posible. Entonces, ¿qué tiene más sentido? ¿Una matriz, vector o lista? No sé lo que estás tratando de hacer, así que no puedo responderte.

El contenedor "predeterminado" tiende a ser un vector . A veces, una matriz también es perfectamente aceptable.

Prefiere un std :: vector over y array. Algunas ventajas del vector son:

Asignan memoria desde el espacio libre al aumentar de tamaño.
NO son un puntero disfrazado.
Pueden aumentar / disminuir el tiempo de ejecución de tamaño.
Pueden hacer una comprobación de rango usando at () .
Un vector conoce su tamaño, por lo que no tiene que contar elementos.

La razón más convincente para usar un vector es que lo libera de la gestión explícita de la memoria y no pierde memoria. Un vector realiza un seguimiento de la memoria que utiliza para almacenar sus elementos. Cuando un vector necesita más memoria para los elementos, asigna más; cuando un vector sale del alcance, libera esa memoria. Por lo tanto, el usuario no necesita preocuparse por la asignación y desasignación de memoria para elementos vectoriales.

Primero un par de notas:

Una buena regla general sobre la selección de estructuras de datos: en general, si examinó todas las posibilidades y determinó que una matriz es su mejor opción, comience nuevamente. Hiciste algo muy mal.

Las listas STL no son compatibles con el operator[] y, si lo hicieran, la razón por la que sería más lento que indexar una matriz no tiene nada que ver con la sobrecarga de una llamada a función.

Es decir, el vector es el claro ganador aquí. La llamada al operator[] es esencialmente insignificante ya que se garantiza que el contenido de un vector sea contiguo en la memoria. Es compatible con las operaciones de insert() y erase() que esencialmente tendría que escribir usted mismo si utilizó una matriz. Básicamente se reduce al hecho de que un vector es esencialmente una matriz actualizada que ya admite todas las operaciones que necesita.

Realmente vale la pena invertir algo de tiempo para comprender las diferencias fundamentales entre listas y vectores. La diferencia más significativa entre los dos es la forma en que almacenan los elementos y los rastrean.

- Listas -

La lista contiene elementos que tienen la dirección de un elemento anterior y siguiente almacenado en ellos. Esto significa que puede INSERTAR o ELIMINAR un elemento en cualquier lugar de la lista con velocidad constante O (1) independientemente del tamaño de la lista. También empalmes (inserte otra lista) en la lista existente en cualquier lugar con velocidad constante también. La razón es que la lista solo necesita cambiar dos punteros (el anterior y el siguiente) para el elemento que estamos insertando en la lista.

Las listas no son buenas si necesita acceso aleatorio. Entonces, si uno planea acceder al n-ésimo elemento en la lista, uno debe atravesar la lista uno por uno: O (n) velocidad

- Vectores -

El vector contiene elementos en secuencia, como una matriz. Esto es muy conveniente para el acceso aleatorio. El acceso al elemento "n" en un vector es un cálculo de puntero simple (velocidad O (1)). Agregar elementos a un vector es, sin embargo, diferente. Si uno quiere agregar un elemento en el medio de un vector, todos los elementos que vienen después de ese elemento tendrán que volver a asignarse para dejar espacio para la nueva entrada. La velocidad dependerá del tamaño del vector y de la posición del nuevo elemento. El peor de los casos es insertar un elemento en la posición 2 en un vector, el mejor es agregar un nuevo elemento. Por lo tanto, inserte trabajos con velocidad O (n), donde "n" es la cantidad de elementos que se deben mover, no necesariamente el tamaño de un vector.

Existen otras diferencias que implican requisitos de memoria, etc., pero realmente vale la pena dedicar algún tiempo a comprender estos principios básicos sobre cómo funcionan realmente las listas y los vectores.

Como siempre ... " La optimización prematura es la raíz de todo mal ", así que primero considere lo que es más conveniente y haga que las cosas funcionen exactamente como usted las quiere, y luego optimícelas. Para 10 entradas que mencione, realmente no importa lo que use, nunca podrá ver ningún tipo de diferencia de rendimiento sea cual sea el método que utilice.

La optimización prematura es la fuente de todos los males.

Según su publicación, diría que no hay ninguna razón para hacer que su elección de la estructura de datos aquí sea basada en el desempeño. Elija lo que sea más conveniente y regrese para cambiarlo si y solo si las pruebas de rendimiento demuestran que es un problema.

Use el vector STL . Proporciona una interfaz igualmente rica como list y elimina el dolor de administrar la memoria que las matrices requieren.

Deberá esforzarse mucho para exponer el costo de rendimiento del operator[] : generalmente se ingresa.

No tengo ningún número que darle, pero recuerdo haber leído un análisis de rendimiento que describía cómo vector<int> era más rápido que list<int> incluso para inserciones y eliminaciones (en un determinado tamaño de curso). La verdad del asunto es que estos procesadores que usamos son muy rápidos, y si su vector encaja en la memoria caché L2, entonces va a ser realmente muy rápido. Las listas, por otro lado, tienen que administrar los objetos del montón que matarán a tu L2.