我很惊讶两种排除元组列表的方法的速度有多么不同。所以我想知道为什么。
我有一个1500个元组的列表，格式为（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次）。我理解为什么这两种方法的时间如此不同，因为第一种方法需要在子列表中搜索主列表中的每个项目。于是，我想出了一个更好的搜索/排除方法：
exclude_dict = dict(exclude_list)
remainder_list = [v for v in tuple_list if v[0] not in exclude_dict]
我不认为这个排除列表项目的版本会比第一个快得多。它不仅比第一种方法快，而且比第二种方法快！它的倍数为0.11177（500倍）。为什么这比我设定的差异/度假方式更快？
您可能需要检查列表和集合操作的时间复杂性。
remainder_list = [v for v in tuple_list if v not in exclude_list]
这里的in操作是O（N），它查看元组列表中的所有元素，看看元素是否存在于exclude_list中。所以它的复杂度是O(len(tuple_list) * len(exclude_list))
对集合的差分-运算具有O（n）复杂性，因为集合使用哈希表作为其底层数据结构，并且具有O（1）成员身份检查。因此，这条线：
remainder_set = set(tuple_list) - set(exclude_list).
具有CCD_ 7复杂度。
列表的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）
当然，对于这个微不足道的例子，我们可以用1个列表comp:来构建整个东西
remainder_list = [v for i,v in enumerate(tuple_list) if (i % 3) != 0]
您的算法并不等价。你的元素是情侣。使用前两种方法，可以通过匹配对来排除图元。使用第三种方法（使用dict），可以排除只比较夫妇中第一个元素的元素。
如果这对夫妇很少有不同的第一元素，那么dict方法会快得多，但结果可能会有所不同。