2010-12-16 174 views
4

C'est presque la même question que here, sauf que je pose des questions sur la solution la plus efficace pour un résultat trié.comment compter de façon optimale les éléments dans une liste python

J'ai une liste (environ 10 entiers au hasard entre 0 et 12), par exemple:

the_list = [5, 7, 6, 5, 5, 4, 4, 7, 5, 4] 

Je veux créer une fonction qui retourne une liste de tuples (point, compte) commandé par le premier élément, par exemple

output = [(4, 3), (5, 4), (6, 1), (7, 2)] 

jusqu'à présent, j'ai utilisé:

def dupli(the_list): 
    return [(item, the_list.count(item)) for item in sorted(set(the_list))] 

Mais j'appeler ce fonctionne presque un millon de temps et j'ai besoin de le faire aussi vite que je peux (python). Par conséquent ma question: Comment rendre cette fonction moins de temps comsuming? (? Qu'en est-mémoire)

J'ai joué un peu, mais rien d'évident venu:

from timeit import Timer as T 
number=10000 
setup = "the_list=[5, 7, 6, 5, 5, 4, 4, 7, 5, 4]" 

stmt = "[(item, the_list.count(item)) for item in sorted(set(the_list))]" 
T(stmt=stmt, setup=setup).timeit(number=number) 

Out[230]: 0.058799982070922852 

stmt = "L = []; \nfor item in sorted(set(the_list)): \n L.append((item, the_list.count(item)))" 
T(stmt=stmt, setup=setup).timeit(number=number) 

Out[233]: 0.065041065216064453 

stmt = "[(item, the_list.count(item)) for item in set(sorted(the_list))]" 
T(stmt=stmt, setup=setup).timeit(number=number) 

Out[236]: 0.098351955413818359 

Merci
Christophe

+0

Quelle version python utilisez-vous? –

+6

En tant que programmeur, je me demanderais pas "Comment puis-je faire cette chose prend moins de temps?" mais "Comment puis-je éviter de le faire un million de fois?" Êtes-vous certain que votre algorithme qui nécessite cette fonction est optimal à plus grande échelle pour commencer? – DGH

+0

Si vous appelez votre fonction "presque un million de fois", cela prendra environ 5 secondes - est-ce vraiment un problème? –

Répondre

2

Changez où vous faites le tri pour une économie d'environ 20%.

Modifier ceci:

def dupli(the_list): 
    return [(item, the_list.count(item)) for item in sorted(set(the_list))] 

à ceci:

def dupli(the_list): 
    count = the_list.count # this optimization added courtesy of Sven's comment 
    result = [(item, count(item)) for item in set(the_list)] 
    result.sort() 
    return result 

La raison pour laquelle c'est plus rapide que le sorted iterator doit créer une liste temporaire, alors que le tri des types de résultats en place.

modifier: Voici une autre approche qui est 35% plus rapide que l'original:

def dupli(the_list): 
    counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
    for n in the_list: 
     counts[n] += 1 
    return [(i, counts[i]) for i in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) if counts[i]] 

Note: Vous pouvez randomiser les valeurs the_list. Ma dernière version de dupli des tests encore plus rapide avec d'autres ensembles de données aléatoires (import random; the_list=[random.randint(0,12) for i in xrange(10)])

+0

C'est l'approche la plus rapide que j'ai vue jusqu'ici (en utilisant CPython 2.6.6). Il peut être légèrement amélioré en recherchant '.count()' en dehors de la compréhension de la liste (ie 'count = the_list.count' avant' result = ... ', puis en utilisant' (item, count (item)) ' dans la compréhension de la liste). –

+0

@Sven Marnach: Belle optimisation. J'ai mis à jour ma réponse pour l'inclure. J'ai également ajouté une autre approche qui était basée sur la réponse de John Machin, mais elle teste beaucoup plus rapidement en raison de l'élimination d '«énumérer» et parce qu'elle étend '[0] * 13' à son résultat. –

3

Je voudrais essayer:

from collections import defaultdict 
output = defaultdict(lambda: 0) 
for item in the_list: output[item] += 1 
return sorted(output.items()) 
+0

Sur mon ordinateur, cela prend environ deux fois le temps de la fonction 'dupli()' dans l'OP . –

+3

il sera plus rapide d'utiliser 'defaultdict (int)' au lieu d'utiliser le lambda –

0

Il pourrait être plus rapide d'écrire votre propre fonction qui compte les nombres en un seul passage dans la liste. Vous appelez la fonction count pour chaque numéro de l'ensemble, et chacun de ces appels nécessite un passage dans la liste.

counts = {} 
for n in the_list: 
    if n not in counts: 
     counts[n] = 0 
    counts[n] += 1 
sorted(counts.items()) 
+0

Ceci est plus lent que la fonction dans l'OP sur ma machine, mais par une marge plus petite que toutes les autres suggestions jusqu'à présent. –

0

Cela semble assez optimal en termes d'espace et de vitesse:

def dupli2(list_):          
    dict_ = {}          
    for item in list_:        
     dict_[item] = dict_.get(item, 0) + 1   
    return sorted(dict_.items())      

Ou ceci:

def dupli3(list_):            
    last = None            
    list_ = sorted(list_)          

    i = 0              
    for item in list_:           
     if item != last and last is not None:     
      yield last, i          
      i = 0            
     i += 1             
     last = item           

    yield last, i 

ne suis pas sûr de la vitesse cependant. Pour cela, je vous recommande que soit le faire en C ou utiliser Psyco;)

Avec Psyco:

In [33]: %timeit list(dupli3(test.the_list)) 
100000 loops, best of 3: 6.46 us per loop 

In [34]: %timeit list(dupli2(test.the_list)) 
100000 loops, best of 3: 2.37 us per loop 

In [35]: %timeit list(dupli(test.the_list)) 
100000 loops, best of 3: 2.7 us per loop 
+0

Ces deux fonctions sont significativement plus lentes sur ma machine que la fonction dans l'OP. De plus, la deuxième fonction renvoie un mauvais résultat. –

+0

@Sven Marnach: cela dépend, si vous utilisez 'psyco' que la méthode' dupli2' est plus rapide ici. Vous avez raison à propos de la méthode 'dupli3', j'ai fait une erreur stupide et j'ai accidentellement posté une version antérieure ici. Je vais le mettre à jour :) – Wolph

+0

OK, j'ai utilisé CPython 2.6.6. Cela devient légèrement plus rapide si vous déplacez la recherche d'attribut pour '.get()' hors de la boucle. –

2

Profitant de la qualification "entre 0 et 12":

>>> the_list = [5, 7, 6, 5, 5, 4, 4, 7, 5, 4] 
>>> answer1 = [0] * 13 
>>> for i in the_list: 
... answer1[i] += 1 
... 
>>> answer1 
[0, 0, 0, 0, 3, 4, 1, 2, 0, 0, 0, 0, 0] 
>>> # You might be able to use that as-is: 
... 
>>> for i, v in enumerate(answer1): 
...  if v: print i, v 
... 
4 3 
5 4 
6 1 
7 2 
>>> # Otherwise you can build the list that you specified: 
... 
>>> answer2 = [(i, v) for i, v in enumerate(answer1) if v] 
>>> answer2 
[(4, 3), (5, 4), (6, 1), (7, 2)] 
>>> 
+0

C'est la première chose que j'ai essayé. Sur ma machine, c'est en moyenne la même vitesse que l'original 'dupli()' - du moins si la sortie est convertie au format demandé ('answer2'). –

0

itertools.groupby est parfait pour cela:

>>> from itertools import groupby 
>>> the_list = [5, 7, 6, 5, 5, 4, 4, 7, 5, 4] 
>>> gb = groupby(sorted(the_list)) 
>>> print [(i,len(list(j))) for i,j in gb] 
[(4, 3), (5, 4), (6, 1), (7, 2)] 
+0

J'aime votre utilisation des itérateurs. En ce qui concerne l'optimisation, votre solution prend 2,5 fois plus de temps que le meilleur effort d'OP. –