Suchen Sie in Python den Eintrag in der Liste der Dicts mit Hilfe von bisect

8

Ich habe eine Liste von Diktaten, etwa so:

%Vor%

Die dict-Elemente sind in der Liste nach den 'offset' -Daten sortiert. Die realen Daten könnten viel länger sein.

Was ich tun möchte, ist, ein Element in der Liste nach einem bestimmten Offset-Wert zu suchen, der nicht genau einer dieser Werte ist, aber in diesem Bereich. Also, eine binäre Suche ist was ich machen will.

Mir ist jetzt das Python-Modul bisect bekannt, bei dem es sich um eine fertige binäre Suche handelt. toll, aber nicht direkt nutzbar für diesen Fall. Ich frage mich nur, was ist der einfachste Weg, um bisect auf meine Bedürfnisse anzupassen. Hier ist, was ich gefunden habe:

%Vor%

Es druckt:

%Vor%

Meine Frage ist, ist dies der beste Weg, um zu tun, was ich will, oder gibt es einen anderen einfacheren, besseren Weg?

    
Craig McQueen 27.08.2009, 23:43
quelle

4 Antworten

3

Das übliche Muster ähnelt dem Sortieren nach einem Attribut, dekorieren, bedienen und nicht verzieren. In diesem Fall müssten Sie nur dekorieren und dann anrufen. Sie möchten dies jedoch vermeiden, da decorate O (n) ist, während Sie möchten, dass O (logn) ist. Daher würde ich Ihre Methode für am besten halten.

    
Alex Gaynor 27.08.2009, 23:56
quelle
6

Sie können auch eine der vielen SortedDict-Implementierungen von Python verwenden, um Ihre test_data zu verwalten. Ein sortierter Ausdruck sortiert die Elemente nach Schlüssel und pflegt eine Zuordnung zu einem Wert. Einige Implementierungen unterstützen auch eine Halbierung der Schlüssel. Zum Beispiel hat das Python sortedcontainers-Modul eine SortedDict , das Ihren Anforderungen entspricht.

In Ihrem Fall würde es ungefähr so ​​aussehen:

%Vor%

Der SortedDict-Typ hat eine Halbierungsfunktion, die den halbierten Index des gewünschten Schlüssels zurückgibt. Mit diesem Index können Sie den tatsächlichen Schlüssel nachschlagen. Und mit diesem Schlüssel können Sie den Wert erhalten.

All diese Operationen sind sehr schnell in sortedcontainers, was auch in pure-Python praktikabel ist. Es gibt auch einen Leistungsvergleich , der andere Auswahlmöglichkeiten diskutiert und Benchmark-Daten enthält.

    
GrantJ 08.04.2014 19:14
quelle
4
___ answer22946210 ___

Sie können auch eine der vielen SortedDict-Implementierungen von Python verwenden, um Ihre test_data zu verwalten. Ein sortierter Ausdruck sortiert die Elemente nach Schlüssel und pflegt eine Zuordnung zu einem Wert. Einige Implementierungen unterstützen auch eine Halbierung der Schlüssel. Zum Beispiel hat das Python sortedcontainers-Modul eine SortedDict , das Ihren Anforderungen entspricht.

In Ihrem Fall würde es ungefähr so ​​aussehen:

%Vor%

Der SortedDict-Typ hat eine Halbierungsfunktion, die den halbierten Index des gewünschten Schlüssels zurückgibt. Mit diesem Index können Sie den tatsächlichen Schlüssel nachschlagen. Und mit diesem Schlüssel können Sie den Wert erhalten.

All diese Operationen sind sehr schnell in sortedcontainers, was auch in pure-Python praktikabel ist. Es gibt auch einen Leistungsvergleich , der andere Auswahlmöglichkeiten diskutiert und Benchmark-Daten enthält.

    
___ answer1344347 ___

Das übliche Muster ähnelt dem Sortieren nach einem Attribut, dekorieren, bedienen und nicht verzieren. In diesem Fall müssten Sie nur dekorieren und dann anrufen. Sie möchten dies jedoch vermeiden, da decorate O (n) ist, während Sie möchten, dass O (logn) ist. Daher würde ich Ihre Methode für am besten halten.

    
___ answer1344501 ___

Was Sie tun können, ist dies

%Vor%

Dies sollte Ihnen erlauben, eine einfache %code% of %code% Instanzen zu erstellen. Der Algorithmus %code% sollte vollkommen glücklich sein, die definierten Operatoren zu verwenden.

Sie können Ihre %code% verwenden.

Oder

%Vor%

Das sollte die %code% eher wie eine %code% machen.

    
___ tag123dictionary ___ Ein Wörterbuch (oder eine Karte) in der Informatik ist eine Datenstruktur, die Schlüssel auf Werte abbildet, so dass bei einem Schlüssel der entsprechende Wert effizient abgerufen werden kann. Bei Fragen zu Mapping-Funktionen über Datensammlungen verwenden Sie bitte das Tag [map-function]; und für Geographie, [Karten]. ___ tag123binarysearch ___ Binäre Suche ist ein effizienter Algorithmus zum Suchen eines Elements in einem sortierten Array. Die Grundidee ist, den Suchraum in jedem Schritt um die Hälfte zu reduzieren. Die Komplexität des Algorithmus ist O (log (n)). ___ tag123python ___ Python ist eine dynamische und stark typisierte Programmiersprache, die die Usability betont. Zwei ähnliche, aber größtenteils inkompatible Versionen von Python sind weit verbreitet (2 und 3). Wenn Sie eine versionsspezifische Python-Frage haben, sollten Sie die Tags [python-2.7] oder [python-3.x] zusätzlich zum Tag [python] verwenden. Wenn Sie eine Python-Variante wie jython, pypy, iron-python usw. verwenden, kennzeichnen Sie diese bitte entsprechend. ___ qstnhdr ___ Suchen Sie in Python den Eintrag in der Liste der Dicts mit Hilfe von bisect ___ qstntxt ___

Ich habe eine Liste von Diktaten, etwa so:

%Vor%

Die dict-Elemente sind in der Liste nach den %code% -Daten sortiert. Die realen Daten könnten viel länger sein.

Was ich tun möchte, ist, ein Element in der Liste nach einem bestimmten Offset-Wert zu suchen, der nicht genau einer dieser Werte ist, aber in diesem Bereich. Also, eine binäre Suche ist was ich machen will.

Mir ist jetzt das Python-Modul %code% bekannt, bei dem es sich um eine fertige binäre Suche handelt. toll, aber nicht direkt nutzbar für diesen Fall. Ich frage mich nur, was ist der einfachste Weg, um %code% auf meine Bedürfnisse anzupassen. Hier ist, was ich gefunden habe:

%Vor%

Es druckt:

%Vor%

Meine Frage ist, ist dies der beste Weg, um zu tun, was ich will, oder gibt es einen anderen einfacheren, besseren Weg?

    
___
sykora 27.08.2009 23:58
quelle
3

Was Sie tun können, ist dies

%Vor%

Dies sollte Ihnen erlauben, eine einfache list of OffsetWithAttributes Instanzen zu erstellen. Der Algorithmus bisect sollte vollkommen glücklich sein, die definierten Operatoren zu verwenden.

Sie können Ihre someOWA.attributes['data'] verwenden.

Oder

%Vor%

Das sollte die OffsetWithAttributes eher wie eine dict machen.

    
S.Lott 28.08.2009 00:55
quelle