为什么使用字典从一个列表中排除另一个列表的速度要快得多？

Question

令我惊讶的是，在两种方法中，排除一个元组列表与另一个元组列表的速度有多么不同。所以我想知道为什么。

我有一个包含1,500个元组的列表，其形式为(int，float )，按元组的值排序。(补充说明:元组列表中的每个int值都是不同的。)我想找出排除子列表的最快方法。所以首先我创建了一个子列表来排除：

exclude_list = [v for i,v in enumerate(tuple_list) if (i % 3) == 0]

然后，我选择了两种不同的方法从tuple_list中删除exclude_list (但这不是我最终确定的两种方法)：

remainder_list = [v for v in tuple_list if v not in exclude_list]

和,

remainder_set = set(tuple_list) - set(exclude_list)
remainder_list = sorted(remainder_set, key=itemgetter(1)) #edited to chance key to 1 from 0

时间上的差异是巨大的:第一种方法为14.7235秒(500次)，第二种方法为0.3426秒(500次)。我理解为什么这两种方法有如此不同的时间，因为第一种方法需要搜索主列表中的每一项的sub_list。因此，我想出了一个更好的搜索/排除方法：

exclude_dict = dict(exclude_list)
remainder_list = [v for v in tuple_list if v[0] not in exclude_dict]

我不认为这个版本的排除列表项会比第一个版本快很多。它不仅比第一种方法快，而且比第二种方法更快！它的时间是0.11177 (500次)。为什么这比我的set-difference/resort方法更快？

Answer 1

列表的in运算符的计算复杂度为O(N)。它只做一个线性搜索。要做得更好，您可以将exclude_list更改为exclude_set

exclude_set = {v for i,v in enumerate(tuple_list) if (i % 3) == 0}

或者，如果您已经有exclude_list

exclude_set = set(exclude_list)

然后像以前一样计算你的remainder_list：

remainder_list = [v for v in tuple_list if v not in exclude_set]

这是更好的WAY，因为集合的in是一个非常令人印象深刻的O(1) (平均)。在这里，您也不需要对remainder_list进行重新排序，因此删除了O(MlogM)步骤(其中M == len(remainder_list)。

当然，通过这个简单的例子，我们可以用一个list-comp来构造整个东西：

remainder_list = [v for i,v in enumerate(tuple_list) if (i % 3) != 0]     

Answer 2

您可能需要检查time complexity of list and set operations。

remainder_list = [v for v in tuple_list if v not in exclude_list] 

这里的in操作是O(N)，它检查tuple_list中的所有元素，看看exclude_list中是否存在该元素。所以它的复杂性是O(len(tuple_list) * len(exclude_list))

集合上的差分-操作的复杂度为O(n)，因为集合使用哈希表作为其底层数据结构，并且具有O(1)成员关系检查。因此，这行代码如下：

remainder_set = set(tuple_list) - set(exclude_list).

具有O(len(tuple_list))复杂性。

Answer 3

你们的算法不是等同的。你们的元素是情侣。使用前两种方法，您可以通过匹配对来排除元素。使用第三种方法(使用dict)，您可以排除仅比较情侣中的第一个元素的元素。

如果配对没有多少不同的第一个元素，那么dict方法要快得多，但结果可能不同。