Python слияния несортированных списков - анализ алгоритма

Question

Указанные два массива со следующей структурой:

array = [(index_1, item_1), (index_2, item_2), ..., (index_n, item_n)] 

Внутри массива элементы могут быть просто не упорядочены, например двух списков Python:

arr1 = [(1,'A'), (2, 'B'), (3,'C')] 
arr2 = [(3,'c'), (2, 'b'), (1,'a')] 

Я хотел бы проанализировать слияние этих массивов. Есть два способа, которыми я мог бы думать о слиянии. Первый из них был бы наивным итерации по обоим массивов:

merged = [] 
for item in arr: 
    for item2 in arr2: 
     if item[0] == item2[0]: 
      merged.append((item[0], item[1], item2[1])) 

# merged 
# [(1, 'A', 'a'), (2, 'B', 'b'), (3, 'C', 'c')] 

Этот наивный подход будет в большой-о О (п ** 2),

Немного лучше было бы (?) сортировать массивы первые (с Python сортировки будучи O (п § п)):

arr.sort(key=lambda t: t[0]) 
arr2.sort(key=lambda t: t[0]) 

for idx, item in enumerate(arrs): 
    merged_s.append(tuple(list(item)+[arr2s[idx][1]])) 

Так что этот подход будет O (N журнал N) в общей сложности, этот анализ правильно?
Что относительно случая, когда списки имеют неравные длины m и n?
Есть ли более эффективный способ сортировки как первым?

Answer 1

С точки зрения вашего анализа, вы правы по обоим пунктам.

Предполагая, что n> m: ваш первый пример выполняется в O (n * m), ваш второй O (nlogn), поскольку более крупный сорт доминирует над меньшим сорт. (! NB: Предполагая, что он работает второй метод имеет хороший шанс вызвать ошибки при п = т - либо повышение ошибки индекса, если len(arr1) > len(arr2), или он будет не хватать пунктов в конце arr2)

Мы можем вероятно, лучше. Учитывая, что ваш первый образец не обеспечивает упорядоченный вывод, я предполагаю, что это не является обязательным требованием. Если это так, ниже будет: a) работать в O (n + m) и b) пропускать элементы, в которых ключ не был найден в обоих списках.

import itertools 
arr1 = [(1,'A'), (2, 'B'), (3,'C'), (4, 'D')] 
arr2 = [(3,'c'), (2, 'b'), (1,'a'), (5, 'E')] 

output_dict = {} 
for key, value in itertools.chain(arr1, arr2): # I like itertools 
    output_dict.setdefault(key, []).append(value) 
output = [(key,)+tuple(values) for key, values in output_dict.items() if len(values)==2] 

Выходной сигнал будет:

[(1, 'A', 'a'), (2, 'B', 'b'), (3, 'C', 'c')] 

Answer 2

arr1 = [(1,'A'), (2, 'B'), (3,'C')] 
arr2 = [(3,'c'), (2, 'b'), (1,'a')] 
key2value = dict() 
for item in arr1: 
    key2value[item[0]] = [item[1]] 
for item in arr2: 
    try: 
     value = key2value[item[0]] 
     value.append(item[1]) 
    except: 
     key2value[item[0]] = [item[1]] 

result = [tuple([key] + value) for key, value in key2value.iteritems()] 

Временная сложность представляет собой О (т + п), где т = Len (arr1) и п = Len (arr2), но этот метод стоит больше пространства памяти

Answer 3

O(N Log(N)) сложность должна быть более предпочтительным, чем O(N²). Сравнить 1000.Log2(1000) ~ 9966 до 1000² = 1000000.

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