刪除元組

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:] 

作爲斯沃恩卡託指出的，一個二進制搜索將加快速度甚至米：與低於閾值的值，然後第一元組使用切片符號刪除其餘的值礦石。 bisect.bisect會很有用，除非您創建一個單獨的密鑰序列（如文檔here），否則它將不適用於您當前的數據結構。但這違反了你禁止創建新的列表。

不過，您可以使用source code作爲您自己的二進制搜索的基礎。或者，你可以改變你的數據結構：

>>> 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))的東西代替。）

我懷疑我在一開始提到的線性時間搜索在大多數情況下是可以接受的。

Answer 2

鑑於您正在處理的元組數量，您可能需要考慮使用NumPy。

定義structured array像

my_array= np.array(myTup, dtype=[('f0',"|S10"), ('f1',float)]) 

您可以myarray['f1']它給你一個int數組訪問元組的第二個元素。佑康知道用fancy indexing技術來過濾你想要的元素，如

my_array[myarray['f1'] < threshold] 

只保留條目在您f1小於你的threshold ..

Answer 3

也許有點快碼比@Curious的：

newTup=[] 
for tup in myTup: 
    if tup[1]>threshold: 
     newTup.append(tup) 
    else: 
     break 

因爲元組是有序的，你不必去通過所有的人。

另一種可能性也是，使用平分法，並找到最後一個元素的索引i，它高於閾值。那麼你會這樣做：

newTup=myTup[:i] 

我認爲最後的方法將是最快的。

Answer 4

您也可以使用itertools例如

from itertools import ifilter 
iterable_filtered = ifilter(lambda x : x[1] > threshold, myTup) 

如果你想要一個迭代過濾列表，或只是：

filtered = filter(lambda x: x[1] > threshold, myTup) 

直來直去的列表。

我對這些方法的相對性能不太熟悉，因此不得不測試它們（例如在IPython using %timeit）。

Answer 5

下面是一個奇特的方法，在執行平分之前將列表包裝在列表類對象中。

import bisect 

def revkey(items): 
    class Items: 
     def __getitem__(self, index): 
      assert 0 <= index < _len 
      return items[_max-index][1] 
     def __len__(self): 
      return _len 
     def bisect(self, value): 
      return _len - bisect.bisect_left(self, value) 
    _len = len(items) 
    _max = _len-1 
    return Items() 

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

for x in range(-2, 12): 
    assert len(tuples) == 10 
    t = tuples[:] 
    stop = revkey(t).bisect(x) 
    del t[stop:] 
    assert t == [item for item in tuples if item[1] >= x]