¿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 irregular de pares de valores de nombre: necesito generar un conjunto de valores de nombre únicos a partir de esto. la matriz irregular 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 & Quot; name = value & Quot; o una clase especializada, por ejemplo KeyValuePair).
Información adicional: Hay 40 nombres distintos y un mayor número 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 creo que puede ser mejor insertar toda mi matriz dentada en una base de datos sql y hacer una selección distinta desde allí).

A continuación se muestra el código actual que estoy 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 ejecutándose en 0.34 segundos en vez de más de 9 minutos

El problema es cuando se comparan las estructuras KeyValuePair. Trabajé alrededor de esto escribiendo un objeto de comparación y pasando una instancia al Diccionario.

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

A medida que el diccionario agrega (y verifica la existencia de) cada elemento, utiliza las funciones Equals y GetHashCode, pero tiene que confiar en la función Equals cuando el código hash es menos exclusivo.

Al proporcionar una función GetHashCode más exclusiva, ejerce 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 complejas.

86,000 * 11 elementos con 10,000 propiedades únicas se ejecutan en 0.34 segundos usando el objeto comparador a continuación (sin el objeto comparador, toma 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();
        }
    }

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

Answer 2

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

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))

Parece que almacenaría lo que necesita, pero no sé cómo recuperaría los datos, ya que no habría una relación semántica entre el amplificador Guid &; lo que originalmente tenías ...

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

Answer 3

¿Usar KeyValuePair como una clase de contenedor y luego crear un diccionario para crear un conjunto quizás? O implemente su propio contenedor que anule Equals 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 usar un Dictionary por qué no extender KeyedCollection<TKey, TItem> ? De acuerdo con la documentación:

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

Luego debe anular la función protected TKey GetKeyForItem(TItem item) . Como es un híbrido entre IList<T> y IDictionary<TKey, TValue> Creo que es probable que sea 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 estaba usando C # 3.0, .NET 3.5:

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

haría el truco.

Answer 6

¿Has perfilado tu código? Estás seguro de que los bucles foreach son el cuello de botella y no el perro perdiguero. ¿ObtenerVehicles ()?

Creé un pequeño proyecto de prueba donde falsifiqué el recuperador y dejé que devolviera 86,000 X 11 valores. Mi primer intento fue a los 5 segundos, creando los datos incluidos.

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

Luego cambié a guías. Mismo resultado.

Luego hice la clave más larga, así:

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

Ahora tardó 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 recibí esta excepción de inmediato.

¿Cuánto duran tus llaves? ¿Su consumo de memoria virtual es la razón de su bajo rendimiento?