Intelligentes löschen von Tupeln

Ich eine Liste von Tupel, wie beschrieben, unten (Diese Tupel werden sortiert in absteigender Reihenfolge nach der zweite Wert):

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

Einem gegebenen Schwellenwert, was ist die beste Art und Weise zu verwerfen, alle Tupel mit der zweite Wert kleiner als dieser Schwellenwert.

Ich bin mit mehr als 5 Millionen Tupel und somit nicht ausführen möchten Vergleich Tupel Tupel von basis-und somit löschen oder hinzufügen zu einer anderen Liste von Tupeln.

Da deine Liste ist bereits sortiert: Wie über den ersten zu tun binäre Suche zu finden ist der index das erste Tupel unterhalb der Schwelle.

InformationsquelleAutor Curious | 2012-09-12

python tuples

7

Da die Tupel sortiert, Sie können einfach eine Suche für das erste Tupel mit einem Wert, der niedriger als der Schwellenwert ist, und löschen Sie dann die verbleibenden Werte mit slice-notation:
```
index = next(i for i, (t1, t2) in enumerate(myTup) if t2 < threshold)
del myTup[index:]
```
Als Vaughn Cato Punkte heraus, eine binäre Suche würde die Dinge beschleunigen sogar noch mehr. bisect.bisect nützlich wäre, außer, dass es gewann ' T Arbeit mit Ihrem aktuellen Struktur der Daten, es sei denn, Sie erstellen eine separate Schlüssel-Sequenz, wie beschrieben,hier. Aber, die gegen Ihr Verbot auf erstellen von neuen Listen.

Immer noch, Sie könnten die source code als Grundlage für Ihre eigene binäre Suche. Oder Sie könnten Ihre Daten ändern Struktur:
```
>>> 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')]
```
Der Nachteil hier ist, dass der Löschvorgang kann auftreten, in der linearen Zeit, da Python wird eine Verschiebung der gesamte Speicherblock zurück... es sei denn Python ist smart über das löschen von Scheiben, die aus 0. (Wer weiß?)

Schließlich, wenn Sie wirklich bereit, Ihre Daten ändern Struktur, Sie könnten dies tun:
```
[(-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')]
```
(Beachten Sie, dass Python 3 wird sich über die None Vergleich, so könnten Sie so etwas wie (-threshold, chr(0)) statt.)

Mein Verdacht ist, dass die lineare Zeit Suche ich schlug vor, am Anfang ist akzeptabel, in den meisten Fällen.

Guter Punkt, um die Werte, die sortiert wird. Wie wäre es mit einer binären Suche zu beschleunigen?
Sie können nicht mit bisect so, denn vergleicht man nur die Schwelle, und nicht die Buchstaben. Ein key argument für bisect wäre toll...
du hast Recht-brauchte eine Sekunde um zu realisieren, dass.
Auch, halbieren nur sortiert in aufsteigender Reihenfolge. Nach der docs, es sieht aus wie Sie empfehlen, die eine Liste (von Schlüssel-mapping-Funktion über die original-Liste) und dabei ein halbieren auf dieser Liste.
Dies ist überraschend schwierig zu tun, richtig (ich war auf halbem Weg durch die reversed-view-wrapper, bevor ich beschlossen, es war dumm). Die bisect Modul ist auf jeden Fall weniger komfortabel als es sein könnte.

InformationsquelleAutor senderle

Hier ist ein exotischer Ansatz, wickelt sich die Liste in ein list-Objekt vor der Durchführung halbieren.

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]

+1: dies ist die Art von Sache, die ich dachte, war oben. Auf Reflexion ich bin tatsächlich ein wenig überrascht, dass ich noch nie brauchte eine umgekehrte Ansicht vor.

InformationsquelleAutor Peter Otten

1

Vielleicht ein bisschen schnelleren code als der @Neugierige:
```
newTup=[]
for tup in myTup:
    if tup[1]>threshold:
        newTup.append(tup)
    else:
        break
```
Da Tupel geordnet sind, müssen Sie nicht zu gehen durch alle von Ihnen.

Andere Möglichkeit wäre auch, zu verwenden Zweiteilung, und finden Sie den index i des letzten Elements, das über der Schwelle. Dann würden Sie tun:
```
newTup=myTup[:i]
```
Ich denke, dass die Letzte Methode ist die Schnellste.

InformationsquelleAutor Nejc
0

Angesichts der Anzahl der Tupel, die Sie zu tun, möchten Sie vielleicht zu prüfen, mit NumPy.

Definieren structured array wie
```
my_array= np.array(myTup, dtype=[('f0',"|S10"), ('f1',float)])
```
Können Sie den Zugriff auf die zweiten Elemente der Tupel mit myarray['f1'] die Ihnen ein float-array. Youcan wissen Verwendung fancy indexing Techniken zum filtern der Elemente, die Sie wollen, wie
```
my_array[myarray['f1'] < threshold]
```
halten nur die Einträge, wo Ihr f1 weniger als Ihre threshold..

InformationsquelleAutor Pierre GM
0

Können Sie auch itertools z.B.
```
from itertools import ifilter
iterable_filtered = ifilter(lambda x : x[1] > threshold, myTup)
```
Wenn Sie wollte einen wiederholenden gefilterten Liste oder einfach nur:
```
filtered = filter(lambda x: x[1] > threshold, myTup)
```
gerade zu gehen zu einer Liste.

Ich bin nicht allzu vertraut mit der relativen performance von diesen Methoden und haben würde, um Sie zu testen (z.B. in IPython mit %timeit).

InformationsquelleAutor Martin

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.