welcher wird schneller sein?

Question

Lassen Sie uns sagen, ich habe ein Array, Größe 40. und das Element, das ich suche, ist in Position 38. mit einer einfachen Schleife, dauert es 38 Schritte richtig? aber mit 2 Schleifen, die parallel laufen, und eine Variable, "gefunden" auf false gesetzt, und ändert sich auf wahr, wenn das Element gefunden wird.

die erste Schleife, aus dem Index 0 die zweite Schleife beginnt, wird aus dem Index 40.

so dass im Grunde starten, wird es nur dann, 4 Schritten oder? um das Element zu finden. Der schlechteste Fall wird sein, wenn das Element in der Mitte des Arrays ist. Recht?

Answer 1

Es hängt davon ab, wie viel Arbeit benötigt wird, um den Zustand zwischen den beiden Threads zu synchronisieren.

Wenn es 0 Arbeit dauert, dann ist dies im Durchschnitt 50% schneller als ein Straight-Through-Algorithmus.

Auf der anderen Seite, wenn es mehr Arbeit als X braucht, wird es langsamer (was sehr wahrscheinlich der Fall ist).

Aus einem Algorithmus Standpunkt, ich glaube nicht, dass dies ist, wie Sie gehen möchten. Selbst 2 Threads werden immer noch O (n) Laufzeit sein. Sie möchten die Daten sortieren (n log n) und dann eine binäre Suche durchführen, um die Daten zu erhalten. Vor allem können Sie es 1 Mal sortieren und für viele Suchen verwenden ...

Answer 2

Wenn Sie über algorithmische Komplexität sprechen, ist dies immer noch eine lineare Suche. Nur weil Sie zwei Elemente pro Iteration suchen, ändert sich nicht die Tatsache, dass der Algorithmus O (n) ist.

In Bezug auf die tatsächliche Leistung, die Sie sehen würden, ist dieser Algorithmus wahrscheinlich langsamer als eine lineare Suche mit einem einzigen Prozessor. Da bei einer Suche pro Element nur sehr wenig Arbeit geleistet wird, wäre der Algorithmus speichergebunden, so dass die Verwendung mehrerer Prozessoren nicht von Vorteil wäre. Da Sie an zwei Standorten suchen, ist dieser Algorithmus nicht so effizient wie Cache. Und dann, wie Bwawok betont, würde viel Zeit in der Synchronisation verloren gehen.

Answer 3

Wenn Sie parallel laufen teilen Sie Ihre CPU-Leistung in zwei + erstellen einige Overhead. Wenn Sie meinen, dass Sie die Suche auf einem sagen, einer Multicore-Maschine ausführen, mit Ihrem vorgeschlagenen Algorithmus dann ist der schlimmste Fall 20 Schritte. Sie ändern die Komplexitätsklasse nicht. Woher kommen diese 4 Schritte, von denen du gesprochen hast?

Answer 4

Im Durchschnitt gibt es keine Unterschiede in der Laufzeit.

Nehmen Sie zum Beispiel, wenn Sie suchen für eine Position von 10
Der ursprüngliche Algorithmus wird in dem folgenden Suchauftrag verarbeiten:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10 

schlimmster Fall ist der letzte Punkt (unter 10 Stufen) .

Während der zweite Algorithmus in dem folgenden Suchauftrag verarbeiten:

1, 3, 5, 7, 9, 10, 8, 6, 4, 2 

schlimmster Fall in diesem Szenario ist Punkt 6 (10 Schritte zu unternehmen).

In einigen Fällen ist Algorithmus 1 schneller.
Es gibt einige Fälle, in denen Algorithmus 2 schneller ist.

Beide nehmen die gleiche Zeit im Durchschnitt - O (n).

---

Nebenbei bemerkt ist es interessant, dies mit einer binären Suchreihenfolge (in einem sortierten Array) zu vergleichen.

In höchstens 4 Schritten zur Fertigstellung.