python 列表减法，优化速度

Question

为了找出 python 中两个列表的替换，我使用：

names_of_files_not_dowloaded = [item for item in total_files if item not in names_of_files_downloaded]

有效。

列表的大小是：

文件总数56373个元素

已下载文件列表 28464 个元素

持续34秒。不知何故，我的直觉是 34 秒太长了。有什么方法可以更有效地进行减法吗？

谢谢

编辑：元素类似于 'AB12345'

这些列表没有任何重复的元素，它们已经是集合了

Answer 1

只需将 files_downloaded 设为集合而不是列表。列表可能需要列表的完整迭代来进行成员资格检查，每次您想进行检查。但是集合是 much more efficient to do a lookup on.

只需使用：

downloaded_set = set(files_downloaded)
list_of_files_not_dowloaded = [item for item in total_files if item not in downloaded_set]

将列表放入集合中需要初始成本，但之后的成员资格检查会快得多。

@juanpa.arrivillaga 在评论中还提到，造成性能下降的另一个原因是 in 对字符串进行相等性检查，而使用 Set 时会比较哈希，而后者要多得多便宜。

看起来，如果我没看错来源，CPython's lists use a straight equality check to do comparisons when checking for membership。据推测，Sets 使用哈希，并且它们在 Set 创建时被缓存。

Answer 2

total_files_set = set(total_files)
files_downloaded_set = set(files_downloaded)
files_not_dowloaded_set = total_files_set - files_downloaded_set 
list_of_files_not_dowloaded = list(files_not_dowloaded_set)

或者如果你想在一行中：

list_of_files_not_dowloaded = list(set(total_files) - set(files_downloaded))

想了解更多关于集合的所有操作，可以查看here

编辑:
我尝试使用 2 个随机列表对这两种方法进行计时

对于具有 50,000 个元素的子集和具有 100,000 个元素的超集

timeit.timeit('l = list(set(l1)-set(l2))', 
setup='import random; l1 = random.sample(range(1000000), 100000); l2 = random.sample(range(1000000), 50000)', 
number = 10)

输出：

0.39393879500130424

timeit.timeit('l = [item for item in l1 if item not in l2]', \
setup='import random; l1 = random.sample(range(1000000), 10000); l2 = random.sample(range(1000000), 5000)', \
number = 1)

输出：

98.58012624000003

如果您恰好已经拥有这两个集合，而不必从列表中转换：

timeit.timeit('l = list(s2-s1)', 
setup='import random; s1 = set(random.sample(range(1000000), 100000)); s2 = set(random.sample(range(1000000), 50000))', 
number = 10)

输出：

0.06160322100004123

Answer 3

如果您不关心元素的顺序并且您的列表不包含重复项，您可以简单地使用：

diff = set(total_files) - set(files_downloaded)

如果您需要以列表形式输出：

diff = list(set(total_files) - set(files_downloaded))

set 覆盖了 __sub__() 方法并将其用作设置差异，这就是您要查找的内容。

正如你的问题所说，列表不包含重复项并且表现得像集合，这应该会以相对较好的性能满足你的需求。

python 列表减法，优化速度

subtraction of lists in python, optimising speed

python

list

subtraction