le comptage en double des mots en python le moyen le plus rapide

J'essayais de compter en double les mots-dessus une liste de 230 mille mots.J'ai utilisé python, dictionnaire de le faire. Le code est donné ci-dessous:

for words in word_list:
    if words in word_dict.keys():
       word_dict[words] += 1
    else:
       word_dict[words] = 1

Le code ci-dessus a pris 3 minutes!. J'ai couru le même code, plus de 1,5 millions de mots, et il était en marche pendant plus de 25 minutes et j'ai perdu ma patience et de la fin. Ensuite, j'ai trouvé que je peux utiliser le code suivant à partir ici (voir également ci-dessous). Le résultat était tellement surprenante, elle a complété en quelques secondes!. Donc ma question est quel est le moyen plus rapide de faire cette opération?. Je suppose que le dictionnaire processus de création doit être prise de O(N) fois. Comment était la Contre la méthode de mesure de terminer ce processus en quelques secondes et créer une exacte dans le dictionnaire de mot-clé et la fréquence comme c'est la valeur?

from collections import Counter
word_dict = Counter(word_list)
Il peut être aussi parce que word_dict.keys() obtient toutes les clés dans une liste, et la vérification de l'appartenance à une liste est une O(n) opération, lors de la vérification de l'appartenance à une table de hachage est beaucoup plus rapide.
Code pour collections.Counter est disponible hg.python.org/cpython/file/2.7/Lib/collections.py
connexes: Python Est un dictionnaire lent à trouver la fréquence de chaque caractère?

OriginalL'auteur Rkz | 2013-01-17

  1. 5

    C'est à cause de cela:

    if words in word_dict.keys():

    .keys() renvoie une liste de toutes les clés. Les listes de prendre le temps linéaire de balayage, de sorte que votre programme était en cours d'exécution dans quadratique du temps!

    Essayez plutôt ceci:

    if words in word_dict:

    Aussi, si vous êtes intéressé, vous pouvez voir l' Compteur de la mise en œuvre pour vous-même. Il écrit régulièrement Python.

    Merci @Eevee qui a aidé à
    Sur Python 3 Compteur peut utiliser _count_elements() helper écrit en C

    OriginalL'auteur Eevee

  2. 3

    votre dictionnaire méthode de comptage n'est pas bien construit.

    vous pourriez avoir utilisé un defaultdict de la manière suivante:

    d = defaultdict(int)

for word in word_list:
    d[word] += 1

    mais la compteur méthode de itertools est encore plus rapide, même si elle est en train de faire presque la même chose, parce que c'est écrit dans une application plus efficace. cependant, avec le compteur méthode, vous devez transmettre une liste à compter, tandis que l'utilisation d'un defaultdict, vous pouvez mettre les sources à partir d'endroits différents et ont une plus compliqué boucle.

    en fin de compte c'est votre préférence. si le comptage d'une liste, counter est le chemin à parcourir, si l'itération à partir de sources multiples, ou vous voulez simplement un compteur dans votre programme et ne veux pas l'extra de recherche pour vérifier si un élément est déjà prise en compte ou pas. puis defaultdict est votre choix.

    même idée 🙂 +1
    Merci très instructif en effet.

    OriginalL'auteur Inbar Rose

  3. 1

    Fait vous pouvez regarder le code Compteur, voici la mise à jour de la méthode qui est appelée sur init:

    (Avis il utilise la performance truc de la définition d'une définition locale de self.get)

    def update(self, iterable=None, **kwds):
    '''Like dict.update() but add counts instead of replacing them.

    Source can be an iterable, a dictionary, or another Counter instance.

    >>> c = Counter('which')
    >>> c.update('witch')           # add elements from another iterable
    >>> d = Counter('watch')
    >>> c.update(d)                 # add elements from another counter
    >>> c['h']                      # four 'h' in which, witch, and watch
    4

    '''
    # The regular dict.update() operation makes no sense here because the
    # replace behavior results in the some of original untouched counts
    # being mixed-in with all of the other counts for a mismash that
    # doesn't have a straight-forward interpretation in most counting
    # contexts.  Instead, we implement straight-addition.  Both the inputs
    # and outputs are allowed to contain zero and negative counts.

    if iterable is not None:
        if isinstance(iterable, Mapping):
            if self:
                self_get = self.get
                for elem, count in iterable.iteritems():
                    self[elem] = self_get(elem, 0) + count
            else:
                super(Counter, self).update(iterable) # fast path when counter is empty
        else:
            self_get = self.get
            for elem in iterable:
                self[elem] = self_get(elem, 0) + 1
    if kwds:
        self.update(kwds)

    OriginalL'auteur monkut

  4. 0

    Vous pouvez également essayer d'utiliser defaultdict plus concurrentiel choix. Essayez:

    from collections import defaultdict

word_dict = defaultdict(lambda: 0)
for word in word_list:
    word_dict[word] +=1

print word_dict

    OriginalL'auteur Thorsten Kranz