¿Cuál es la forma más eficiente de hacer tabla de consulta en C#

Question

Cuál es la forma más eficiente de hacer tabla de consulta en C#

Tengo una tabla de consulta. Algo así como

0 "Thing 1" 
1 "Thing 2" 
2 "Reserved" 
3 "Reserved" 
4 "Reserved" 
5 "Not a Thing" 

Así que si alguien quiere "la cosa 1" o "cosa 2" que pasan en 0 ó 1. Pero pueden pasar en algo más también. Tengo 256 de este tipo de cosas y tal vez 200 de ellas están reservadas.

Entonces, ¿cuál es la manera más eficiente de configurar esto?

• Una matriz de cadena o una variable de diccionario que obtiene todos los valores. Y luego tome el número entero y devuelva el valor en ese lugar.

Un problema que tengo con esta solución son todos los valores "Reservados". No quiero crear esos valores redundantes "reservados". O bien, puedo tener una declaración if en todos los lugares que están "reservados", pero ahora pueden ser solo 2-3, podrían ser 2-3, 40-55 y todos los lugares diferentes en el byte. Esta declaración if se volvería ingobernable rápidamente

• Mi otra opción que estaba pensando era una declaración de cambio. Y tendría todos los 50 valores conocidos y no cumpliría con los valores reservados.

Me pregunto si esto es mucho más procesamiento que crear una matriz de cadenas o un diccionario y simplemente devolver el valor apropiado.

• ¿Algo más? ¿Hay alguna otra manera de considerar?

Answer 1

var things = new Dictionary<int, string>(); 
things[0]="Thing 1"; 
things[1]="Thing 2"; 
things[4711]="Carmen Sandiego"; 

Answer 2

Si usted tiene un montón de valores reservados (actualmente no se utiliza) o si el rango de los valores enteros puede ser muy grande, entonces me gustaría utilizar un diccionario genérico (Diccionario):

var myDictionary = new Dictionary<int, string>(); 
myDictionary.Add(0, "Value 1"); 
myDictionary.Add(200, "Another value"); 
// and so on 

de lo contrario, si usted tiene un número fijo de valores y sólo unos pocos de los no se utilizan actualmente, a continuación, que haría uso de una matriz de cadenas (string [200]) y ajuste/dejar las entradas reservadas a null.

var myArray = new string[200]; 
myArray[0] = "Value 1"; 
myArray[2] = "Another value"; 
//myArray[1] is null 

Answer 3

La in-construido Dictionary objeto (preferiblemente un diccionario genérico) sería ideal para esto, y está diseñado específicamente para una rápida recuperación/eficiente de los valores relativos a las llaves.

Desde el artículo de MSDN vinculado:

Recuperando un valor utilizando su clave es muy rápido, cerca de O (1), porque el Diccionario < (De < (TKey, TValue>)> La clase se implementa como una tabla hash.

Por lo que respecta a sus claves "reservadas", no me preocuparía en absoluto si solo estamos hablando de unas pocas claves/valores. Solo cuando alcances decenas, quizás cientos de miles de claves/valores "reservados", querrás implementar algo más eficiente.

En esos casos, probablemente el contenedor de almacenamiento más eficiente sería una implementación de Sparse Matrix.

Answer 4

No estoy muy seguro de entender su problema correctamente. Tienes una colección de cadenas. Cada cadena está asociada a un índice. Las solicitudes de los consumidores dan un índice y usted devuelve la cadena correspondiente, a menos que el índice sea reservado. ¿Derecha?

¿No es fácil establecer elementos reservados como null en la matriz.

De lo contrario, utilizar un diccionario que no contenga los elementos reservados parece una solución razonable.

De todos modos, es probable que obtenga mejores respuestas si aclara su problema.

Answer 5

cargar todos los valores en

var dic = new Dictionary<int, string>(); 

y utilizar esto para su recuperación:

string GetDescription(int val) 
{ 
    if(0 <= val && val < 256) 
     if(!dic.Contains(val)) 
      return "Reserved"; 
     return dic[val]; 
    throw new ApplicationException("Value must be between 0 and 255"); 
} 

Answer 6

me gustaría utilizar un diccionario para hacer las operaciones de búsqueda. Esta es la forma más eficiente de hacer búsquedas con mucho. Usar una cadena se ejecutará en algún lugar en la región de O (n) para encontrar el objeto.

Podría ser útil tener un segundo diccionario a todo lo que hacer una búsqueda inversa si es necesario

Answer 7

Pedido del HybridDictionary. Ajusta automáticamente su mecanismo de almacenamiento subyacente en función del tamaño para obtener la mayor eficiencia.

http://msdn.microsoft.com/en-us/library/system.collections.specialized.hybriddictionary.aspx

Answer 8

La forma más rápida absoluta para hacer búsquedas de valores enteros en C# es con una matriz. Esto será preferible al uso de un diccionario, tal vez, si está tratando de hacer decenas de miles de búsquedas a la vez. Para la mayoría de los propósitos, esto es excesivo; Es más probable que necesite optimizar el tiempo del desarrollador que el tiempo del procesador.

Si las claves reservadas no son simplemente todas las claves que no están en la tabla de búsqueda (es decir, si una búsqueda puede devolver el valor encontrado, un estado no encontrado o un estado reservado), usted necesita guardar las claves reservadas en algún lugar. Guardarlos como entradas de diccionario con valores mágicos (por ejemplo, la clave de cualquier entrada de diccionario cuyo valor sea nulo está reservado) está bien a menos que escriba código que itere sobre las entradas del diccionario sin filtrarlas.

Una manera de resolver este problema es utilizar un HashSet<int> separada para almacenar las claves reservadas, y tal vez hornear todo el asunto en una clase, por ejemplo:

public class LookupTable 
{ 
    public readonly Dictionary<int, string> Table { get; } 
    public readonly HashSet<int> ReservedKeys { get; } 

    public LookupTable() 
    { 
     Table = new Dictionary<int, string>(); 
     ReservedKeys = new HashSet<int>(); 
    } 

    public string Lookup(int key) 
    { 
     return (ReservedKeys.Contains(key)) 
     ? null 
     : Table[key]; 
    } 
} 

Se habrá dado cuenta de que esto todavía tiene la número de valor mágico - Lookup devuelve nulo si la clave está reservada, y arroja una excepción si no está en la tabla, pero al menos ahora puede iterar sobre Table.Values sin filtrar valores mágicos.

Answer 9

Su pregunta parece implicar que la clave de consulta es un número entero. Como tiene como máximo 256 elementos, la clave de consulta está en el rango 0..255, ¿no? Si es así, solo tiene una matriz de cadenas de 256 cadenas y use la clave como un índice en la matriz.

Si su clave de consulta es un valor de cadena, entonces es más como una tabla de búsqueda real. Usar un objeto de diccionario es simple, pero si busca la velocidad bruta para un conjunto de unas 50 respuestas reales, un enfoque de "hágalo usted mismo" como la búsqueda binaria o un trie podría ser más rápido. Si usa la búsqueda binaria, dado que la cantidad de elementos es muy pequeña, puede desenrollarla.

¿Con qué frecuencia cambia la lista de elementos? Si solo cambia muy raramente, puede obtener una velocidad aún mejor generando código para hacer la búsqueda, que luego puede compilar y ejecutar para realizar cada consulta.

Por otro lado, supongo que ha demostrado que esta búsqueda es su cuello de botella, ya sea mediante el perfil o taking stackshots. Si se gasta menos del 10% del tiempo cuando se gasta en esta consulta, entonces es no su cuello de botella así que puede hacer lo que es más fácil de codificar.