Каков самый быстрый способ комбинировать и сортировать списки кортежей?

Question

У меня есть список списков кортежей. Каждый кортеж имеет форму (string,int), например.

lst = list() 
lst.append([('a',5),('c',10),('d',3),('b',1)]) 
lst.append([('c',14),('f',4),('b',1)]) 
lst.append([('d',22),('f',2)]) 

Think из int-х, как эпизоды каждой строки в различных блоках текста.

Что мне нужно сделать, это создать список топ-N возникающих строк вместе с их совокупными значениями. Таким образом, в приведенном выше примере, a появляется в 5 раз, b появляется дважды, c появляется 24 раз и т.д. Если N=2, то я должен был бы производить либо пару параллельных списков ['d','c'] и [25,24] или список кортежей [('d',25),('c',24)]. Мне нужно сделать это как можно быстрее. У моей машины много оперативной памяти, поэтому память не является проблемой.

У меня есть эта реализация:

import numpy as np 
def getTopN(lst,N): 

    sOut = [] 
    cOut = [] 

    for l in lst: 
     for tpl in l: 
      s = tpl[0] 
      c = tpl[1] 

      try: 
       i = sOut.index(s) 
       cOut[i] += c 
      except: 
       sOut.append(s) 
       cOut.append(c) 

    sIndAsc = np.argsort(cOut).tolist() 
    sIndDes = sIndAsc[::-1] 
    cOutDes = [cOut[sir] for sir in sIndDes] 
    sOutDes = [sOut[sir] for sir in sIndDes] 

    return sOutDes[0:N],cOutDes[0:N] 

Там Должен быть лучший путь, но что бы это было?

Answer 1

Использование collections.Counter:

import collections 
c = collections.Counter() 
for x in lst: 
    c.update(dict(x)) 
print(c.most_common(2)) 

Выход:

[('d', 25), ('c', 24)] 

Counter в основном словарь с некоторой дополнительной функциональностью, поэтому глядя значение и добавляя к нему актуальностью счетчик очень быстро. dict(x) просто превратит список кортежей в обычный dict, преобразуя строки в числа, тогда метод update из Counter добавит эти подсчеты (вместо того, чтобы просто переписать значения, как это сделал бы обычный dict).

В качестве альтернативы, более ручной подход с использованием defaultdict:

c = collections.defaultdict(int) 
for x, y in (t for x in lst for t in x): 
    c[x] += y 
return [(k, c[k]) for k in sorted(c, key=c.get, reverse=True)][:2] 

Как отметил Джон в комментариях defaultdict действительно намного быстрее:

In [2]: %timeit with_counter() 
10000 loops, best of 3: 17.3 µs per loop 
In [3]: %timeit with_dict() 
100000 loops, best of 3: 4.97 µs per loop 

Answer 2

Другой вариант, используя numpy:

# make a flattened numpy version of the list 
lst_np = np.asarray([item for sublist in lst for item in sublist]) 

# split into the two columns 
chars = lst_np[:,0] 
counts = lst_np[:,1].astype('int') 

# get unique characters, and compute total counts for each 
[unique_chars, unique_inds] = np.unique(chars, return_inverse=True) 
unique_counts = np.asarray([np.sum(counts[unique_inds==x]) 
    for x in range(len(unique_chars))]) 

Это даст вам c ounts (unique_counts) для каждого уникального персонажа (unique_chars) в списках, а не только в верхней части N. Это должно быть довольно быстро, но может быть тяжелым в памяти.