как оптимально считать элементы в списке Python

Question

Это почти тот же вопрос, что и здесь , за исключением того, что я спрашиваю о наиболее эффективном решении для отсортированного результата.

У меня есть список (около 10 целых чисел случайным образом от 0 до 12), например:

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

Я хочу создать функцию, которая возвращает список кортежей (элемент, количество), упорядоченных по первому элементу, например

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

До сих пор я использовал:

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

Но я вызываю эту функцию почти миллионный раз, и мне нужно сделать это так быстро, как я (Python) могу.Поэтому мой вопрос: Как сделать эту функцию менее трудоемкой?(как насчет памяти?)

Я немного поиграл, но ничего очевидного не возникло:

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

Спасибо
Кристоф

Answer 1

Изменение места сортировки для экономии около 20%.

Изменить это:

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

К этому:

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

Причина, по которой это происходит быстрее, заключается в том, что итератор sorted должен создать временный список, в то время как сортировка результатов производится по месту.

редактирование: Вот еще один подход, который на 35% быстрее вашего оригинала:

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

Примечание. Возможно, вы захотите рандомизировать значения для the_list. Моя окончательная версия dupli тестирует еще быстрее с другими случайными наборами данных (import random; the_list=[random.randint(0,12) for i in xrange(10)])

Answer 2

Я бы попробовал:

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

Answer 3

Воспользовавшись квалификацией "от 0 до 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 4

itertools.groupby идеально подходит для этого:

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

Answer 5

Это кажется довольно оптимальным с точки зрения пространства и скорости:

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

Или это:

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 

Не уверен насчет скорости, хотя. Для этого я бы порекомендовал вам сделать это на C или использовать 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 6

Может быть быстрее написать собственную функцию, которая подсчитывает числа за один проход по списку. Вы вызываете функцию подсчета для каждого номера в наборе, и для каждого из этих вызовов требуется пройти по списку.

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