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

这种天真的方法在 big-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 不相等怎么办？
有没有比先排序更有效的方法？

Answer 1

就您的分析而言，您在这两个方面都是正确的。

假设 n > m:您的第一个示例运行时间为 O(n*m)，您的第二个示例运行时间为 O(nlogn)，因为较大的排序支配较小的排序。 (注意: 假设它运行!当 n!=m 时，第二种方法很有可能导致错误 - 如果 len(arr1) > len(arr2)，否则它会遗漏 arr2)

末尾的项目

我们或许可以做得更好。鉴于您的第一个样本不能确保有序输出，我假设这不是必需的。如果是这样，下面将 a) 在 O(n+m) 中运行和 b) 跳过在两个列表中都没有找到 key 的项目。

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