从一个Python列表中移除重复项，并根据其修剪其他列表
我遇到了一个问题，虽然用一种不太好看的方法可以解决，但我在想有没有更符合Python风格的方法。
假设我有三个列表，A、B和C。
A = [1, 1, 2, 3, 4, 4, 5, 5, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 9]
C = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# The actual data isn't important.
我需要从列表A中删除所有重复的项，但当删除一个重复项时，我也希望从B和C中删除对应的索引：
A = [1, 2, 3, 4, 5]
B = [1, 3, 4, 5, 7]
C = [1, 3, 4, 5, 7]
用更长的代码把所有东西移动到新列表中，这个操作其实挺简单的：
new_A = []
new_B = []
new_C = []
for i in range(len(A)):
if A[i] not in new_A:
new_A.append(A[i])
new_B.append(B[i])
new_C.append(C[i])
但是有没有更优雅、更高效（而且不那么重复）的做法呢？如果列表的数量增加，这样的操作可能会变得很麻烦。
2 个回答
这样做怎么样呢 - 首先获取集合A中所有不重复的元素，然后找到这些元素在原始列表中的位置，最后根据这些位置创建一个新的列表。
new_A = list(set(A))
indices_to_copy = [A.index(element) for element in new_A]
new_B = [B[index] for index in indices_to_copy]
new_C = [C[index] for index in indices_to_copy]
你可以为第二个步骤写一个函数，这样以后可以重复使用：
def get_new_list(original_list, indices):
return [original_list[idx] for idx in indices]
把这三个列表合并在一起，基于第一个元素去重，然后再拆分开：
from operator import itemgetter
from more_itertools import unique_everseen
abc = zip(a, b, c)
abc_unique = unique_everseen(abc, key=itemgetter(0))
a, b, c = zip(*abc_unique)
这种做法非常常见。每当你想要对一堆列表（或者其他可迭代对象）进行同步操作时，就可以把它们合并在一起，然后遍历结果。
而且，如果你从三个列表扩展到四十二个（“如果列表数量增加，这可能会变得麻烦。”），这个方法也很容易扩展：
abc = zip(*list_of_lists)
abc_unique = unique_everseen(abc, key=itemgetter(0))
list_of_lists = zip(*abc_unique)
一旦你掌握了 zip，那么“去重”就是唯一比较复杂的部分，让我来解释一下。
你现有的代码通过在 new_A 中查找每个元素来检查它是否已经出现过。由于 new_A 是一个列表，这意味着如果你有 N 个元素，其中 M 个是唯一的，平均来说你会对每个 N 元素进行 M/2 次比较。假设数字很大，NM/2 会变得非常庞大——例如，1百万个值，其中一半是唯一的，你就要进行 2500 亿次比较。
为了避免这种平方级的时间复杂度，你可以使用 set。set 可以以常数时间检查一个元素是否存在，而不是线性时间。所以，比较次数从 2500 亿次减少到 100 万次哈希查找。
如果你不需要保持顺序或者对值进行装饰处理，只需将列表复制到一个 set 中就可以了。如果需要装饰，可以用 dict 替代 set（用键作为 dict 的键，其他内容放在值中）。为了保持顺序，你可以使用 OrderedDict，但在这种情况下，使用一个 list 和一个 set 并排使用会更简单。例如，最小的代码修改如下：
new_A_set = set()
new_A = []
new_B = []
new_C = []
for i in range(len(A)):
if A[i] not in new_A_set:
new_A_set.add(A[i])
new_A.append(A[i])
new_B.append(B[i])
new_C.append(C[i])
但这可以被推广——尤其是如果你打算从 3 个列表扩展到很多个。
itertools 文档中的配方包含一个叫 unique_everseen 的函数，正好可以实现我们想要的功能。你可以把它复制粘贴到你的代码中，自己写一个简化版，或者 pip install more-itertools 使用别人的实现（就像我上面做的那样）。
PadraicCunningham 问：
zip(*unique_everseen(zip(a, b, c), key=itemgetter(0)))的效率如何？
如果有 N 个元素，M 个唯一元素，它的时间复杂度是 O(N)，空间复杂度是 O(M)。
实际上，它的工作量和上面 10 行代码的版本是一样的。在这两种情况下，循环中唯一不明显简单的工作是 key in seen 和 seen.add(key)，由于这两个操作对于 set 来说是摊销常数时间，所以整个过程的时间复杂度是 O(N)。实际上，对于 N=1000000, M=100000，这两个版本的执行时间分别是大约 278 毫秒和 297 毫秒（我忘了哪个是哪个），而平方版本则需要几分钟。你可能可以微调到 250 毫秒左右——但很难想象在这种情况下你需要这么快，而不考虑使用 PyPy 替代 CPython，或者用 Cython 或 C 编写，或者使用 numpy，或者换一台更快的电脑，或者并行处理。
至于空间，显式版本让这一点非常明显。像任何可能的非变异算法一样，我们同时保留了三个 new_Foo 列表和原始列表，并且还增加了同样大小的 new_A_set。由于这些都是长度为 M，所以总共占用 4M 的空间。我们可以通过一次遍历获取索引来将其减半，然后做和 mu 无 的答案一样的事情：
indices = set(zip(*unique_everseen(enumerate(a), key=itemgetter(1))[0])
a = [a[index] for index in indices]
b = [b[index] for index in indices]
c = [c[index] for index in indices]
但没有办法再低于这个；你必须至少保留一个长度为 M 的集合和一个列表，才能在线性时间内对长度为 N 的列表去重。
如果你真的需要节省空间，可以就地修改这三个列表。但这要复杂得多，而且会稍微慢一点（虽然仍然是线性时间*）。
此外，值得注意的是 zip 版本的另一个优点：它可以在任何可迭代对象上工作。你可以给它三个惰性迭代器，它就不需要急于实例化它们。我认为在 2M 空间内是做不到的，但在 3M 空间内并不太难：
indices, a = zip(*unique_everseen(enumerate(a), key=itemgetter(1))
indices = set(indices)
b = [value for index, value in enumerate(b) if index in indices]
c = [value for index, value in enumerate(c) if index in indices]
* 注意，单纯使用 del c[i] 会使其变成平方时间，因为从列表中间删除元素需要线性时间。幸运的是，这种线性时间是一个巨大的内存移动，速度比相同数量的 Python 赋值快几个数量级，所以如果 N 不会“太大”，你可以这样做——实际上，对于 N=100000, M=10000，它的速度是不可变版本的两倍……但如果 N 可能会太大，你就必须用一个哨兵替换每个重复元素，然后在第二次遍历中遍历列表，这样每个元素只移动一次，这样反而比不可变版本慢 50%。