Quel est le moyen le plus rapide de générer un ensemble unique en .net 2

Question

J'ai ce qui est essentiellement un tableau irrégulier de paires de valeurs de noms - j'ai besoin de générer un ensemble de valeurs de noms uniques à partir de cela. le tableau dentelé est d'environ 86 000 x 11 valeurs. Peu importe comment je dois stocker une paire de valeurs de nom (une seule chaîne "nom = valeur" ou une classe spécialisée par exemple KeyValuePair).
Informations supplémentaires: Il existe 40 noms distincts et un plus grand nombre de valeurs distinctes - probablement dans la région 10 000 valeurs. J'utilise C# et .NET 2.0 (et les performances sont si faibles que je pense qu'il vaudrait mieux pousser tout mon tableau dentelé dans une base de données sql et faire un select distinct de là).

est Ci-dessous le code actuel Im en utilisant:

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

Je l'ai en cours d'exécution en 0,34 secondes vers le bas de 9+ minutes

Le problème est lorsque l'on compare les struct KeyValuePair. J'ai travaillé autour d'elle en écrivant un objet de comparaison, et en passant une instance de celui-ci au dictionnaire. D'après ce que je peux déterminer, KeyValuePair.GetHashCode() renvoie le hashcode de son objet Key (dans cet exemple, l'objet le moins unique). Comme le dictionnaire ajoute (et vérifie l'existence de) chaque élément, il utilise les fonctions Equals et GetHashCode, mais doit s'appuyer sur la fonction Equals lorsque le hashcode est moins unique. En fournissant une fonction GetHashCode plus unique, elle excerce la fonction Equals beaucoup moins souvent. J'ai également optimisé la fonction Equals pour comparer les valeurs les plus uniques avant les clés moins unqiue.

86000 * 11 éléments avec 10.000 propriétés uniques fonctionne en 0,34 secondes en utilisant l'objet comparateur ci-dessous (sans l'objet comparateur prend 9 minutes 22 secondes)

Hope this helps :)

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 c'était juste une chaîne (au lieu d'un KeyValuePair, où string = Name + Value), il serait environ deux fois plus rapide. C'est un joli problème intressant, et j'ai passé faaaaaar trop de temps dessus (J'ai appris calme un peu si)

Answer 2

si vous ne avez pas besoin de corrélation spécifique entre chaque paire clé/valeur et les valeurs uniques que vous générez, vous pouvez simplement utiliser un GUID? Je suppose que le problème est que votre «clé» actuelle n'est pas unique dans ce tableau déchiqueté.

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

Sons comme il stockerait ce que vous avez besoin, mais je ne sais pas comment vous extraire des données de retour de cela comme il n'y aurait pas de lien sémantique entre les générer Guid & ce que vous aviez à l'origine ...

Pouvez-vous fournir plus d'informations dans votre question?

Answer 3

Utilisez KeyValuePair comme une classe wrapper, puis créez un dictionnaire avec pour créer un ensemble peut-être? Ou implémentez votre propre wrapper qui remplace les Equals et 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

Au lieu d'utiliser un Dictionary pourquoi ne pas étendre KeyedCollection<TKey, TItem>? Selon la documentation:

Fournit la classe de base abstraite pour une collection dont les clés sont incorporées dans les valeurs.

Vous devez ensuite remplacer la fonction protected TKey GetKeyForItem(TItem item). Comme il s'agit d'un hybride entre IList<T> et IDictionary<TKey, TValue>, je pense que c'est assez rapide.

Answer 5

Que diriez-vous:

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; 

bien sûr, si vous utilisez C# 3.0, .NET 3.5:

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

ferait l'affaire.

Answer 6

Avez-vous profilé votre code? Vous êtes certain que les boucles foreach sont le goulot d'étranglement, et non retriever.GetVehicles()?

J'ai créé un petit projet de test où je simule le retriever et le laisse retourner 86.000 X 11 valeurs. Ma première tentative a duré 5 secondes, créant les données incluses.

J'ai utilisé la même valeur pour la clé et la valeur où la première clé était "0 # 0" et la dernière "85999 # 10".

Ensuite, je suis passé à guids. Même résultat

Alors je pris la clé plus, comme ceci:

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

Maintenant, il a fallu près de 10 secondes.

Puis j'ai fait les clés incroyablement longues et j'ai eu une exception de mémoire insuffisante. Je n'ai pas de fichier d'échange sur mon ordinateur, j'ai donc obtenu cette exception immédiatement.

Combien de temps sont vos clés? Votre consommation de mémoire virtuelle est-elle la raison de vos mauvaises performances?