Es gibt ein Array, in dem alle bis auf eine Zelle 0 sind, und wir wollen den Index dieser einzelnen von Null verschiedenen Zelle finden. Das Problem ist, dass jedes Mal, wenn Sie nach einer Zelle in diesem Array suchen, dieses Nicht-Null-Element einen der folgenden Schritte ausführt:
Wenn dieses Element z. B. an Position 10 ist und ich überprüfe, was in arr[5] ist, dann kann das Element an Position 9, 10 oder 11 sein, nachdem ich arr[5] überprüft habe.
Wir müssen nur die Position finden, an der sich das Element gerade befindet und nicht wo es angefangen hat (was unmöglich ist).
Der schwierige Teil ist, wenn wir eine for-Schleife schreiben, gibt es wirklich keine Möglichkeit zu wissen, ob sich das Element gerade vor dir oder hinter dir befindet.
Etwas mehr Kontext, wenn es hilft:
Tl; dr: Am besten ist es, jeden geraden Index im Array zu überprüfen und ihn so oft wie nötig zu umbrechen, bis Sie Ihr Ziel gefunden haben. Im Durchschnitt stolpern Sie in der Mitte Ihres zweiten Durchgangs über Ihr Ziel.
Zunächst einmal, wie viele bereits gesagt haben, ist es in der Tat unmöglich sicherzustellen, dass Sie Ihr Zielelement in einem bestimmten Zeitraum finden. Wenn das Element weiß, wo Ihr nächstes Sample sein wird, kann es sich immer woanders hinstellen. Das Beste, was Sie tun können, ist, das Array so zu testen, dass die erwartete Anzahl an Zugriffen minimiert wird - und weil nach jeder Probe nichts gelernt wird, außer Sie erfolgreich waren oder nicht und ein Erfolg bedeutet, dass Sie mit der Probenahme aufhören, kann eine optimale Strategie beschrieben werden einfach als eine Reihe von Indizes, die überprüft werden sollten, nur abhängig von der Größe des Arrays, das Sie gerade durchsuchen. Wir können jede Strategie der Reihe nach mit automatisierten Mitteln testen, um zu sehen, wie gut sie funktionieren. Die Ergebnisse hängen von den Besonderheiten des Problems ab. Lassen Sie uns also einige Annahmen machen:
Die Algorithmen , die ich getestet habe, sind:
Ergebnisse:
Die Ergebnisse werden als [Durchschnitt] ± [Standardabweichung] angezeigt.
Stichprobenauswahl: 100.889145 ± 100.318212
An diesem Punkt habe ich in meinem Code einen Fencing-Fehler festgestellt. Gut, dass wir eine Kontrollprobe haben. Dies stellt auch fest, dass wir im Ballpark zwei oder drei Stellen mit nützlicher Genauigkeit haben (sqrt #samples), was mit anderen Tests dieses Typs übereinstimmt.
Sweep: 100,327030 ± 91,210692
Die Chance, dass unser Ziel gut durch das Netz quetscht, wirkt dem Effekt entgegen, dass das Ziel im Durchschnitt n / 2 Mal ins Netz kommt. Der Algorithmus schneidet nicht wirklich besser ab als eine zufällige Stichprobe, aber er ist konsistenter in seiner Leistung und es ist auch nicht schwer, ihn zu implementieren.
langsamer Durchlauf (x 0,5): 128,272588 ± 99,003681
Während die langsame Bewegung unseres Netzes bedeutet, dass unser Ziel während des ersten Sweeps im Netz hängen bleibt und keinen zweiten Sweep benötigt, bedeutet dies auch, dass der erste Sweep doppelt so lange dauert . Alles in allem scheint es etwas ineffizient, sich auf das Ziel zu verlassen, das auf uns zukommt.
schneller Sweep x2: 75.981733 ± 72.620600
schneller Durchlauf x5: 91.264716 ± 90.337139
Das ist ... zunächst ein wenig überraschend. Während wir jeden zweiten Schritt überspringen, bedeutet das, dass wir jede Runde in doppelt so vielen Runden absolvieren, jede Runde hat auch eine geringere Chance, das Ziel tatsächlich zu treffen.Eine schönere Ansicht ist es, Sweep und FastSweep im Besenraum zu vergleichen: Drehe jedes Sample so, dass der Index, der gerade gesampelt wird, immer bei 0 ist und das Ziel etwas schneller nach links driftet. In Sweep bewegt sich das Ziel bei jedem Schritt um 0, 1 oder 2. Eine schnelle Parallele zur Fibonacci-Basis sagt uns, dass das Ziel ungefähr 62% der Zeit auf den Besen / das Netz treffen sollte. Wenn es verfehlt, braucht es weitere 100 Umdrehungen, um wiederzukommen. In FastSweep bewegt sich das Ziel bei jedem Schritt mit 1, 2 oder 3 Geschwindigkeiten, was bedeutet, dass es häufiger fehlt, aber es auch halb so lange dauert, es erneut zu versuchen. Da die Wiederholungszeit mehr als die Trefferrate abfällt, ist es vorteilhaft, FastSweep over Sweep zu verwenden.
Links-Rechts-Sweep: 100.572156 ± 91.503060
Meistens wirkt es wie ein gewöhnlicher Sweep, und seine Punktzahl und Standardableitung spiegeln das wider. Kein allzu überraschendes Ergebnis.
Aziuth ist schlau gierig: 87.982552 ± 85.649941
An dieser Stelle muss ich einen Fehler in meinem Code zugeben: Dieser Algorithmus hängt stark von seinem anfänglichen Verhalten ab (das von Aziuth nicht spezifiziert ist und in meinen Tests zufällig ausgewählt wurde). Aufgrund von Leistungsbedenken musste dieser Algorithmus immer die gleiche zufällige Reihenfolge wählen. Die Ergebnisse sind dann charakteristisch für diese Randomisierung und nicht für den Algorithmus als Ganzes.
Immer den wahrscheinlichsten Punkt zu finden, sollte unser Ziel so schnell wie möglich finden, richtig? Leider konkurriert dieser komplexe Algorithmus kaum mit Sweep 3x. Warum? Mir ist klar, dass dies nur Spekulation ist, aber lassen Sie uns einen Blick auf die Sequenz werfen, die Smart Greedy tatsächlich generiert: Während des ersten Durchgangs hat jede Zelle die gleiche Wahrscheinlichkeit, das Ziel zu enthalten, also muss der Algorithmus wählen. Wenn es sich zufällig entscheidet, könnte es im Ballpark von 20% der Zellen auffliegen, bevor die Wahrscheinlichkeitssprünge alle erreichen. Danach ist die Landschaft größtenteils glatt, wo das Array vor kurzem nicht abgetastet wurde, so dass der Algorithmus schließlich aufhört zu fegen und nach dem Zufallsprinzip zu springen. Das eigentliche Problem ist, dass der Algorithmus zu gierig ist und sich nicht wirklich darum kümmert, das Ziel zu hüten, damit es das Ziel leichter treffen kann.
Trotzdem ist dieser komplexe Algorithmus besser als ein einfacher Sweep und ein Zufallssampler. Es kann jedoch immer noch nicht mit der Einfachheit und überraschenden Effizienz von FastSweep konkurrieren. Wiederholte Tests haben gezeigt, dass die anfängliche Randomisierung die Effizienz irgendwo zwischen 80% Laufzeit (20% Beschleunigung) und 90% Laufzeit (10% Beschleunigung) schwingen kann.
Zum Schluss folgt der Code , mit dem die Ergebnisse generiert wurden:
%Vor%Nein, alles über Schleifen vergessen. Kopiere dieses Array in ein anderes Array und überprüfe dann, welche Zellen jetzt nicht Null sind. Wenn Ihr Hauptarray beispielsweise mainArray [] ist, können Sie Folgendes verwenden:
%Vor%Ein Ansatz vielleicht:
i - Habe vier Indexvariablen f, f1, l, l1. f zeigt auf 0, f1 auf 1, l zeigt auf n-1 (Ende des Arrays) und l1 auf n-2 (vorletztes Element)
ii - Überprüfen Sie die Elemente bei f1 und l1 - sind einige von ihnen nicht Null? Wenn ja, hör auf. Falls nicht, überprüfe die Elemente bei f und l (um zu sehen, ob das Element zurückspringt 1).
iii - Wenn f und l noch Null sind, erhöhen Sie die Indizes und wiederholen Sie Schritt ii. Stoppen wenn f1 & gt; l1
Iff Eine Gleichheitsprüfung gegen einen Array-Index lässt das Element ungleich Null springen.
Warum sollten Sie nicht einen Weg suchen, bei dem wir keine Gleichheitsprüfung mit einem Array-Index benötigen?
%Vor% Orrr. Vielleicht kannst du arr[mid] weiterlesen. Das Nicht-Null-Element wird dort enden. Irgendwann mal. Begründung: Patrick Trentin scheint es in seine Antwort geschrieben zu haben (etwas, das ist nicht wirklich das, aber Sie werden eine Idee bekommen).
Wenn Sie Informationen über das Array haben, können wir vielleicht einen nobeleren Ansatz finden.
Wenn Sie den trivialen Fall ignorieren, bei dem die 1 in der ersten Zelle des Arrays ist, wenn Sie durch das Array iterieren und jedes Element der Reihe nach testen, müssen Sie schließlich zu der Position i gelangen, wo die 1 in Zelle i + 2 ist. Wenn du Zelle I + 1 liest, wird eines von drei Dingen passieren.
Wenn Sie die i + 1-Zelle erneut lesen, wird die 1 in Fall 3 gefunden, aber geben Sie ihr nur eine weitere Möglichkeit, in Fall 1 und 2 zu wechseln, damit eine auf dem erneuten Lesen basierende Strategie nicht funktioniert.
Meine Option würde daher einen Brute-Force-Ansatz verfolgen, wenn ich das Array weiter scanne, dann werde ich Fall 1 irgendwann treffen und die schwer fassbare 1 finden.
Annahmen:
Das Array ist kein echtes Array. Dies ist angesichts des Problems offensichtlich. Wir haben eine Klasse, die sich etwas wie ein Array verhält.
Das Array ist größtenteils ausgeblendet. Die einzigen öffentlichen Operationen sind [] und size ().
Das Array ist verschleiert. Wir können keine Informationen erhalten, indem wir seine Adresse abrufen und dann die Erinnerung an dieser Position analysieren. Selbst wenn wir die gesamte Speicherkapazität unseres Systems durchlaufen, können wir aufgrund einiger fortschrittlicher kryptographischer Mittel keine Tricks ausführen.
Jedes Feld des Arrays hat die gleiche Wahrscheinlichkeit, dass es das erste Feld ist, in dem sich das Feld befindet.
Wir kennen die Wahrscheinlichkeiten, wie der Benutzer seine Position ändert, wenn er ausgelöst wird.
Wahrscheinlichkeitsgesteuerter Algorithmus:
Es könnte in der Lage sein, dies zu optimieren, indem es den Fluss der Wahrscheinlichkeiten steuert, aber das muss auf dem wandernden Ereignis basieren und könnte einige Nachforschungen erfordern.
Kein Algorithmus, der versucht, dieses Problem zu lösen, wird nach einiger Zeit garantiert beendet. Für eine Komplexität würden wir den durchschnittlichen Fall analysieren.
Beispiel: Sprungwahrscheinlichkeiten sind 1/3, nichts passiert, wenn man versucht, außerhalb der Grenzen zu springen
Initialisieren:
Erste Iteration: try [0] - & gt; Fehler
Zweite Iteration: try [2] als 1/7 ist das Maximum und dies ist das erste Feld mit 1/7 - & gt; Erfolg (Beispiel sollte jetzt klar sein, natürlich würde dies bei einem anderen Beispiel nicht so schnell funktionieren, hatte kein Interesse, dies für viele Iterationen zu tun, da die Wahrscheinlichkeiten mühsam werden würden, um sie manuell zu berechnen, müssten sie implementiert werden dass, wenn der eine nach links gesprungen wäre, wir es nicht so schnell überprüft hätten, selbst wenn es für einige Zeit dort geblieben wäre)