智能删除元组的方法

Question

我有一个元组列表,如下所述(此元组按第二个值的降序排序):

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万元组,因此不希望按元组基础执行比较元组,因此删除或添加到另一个元组列表.

Answer 1

由于元组已排序,您只需搜索值低于阈值的第一个元组,然后使用切片表示法删除其余值:

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

正如Vaughn Cato指出的那样,二进制搜索会加快速度.bisect.bisect除非你创建一个单独的键序列,否则它将不适用于您当前的数据结构,如此处所述.但这违反了您禁止创建新列表的禁令.

不过,您可以使用源代码作为自己的二进制搜索的基础.或者,您可以更改数据结构:

>>> 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.(有人知道吗？)

最后,如果您真的愿意更改数据结构,可以这样做:

[(-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)).)

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