时间戳

首页 > 解决方案 > Python：高效优雅地从大量列表中删除所有重复项

python - Python：高效优雅地从大量列表中删除所有重复项

问题描述

我有一个 xy 坐标列表作为列表：

print(xy[0:10])

[[104.44464000013596, 21.900339999891116],
 [9.574480000151937, 0.32839999976022227],
 [9.932610000251373, 0.19092000005798582],
 [9.821009999711748, 0.26556000039374794],
 [9.877130000349268, -0.6701499997226392],
 [149.51198999973872, -28.469329999879562],
 [149.35872999988965, -28.684280000021943],
 [9.859010000211413, -0.03293000041912819],
 [9.38918000035676, -0.9979400000309511],
 [77.35380000007001, 32.926530000359264]]

这里显示的是前 10 个，但我的列表中有大约 100,000 个坐标对。

我想从此列表中删除所有重复的列表，但要有效。作为一个更容易理解的示例，我想创建一个remove_dupes产生以下结果的函数：

a = [[1, 2], [3, 4], [5, 6], [1, 2], [1, 2], [8, 9], [3, 4]]
b = remove_dupes(a)
print(b)
b = [[5, 6], [8 ,9]]

请注意，保持顺序很重要。

但是，因为我有这么大的列表，我发现使用 .count() 方法并遍历列表太费时了。我还尝试了 set() 和 numpy 的独特功能的各种技巧。

这是我能想到的最快的版本：

xy = [[x1,y1], [x2,y2], ... [xn, yn]]

def remove_dupes(xy):

    xy = [tuple(p) for p in xy] # Tupelize coordinates list for hashing

    p_hash = [hash(tuple(p)) for p in xy] # Hash each coordinate-pair list to a single value

    counts = Counter(p_hash) # Get counts (dictionary) for each unique hash value

    p_remove = [key for (key, value) in counts.items() if value > 1] # Store keys with count > 1

    p_hash = np.array(p_hash) # Cast from list to numpy array 

    remove = np.zeros((len(xy),1), dtype=np.bool) # Initialize storage

    for p in p_remove: # Loop through each non-unique hash and set all the indices where it appears to True // Most time-consuming portion
        remove[np.where(p==p_hash)[0]] = True

    xy = np.array(xy) # Cast back to numpy array for indexing

    xy = xy[remove.flat==False, :]  # Keep only the non-duplicates

    return xy

对于约 100,000 个值，这需要约 2 秒（如果有更多重复的对、三元组等，则需要更长的时间）。困扰我的是，有像 numpy.unique() 这样的函数可以在几分之一秒内返回计数和索引，但我不知道如何符合它们的输出来解决这个问题。我浏览了几十个类似的其他 Stackexchange 帖子，但我发现没有一个既高效又优雅的帖子。有没有人有比我在这里提出的更优雅的解决方法的建议？

编辑：

我收到了两个提供正确结果（并保持顺序）的答案。RafaelC 提供了 Pandas 选项，DYZ 提供了 Counter 选项。我不太熟悉如何正确计时，但我运行了 100 次迭代（在相同的数据上），结果如下（使用 time.time()）

熊猫：13.02 秒

计数器：28.15 秒

我不确定为什么 Pandas 的实现速度更快；一个区别是 Pandas 解决方案返回元组（这没关系），所以我尝试了 Counter 解决方案而不转换回列表，它仍然是 25 秒。

标签： pythonperformanceduplicates

解决方案

我会用pandas

s = pd.Series(list(map(tuple, l)))
s[~s.duplicated(keep=False)].tolist()

需要

211 ms ± 16.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

对于 100000 个条目，因此加速了 10 倍。

推荐阅读