Begründung: Ich versuche in Python etwas Ähnliches wie git bisect zu implementieren, aber mit einer Liste von Verzeichnissen.
Ich habe eine (lange) Liste von Versionsnummern wie folgt:
['1.0', '1.14', '2.3', '3.1', '4']
Ich habe eine Funktion works() , die eine Versionsnummer annimmt und einen Wert zurückgibt.
[works(x) for x in my_list] würde folgendermaßen aussehen:
%Code%
... aber das Ausführen von ['foo', 'foo', 'foo', 'bar', 'bar'] ist sehr teuer.
Ich möchte eine Art Halbierung durchführen, bei der die Änderungsgrenze gefunden wird.
Sie können einfach binäre Suche :
verwenden %Vor% Es wird der erste Index i zurückgegeben, für den bool(f(list[i])) ist True .
Natürlich geht die Funktion davon aus, dass die Karte von f auf der list die folgende Form hat:
Wenn dies nicht der Fall ist, findet es normalerweise einen swap , aber welcher ist eher undefiniert.
Sagen Sie f ist einfach " die Version ist 2 oder höher " also lambda v:v >= '2' , dann wird es zurückgeben:
Also index 2 . Falls die gesamte Liste mit False Objekten zurückkehren würde, wird ** len(list) zurückgegeben. Da es "annimmt", wird das Element außerhalb der Liste nach True ausgewertet:
In Ihrem Beispiel ist f natürlich works .
Experimente:
%Vor%(Ich habe hier natürlich eine sehr billige Versionsprüfung gemacht, aber es funktioniert natürlich auch für anspruchsvollere Prädikate).
Da dies eine binäre Suche ist, wird es in O (log n) mit n die Anzahl der Elemente in der Liste ausgeführt, während lineare Suche kann Ergebnis in O (n) checks (was normalerweise teurer ist).
Bearbeiten : Falls die Liste zwei Werte enthält und Sie finden die Swap , können Sie einfach zuerst den Wert für den Index berechnen 0 :
und dann binary_f :
Oder setzen Sie es in eine nette Funktion:
%Vor%Sie wollen also im Grunde binären Suchalgorithmus implementieren ... das ist ziemlich einfach, der grobe Entwurf des Algorithmus ist unten. Ich habe es nicht getestet, aber Sie sollten die Idee bekommen und auf Kantenfälle achten, wenn Ihre Versionsliste der Länge 1 oder 2:
%Vor% Dafür steht next() .
Ein schneller Weg, aber ein komplizierter wäre:
%Vor% Was ist eine halbierte Methode? Schneidet die Liste rekursiv um die Hälfte, prüft das Element in der Mitte und verschiebt das Segment links, wenn es 1 ist oder rechts, wenn es eine 0 ist.% Co_de% verfolgt den Index. Ich würde gerne eine tracking von jemandem haben, wenn er die Zeit hat.
Tags und Links python bisect bisection git-bisect