Das erste Element einer Mathematica-Liste ist größer als ein Schwellenwert
Ich habe mich gefragt, wie ich das erste Element einer (bereits geordneten) Liste erhalten könnte, die größer ist als ein vorgegebener Schwellenwert.
Ich kenne die Listenmanipulationsfunktion in Mathematica nicht wirklich gut, vielleicht kann mir jemand einen Trick dafür geben.
6 Antworten
Select leistet, was Sie brauchen, und wird konsistent sein und die bestehende Bestellung respektieren der Liste:
Zum Beispiel:
%Vor%Sie können jede erforderliche Schwellenwert- oder Kriteriumfunktion im zweiten Argument angeben.
Das dritte Argument gibt nur eines (d. h. das erste) Element an, das übereinstimmt.
Hoffe das hilft!
Joe gibt korrekt in seinem antworten , dass man erwarten würde, dass eine binäre Suchtechnologie schneller ist als Select , die scheinbar nur eine lineare Suche durchführt, selbst wenn die Liste sortiert ist:
(Ich habe den Schwellenwert willkürlich zu Demonstrationszwecken auf 2 gesetzt.)
Allerdings ist die Funktion BinarySearch in Combinatorica a) nicht geeignet (sie gibt ein Element zurück, das mit dem angeforderten übereinstimmt, aber nicht das erste (ganz links), was die Frage darstellt.
Um das Element ganz links zu erhalten, das größer als ein Schwellenwert ist, können wir bei einer geordneten Liste rekursiv fortfahren:
%Vor%oder iterativ:
%Vor%Der rekursive Ansatz ist klarer, aber ich halte mich an den iterativen.
Um seine Geschwindigkeit zu testen,
%Vor%was produziert
also, viel schneller und mit besserem Skalierungsverhalten.
Eigentlich ist es nicht notwendig, es zu kompilieren, aber ich habe es trotzdem getan.
Abschließend sollten Sie Select nicht für lange Listen verwenden.
Damit ist meine Antwort abgeschlossen. Es folgen einige Kommentare zu einer binären Suche von Hand oder über das Combinatorica-Paket.
Ich habe die Geschwindigkeit einer (kompilierten) kurzen Routine verglichen, um eine binäre Suche im Vergleich zum BinarySearch von Combinatorica durchzuführen. Beachten Sie, dass dies nicht das tut, was die Frage verlangt (und auch nicht BinarySearch von Combinatorica ); Der Code, den ich oben angegeben habe, funktioniert.
Die binäre Suche kann iterativ als
implementiert werden %Vor% und wir können das jetzt vergleichen und BinarySearch von Combinatorica . Beachten Sie, dass a) die Liste sortiert sein muss; b) das erste passende Element nicht zurückgegeben wird, sondern ein übereinstimmendes Element.
Vergleichen wir die beiden binären Suchroutinen. 50000 Mal wiederholen:
%Vor% Also ist die handschriftliche schneller. Jetzt, da tatsächlich eine binäre Suche nur 6-7 Punkte in der Liste für diese Parameter aufruft (etwas wie {500000, 250000, 125000, 62500, 31250, 15625, 23437} zum Beispiel), ist der Unterschied eindeutig einfach Overhead; vielleicht ist BinarySearch beispielsweise allgemeiner oder nicht kompiliert.
Die Verwendung von Select wird das Problem lösen, aber es ist eine schlechte Lösung, wenn Sie auf Effizienz achten. Select geht über alle Elemente der Liste und benötigt daher Zeit, die in der Länge der Liste linear ist.
Da Sie sagen, dass die Liste geordnet ist, ist es viel besser, BinarySearch zu verwenden arbeite in einer Zeit, die in der Größe der Liste logarithmisch ist. Der Ausdruck ( bearbeiten : Ich habe eine kleine Anpassung vorgenommen, da der vorherige Ausdruck, den ich geschrieben habe, nicht korrekt wiederkehrende Elemente in der Liste gehandhabt hat. ein anderer Schnitt : Dies funktioniert immer noch nicht wenn der Schwellenwert selbst in der Liste als wiederkehrendes Element erscheint, siehe Kommentare):
gibt Ihnen den Index des gewünschten Elements. Wenn alle Elemente kleiner als der Schwellenwert sind, erhalten Sie die Länge der Liste plus eins.
p.s. Vergiss nicht, Needs["Combinatorica'"] vor der Verwendung von BinarySearch aufzurufen.
Nur für eine zukünftige Referenz, beginnend mit v10 können Sie SelectFirst
Es hat einige zusätzliche Feinheiten wie die Rückgabe von Missing[] oder Standardwerte.
Aus der Dokumentation:
SelectFirst[{e1,e2,…}, crit]gibt die ersteeifür diecrit[ei]istTrueoderMissing["NotFound"]wenn keine gefunden wird.
SelectFirst[{e1,e2,…}, crit, default]gibtdefault, wenn es keineeigibt, so dasscrit[ei]istTrue.
Für Ihren speziellen Fall würden Sie verwenden:
%Vor%Tags und Links wolfram-mathematica