Объединения списков с одинаковым первым индексом, но другим вторым индексом

Question

Я работаю на алгоритме поиска в питоне, но есть что-то я не получаю работать ..

У меня есть список, который выглядит как это [[» А», "1.txt"], [ "А", "2.txt"], [ "А", "3.txt"], [ "В", "1.txt"], [ "В" , "3.txt"]]

Теперь я хочу объединить суб-списки, имеющие тот же самый первый индекс. Таким образом, результатом будет:

[["A", ["1.txt", "2.txt", 3.txt "]], [" B ", [" 1.txt "], [ «3.txt»]]]

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

def merge_pairs(data): 
if len(data) <= 1 : 
    return data[:] 
else: 
     mid = len(data) // 2 
     fst = merge_pairs(data[:mid]) 
     snd = merge_pairs(data[mid:]) 
     res = [] 
     fi = 0 
     si = 0 
     while fi < len(fst) and si < len(snd): 
      if fst[fi][0] < snd[si][0] or fst[fi][0] == snd[si][0] and fst[fi][1] < snd[si][1]: 
       res.append(fst[fi]) 
       fi = fi + 1 
      else: 
       res.append(snd[si]) 
       si = si + 1 
     if fi < len(fst) : 
      res.extend(fst[fi:]) 
     elif si < len(snd) : 
      res.extend(snd[si:]) 
return res 

Так я как не использовать функцию ДИКТ() питона

Спасибо заранее

Answer 1

Th е простой способ (который может или не может быть медленнее, чем жесткий путь) заключается в использовании defaultdict:

>>> from collections import defaultdict 
>>> result = defaultdict(list) 
>>> mylist = [["A","1.txt"],["A","2.txt"],["A","3.txt"],["B","1.txt"],["B","3.txt"]] 
>>> for key, value in mylist: 
...  result[key].append(value) 
... 
>>> print(sorted(result.items())) 
[('A', ['1.txt', '2.txt', '3.txt']), ('B', ['1.txt', '3.txt'])] 

Трудный путь (если данные действительно уже отсортированы):

>>> src = [["A","1.txt"],["A","2.txt"],["A","3.txt"],["B","1.txt"],["B","3.txt"]] 
>>> prev = None 
>>> dst = [] 
>>> for key, value in src: 
...  if key != prev: 
...   prev = key 
...   dst.append((key, [])) 
...  dst[-1][-1].append(value) 
... 
>>> print(dst) 
[('A', ['1.txt', '2.txt', '3.txt']), ('B', ['1.txt', '3.txt'])] 

Но обратите внимание, что сортировка Python действительно, очень быстрая, и петли Python вроде этого ... Не так много.

Редактировать Согласно вашему комментарию ниже, вы также можете рассчитывать. Опять же есть словарь способ:

>>> from collections import defaultdict 
>>> result = defaultdict(lambda: defaultdict(int)) 
>>> mylist = [["A","1.txt"],["A","2.txt"],["A", "2.txt"],["A","3.txt"],["B","1.txt"],["B","3.txt"]] 
>>> for key, value in mylist: 
...  result[key][value] += 1 
... 
>>> print(sorted((x, sorted(y.items())) for (x, y) in result.items())) 
[('A', [('1.txt', 1), ('2.txt', 2), ('3.txt', 1)]), ('B', [('1.txt', 1), ('3.txt', 1)])] 

и способ цикла:

>>> src = [["A","1.txt"],["A","2.txt"],["A", "2.txt"],["A","3.txt"],["B","1.txt"],["B","3.txt"]] 
>>> prevkey, prevvalue = None, None 
>>> dst = [] 
>>> for key, value in src: 
...  if key != prevkey: 
...   prevkey = key 
...   prevvalue = None 
...   dst.append((key, [])) 
...  if value != prevvalue: 
...   prevvalue = value 
...   dst[-1][-1].append([value, 0]) 
...  dst[-1][-1][-1][-1] += 1 
... 
>>> dst 
[('A', [['1.txt', 1], ['2.txt', 2], ['3.txt', 1]]), ('B', [['1.txt', 1], ['3.txt', 1]])] 

Вы бы действительно хотите запустить timeit, чтобы быть уверенным, но в этом случае петля путь выглядит почти гарантированно быть медленнее (и, конечно, словарный способ не требует от вас предварительной сортировки.)