我有一个很容易以丑陋的方式做的问题,但我想知道是否有更多的Pythonic方式.
说我有三个列表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])
但这样做是否有更优雅,更有效(且重复性更低)的方式？如果列表数量增加,这可能会变得很麻烦.
拉链的三个列表,uniquify基于第一个元素,然后解压:
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)
这是一种非常常见的模式.无论何时你想锁定一堆列表(或其他迭代),你都可以将它们压缩在一起并循环结果.
此外,如果你从3个列表转到其中的42个("如果列表数量增长,这可能会变得很麻烦,它可能会."),这是微不足道的扩展:
abc = zip(*list_of_lists)
abc_unique = unique_everseen(abc, key=itemgetter(0))
list_of_lists = zip(*abc_unique)
一旦你掌握了zip,"uniquify"是唯一的难点,所以让我解释一下.
您现有的代码通过搜索每个元素来检查是否已经看到每个元素new_A.既然new_A是一个列表,这意味着如果你有N个元素,其中M个是唯一的,平均而言你将要对这N个元素中的每个元素进行M/2比较.插入一些大数字,NM/2变得非常大 - 例如,100万个值,其中一半是唯一的,并且你正在进行2500亿次比较.
要避免这种二次时间,请使用a set.A set可以在恒定而非线性的时间内测试元素的成员资格.因此,而不是2500亿次比较,这是100万次哈希查找.
如果您不需要维护订单或装饰 - 处理 - 未设计值,只需将列表复制到a即可set.如果你需要装饰,你可以使用一个dict而不是一个集合(键作为dict键,其他一些隐藏在值中).为了保持秩序,您可以使用OrderedDict,但在这一点上,更容易使用a list和a 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,两个版本大约是278ms和297ms(我忘记哪个是哪个)与二次版本的分钟相比.您可能可以将其优化微调至250毫秒左右 - 但很难想象您需要的情况,但不会因在PyPy中运行而不是CPython,或者在Cython或C中编写,或者把它弄得一团糟,或者让一台更快的计算机,或者并行化它.
至于空间,显式版本使它非常明显.像任何可以想象的非变异算法一样,我们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]将它设为二次方,因为从列表中间删除需要线性时间.幸运的是,线性时间是一个巨大的memmove,比同等数量的Python赋值快几个数量级,所以如果N不是太大你可以侥幸逃脱它 - 事实上,N=100000, M=10000它的速度是不可变版本的两倍......但是如果N可能太大,则必须用sentinel替换每个重复元素,然后在第二遍中循环遍历列表,这样您只能将每个元素移位一次,这比不可变版本慢50%.