Pour les très petites collections, la différence sera négligeable. À l'extrémité inférieure de votre gamme (500 000 éléments), vous commencerez à voir une différence si vous faites beaucoup de recherches. Une recherche binaire sera O(log n), alors qu'une recherche par hachage sera O(1), amorti . Ce n'est pas la même chose que d'être vraiment constant, mais il faudrait quand même avoir une fonction de hachage assez terrible pour obtenir des performances inférieures à celles d'une recherche binaire.
(Quand je dis "hachage terrible", je veux dire quelque chose comme :
hashCode()
{
return 0;
}
Oui, c'est très rapide en soi, mais cela fait que votre carte de hachage devient une liste liée).
ialiashkevich J'ai écrit du code C# en utilisant un tableau et un dictionnaire pour comparer les deux méthodes, mais en utilisant des valeurs longues pour les clés. Je voulais tester quelque chose qui exécuterait réellement une fonction de hachage pendant la recherche, alors j'ai modifié ce code. Je l'ai changé pour utiliser des valeurs String, et j'ai refactorisé les sections populate et lookup dans leurs propres méthodes pour que ce soit plus facile à voir dans un profiler. J'ai également conservé le code qui utilisait des valeurs Long, juste comme point de comparaison. Enfin, je me suis débarrassé de la fonction de recherche binaire personnalisée et j'ai utilisé celle de la section Array classe.
Voici ce code :
class Program
{
private const long capacity = 10_000_000;
private static void Main(string[] args)
{
testLongValues();
Console.WriteLine();
testStringValues();
Console.ReadLine();
}
private static void testStringValues()
{
Dictionary<String, String> dict = new Dictionary<String, String>();
String[] arr = new String[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " String values...");
stopwatch.Start();
populateStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
Array.Sort(arr);
stopwatch.Stop();
Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with random values. */
private static void populateStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness
}
}
/* Populate a dictionary with values from an array. */
private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(arr[i], arr[i]);
}
}
/* Search a Dictionary for each value in an array. */
private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
String value = dict[arr[i]];
}
}
/* Do a binary search for each value in an array. */
private static void searchStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
private static void testLongValues()
{
Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue);
long[] arr = new long[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " Long values...");
stopwatch.Start();
populateLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with long values. */
private static void populateLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = i;
}
}
/* Populate a dictionary with long key/value pairs. */
private static void populateLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(i, i);
}
}
/* Search a Dictionary for each value in a range. */
private static void searchLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
long value = dict[i];
}
}
/* Do a binary search for each value in an array. */
private static void searchLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
/**
* Generate a random string of a given length.
* Implementation from https://stackoverflow.com/a/1344258/1288
*/
private static String generateRandomString(int length)
{
var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
var stringChars = new char[length];
var random = new Random();
for (int i = 0; i < stringChars.Length; i++)
{
stringChars[i] = chars[random.Next(chars.Length)];
}
return new String(stringChars);
}
}
Voici les résultats avec plusieurs tailles de collections différentes. (Les temps sont en millisecondes).
500000 Valeurs longues...
Remplir le dictionnaire long : 26
Remplir le tableau long : 2
Recherche dans le dictionnaire long : 9
Recherche Long Array : 80
500000 Valeurs de chaîne...
Remplir le tableau des chaînes : 1237
Remplir le dictionnaire des chaînes : 46
Trier un tableau de chaînes de caractères : 1755
Dictionnaire des chaînes de recherche : 27
Tableau des chaînes de recherche : 1569
1000000 Valeurs longues...
Remplir le dictionnaire long : 58
Remplir le Long Array : 5
Recherche dans le dictionnaire long : 23
Recherche Long Array : 136
1000000 valeurs de chaîne...
Remplir le tableau de chaînes : 2070
Remplir le dictionnaire de chaînes : 121
Trier un tableau de chaînes de caractères : 3579
Dictionnaire des chaînes de recherche : 58
Tableau des chaînes de recherche : 3267
3000000 Valeurs longues...
Remplir le dictionnaire long : 207
Remplir le Long Array : 14
Recherche dans le dictionnaire long : 75
Recherche Long Array : 435
3000000 valeurs de chaîne...
Remplir le tableau des chaînes : 5553
Remplir le dictionnaire des chaînes : 449
Trier le tableau des chaînes de caractères : 11695
Dictionnaire des chaînes de recherche : 194
Tableau des chaînes de recherche : 10594
10000000 Valeurs longues...
Remplir le dictionnaire long : 521
Remplir le Long Array : 47
Recherche dans le dictionnaire long : 202
Recherche Long Array : 1181
10000000 Valeurs de chaîne...
Remplir le tableau des chaînes : 18119
Remplir le dictionnaire des chaînes : 1088
Trier le tableau des chaînes de caractères : 28174
Dictionnaire des chaînes de recherche : 747
Tableau des chaînes de recherche : 26503
Et à titre de comparaison, voici la sortie du profileur pour la dernière exécution du programme (10 millions d'enregistrements et de consultations). J'ai mis en évidence les fonctions pertinentes. Elles correspondent assez bien aux mesures de temps du chronomètre ci-dessus.
![Profiler output for 10 million records and lookups]()
Vous pouvez constater que les recherches dans le dictionnaire sont beaucoup plus rapides que la recherche binaire, et (comme prévu) la différence est d'autant plus prononcée que la collection est grande. Donc, si vous disposez d'une fonction de hachage raisonnable (assez rapide avec peu de collisions), une consultation de hachage devrait battre la recherche binaire pour les collections de cette taille.
1 votes
Qu'est-ce que le "lookup" ? Voulez-vous seulement tester l'appartenance (si un élément particulier existe ou non) ? Ou bien avez-vous des paires clé-valeur, et voulez-vous trouver la valeur associée à une certaine clé ?
0 votes
Cela dépend du niveau de perfection de la fonction de hachage.