蟒合併未分類的清單 - 算法分析

鑑於兩個陣列具有如下結構：蟒合併未分類的清單 - 算法分析

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

陣列中的項目可以是未orderd內部，例如兩個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')]

這種幼稚的做法是在大澳爲O（n ** 2），

一個稍微好一點的方法是（？）排序列第一（與Python的排序是爲O（n log n）的）：

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 log n）的，是這個分析是正確的？
如果列表的長度不相等，那麼情況如何？m和n？
有沒有一種更有效的方法，然後再排序呢？

來源

2015-09-10 Oz123

如果物品丟失，應該輸出什麼內容？ – thefourtheye

你是說兩個數組的長度總是一樣嗎？ – Shrey

'元組（list（item）+ [arr2s [idx] [1]]）'可以是'item + arr2s [idx] [1：]'。由於元組的切片是元組，並且'+'連接元組就像列表一樣。 –

在你的分析而言，你在這兩方面都是正確的。

假設n> m：您的第一個示例運行在O（n * m），您的第二個O（nlogn）作爲較大的排序支配較小的排序。

我們可以 - （！NB！假設它運行的第二種方法導致的錯誤的一個很好的機會，當N = M或者提高索引錯誤，如果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')]

來源

2015-09-10 06:41:59 zehnpaard

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

的時間複雜度是O（M + N），其中m = LEN（ARR1）和n = LEN（ARR2），但這種方法花費更多的存儲器空間

來源

2015-09-10 06:03:41 Hooting

O(N Log(N))複雜必須在O(N²)是優選的。將1000.Log2(1000) ~ 9966與1000² = 1000000進行比較。

無論如何，這個頁面上的所有分析都是錯誤的，因爲他們認爲對諸如append或dictionary插入等Python結構的操作需要一定的時間，這是錯誤的。

來源

2015-09-10 09:09:38

是什麼讓你這麼說？ Python維基說其他網址https://wiki.python.org/moin/TimeComplexity – Oz123

因爲它們沒有考慮到動態內存分配/釋放的開銷。 –

那會是什麼複雜性？這是否改變我的分析？ – Oz123

蟒合併未分類的清單 - 算法分析

回答

相關問題