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

这种天真的方法是大 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

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)，但这种方法需要更多的内存space

Answer 2

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

假设 n > m：您的第一个示例运行s 在 O(n*m) 时，您的第二个 O(nlogn) 作为较大的排序支配较小的排序。（注意： 假设它运行s！当 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')]

Answer 3

O(N Log(N)) 复杂性必须优先于 O(N²)。比较 1000.Log2(1000) ~ 9966 与 1000² = 1000000.

无论如何，本页的所有分析都是错误的，因为它们假设对 Python 结构的操作（例如追加或字典插入）需要常数时间，这是错误的。

python 合并未排序列表 - 算法分析

python merging unsorted lists - algorithm analysis

python

sorting

algorithm

big-o

list