Pourquoi les recherches dict sont-elles toujours meilleures que les recherches liste?

Question

J'ai été en utilisant un dictionnaire comme une table de recherche, mais j'ai commencé à me demander si liste serait mieux pour mon application, la quantité d'entrées dans ma table de recherche n'était pas si grande que cela. Je sais que les listes d'utiliser C des tableaux sous le capot, ce qui m'a fait conclure que la recherche dans une liste, avec seulement quelques éléments serait mieux que dans un dictionnaire (l'accès à quelques-uns des éléments d'un tableau est plus rapide que le calcul d'un hash).

J'ai décidé de profil les solutions de rechange, mais les résultats m'ont surpris. La recherche de liste a été seulement de mieux avec un seul élément! Voir la figure suivante (graphe log-log):

Donc, voici la question: Pourquoi faire des recherches dans les listes effectuer si mal? Ce qui me manque?

Sur un côté de la question, quelque chose d'autre qui a appelé mon attention était un peu "discontinuité" dans le dict de recherche de temps après environ 1000 entrées. J'ai tracé le dict recherche du temps seul à le montrer.

p.s.1-je savoir au sujet de O(n) vs O(1) amorti temps pour les tableaux et les tables de hachage, mais c'est généralement le cas que pour un petit nombre d'éléments de parcourir un tableau est mieux que d'utiliser une table de hachage.

p.s.2 Voici le code que j'ai utilisé pour comparer les dict et la recherche de liste de temps:

import timeit

lengths = [2 ** i for i in xrange(15)]

list_time = []
dict_time = []
for l in lengths:
    list_time.append(timeit.timeit('%i in d' % (l/2), 'd=range(%i)' % l))
    dict_time.append(timeit.timeit('%i in d' % (l/2),
                                   'd=dict.fromkeys(range(%i))' % l))
    print l, list_time[-1], dict_time[-1]

p.s.3 À L'Aide De Python 2.7.13

Answer 1

Je sais que les listes d'utiliser C des tableaux sous le capot, ce qui m'a fait conclure que la recherche dans une liste, avec seulement quelques éléments serait mieux que dans un dictionnaire (l'accès à quelques-uns des éléments d'un tableau est plus rapide que le calcul d'un hash).

Accéder à quelques-uns des éléments d'un tableau n'est pas cher, bien sûr, mais le calcul de == est étonnamment lourd en Python. Voir que spike dans votre deuxième graphique? C'est le coût de calcul de == pour les deux ints là.

Votre liste de recherches pour calculer les == beaucoup plus que votre dict recherches de faire.

Pendant ce temps, le calcul de hachages peut-être un peu de poids lourd opération pour beaucoup d'objets, mais pour tous les entiers en cause ici, ils ont juste de hachage pour eux-mêmes. (-1 hachage à -2, et de grands entiers (techniquement longs) serait de hachage pour les plus petits entiers, mais qui ne s'applique pas ici.)

Dict la recherche n'est pas vraiment mauvais en Python, en particulier lorsque vos clés sont tout simplement un plusieurs à la suite d'entiers. Tous les services de renseignements ici de hachage pour eux-mêmes, et Python utilise un custom ouvrir le schéma d'adressage au lieu d'enchaîner, de sorte que tous vos clés finissent presque aussi contigus en mémoire que si vous aviez utilisé une liste (c'est-à-dire, les pointeurs pour les clés à la fin dans une plage contiguë de PyDictEntrys). La recherche de la procédure est rapide, et dans votre cas de test, elle atteint toujours la touche de droite sur la première sonde.

---

Bon, revenons-en à la pointe dans le graphique 2. Le pic de la recherche fois à 1024 entrées dans le second graphique est parce que, pour toutes les tailles les plus petites, les entiers que vous cherchiez étaient tous <= 256, donc ils sont tous tombés à l'intérieur de la gamme de Disponible du petit entier de cache. L'implémentation de référence de Python garde canonique entier des objets pour tous les entiers à partir de -5 à 256, inclusivement. Pour ces entiers, Python a été en mesure d'utiliser un rapide pointeur de comparaison pour éviter de passer par la (étonnamment lourd) processus de calcul des ==. Pour les grands nombres entiers, l'argument in n'était plus le même objet que la correspondance entier dans le dict, et Python ont eu à passer par l'ensemble de l' == processus.

Answer 2

La réponse courte est que les listes d'utiliser la recherche linéaire et dicts utilisation amorti O(1) de la recherche.

En outre, dict recherches peuvent passer un test d'égalité soit lorsque 1) les valeurs de hachage ne correspond pas ou 2) lorsqu'il existe une identité de match. Listes seulement de bénéficier de l'identité implique l'égalité de l'optimisation.

En 2008, j'ai donné une conférence sur ce sujet, où vous trouverez tous les détails: https://www.youtube.com/watch?v=hYUsssClE94

À peu près la logique de la recherche de listes:

for element in s:
    if element is target:
        # fast check for identity implies equality
        return True
    if element == target:
        # slower check for actual equality
        return True
return False

Pour les dicts la logique est à peu près:

h = hash(target)
for i in probe_sequence(h, len(table)):
    element = key_table[i]
    if element is UNUSED:
        raise KeyError(target)
    if element is target:
        # fast path for identity implies equality
        return value_table[i]
    if h != h_table[i]:
        # unequal hashes implies unequal keys
        continue
    if element == target:
        # slower check for actual equality
        return value_table[i]

Dictionnaire des tables de hachage sont généralement entre un tiers et deux tiers, de sorte qu'ils ont tendance à avoir peu de collisions (quelques voyages autour de la boucle ci-dessus), indépendamment de la taille. Aussi, la valeur de hachage de vérification empêche inutile de ralentir les contrôles d'égalité (la probabilité de perdre un contrôle d'égalité est d'environ 1 sur 2**64).

Si votre timing est axé sur des entiers, il y a quelques autres effets en jeu. Que de hachage d'un int est le type int lui-même, de sorte que le hachage est très rapide. En outre, cela signifie que si vous êtes stocker des nombres entiers consécutifs, il y a généralement pas de collisions à tous.

Answer 3

Vous dites "accéder à quelques éléments d'un tableau est plus rapide que de calculer un hachage".

Une simple règle de hachage pour les chaînes pourrait être simplement une somme (avec un modulo à la fin). Il s'agit d'une opération sans branche qui peut être avantageusement comparée aux comparaisons de caractères, en particulier lorsque le préfixe correspond longtemps.