comment compter de façon optimale les éléments dans une liste python

Question

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é.

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

Answer 1

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)])

Answer 2

Je voudrais essayer:

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

Answer 3

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()) 

Answer 4

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 

Answer 5

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)] 
>>> 

Answer 6

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)]