¿Cuál es la forma más rápida de generar un conjunto único en .net 2

Question

Tengo lo que es esencialmente una matriz dentada de pares de valores de nombres? Necesito generar un conjunto de valores de nombres únicos a partir de esto. la matriz dentada tiene aproximadamente 86,000 x 11 valores. No me importa de qué manera tengo que almacenar un par de nombre y valor (una sola cadena "nombre = valor" o una clase especializada, por ejemplo, KeyValuePair).
Información adicional: Hay 40 nombres distintos y un número mayor de valores distintos, probablemente en la región 10.000 valores.

Estoy usando C# y .NET 2.0 (y el rendimiento es tan bajo que estoy pensando que puede ser mejor empujar toda mi matriz irregular en una base de datos sql y hacer una selección distinta desde allí).

A continuación se muestra el código actual Im usando:

List<List<KeyValuePair<string,string>>> vehicleList = retriever.GetVehicles(); 
this.statsLabel.Text = "Unique Vehicles: " + vehicleList.Count; 

Dictionary<KeyValuePair<string, string>, int> uniqueProperties = new Dictionary<KeyValuePair<string, string>, int>(); 
foreach (List<KeyValuePair<string, string>> vehicle in vehicleList) 
{ 
    foreach (KeyValuePair<string, string> property in vehicle) 
    { 
     if (!uniqueProperties.ContainsKey(property)) 
     { 
      uniqueProperties.Add(property, 0); 
     } 
    } 
} 
this.statsLabel.Text += "\rUnique Properties: " + uniqueProperties.Count; 

Answer 1

lo tengo funcionando en 0.34 segundos abajo de 9+ minutos

El problema es cuando se comparan las estructuras KeyValuePair. Trabajé alrededor escribiendo un objeto comparador y pasando una instancia del mismo al Diccionario.

Según lo que puedo determinar, KeyValuePair.GetHashCode() devuelve el código de hash de su objeto Key (en este ejemplo, el objeto menos exclusivo).

Como el diccionario agrega (y verifica la existencia de) cada elemento, usa las funciones Equal y GetHashCode, pero tiene que confiar en la función Equals cuando el código hash es menos único.

Al proporcionar una función GetHashCode más única, utiliza la función Equals con mucha menos frecuencia. También optimicé la función Equals para comparar los valores más únicos antes de las claves menos unqiue.

86.000 * 11 elementos con 10.000 propiedades únicas ejecuta en 0.34 segundos utilizando el objeto comparador siguiente (sin el objeto comparador se tarda 9 minutos 22 segundos)

espero que esto ayude :)

class StringPairComparer 
     : IEqualityComparer<KeyValuePair<string, string>> 
    { 
     public bool Equals(KeyValuePair<string, string> x, KeyValuePair<string, string> y) 
     { 
      return x.Value == y.Value && x.Key == y.Key; 
     } 
     public int GetHashCode(KeyValuePair<string, string> obj) 
     { 
      return (obj.Key + obj.Value).GetHashCode(); 
     } 
    } 

EDIT: Si fuera solo una cadena (en lugar de un KeyValuePair, donde string = Name + Value), sería aproximadamente el doble de rápido. Es un buen problema interesante, y he pasado demasiado tiempo en faaaaar (aunque aprendí un poco)

Answer 2

si no necesita ninguna correlación específica entre cada par clave/valor y los valores únicos se está generando, usted podría usar un GUID? Supongo que el problema es que su 'Clave' actual no es única en esta matriz dentada.

Dictionary<System.Guid, KeyValuePair<string, string>> myDict 
    = new Dictionary<Guid, KeyValuePair<string, string>>(); 


foreach of your key values in their current format 
    myDict.Add(System.Guid.NewGuid(), new KeyValuePair<string, string>(yourKey, yourvalue)) 

suena como que almacenaría lo que necesita, pero no sé cómo le extraer datos de volver de este ya que no habría ninguna relación semántica entre el Guid generar & lo que tenía originalmente ...

¿Puede proporcionar más información en su pregunta?

Answer 3

Use KeyValuePair como una clase contenedora y luego cree un diccionario para crear un conjunto tal vez? O implemente su propio contenedor que anule Iguales y GetHashCode.

Dictionary<KeyValuePair, bool> mySet; 

for(int i = 0; i < keys.length; ++i) 
{ 
    KeyValuePair kvp = new KeyValuePair(keys[i], values[i]); 
    mySet[kvp] = true; 
} 

Answer 4

En lugar de utilizar un Dictionary por qué no extender KeyedCollection<TKey, TItem>? Según la documentación:

Proporciona la clase base abstracta para una colección cuyas claves están incrustadas en los valores.

Luego debe sobrescribir la función protected TKey GetKeyForItem(TItem item). Como es un híbrido entre IList<T> y IDictionary<TKey, TValue>, creo que es bastante rápido.

Answer 5

¿Qué tal:

Dictionary<NameValuePair,int> hs = new Dictionary<NameValuePair,int>(); 
foreach (i in jaggedArray) 
{ 
    foreach (j in i) 
    { 
     if (!hs.ContainsKey(j)) 
     { 
      hs.Add(j, 0); 
     } 
    } 
} 
IEnumerable<NameValuePair> unique = hs.Keys; 

por supuesto, si estuviera usando C# 3.0, .NET 3.5:

var hs = new HashSet<NameValuePair>(); 
hs.UnionWith(jaggedArray.SelectMany(item => item)); 

que hacer el truco.

Answer 6

¿Ha perfilado su código? Está seguro de que los bucles foreach son el cuello de botella y no el recuperador. GetVehicles()?

Creé un pequeño proyecto de prueba donde falsifico el retriever y lo dejo devolver 86,000 X 11 valores. Mi primer intento se ejecutó en 5 segundos, creando los datos incluidos.

Usé el mismo valor para la clave y el valor donde la primera clave era "0 # 0" y la última "85999 # 10".

Luego cambié a las guías. Mismo resultado.

Entonces hice la tecla más tiempo, así:

 var s = Guid.NewGuid().ToString(); 
     return s + s + s + s + s + s + s+ s + s + s; 

Ahora se tomó casi 10 segundos.

Luego hice las teclas increíblemente largas y obtuve una excepción de falta de memoria. No tengo un archivo de intercambio en mi computadora, así que obtuve esta excepción de inmediato.

¿Cuánto duran sus llaves? ¿El consumo de memoria virtual es el motivo de tu bajo rendimiento?