4

以下に説明するようにタプルのリストがあります(このタプルは2番目の値の降順でソートされています):

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

しきい値が与えられた場合、2番目の値がこのしきい値よりも小さいすべてのタプルを破棄するための最良の方法は何ですか。

500万を超えるタプルを使用しているため、タプルごとに比較タプルを実行して、別のタプルのリストを削除または追加したくありません。

4

5 に答える 5

7

タプルはソートされているため、しきい値よりも低い値を持つ最初のタプルを検索し、スライス表記を使用して残りの値を削除するだけです。

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))

私の疑惑は、最初に提案した線形時間検索がほとんどの状況で受け入れられるということです。

于 2012-09-12T15:37:14.630 に答える
2

これは、バイセクトを実行する前にリストをリストのようなオブジェクトにラップするエキゾチックなアプローチです。

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]
于 2012-09-12T18:02:17.433 に答える
1

たぶん@Curiousよりも少し速いコードです:

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

タプルは順序付けられているため、すべてを通過する必要はありません。

iもう1つの可能性は、二分法を使用して、しきい値を超えている最後の要素のインデックスを見つけることです。次に、次のようにします。

newTup=myTup[:i]

最後の方法が最速だと思います。

于 2012-09-12T15:40:19.070 に答える
0

扱っているタプルの数を考えると、NumPyの使用を検討することをお勧めします。

次のような構造化配列を定義します

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

タプルの2番目の要素にアクセスしてmyarray['f1']、float配列を取得できます。高度なインデックス作成手法を使用して、必要な要素をフィルタリングすることができます。

my_array[myarray['f1'] < threshold]

f1あなたがあなたよりも小さいエントリのみを保持しますthreshold

于 2012-09-12T15:35:16.343 に答える
0

itertoolsまた、例えばを使用することができます

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

反復可能なフィルタリングされたリストが必要な場合、または単に:

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

リストに直接移動します。

私はこれらのメソッドの相対的なパフォーマンスにあまり精通していないため、テストする必要があります(たとえば、%timeitを使用するIPythonで)。

于 2012-09-12T15:40:25.050 に答える