qual è il modo più veloce per generare un set univoco in .net 2

Question

Ho quello che è essenzialmente un array frastagliato di coppie di valori dei nomi - ho bisogno di generare un insieme di valori di nomi univoci da questo. l'array frastagliato è di circa 86.000 x 11 valori. Non mi importa in che modo devo memorizzare una coppia nome valore (una singola stringa & Quot; nome = valore & Quot; o una classe specializzata, ad esempio KeyValuePair).
Informazioni aggiuntive: ci sono 40 nomi distinti e un numero maggiore di valori distinti, probabilmente nella regione 10.000 valori.

Sto usando C # e .NET 2.0 (e le prestazioni sono così scarse che sto pensando che potrebbe essere meglio spingere il mio intero array frastagliato in un database sql e fare una selezione distinta da lì).

Di seguito è riportato il codice corrente che sto 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

Ce l'ho in esecuzione in 0,34 secondi da 9+ minuti

Il problema è quando si confrontano le strutture KeyValuePair. Ho lavorato intorno scrivendo un oggetto comparatore e passandone un'istanza al Dizionario.

Da quello che posso determinare, KeyValuePair.GetHashCode () restituisce l'hashcode del suo oggetto Key (in questo esempio l'oggetto meno unico).

Man mano che il dizionario aggiunge (e verifica l'esistenza di) ogni elemento, utilizza entrambe le funzioni Equals e GetHashCode, ma deve fare affidamento sulla funzione Equals quando l'hashcode è meno univoco.

Fornendo una funzione GetHashCode più unica, viene meno la frequenza della funzione Equals. Ho anche ottimizzato la funzione Equals per confrontare i valori più unici prima delle chiavi meno unqiue.

86.000 * 11 elementi con 10.000 proprietà univoche vengono eseguiti in 0,34 secondi utilizzando l'oggetto di confronto in basso (senza l'oggetto di confronto ci vogliono 9 minuti e 22 secondi)

Spero che questo aiuti :)

    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 : se fosse solo una stringa (anziché un KeyValuePair, dove string = Name + Value) sarebbe circa il doppio più veloce. È un bel problema interessante, e ho trascorso faaaaaar troppo tempo su di esso (ho imparato un po 'di silenzio)

Answer 2

se non hai bisogno di alcuna correlazione specifica tra ciascuna coppia chiave / valore e i valori univoci che stai generando, potresti semplicemente utilizzare un GUID? Suppongo che il problema sia che l'attuale "chiave" non sia unica in questo array frastagliato.

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

Sembra che memorizzerebbe ciò di cui hai bisogno, ma non so come trarresti i dati da questo dato che non ci sarebbe alcuna relazione semantica tra l'amplificatore Guid & generato; quello che avevi originariamente ...

Puoi fornire ulteriori informazioni nella tua domanda?

Answer 3

Utilizzare KeyValuePair come classe wrapper e quindi creare un dizionario con forse per creare un set? Oppure implementa il tuo wrapper che sovrascrive Equals e 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

Invece di utilizzare un Dictionary perché non estendere KeyedCollection<TKey, TItem> ? Secondo la documentazione:

Fornisce la classe base astratta per una raccolta le cui chiavi sono incorporate nei valori.

È quindi necessario sostituire la protected TKey GetKeyForItem(TItem item) . Essendo un ibrido tra IList<T> e IDictionary<TKey, TValue> Penso che probabilmente sarà abbastanza veloce.

Answer 5

Che ne dici di:

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;

ovviamente, se stavi usando C # 3.0, .NET 3.5:

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

farebbe il trucco.

Answer 6

Hai profilato il tuo codice? Sei certo che i loop foreach siano il collo di bottiglia e non retriever.GetVehicles ()?

Ho creato un piccolo progetto di test in cui fingo il retriever e gli ho lasciato restituire 86.000 valori X 11. Il mio primo tentativo è durato 5 secondi, creando i dati inclusi.

Ho usato lo stesso valore sia per la chiave che per il valore in cui la prima chiave era " 0 # 0 " e l'ultimo " 85999 # 10 " ;.

Poi sono passato alle guide. Stesso risultato.

Quindi ho allungato la chiave, in questo modo:

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

Ora ci sono voluti quasi 10 secondi.

Quindi ho reso le chiavi follemente lunghe e ho ottenuto un'eccezione di memoria esaurita. Non ho un file di scambio sul mio computer, quindi ho immediatamente ricevuto questa eccezione.

Quanto durano le tue chiavi? Il consumo di memoria virtuale è il motivo delle scarse prestazioni?