Suchen Sie ein Element in einem Array, aber das Element kann springen

8

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:

  1. um 1 vorrücken
  2. um 1 zurückgehen
  3. bleib wo es ist.

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:

  1. Der Interviewer gab einen Hinweis, dass ich vielleicht nach der Überprüfung der x-Anzahl der Zellen meinen Zeiger zurückbewegen sollte. Das Problem ist, wann sollte ich zurück und um wieviele Slots?
  2. Während ich "laut gedacht" habe, habe ich angefangen, ein paar gemeinsame Ansätze zu sagen, in der Hoffnung, dass etwas passieren würde. Als ich Rekursion sagte, sagte der Interviewer "Rekursion ist ein guter Anfang". Ich weiß nicht, Rekursion ist wirklich der richtige Ansatz, weil ich nicht sehe, wie ich Rekursion und # 1 zur gleichen Zeit tun kann.
  3. Der Interviewer sagte, dass dieses Problem nicht in O (n ^ 2) gelöst werden kann. Wir betrachten also mindestens O (n ^ 3) oder vielleicht sogar exponentiell.
Kent 22.03.2016, 08:23
quelle

6 Antworten

6

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 Frage spezifiziert nicht die Ausgangsposition unseres Ziels. Nehmen wir an, dass die Startposition über das gesamte Array einheitlich gewählt wird.
  • Die Frage gibt nicht die Wahrscheinlichkeit an, mit der sich unser Ziel bewegt. Der Einfachheit halber ist es unabhängig von Parametern wie der aktuellen Position im Array, der verstrichenen Zeit und der Historie der Samples. Die Verwendung der Wahrscheinlichkeit 1/3 für jede Option gibt uns die wenigsten Informationen, also benutzen wir das.
  • Lassen Sie uns unsere Algorithmen auf einem Array von 100 101 Elementen testen. Lassen Sie uns außerdem jeden Algorithmus eine Million Mal testen, um das durchschnittliche Fallverhalten einigermaßen sicher einschätzen zu können.

Die Algorithmen , die ich getestet habe, sind:

  • Zufallsauswahl: Nach jedem Versuch vergessen wir, wo wir hinschauen und wählen zufällig einen völlig neuen Index. Jedes Sample hat eine unabhängige 1 / n-Wahrscheinlichkeit, also erwarten wir, dass wir im Durchschnitt n Samples nehmen. Das ist unsere Kontrolle.
  • Sweep: Probieren Sie jede Position nacheinander aus, bis unser Ziel gefunden ist. Wenn sich unser Ziel nicht bewegt, würde dies im Durchschnitt n / 2 Proben erfordern. Unser Ziel ist jedoch Bewegung, so dass wir es bei unserem ersten Schwung verpassen können.
  • Langsamer Lauf: Das Gleiche, außer dass wir jede Position mehrmals testen, bevor wir weitermachen. Vorgeschlagen von Patrick Trentin mit einem Verlangsamungsfaktor von 30x, getestet mit einem Verlangsamungsfaktor von 2x.
  • Schneller Sweep: das Gegenteil von Slow Sweep. Nach der ersten Probe überspringen wir (k-1) Zellen, bevor wir die nächste testen. Der erste Durchlauf beginnt bei ary [0], der nächste bei ary [1] und so weiter. Getestet mit jedem Beschleunigungsfaktor (k) von 2 bis 5.
  • Links-rechts-Sweep: Zuerst prüfen wir jeden Index der Reihe nach von links nach rechts, dann jeden Index von rechts nach links. Dieser Algorithmus würde garantiert unser Ziel finden, wenn er sich immer bewegt (was nicht der Fall ist).
  • Smart gierig: Vorgeschlagen von Aziuth . Die Idee hinter diesem Algorithmus ist, dass wir jede Zellwahrscheinlichkeit verfolgen, die unser Ziel hält, und dann immer die Zelle mit der höchsten Wahrscheinlichkeit abtastet. Auf der einen Seite ist dieser Algorithmus relativ komplex, auf der anderen Seite klingt es wie sollte uns die optimalen Ergebnisse geben.

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 x3: 84.576265 ± 83.117648
  • schneller Durchlauf x4: 88,811068 ± 87,676049
  • 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%     
John Dvorak 22.03.2016 17:32
quelle
0

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%     
Daniel Of Mine 22.03.2016 08:41
quelle
0

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

    
auburg 22.03.2016 08:44
quelle
0

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.

    
Debosmit Ray 22.03.2016 08:55
quelle
0

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.

  1. Die 1 bleibt, wo sie ist, du wirst sie beim nächsten Mal finden
  2. Die 1 bewegt sich von dir weg, dein Rücken zur nächsten Position mit der 1 bei i + 2
  3. Die 1 bewegt sich in die Zelle, die Sie gerade überprüft haben, sie ist Ihrem Scan ausgewichen

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.

    
Jackson 22.03.2016 10:04
quelle
0

Annahmen:

  1. Das Array ist kein echtes Array. Dies ist angesichts des Problems offensichtlich. Wir haben eine Klasse, die sich etwas wie ein Array verhält.

  2. Das Array ist größtenteils ausgeblendet. Die einzigen öffentlichen Operationen sind [] und size ().

  3. 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.

  4. Jedes Feld des Arrays hat die gleiche Wahrscheinlichkeit, dass es das erste Feld ist, in dem sich das Feld befindet.

  5. Wir kennen die Wahrscheinlichkeiten, wie der Benutzer seine Position ändert, wenn er ausgelöst wird.

Wahrscheinlichkeitsgesteuerter Algorithmus:

  1. Führe ein weiteres Array derselben Größe ein, das Wahrscheinlichkeits-Array (über Double). Dieses Array wird mit allen Feldern initialisiert, die 1 / size entsprechen.
  2. Jedes Mal, wenn wir [] für das Basisarray verwenden, ändert sich das Wahrscheinlichkeitsarray auf diese Weise:
    1. Die Position, auf die zugegriffen wird, ist auf Null gesetzt (enthielt nicht die eine)
    2. Ein Eintrag wird zur Summe seiner Nachbarn multipliziert mit der Wahrscheinlichkeit, dass dieser Nachbar zur Einsprungposition springt. (prob_array_next_it [i] = prob_array_last_it [i-1] * prob_sprung_zu_recht + prob_array_last_it [i + 1] * prob_sprung_zu_left + prob_array_last_it [i] * prob_dont_sprung, anders für i = 0 und i = Größe-1 natürlich)
    3. Das Wahrscheinlichkeitsfeld ist normalisiert (wenn ein Eintrag auf Null gesetzt wird, wird die Summe der Wahrscheinlichkeiten auf unter eins gesetzt) ​​
  3. Der Algorithmus greift auf das Feld mit der höchsten Wahrscheinlichkeit zu (wählt unter den, die haben)

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:

  • Verstecktes Array: 0 0 1 0 0 0 0 0
  • Wahrscheinlichkeits-Array: 1/8 1/8 1/8 1/8 1/8 1/8 1/8 1/8

Erste Iteration: try [0] - & gt; Fehler

  • Verstecktes Array: 0 0 1 0 0 0 0 0 (kein Sprung)
  • Wahrscheinlichkeitsarray Schritt 1: 0 1/8 1/8 1/8 1/8 1/8 1/8 1/8
  • Wahrscheinlichkeitsarray Schritt 2: 1/24 2/24 1/8 1/8 1/8 1/8 1/8 1/8
  • Wahrscheinlichkeitsarray Schritt 2: gleich normalisiert (ganzes Array * 8/7):
  • 1/21 2/21 1/7 1/7 1/7 1/7 1/7 1/7

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)

    
Aziuth 22.03.2016 11:38
quelle

Tags und Links