def removeDuplicatesFromList(seq):
# Not order preserving
keys = {}
for e in seq:
keys[e] = 1
return keys.keys()
def countWordDistances(li):
'''
If li = ['that','sank','into','the','ocean']
This function would return: { that:1, sank:2, into:3, the:4, ocean:5 }
However, if there is a duplicate term, take the average of their positions
'''
wordmap = {}
unique_words = removeDuplicatesFromList(li)
for w in unique_words:
distances = [i+1 for i,x in enumerate(li) if x == w]
wordmap[w] = float(sum(distances)) / float(len(distances)) #take average
return wordmap
How do I make this function faster?
8 Réponses :
Utilisez un ensemble:
def countWordDistances(li):
'''
If li = ['that','sank','into','the','ocean']
This function would return: { that:1, sank:2, into:3, the:4, ocean:5 }
However, if there is a duplicate term, take the average of their positions
'''
wordmap = {}
unique_words = set(li)
for w in unique_words:
distances = [i+1 for i,x in enumerate(li) if x == w]
wordmap[w] = float(sum(distances)) / float(len(distances)) #take average
return wordmap
La première chose à gérer est d'utiliser un ensemble pour supprimer des mots en double: en général, si vous êtes inquiet, si vous êtes inquiet de la vitesse, vous devez profiler la fonction pour Voir où le goulot d'étranglement est, puis essayez de réduire ce goulot d'étranglement.
Tout le monde recommande d'utiliser SET. Quel est l'avantage d'utiliser le gelenget?
@ user849364: La principale différence est que un définir est mutable, tandis qu'un gelenset est immuable. Je pense qu'aucun avantage de la performance, mais cela indique aux lecteurs de votre code que l'ensemble ne sera pas modfié. Voir les docs Python pour plus d'informations.
OnEliner - Ce que je fais dans la dernière ligne est une compréhension de dictionnaire, similaire à une compréhension de la liste.
Des compréhensions de dictionnaire sont également disponibles à Python 2.7. Avant cela, la même idée peut être utilisée en appelant dict avec une compréhension génératrice, par exemple, `dict ((i, 2 * i) pour i in gamme (4)) 'produit' {0: 0, 1: 2, 2: 4, 3: 6} '.
Est-ce que ça marche pour toi? Je reçois "nom global" W 'n'est pas défini "car le" x == w "est à l'intérieur de la boucle qui définit w.
Utilisation de la compréhension de la liste:
def countWordDistances(l):
unique_words = set(l)
idx = [[i for i,x in enumerate(l) if x==item]
for item in unique_words]
return {item:1.*sum(idx[i])/len(idx[i]) + 1.
for i,item in enumerate(unique_words)}
li = ['that','sank','into','the','ocean']
countWordDistances(li)
# {'into': 3.0, 'ocean': 5.0, 'sank': 2.0, 'that': 1.0, 'the': 4.0}
li2 = ['that','sank','into','the','ocean', 'that']
countWordDistances(li2)
# {'into': 3.0, 'ocean': 5.0, 'sank': 2.0, 'that': 3.5, 'the': 4.0}
Je ne sais pas si cela sera plus rapide que d'utiliser un ensemble, mais il ne nécessite qu'un seul passage dans la liste: Ceci renvoie une version modifiée de WordMap, avec les valeurs associé à chaque clé étant un tuple de la position moyenne et du nombre de survenances. Vous pouvez évidemment transformer cela facilement en la forme de la sortie d'origine, mais cela prendrait du temps. Le code maintient essentiellement une moyenne courante tout en itérant dans la liste, recalculant chaque fois en prenant une moyenne pondérée.
Faire une seule passe à travers la liste est la clé.
import collections
def countWordDistances(li):
wordmap = collections.defaultdict(list)
for i, w in enumerate(li, 1):
wordmap[w].append(i)
for k, v in wordmap.iteritems():
wordmap[k] = sum(v)/float(len(v))
return wordmap
This makes only one pass through the list, and keeps operations to a minimum. I timed this on a word list with 1.1M entries, 29k unique words, and it was almost twice as fast as Patrick's answer. On a list of 10k words, 2k unique, it was more than 300x faster than the OP's code.To make Python code go faster, there are two rules to keep in mind: use the best algorithm, and avoid Python. On the algorithm front, iterating the list once instead of N+1 times (N= number of unique words) is the main thing that will speed this up. On the "avoid Python" front, I mean: you want your code to be executing in C as much as possible. So using defaultdict is better than a dict where you explicitly check if the key is present. defaultdict does that check for you, but does it in C, in the Python implementation. enumerate is better than for i in range(len(li)), again because it's fewer Python steps. And enumerate(li, 1) makes the counting start at 1 instead of having to have a Python +1 somewhere in the loop.Edited: Third rule: use PyPy. My code goes twice as fast on PyPy as on 2.7.
+1 pour les optimisations de refroidissement. J'ai eu une idée décente du meilleur algorithme mais je n'ai pas eu le savoir-faire Python que vous avez clairement.
Pourquoi ne pas accumuler le total et le nombre de statistiques suffisantes? Je vais ajouter une réponse.
@Neil G: Bon travail, le vôtre est d'environ 10% plus rapide que le mien et suggère une autre règle: éviter les allocations de mémoire.
+1 pour "Évitez Python [en utilisant Python Smirlyment]" - de votre tweet, je m'attendais à "éviter le python" d'avoir des extensions indigènes ou quelque chose du genre.
"Utilisez pypy" et "éviter Python" ne vient pas que bien ensemble. De préférence "utiliser pypy" et "utiliser python"?
La solution de Batchelder basée sur @ned Batchelder, mais sans créer des listes digues:
OK, comment cela est-ce pour un hack brut: si vous n'avez besoin que d'une liste de deux réels, utilisez plutôt un seul numéro complexe! Il coupe 25% de réduction sur la période de fonctionnement de votre solution, mais yuck!
@Ned: ha, oui! Avez-vous essayé lambda: numpy.zeros (2) ? Vous sauriez mieux que moi, mais un jour, j'espère que quelqu'un écrit un grand optimiseur Python afin que nous puissions nous concentrer sur les algorithmes (c'est pourquoi je suis tombé amoureux de Python.)