C# Dictionary: acceso más rápido pero menos espacio en la memoria

Question

Quiero recibir algunos consejos sobre la mejor manera de almacenar y acceder con un espacio de memoria mínimo y un rendimiento de acceso máximo.

Por ejemplo. para cada vehículo, quiero guardar el modelo y el nombre.

tengo algunas ideas siguientes:

Opción 1:

Dictionary<string, Dictionary<string, string>> values = new Dictionary<string, Dictionary<string, string>>(); 
Dictionary<string, string> list = new Dictionary<string, string>(); 
list.Add("2001", "Jetta S"); 
list.Add("2002", "Jetta SE"); 
list.Add("2002", "Jetta LE"); 
values.Add("VolksWagen", list); 

Opción 2:

Dictionary<string, List<KeyValuePair<string, string>>> values2 = new Dictionary<string, List<KeyValuePair<string, string>>>(); 
<pre lang="xml">List<KeyValuePair<string, string>> list2 = new List<KeyValuePair<string, string>>(); 
list2.Add(new KeyValuePair<string, string>("2001", "Jetta S")); 
list2.Add(new KeyValuePair<string, string>("2002", "Jetta SE")); 
list2.Add(new KeyValuePair<string, string>("2002", "Jetta LE")); 
values2.Add("VolksWagen", list2); 

Opción 3:

Dictionary<string, List<string>> values1 = new Dictionary<string, List<string>>(); 
List<string> list1 = new List<string>(); 
list1.Add("2001:Jetta S"); 
list1.Add("2002:Jetta SE"); 
list1.Add("2002:Jetta LE"); 
values1.Add("VolksWagen", list1); 

• Opción 1: un acceso más rápido de la marca y el nombre pero la mayoría de memoria huella de
• Opción 2: acceso rápido de marca y nombre pero más memoria huella de
• Opción 3: Acceso lenta de marca y nombre (habría que analizar) pero menos huella de memoria

habría más de 1500 diccionarios como el anterior.

¿Se aprecian todas las sugerencias para un acceso más rápido pero con menos huella de memoria?

Gracias.

Answer 1

SortedList<TKey,TValue> es una lista plana (por lo que no enorme aumento en el consumo de memoria), que utiliza búsqueda binaria para el acceso - por lo O(log(n)) - por lo que no tan rápido como Dictionary<TKey,TValue> en O(1) - pero mucho mejor que un (u otra búsqueda lineal List<T>) al O(n).

Si desea acceso más rápido, necesita utilizar memoria adicional para una tabla hash.

Como nota lateral, SortedList<TKey,TValue> también permite un acceso eficiente por int index, que es difícil para SortedDictionary<TKey,TValue>, y prácticamente carece de sentido para Dictionary<TKey,TValue>.

Obviamente, en su escenario puede que tenga que combinar SortedList<,> con cualquiera de anidación o una clave compuesta - pero la OMI que va a ser su mejor ruta para conseguir un equilibrio de la memoria y el rendimiento de acceso. Se podría utilizar una tecla dedicada compuesto, es decir, un iummutablestruct con los miembros claves compuestas, anulando GetHashCode() y Equals, implementar IEquatable<T>, y para la clasificación: la implementación de IComparable y IComparable<T>.

Answer 2

No debe elegir su estructura de datos principalmente por "huella" de memoria sino por patrón de acceso: ¿Cuáles son las búsquedas más frecuentes que desea hacer, con qué frecuencia se actualizará la estructura y demás?

Si desea llenar la estructura una vez y luego buscar los autos por año de fabricación y construcción, el primer enfoque parece más razonable (y legible/comprensible).

Por cierto, dado que varios modelos se pueden lanzar en un año, probablemente debería usar un Dictionary<string, Dictionary<string, List<string>>>. Y si realmente es años que desea almacenar, no debe usar cadenas como claves sino Int16.

Answer 3

Cuando se habla de acceso en las estructuras de datos, es importante entender la diferencia entre leer acceso y escritura acceso. En cuanto al diccionario, obtendrá O(1) acceso a value por key vez, pero O(log(n)) escriba el tiempo, si no me equivoco. Si utiliza listas simples, siempre es O(1) para agregar, pero es O(n) para acceder a los datos. En cuanto a la huella de memoria, es prácticamente la misma: O(n) en el peor de los casos.

¿Cuántos valores necesita almacenar/acceder? De acuerdo con sus ejemplos de código,

Opción 1: es inapropiado:

list.Add("2002", "Jetta SE"); 
list.Add("2002", "Jetta LE"); 

Las claves deben ser únicas, por lo

Opción 2: Dictionary<string, List<KeyValuePair<string, string>>> es lo que necesita.

Answer 4

Se puede utilizar un Dictionary con NameValueCollection:

var values = new Dictionary<string, NameValueCollection>(); 
NameValueCollection list = new NameValueCollection(); 
list.Add("2001", "Jetta S"); 
list.Add("2002", "Jetta SE"); 
list.Add("2002", "Jetta LE"); 
values.Add("VolksWagen", list); 

O con Inicializadores de recogida:

var values = new Dictionary<string, NameValueCollection> 
    { 
     { "VolksWagen", new NameValueCollection 
      { 
       { "2001", "Jetta S" }, 
       { "2002", "Jetta SE" }, 
       { "2002", "Jetta LE" } 
      } 
     } 
    }; 

Aunque no soy un experto en la huella de la memoria, en mi humilde opinión esto le proporcionará el mejor patrón de acceso en este escenario particular