删除元组的智能方法

我有一个元组列表，如下所述（该元组按第二个值的降序排序）：

from string import ascii_letters
myTup = zip (ascii_letters, range(10)[::-1])
threshold = 5.5

>>> myTup
[('a', 9), ('b', 8), ('c', 7), ('d', 6), ('e', 5), ('f', 4), ('g', 3), ('h', 2), \
('i', 1), ('j', 0)]

给定一个阈值，丢弃第二个值小于该阈值的所有元组的最佳方法是什么。

我有超过 500 万个元组，因此不想逐个元组执行比较，从而删除或添加到另一个元组列表。

由于元组已排序，因此您可以简单地搜索值低于阈值的第一个元组，然后使用切片表示法删除剩余的值：

index = next(i for i, (t1, t2) in enumerate(myTup) if t2 < threshold)
del myTup[index:]

正如沃恩·卡托 (Vaughn Cato) 指出的那样，二分搜索会加快速度。bisect.bisect会很有用，但它不适用于您当前的数据结构，除非您创建一个单独的键序列，如文档所示here http://docs.python.org/library/bisect.html#other-examples。但这违反了您创建新列表的禁令。

不过，您仍然可以使用源代码 http://hg.python.org/cpython/file/2.7/Lib/bisect.py作为您自己的二分搜索的基础。或者，您可以更改数据结构：

>>> myTup
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e'), (5, 'f'), 
 (6, 'g'), (7, 'h'), (8, 'i'), (9, 'j')]
>>> index = bisect.bisect(myTup, (threshold, None))
>>> del myTup[:index]
>>> myTup
[(6, 'g'), (7, 'h'), (8, 'i'), (9, 'j')]

这里的缺点是删除可能会在线性时间内发生，因为Python必须将整个内存块移回...除非Python很聪明地删除从0。 （有人知道吗？）

最后，如果你是really愿意改变你的数据结构，你可以这样做：

[(-9, 'a'), (-8, 'b'), (-7, 'c'), (-6, 'd'), (-5, 'e'), (-4, 'f'), 
 (-3, 'g'), (-2, 'h'), (-1, 'i'), (0, 'j')]
>>> index = bisect.bisect(myTup, (-threshold, None))
>>> del myTup[index:]
>>> myTup
[(-9, 'a'), (-8, 'b'), (-7, 'c'), (-6, 'd')]

（请注意，Python 3 会抱怨None比较，所以你可以使用类似的东西(-threshold, chr(0))反而。）

我怀疑我一开始建议的线性时间搜索在大多数情况下是可以接受的。