1

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

我有一个（int，float）形式的1,500个元组的列表，按float值排序。（添加注意：元组列表中的每个 int 值都是不同的。）我想找出排除子列表的最快方法。所以首先我创建了一个要排除的子列表：

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

然后我确定了两种不同的移除方法exclude_list（tuple_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 次）。为什么这比我的设置差异/度假方法更快？

4

3 回答 3

3

您可能想要检查list 和 set 操作的时间复杂度。

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))复杂性。

于 2013-02-22T14:07:20.833 回答
2

列表的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]

这要好得多，因为in对于一个集合来说是一个非常令人印象深刻的 O(1)（平均而言）。在这里，您不需要重新排序remainder_list，因此删除了 O(MlogM) 步骤（其中M == len(remainder_list)）

当然，通过这个简单的例子，我们可以用 1 个 list-comp 构建整个事物：

remainder_list = [v for i,v in enumerate(tuple_list) if (i % 3) != 0]
于 2013-02-22T14:01:29.843 回答
2

您的算法不等效。你的元素是情侣。使用前两种方法，您可以通过匹配对来排除元素。使用第三种方法（使用 dict），您可以排除仅比较夫妻的第一个元素的元素。

如果这对夫妇的第一个元素很少不同，那么 dict 方法会快得多，但结果可能会有所不同。

于 2013-02-22T14:10:38.037 回答