Ich dachte über Sortieralgorithmen in Software nach und über mögliche Möglichkeiten, die O(nlogn)Straßensperre zu überwinden . Ich denke nicht, dass es möglich ist, im praktischen Sinne schneller zu sortieren, also denke bitte nicht, dass ich es tue.

Trotzdem scheint es, dass bei fast allen Sortieralgorithmen die Software die Position jedes Elements kennen muss. Was macht sonst Sinn, wie würde es wissen, wo jedes Element nach bestimmten Sortierkriterien platziert werden soll?

Aber als ich dieses Denken mit der realen Welt kreuzte, hat eine Zentrifuge keine Ahnung, in welcher Position sich jedes Molekül befindet, wenn es die Moleküle nach Dichte "sortiert". Tatsächlich kümmert es sich nicht um die Position jedes Moleküls. Es kann jedoch in relativ kurzer Zeit Billionen nach Billionen von Gegenständen sortieren, da jedes Molekül den Dichte- und Gravitationsgesetzen folgt - was mich zum Nachdenken brachte.

Wäre es möglich, mit einem gewissen Overhead auf jedem Knoten (einem Wert oder einer Methode, die an jeden der Knoten angeheftet ist) die Reihenfolge der Liste zu erzwingen? So etwas wie eine Zentrifuge, bei der sich nur jedes Element um seine relative Position im Raum kümmert (im Verhältnis zu anderen Knoten). Oder verstößt dies gegen eine Berechnungsregel?

Ich denke, einer der großen Punkte, die hier angesprochen werden, sind die quantenmechanischen Effekte der Natur und wie sie parallel auf alle Teilchen gleichzeitig angewendet werden.

Vielleicht beschränken klassische Computer die Sortierung von Natur aus auf den Bereich O(nlogn), in dem Quantencomputer diesen Schwellenwert möglicherweise O(logn)in parallel wirkende Algorithmen überschreiten können .

Der Punkt, dass eine Zentrifuge im Grunde eine parallele Blasensorte ist, scheint richtig zu sein, was eine zeitliche Komplexität von hat O(n).

Ich denke, der nächste Gedanke ist, wenn die Natur sich einordnen kann O(n), warum können Computer dann nicht?

EDIT: Ich hatte den Mechanismus einer Zentrifuge falsch verstanden und es scheint, dass sie einen Vergleich durchführt, einen massiv parallelen. Es gibt jedoch physikalische Prozesse, die mit einer Eigenschaft der zu sortierenden Entität arbeiten, anstatt zwei Eigenschaften zu vergleichen. Diese Antwort behandelt Algorithmen dieser Art.

Eine Zentrifuge wendet einen Sortiermechanismus an, der nicht wirklich durch Vergleiche zwischen Elementen funktioniert, sondern tatsächlich durch eine Eigenschaft ("Zentrifugalkraft") auf jedes einzelne Element für sich. Einige Sortieralgorithmen fallen in dieses Thema, insbesondere Radix Sort . Wenn dieser Sortieralgorithmus parallelisiert wird, sollte er sich dem Beispiel einer Zentrifuge nähern.

Einige andere nicht vergleichende Sortieralgorithmen sind Bucket Sort und Counting Sort . Möglicherweise passt die Eimersortierung auch in die allgemeine Idee einer Zentrifuge (der Radius könnte einem Behälter entsprechen).

Ein weiterer sogenannter "Sortieralgorithmus", bei dem jedes Element isoliert betrachtet wird, ist die Schlafsortierung . Hier wirkt eher die Zeit als die Zentrifugalkraft als die zum Sortieren verwendete Größe.

Rechenkomplexität wird immer in Bezug auf ein Rechenmodell definiert. Zum Beispiel wird ein Algorithmus, ist O ( n ) auf einem typischen Computer könnte sein , O (2 ⁿ ) , wenn in realisiert Brainfuck .

Das Rechenmodell der Zentrifuge weist einige interessante Eigenschaften auf. beispielsweise:

• es unterstützt willkürliche Parallelität; Unabhängig davon, wie viele Partikel sich in der Lösung befinden, können alle gleichzeitig sortiert werden.
• es gibt keine streng lineare Art von Partikeln nach Masse, sondern eine sehr enge (energiearme) Näherung.
• Es ist nicht möglich, die einzelnen Partikel im Ergebnis zu untersuchen.
• Es ist nicht möglich, Partikel nach unterschiedlichen Eigenschaften zu sortieren. Es wird nur die Masse unterstützt.

Da wir nicht in der Lage sind, so etwas in Allzweck-Computerhardware zu implementieren, hat das Modell möglicherweise keine praktische Relevanz. Aber es kann sich trotzdem lohnen, zu prüfen, ob daraus etwas zu lernen ist. Nichtdeterministische Algorithmen und Quantenalgorithmen waren beispielsweise beide aktive Forschungsbereiche, obwohl keiner von beiden heute tatsächlich implementierbar ist.

Der Trick ist, dass Sie nur die Wahrscheinlichkeit haben, Ihre Liste mit einer Zentrifuge zu sortieren. Wie bei anderen realen Sorten [Zitieren erforderlich] können Sie die Wahrscheinlichkeit ändern, dass Sie Ihre Liste sortiert haben, aber niemals sicher sein, ohne alle Werte (Atome) zu überprüfen.

Stellen Sie sich die Frage: "Wie lange sollten Sie Ihre Zentrifuge laufen lassen?"
Wenn Sie es nur eine Pikosekunde lang ausgeführt haben, ist Ihre Probe möglicherweise weniger sortiert als der Ausgangszustand. Wenn Sie es einige Tage lang ausgeführt haben, ist es möglicherweise vollständig sortiert. Sie würden es jedoch nicht wissen, ohne den Inhalt tatsächlich zu überprüfen.

Ein reales Beispiel für eine computergestützte "Bestellung" wären autonome Drohnen, die kooperativ zusammenarbeiten, sogenannte "Drohnenschwärme". Die Drohnen agieren und kommunizieren sowohl als Einzelpersonen als auch als Gruppe und können mehrere Ziele verfolgen. Die Drohnen entscheiden gemeinsam, welche Drohnen welchen Zielen folgen, und die offensichtliche Notwendigkeit, Kollisionen zwischen Drohnen zu vermeiden. Die frühen Versionen davon waren Drohnen, die sich durch Wegpunkte bewegten, während sie in Formation blieben, aber die Formation konnte sich ändern.

Für eine "Sortierung" könnten die Drohnen so programmiert werden, dass sie eine Linie oder ein Muster in einer bestimmten Reihenfolge bilden, die anfänglich in einer beliebigen Permutation oder Form freigegeben werden, und gemeinsam und parallel würden sie schnell die geordnete Linie oder das geordnete Muster bilden.

Zurück zu einer computergestützten Sortierung: Ein Problem besteht darin, dass es einen Hauptspeicherbus gibt und eine große Anzahl von Objekten sich nicht parallel im Speicher bewegen kann.

kennen die Position jedes Elements

Bei einer Bandsortierung ist die Position jedes Elements (Datensatzes) nur dem "Band" "bekannt", nicht dem Computer. Eine bandbasierte Sortierung muss nur mit zwei Elementen gleichzeitig arbeiten und eine Möglichkeit bieten, Laufgrenzen auf einem Band (Dateimarkierung oder Datensatz unterschiedlicher Größe) zu kennzeichnen.

IMHO, Leute überdenken log (n). O (nlog (n)) IST praktisch O (n). Und Sie brauchen O (n), um die Daten zu lesen.

Viele Algorithmen wie Quicksort bieten eine sehr schnelle Möglichkeit, Elemente zu sortieren. Sie könnten Variationen von Quicksort implementieren, die in der Praxis sehr schnell wären.

Inhärent sind alle physikalischen Systeme unendlich parallel. Möglicherweise haben Sie eine Menge Atome in einem Sandkorn. Die Natur verfügt über genügend Rechenleistung, um herauszufinden, wo sich jedes Elektron in jedem Atom befinden sollte. Wenn Sie also über genügend Rechenressourcen (O (n) Prozessoren) verfügen, können Sie n Zahlen in log (n) Zeit sortieren.

Aus Kommentaren:

1. Bei einem physischen Prozessor mit k Elementen kann eine Parallelität von höchstens O (k) erreicht werden. Wenn Sie n Zahlen willkürlich verarbeiten, wird sie immer noch mit einer Rate verarbeitet, die sich auf k bezieht. Sie können dieses Problem auch physisch formulieren. Sie könnten n Stahlkugeln mit Gewichten erstellen, die proportional zu der Zahl sind, die Sie codieren möchten, was durch eine Zentrifuge in einer Theorie gelöst werden könnte. Aber hier ist die Menge der Atome, die Sie verwenden, proportional zu n. Während in einem Standardfall eine begrenzte Anzahl von Atomen in einem Prozessor vorhanden ist.

2. Eine andere Möglichkeit, darüber nachzudenken, besteht darin, dass an jede Nummer ein kleiner Prozessor angeschlossen ist und jeder Prozessor mit seinen Nachbarn kommunizieren kann. Sie können alle diese Nummern in O (log (n)) -Zeit sortieren.

Ich habe nach der High School im Sommer in einem Büro gearbeitet, als ich mit dem College anfing. Ich hatte in AP Informatik unter anderem Sortieren und Suchen studiert .

Ich habe dieses Wissen in mehreren physikalischen Systemen angewendet, an die ich mich erinnern kann:

Natürliche Zusammenführungssorte zum Starten…

Ein System druckte mehrteilige Formulare mit einem Abriss im Format einer Karteikarte, der in einer Schubladenbank abgelegt werden musste.

Ich begann mit einem Stapel davon und sortierte den Stapel zunächst. Der erste Schritt besteht darin, ungefähr 5 aufzunehmen, von denen einige leicht genug sind, um in der richtigen Reihenfolge in Ihrer Hand platziert zu werden. Legen Sie das sortierte Paket ab und kreuzen Sie jeden Stapel, um sie getrennt zu halten.

Dann verschmilzt jedes Paar von Stapeln, einen größeren Stapel zu erzeugen. Wiederholen, bis nur noch ein Stapel vorhanden ist.

… Einfügungssortierung zum Abschluss

Es ist einfacher, die sortierten Karten abzulegen, da sich jede nächste etwas weiter unten in derselben offenen Schublade befindet.

Radix sort

Dieser hier hat niemand verstanden, wie ich es so schnell gemacht habe, trotz wiederholter Versuche, es zu lehren.

Eine große Schachtel mit Scheckstummeln (die Größe von Lochkarten) muss sortiert werden. Es sieht so aus, als würde man Solitaire auf einem großen Tisch spielen - austeilen, stapeln, wiederholen.

Allgemein

Vor 30 Jahren habe ich bemerkt, wonach Sie fragen: Die Ideen werden ganz direkt auf physische Systeme übertragen, da die Kosten für Vergleiche und die Verarbeitung von Datensätzen sowie die Caching- Kosten relativ hoch sind.

Über gut verstandene Äquivalente hinausgehen

Ich erinnere mich an einen Aufsatz über Ihr Thema, der die Spaghetti-Sorte hervorbrachte . Sie schneiden eine Länge getrockneter Nudeln, um den Schlüsselwert anzuzeigen, und beschriften sie mit der Datensatz-ID. Dies ist O (n), wobei jeder Artikel einfach einmal verarbeitet wird.

Dann nimmst du das Bündel und tippst auf ein Ende des Tisches. Sie werden an den unteren Rändern ausgerichtet und sind jetzt sortiert. Sie können den längsten trivial abnehmen und wiederholen. Die Anzeige ist auch O (n).

Hier in der „realen Welt“ gibt es zwei Dinge, die nicht den Algorithmen entsprechen. Erstens ist das Ausrichten der Kanten eine parallele Operation. Jedes Datenelement ist auch ein Prozessor (für ihn gelten die Gesetze der Physik). Im Allgemeinen skalieren Sie also die verfügbare Verarbeitung mit n und teilen Ihre klassische Komplexität im Wesentlichen durch einen Faktor auf n.

Zweitens, wie erreicht das Ausrichten der Kanten eine Sortierung? Die eigentliche Sortierung ist in der Auslese , die Sie am längsten in einem Schritt ermöglicht zu finden, obwohl Sie haben alle von ihnen zu vergleichen , die längsten zu finden. Teilen Sie erneut durch einen Faktor von n, sodass das Finden des größten jetzt O (1) ist.

Ein anderes Beispiel ist die Verwendung von analogem Rechnen: Ein physikalisches Modell löst das Problem „sofort“ und die Vorbereitungsarbeit ist O (n). Im Prinzip skaliert die Berechnung mit der Anzahl der interagierenden Komponenten, nicht mit der Anzahl der vorbereiteten Elemente. Die Berechnung skaliert also mit n². Das Beispiel, an das ich denke, ist eine gewichtete Multi-Faktor-Berechnung, bei der Löcher in eine Karte gebohrt, Gewichte an durch die Löcher verlaufenden Saiten aufgehängt und alle Saiten an einem Ring gesammelt wurden.

Die Sortierung ist immer noch O (n) Gesamtzeit. Dass es schneller ist als das, liegt an der Parallelisierung .

Sie können eine Zentrifuge als eine Bucketsort von n Atomen betrachten, die über n Kerne parallelisiert sind (jedes Atom fungiert als Prozessor).

Sie können die Sortierung durch Parallelisierung beschleunigen, jedoch nur durch einen konstanten Faktor, da die Anzahl der Prozessoren begrenzt ist und O (n / C) immer noch O (n) ist (CPUs haben normalerweise <10 Kerne und GPUs <6000).

Die Zentrifuge sortiert die Knoten nicht, sie übt eine Kraft auf sie aus, dann reagieren sie parallel dazu. Wenn Sie also eine Blasensortierung implementieren würden, bei der sich jeder Knoten basierend auf seiner "Dichte" parallel nach oben oder unten bewegt, hätten Sie eine Zentrifugenimplementierung.

Denken Sie daran, dass Sie in der realen Welt eine sehr große Anzahl paralleler Aufgaben ausführen können, während Sie in einem Computer maximal reale parallele Aufgaben haben können, die der Anzahl der physischen Verarbeitungseinheiten entsprechen.

Am Ende wäre der Zugriff auf die Liste der Elemente auch eingeschränkt, da sie nicht gleichzeitig von zwei Knoten geändert werden kann ...

Wäre es möglich, mit einem gewissen Overhead auf jedem Knoten (einem Wert oder einer Methode, die an jeden der Knoten angeheftet ist) die Reihenfolge der Liste zu erzwingen?

Wenn wir mit Computerprogrammen sortieren, wählen wir eine Eigenschaft der zu sortierenden Werte aus. Das ist normalerweise die Größe der Zahl oder der alphabetischen Reihenfolge.

So etwas wie eine Zentrifuge, bei der sich nur jedes Element um seine relative Position im Raum kümmert (im Verhältnis zu anderen Knoten).

Diese Analogie erinnert mich treffend an eine einfache Blasensortierung. Wie kleinere Zahlen in jeder Iteration auftauchen. Wie Ihre Zentrifugenlogik.

Um dies zu beantworten, machen wir bei der softwarebasierten Sortierung nicht tatsächlich etwas Ähnliches?

Zunächst vergleichen Sie zwei verschiedene Kontexte, einer ist Logik (Computer) und der andere ist Physik. Dies ist (bisher) bewiesen, dass wir einige Teile davon mithilfe mathematischer Formeln modellieren können und wir als Programmierer diese Formeln zur Simulation verwenden können (einige Teile der) Physik in der Logik arbeiten (zB Physik-Engine in der Game-Engine).

Zweitens haben wir einige Möglichkeiten in der Computer- (Logik-) Welt, die in der Physik nahezu unmöglich sind. Zum Beispiel können wir jederzeit auf den Speicher zugreifen und den genauen Ort jeder Entität finden, aber in der Physik ist dies ein großes Problem. Heisenbergs Unsicherheitsprinzip .

Drittens Wenn Sie Zentrifugen und ihren Betrieb in der realen Welt auf die Computerwelt abbilden möchten, ist es so, als hätte Ihnen jemand (der Gott) einen Supercomputer mit allen Regeln der Physik gegeben, und Sie sortieren darin ( mit Zentrifuge) und wenn Sie sagen, dass Ihr Sortierproblem in o (n) gelöst wurde, ignorieren Sie die riesige Physiksimulation im Hintergrund ...

Eine andere Perspektive ist, dass das, was Sie mit der Zentrifuge beschreiben, analog zu dem ist, was als "Spaghetti-Sorte" bezeichnet wird ( https://en.wikipedia.org/wiki/Spaghetti_sort ). Angenommen, Sie haben eine Schachtel mit ungekochten Spaghettistangen unterschiedlicher Länge. Halten Sie sie in Ihrer Faust und lösen Sie Ihre Hand, um sie vertikal abzusenken, sodass alle Enden auf einem horizontalen Tisch ruhen. Boom! Sie sind nach Höhe sortiert. O (konstante) Zeit. (Oder O (n), wenn Sie die Stangen nach Höhe heraussuchen und in ein ... Spaghettiträger legen, denke ich?)

Sie können dort feststellen, dass es O (konstant) in der Anzahl der Spaghetti-Stücke ist, aber aufgrund der endlichen Schallgeschwindigkeit in Spaghetti ist es O (n) in der Länge des längsten Strangs. Also ist nichts umsonst.

Bedenken Sie: Ist "Zentrifugensortierung" wirklich besser skalierbar? Überlegen Sie, was beim Skalieren passiert.

• Die Reagenzgläser müssen immer länger werden.
• Das schwere Zeug muss immer weiter reisen, um auf den Grund zu kommen.
• Das Trägheitsmoment nimmt zu und erfordert mehr Leistung und längere Zeiten, um auf die Sortiergeschwindigkeit zu beschleunigen.

Es lohnt sich auch, andere Probleme mit der Zentrifugensorte in Betracht zu ziehen. Beispielsweise können Sie nur auf einer schmalen Größenskala arbeiten. Ein Computersortierungsalgorithmus kann Ganzzahlen von 1 bis 2 ^ 1024 und darüber hinaus ohne Schweiß verarbeiten. Geben Sie etwas, das 2 ^ 1024-mal so viel wie ein Wasserstoffatom wiegt, in eine Zentrifuge, und das ist ein Schwarzes Loch, und die Galaxie wurde zerstört. Der Algorithmus ist fehlgeschlagen.

Die eigentliche Antwort hier ist natürlich, dass die Komplexität der Berechnungen relativ zu einem Rechenmodell ist, wie in anderen Antworten erwähnt. Und "Zentrifugensortierung" ist im Kontext gängiger Rechenmodelle wie dem RAM-Modell oder dem E / A-Modell oder Multitape-Turing-Maschinen nicht sinnvoll.