Ce qui est plus rapide et pourquoi? Ensemble ou une Liste?

Permet de dire que j'ai un graphique et vous voulez voir si b in N[a]. Qui est le plus rapide de la mise en œuvre et pourquoi?

a, b = range(2)
N = [set([b]), set([a,b])]

OU 

N= [[b],[a,b]]

C'est évidemment simpliste, mais imaginez que le graphe devient vraiment dense.

InformationsquelleAutor locoboy | 2011-10-10
  1. 36

    Adhésion à l'essai dans un ensemble est largement plus rapide, surtout pour les grands ensembles. C'est parce que le jeu utilise un fonction de hachage à la carte d'un seau. Depuis Python implémentations de redimensionner automatiquement que la table de hachage, la vitesse peut être constante ( O(1) ), peu importe la taille de l'ensemble (en supposant que la fonction de hachage est suffisamment bonne).

    En revanche, pour évaluer si un objet est un membre de une liste, Python est de comparer chaque membre de l'égalité, c'est à dire le test est O(n).

    • Me battre pour elle. Il est également intéressant de souligner que l'OP a une liste de listes dans le premier exemple, et une liste de jeux dans le second. Parce que le contenant extérieur est une liste dans les deux cas, la recherche est O(n) dans les deux situations.
    • Python ensembles sont redimensionné dynamiquement les tables de hashage, de sorte que vous obtenez amorti O(1) quel que soit le nombre d'éléments. @g.d.d.c OP pose à propos de l'adhésion les tests pour un seul élément (b in N[a]) de la liste de conteneurs, c'est-à N, donc non, il n'est pas O(n) de toute façon.
    • Vous avez raison, O(1) (+notes) est une meilleure description que O(log n) (-notes).
    • O(1) n'est pas seulement mieux que O(log n) O(1) est correct, et O(log n) ne l'est pas.
    • En fait, si vous regardez la définition mathématique, vous trouverez que O(log N) est correcte chaque fois que O(1) est – si c'est constant, c'est également délimitée par log N. Donc O(1) est “juste” mieux que O(log N).
    • oui, c'est la partie de la définition de " big-O, de sorte que vous êtes correct. O(log n) n'est pas mauvais, il est simplement trompeuse et inutile! 🙂 D'autres description correcte de l'adhésion les tests d'un ensemble O(N2), O(NN), O(NNN), etc, etc.
    • Vous avez raison. Mon instinct était de citer O(log n), car c'est ce qui est réalisable, peu importe le réglage précis (de seau de nombres et des fonctions de hachage), mais O(1) est la description correcte ici. Fixe.

    InformationsquelleAutor phihag
  2. 5

    Tout dépend de ce que vous essayez d'accomplir. À l'aide de votre exemple verbatim, c'est plus rapide d'utiliser des listes, que vous n'avez pas à passer par la surcharge de la création de la scénographie:

    import timeit

def use_sets(a, b):
    return [set([b]), set([a, b])]

def use_lists(a, b):
    return [[b], [a, b]]

t=timeit.Timer("use_sets(a, b)", """from __main__ import use_sets
a, b = range(2)""")
print "use_sets()", t.timeit(number=1000000)

t=timeit.Timer("use_lists(a, b)", """from __main__ import use_lists
a, b = range(2)""")
print "use_lists()", t.timeit(number=1000000)

    Produit:

    use_sets() 1.57522511482
use_lists() 0.783344984055

    Toutefois, pour les raisons déjà mentionnées ici, vous bénéficiez de l'aide de jeux quand vous êtes recherche de grands ensembles. Il est impossible de dire, par votre exemple, où ce point d'inflexion est fait pour vous et si vous allez voir les avantages.

    Je vous suggère de tester les deux méthodes pour aller avec tout ce qui est plus rapide pour votre cas d'utilisation.

    InformationsquelleAutor Austin Marshall
  3. 3

    Jeu ( je veux dire un hachage en fonction définie comme HashSet) est beaucoup plus rapide que la Liste à la recherche d'une valeur. La liste doit aller de manière séquentielle afin de savoir si la valeur existe. HashSet pouvez directement sauter et de localiser le seau et regarder pour une valeur presque constante de temps.

    InformationsquelleAutor java_mouse