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

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

diff = set(total_files) - set(files_downloaded)

如果需要输出作为列表：

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

set重写__sub__()方法并将其用作集差，这就是您要查找的内容。你知道吗

正如您的问题所说的，列表不包含重复项，其行为类似于集合，这将以相对良好的性能满足您的需求。你知道吗

Answer 2

把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]

这将有一个初始成本，把名单到一个集合，但成员资格检查之后将快得多。你知道吗

---

你知道吗@胡安帕.阿里维拉加在评论中还提到了另一个导致性能下降的原因是in对字符串进行了相等性检查，而在使用集合时比较哈希，后者要便宜得多。你知道吗

似乎，如果我读对了源代码，CPython's lists use a straight equality check to do comparisons when checking for membership。据推测，集合使用哈希，它们在集合创建时被缓存。你知道吗

Answer 3

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个随机列表

• 对于包含50000个元素的子集和包含100000个元素的超集

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