Comment supprimer aléatoirement une clé du dictionnaire en fonction de sa valeur ?

Question

Comment puis-je supprimer de manière aléatoire une clé ayant la valeur 0 de manière efficace ?

Dictionary<string, int> dict = new Dictionary<Edge, int>();
dict.add("a",0);
dict.add("b",0);
dict.add("c",0);
dict.add("d",1);

La taille du dictionnaire est de 10000.

Answer 1

Quelque chose comme ceci devrait suffire :

IEnumerable<string, int> pairsToRemove = dictionary.Where(pair => pair.Value == 0);

Pour générer un index aléatoire, vous pouvez utiliser :

int indexToRemove = [RandomNumber] % pairsToRemove.Length() -1;

Trouver l'élément indexToRemove th dans pairsToRemove et le supprimer du dictionnaire.

En ce qui concerne l'efficacité : La complexité devrait être O(n) [obtenir tous les éléments de valeur 0] + O(.6N) [trouver la ième valeur à supprimer] + O(log(n)) [suppression] en supposant que la génération de nombres aléatoires se fasse en temps constant.

Le problème est qu'il n'existe aucun moyen d'effectuer une recherche de valeur dans un dictionnaire en un temps supérieur à O(n). C'est donc là que se situe votre goulot d'étranglement.

Answer 2

Cela permet de supprimer le premier élément dont la valeur est égale à zéro. Ce n'est pas précisément "aléatoire", mais non déterministe.

Dictionary<string, int> dict = new Dictionary<string, int>();
string keyToRemove = null;
foreach (var kvp in dict)
{
    if (kvp.Value == 0)
    {
        keyToRemove = kvp.Key;
        break;
    }
}
if (keyToRemove != null)
{
    dict.Remove(keyToRemove);
}