我很惊讶两种方法排除一个元组列表的速度有多么不同。所以我想知道为什么。
我有一个包含 1,500 个元组的列表，形式为 (int, float)，按 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 次)。为什么这比我的集合差异/度假村方法更快？
请您参考如下方法:
您可能需要检查 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)) 复杂度。
