Matriz que puede redimensionarse rápidamente

Question

Estoy buscando un tipo de tipo de datos de matriz que pueda agregar fácilmente elementos, sin afectar el rendimiento.

• Sistema. Matriz - Redim Preserve copia toda la RAM de la antigua a la nueva, tan lenta como la cantidad de elementos existentes
• System.Collections. ArrayList - ¿suficientemente bueno?
• System.Collections. IList - ¿suficientemente bueno?

Answer 1

Solo para resumir algunas estructuras de datos:

System.Collections.ArrayList : las estructuras de datos sin tipo son obsoletas. Utilice la Lista (de t) en su lugar.

System.Collections.Generic.List (of t) : esto representa una matriz redimensionable. Esta estructura de datos utiliza una matriz interna detrás de escena. Agregar elementos a la Lista es O (1) siempre que la matriz subyacente no se haya llenado; de lo contrario, es O (n + 1) para cambiar el tamaño de la matriz interna y copiar los elementos.

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

Agregar elementos solo es eficiente cuando se agrega al final de la lista. Insertar en el medio obliga a la matriz a desplazar todos los elementos hacia adelante, que es una operación O (n). Eliminar elementos también es O (n), ya que la matriz necesita desplazar los elementos hacia atrás.

System.Collections.Generic.LinkedList (of t) : si no necesita acceso aleatorio o indexado a los elementos de su lista, por ejemplo, solo planea agregar elementos e iterar desde el principio para durar, entonces un LinkedList es tu amigo. Las inserciones y eliminaciones son O (1), la búsqueda es O (n).

Answer 2

Debe usar la Lista genérica < > ( System.Collections.Generic.List ) para esto. Funciona en tiempo amortizado constante .

También comparte las siguientes características con matrices.

• Acceso aleatorio rápido (puede acceder a cualquier elemento de la lista en O (1))
• Es rápido dar la vuelta
• Lento para insertar y eliminar objetos en el inicio o en el medio (ya que tiene que hacer una copia de toda la lista)

Si necesita inserciones y eliminaciones rápidas al principio o al final, use listas vinculadas o colas

Answer 3

¿La LinkedList < T & Gt; estructura de trabajo para usted? No es (en algunos casos) tan intuitivo como una matriz directa, pero es muy rápido.

• AddLast para agregar hasta el final
• AddBefore / AddAfter para insertar en la lista
• AddFirst para agregar al principio

Sin embargo, no es tan rápido para el acceso aleatorio, ya que debe iterar sobre la estructura para acceder a sus elementos ... sin embargo, tiene los métodos .ToList () y .ToArray () para obtener una copia de la estructura en la lista / array, por lo que para el acceso de lectura, puede hacerlo en un apuro. El aumento del rendimiento de las inserciones puede superar la disminución del rendimiento de la necesidad de acceso aleatorio o no. Dependerá completamente de su situación.

También existe esta referencia que lo ayudará a decidir cuál es el camino correcto:

Cuándo usar una lista vinculada una matriz / lista de matriz?

Answer 4

¿Qué es " suficientemente bueno " ¿para ti? ¿Qué es exactamente lo que quieres hacer con esa estructura de datos?

Ninguna estructura de matriz (es decir, acceso O (n)) permite la inserción en el medio sin un tiempo de ejecución O (n); la inserción al final es O (n) en el peor de los casos, un O (1) amortizado para arreglos de cambio de tamaño como ArrayList.

Quizás las tablas hash (acceso e inserción amortizados de O (1) en cualquier lugar, pero O (n) peor caso para la inserción) o árboles (O (log (n)) para acceso e inserción en cualquier lugar, garantizado) son más adecuados.

Answer 5

Si la velocidad es su problema, no veo cómo la respuesta seleccionada es mejor que usar una matriz sin formato, aunque cambia de tamaño, usa el mismo mecanismo que usaría para cambiar el tamaño de una matriz (y debería tomar solo un toque más) A MENOS QUE siempre esté agregando al final, en cuyo caso debería hacer las cosas un poco más inteligentes porque asigna un fragmento a la vez en lugar de solo un elemento.

Si a menudo agrega cerca del principio / medio de su colección y no indexa en el medio / final muy a menudo, probablemente desee una Lista vinculada. Eso tendrá el tiempo de inserción más rápido y tendrá un gran tiempo de iteración, simplemente apesta en la indexación (como mirar el tercer elemento desde el final o el 72. ° elemento).