Schwerkraft Sortierung: Ist das programmgesteuert möglich? [abgeschlossen

Question

Ich habe kürzlich darüber nachgedacht, das objektorientierte Design im Sortieralgorithmus zu verwenden. Ich konnte jedoch keinen richtigen Weg finden, um diesen Sortieralgorithmus zu machen, der die Sortierung in O (n) Zeit macht.

Ok, hier ist, was ich seit einer Woche gedacht habe. Ich habe eine Reihe von Eingabedaten. Ich werde jedem der Eingabedaten eine Masse zuweisen (übernehmen Sie Eingabedaten, eine Art von Art von Mass und eine Art von Art von Sphere. Wenn wir annehmen, dass alle Objekte perfekt kugelförmige Objekte mit Formen sind, die proportional zu ihrer Masse sind, berührt der schwerste zuerst den Boden.). Ich werde alle meine Eingabedaten im Raum in gleicher Entfernung von der Erde platzieren. Und ich werde sie frei fallen lassen. Nach dem Gravitationsgesetz trifft der schwerste zuerst den Boden. Und die Reihenfolge, in der sie schlagen, gibt mir die sortierten Daten. Dies ist in irgendeiner Weise lustig, aber darunter habe ich das Gefühl, dass dies mit dem OO, das ich bisher gelernt habe, möglich sein sollte

Ist es wirklich möglich, eine Sortierungstechnik zu erstellen, bei der das Szenario für das Gravitationszug verwendet wird, oder bin ich dumm/verrückt?

Bearbeiten: Es stellt sich heraus, dass alle Objekte gleichzeitig auf den Boden gehen, daher habe ich das sphärische Objektkonzept eingeführt.

Answer 1

Die Sache ist, obwohl einer der Ideen Oop mag es sein, die reale Welt zu modellieren, das bedeutet nicht, dass es eine direkte Korrespondenz zwischen dem, wie lange etwas in der realen Welt dauert und wie lange es dauern würde, um sie mit einem Computer zu simulieren.

Stellen Sie sich die tatsächlichen Schritte vor, die für Ihr Verfahren erforderlich sind:

1. Für jedes Element in Ihrem Datensatz muss ein Objekt konstruiert werden. Bei den meisten modernen Hardware würde dies allein eine ITRANation erfordern und daher Ihre Strategie o (n) bei Beste.
2. Die Wirkung der Schwerkraft müsste für jedes Objekt simuliert werden. Auch hier wäre der offensichtlichste und unkomplizierteste Weg, dies umzusetzen.
3. Die Zeit, in der jedes Objekt auf der Oberfläche der "Erde" in Ihrem Programmiermodell landet, müsste erfasst werden, und über einen implementierungsspezifischen Mechanismus müsste das entsprechende Objekt als Ergebnis in eine geordnete Liste eingefügt werden.

Die Berücksichtigung des Problems führt weiter zusätzliche Komplikationen ein. Fragen Sie sich Folgendes: Wie hoch müssen Sie diese Objekte positionieren, um zu beginnen? Offensichtlich hoch genug, damit das größte tatsächlich Stürze; dh weiter von der Erde entfernt als der Radius des größten Objekts. Aber woher weißt du, wie weit das ist? Sie müssten zuerst das größte Objekt in der Sammlung bestimmen. Dies würde wieder (wahrscheinlich) eine Iteration erfordern. Man könnte sich auch vorstellen, dass diese Simulation mit Multithread versucht werden könnte, das Echtzeitverhalten des Begriffs von Objekten zu simulieren eigentlich fällen; Aber dann werden Sie versuchen, Gegenstände zu einer Sammlung hinzuzufügen (eine Operation, die offensichtlich eine Menge Zeit in Anspruch nimmt) möglicherweise gleichzeitig, als neue Kollisionen erkannt werden. Dadurch werden auch Threading -Probleme erzeugt.

Kurz gesagt, ich habe Probleme, mir vorzustellen, wie diese Idee ordnungsgemäß mit OOP ohne spezielle Hardware ordnungsgemäß implementiert werden könnte. Das heißt, es wirklich ist eine gute Idee. Es erinnert mich in der Tat an Perlenart-Ein Algorithmus, der zwar nicht dasselbe wie Ihre Idee ist, auch eine Sortierlösung ist, die das sehr physikalische Konzept der Schwerkraft ausnutzt und nicht überraschenderweise spezielle Hardware erfordert.

Answer 2

Sie haben gerade das Problem angepasst. Die Berechnung der Reihenfolge der Gravitationseffekte hat bestenfalls das O der Art Algorithmen, die Sie schlagen möchten.

Answer 3

Die Gravitationsberechnung ist nur in der realen Welt kostenlos. In Programm müssen Sie es modellieren. Es wird ein weiteres n in Komplexitätsminimum sein

Answer 4

Allgemeine Sortierung ist bestenfalls O (N Log N). Um dies zu verbessern, müssen Sie etwas über die Daten wissen, als nur, wie Sie Werte vergleichen können.

Wenn die Werte alle Zahlen sind, Radix -Sortierung gibt O (n) unter der Annahme, dass Sie obere und untere Grenzen für die Zahlen haben. Dieser Ansatz kann erweitert werden, um eine beliebige Zahl zu verarbeiten - und letztendlich werden alle Daten in einem Computer mit Zahlen dargestellt. Zum Beispiel können Sie in jedem Pass radix-sort-Zeichenfolgen durch einen Zeichen sortieren, als wäre es eine Ziffer.

Leider bedeutet die Umgang mit variablen Datengrößen von Daten, eine variable Anzahl von Durchgängen durch die Radix -Sortierung. Sie haben am Ende O (n log m), wobei m der größte Wert ist (da k-Bits Ihnen einen Wert von bis zu (2^k) -1 für nicht signiert, halb das für unterschrieben haben). Wenn Sie beispielsweise die Ganzzahlen von 0 bis M -1 sortieren, haben Sie tatsächlich wieder O (n log n).

Das Übersetzen eines Problems in ein anderes kann ein sehr guter Ansatz sein, aber manchmal fügt es nur eine weitere Ebene der Komplexität und des Overheads hinzu.

Answer 5

Die Idee mag einfach erscheinen, aber der Unterschied zwischen der realen und der modellierten in diesem Fall ist, dass in der realen Welt alles parallel passiert. Um die Gravitationsart zu modellieren, wie Sie beschreiben, müssten Sie zunächst an jedes Objekt in einem separaten Thread mit einem sicheren Weg denken, um sie in der Reihenfolge zu fügen, in der sie fertig sind. Realistisch in Bezug auf die Sortierung der Leistung würden Sie wahrscheinlich nur eine schnelle Sorte in der Zeit verwenden, oder da sie in der gleichen Entfernung die sinkende Rate des Sturzes haben. Wenn Ihre Formel jedoch proportional zur Masse ist, überspringen Sie das alles und sortieren die Masse.

Answer 6

In einem fiktiven "Gravitationscomputer" würde diese Art des Sortierens O (1) gelöst werden. Aber mit den echten Computern wie wir es wissen, würde Ihr seitlicher Gedanke nicht helfen.

Answer 7

Sobald Sie alle Zeiten berechnet haben, die sie zum Boden nehmen, müssen Sie diese Werte immer noch sortieren. Sie gewinnen nicht wirklich etwas, Sie sortieren nur verschiedene Zahlen, nachdem Sie eine zusätzliche unnötige Berechnung durchgeführt haben.

BEARBEITEN: Whoops. Physik vergessen 101. Natürlich werden sie alle gleichzeitig treffen. :)

Jede Art von Modellierung wie diese verwandelt nur ein Sortierproblem in ein anderes. Sie werden nichts gewinnen.

Answer 8

Wenn Sie alle Mängel ignorieren, die alle anderen erwähnt haben, läuft dies im Wesentlichen auf eine hinaus O(n^2) Algorithmus, nicht O(n). Sie müssten über alle "Kugeln" iterieren, den "schwersten" oder "größten" finden und ihn dann auf eine Liste schieben, dann ausspülen und wiederholen. IE, um den zu finden, der zuerst den Boden triff O(n) Zeit könnte der zweite dauern O(n-1), usw. ... aber schlimmer als das, Sie müssen jedes Mal eine Reihe mathematischer Operationen ausführen, um einen nutzlosen "Zeitwert" zu berechnen, wenn Sie den Wert hätten sortieren können, an dem Sie sich überhaupt interessiert haben.

Answer 9

Hmmmm. Schwerkraft Sort.

Wenn Sie Ihr spezifisches Schwerkraftmodell ignorieren, sehen wir, wohin diese Idee uns führt.

Physische Realität hat 10^80 Prozessoren.

Es ist bekannt, dass die tatsächlichen Untergrenzen der Sortierung log (n) sind, wenn Sie N/2 -Prozessoren haben, um N -Objekte zu sortieren.

Wenn Sie mehrere CPU -Kerne zur Verfügung haben, gibt es keinen Grund, dass Sie Mergesort auf mehreren Threads nicht ausführen können.

Answer 10

Es gibt tatsächlich einen ziemlich berühmten Sortieralgorithmus namens Spaghetti -Sort, der Ihnen ähnlich ist. Sie können einige der vielen Analysen im Internet überprüfen. zB auf csthory.

Answer 11

Es sollte definitiv nur sein, dass Sie eine ordnungsgemäße Hardware dafür unterstützen sollten. Ansonsten klingt das eine sehr coole Idee. Ich hoffe, jemand präsentiert ein IEEE -Papier, um diesen verrückten Traum sich visualisiert zu machen.

Answer 12

Ich liebe die Idee! Es ist klug. Während ja, was andere sagen, ist Im Algemeinen Richtig, dass die O (n log n) gebundene Offenbar für das Sortierproblem im Allgemeinen berücksichtigen müssen Vergleichsbasiert Modelle. Was Sie hier vorschlagen, ist ein ganz anderes Modell, es verdient weitere Gedanken.

Wie James und Matrix hervorgehoben haben, weist Sie das Modell offensichtlich an etwas an etwas an, bei dem das schwerere Objekt (Anzahl) tatsächlich schneller/weiter wandeln würde (oder langsamer/weniger weiter), damit Sie die Zahlen irgendwie unterscheiden können (eine Zentrifuge fällt auch in den Sinn).

Benötigt mehr Gedanken, aber Ihre Idee ist scharf!

(Bearbeiten) Wenn ich nun die Phys2D -Idee von Enrique betrachte, denke ich, dass es viel sinnvoller ist.

Eine Sache, die ich vorschlagen würde, ist, den Effizienzaspekt vorerst definitiv zu ignorieren. (Ich weiß, ich weiß, dass das das gesamte Ziel war). Es ist ein neues Modell, und wir müssen zunächst die Lücke zwischen der Idee und ihrer Implementierung schließen. Nur dann können wir verstehen, was die Zeitkomplexität überhaupt für dieses Modell bedeutet.

Answer 13

Ich denke Zeilen und nicht Kugeln ... In diesem Fall können Sie einfach sagen, dass Heightofftheground = max_value - Masse.

Sie müssen sich im Laufe der Zeit auch keine Sorgen um die Beschleunigung machen ... da es Ihnen egal ist, wie schnell sie gehen oder realistische Physik, können Sie ihnen allen eine anfängliche Geschwindigkeit x geben und von dort aus gehen.

Das Problem ist dann, dass wir das Problem im Wesentlichen nur angepasst und so gelöst haben (Pseudocode):

int[] sortedArray; // empty
int[] unsortedArray; // full of stuff
int iVal = MAX_INT_VALUE;
while (true)
{
    foreach (currentArrayValue in sortedArray)
    {
        if (iVal = current array value
        {
            put it in my sortedArray
            remove the value from my unsortedArray
        }
    }
    if (unsortedArray is empty)
    {
        break;  // from while loop
    } 
    iVal--
}

Das Problem ist, dass Sie über jede Zeiteinheit iterieren müssen, um die Physik -Engine zu betreiben, und das wird O (1) ... mit a sehr Große Konstante ... die konstante Anzahl der Delta -Werte, auf denen das System ausgeführt wird. Der Nachteil besteht wird schlagen.

Sie könnten versuchen, einfach zu sagen, na ja, lass uns viele Vermittlerschritte überspringen und einfach vorwärts springen, bis ein Treffer erzielt wird! Aber das bedeutet, dass Sie wissen müssen, welches das größte ist ... und Sie sind wieder zum Sortierproblem.

Answer 14

Ich werde deine Idee ein wenig anpassen. Wir haben unsere Objekte, aber sie unterscheiden sich nicht in Gewicht, sondern in Geschwindigkeit. Zu Beginn sind alle Objekte an der Startlinie und auf dem Startschuss ausgerichtet, sie werden alle mit ihren jeweiligen Geschwindigkeiten bis zum Ziel bewegen.

Klar genug: Das erste Objekt im Finish wird ein Signal ausstrahlt und sagt, dass es da ist. Sie fangen das Signal und schreiben auf das Ergebnispapier, wer es war.

Okay, also willst du das simulieren.

Wir nehmen die Länge Ihres Feldes, um es zu sein L=1. Mit Schrittgröße ∆t Jedes von dir N Objekte bewegt eine Länge von vᵢ∙∆t zu einer Zeit. Das heißt, jedes Objekt braucht sᵢ = L / (vᵢ∙∆t) Schritte, bevor Sie das Ziel erreichen.

Der Punkt ist nun, um zwischen zwei Objekten mit sehr engen Geschwindigkeiten zu unterscheiden, dass Sie für alle Ihre Objekte eine andere Schrittgröße haben müssen.

Jetzt in der Beste Fall, dies bedeutet, dass Objekt 1 in einem Schritt endet, Objekt 2 in zwei usw. Daher ist die Gesamtzahl der Schritte S = 1 + 2 + … + N = N∙(N + 1)/2. Dies ist in Ordnung N∙N.

Wenn es nicht der beste Fall ist und die Geschwindigkeiten nicht gleich nahe beieinander sind, müssen Sie die Schrittgröße senken und noch viel mehr Male wiederholen.

Answer 15

Wenn ein Computer so erstellt werden würde, dass sortierte Objekte basierend auf einigen Kriterien (was nicht völlig lächerlich zu denken ist), dann glaube ich, dass die Reihenfolge der Komplexität nichts mit der Anzahl der Objekte zu tun hätte, sondern die Rate der lokalen Beschleunigung aufgrund der Schwerkraft. Angenommen, es ist auf der Erde modelliert, wäre die Komplexität o (g₀) wo g₀ ist:

Die einfache Argumentation ist, dass die Anzahl der sphärischen Objekte (n) ist irrelevant, wenn ihre Zentren zu Beginn ausgerichtet sind. Darüber hinaus wird die Beschleunigung aufgrund der Schwerkraft einen viel größeren Einfluss haben als die Höhe selbst, wenn sie zunimmt. Wenn wir beispielsweise die Höhe aller Objekte um das 10 -fache erhöhen, würde sie nicht die Zeit brauchen, um den Boden zu treffen, sondern viel geringer. Dies schließt verschiedene vernachlässigbare Näherungen ein, da die Beschleunigung tatsächlich von der Entfernung zwischen zwei Objekten abhängt, die jedoch ignoriert werden können, da wir eher an einem größeren Bild als an einem bestimmten Wert interessiert sind.

Trotzdem geniale Idee.

Außerdem liebe ich das von @Jeremy gepostete Münzsortiervideo. Und schließlich wäre die Objektorientierung das geringste meiner Bedenken beim Aufbau einer solchen Maschine. Wenn Sie mehr darüber nachdenken, hier sind meine dummen zwei Cent zum Aufbau einer solchen Maschine:

O 0 o O o

. . . . .
. . . . .
. . . . .
= = = = =

Alle Objekte haben unterschiedliche Größen proportional zu den Kriterien, nach denen wir sortieren möchten. Sie werden zunächst horizontal von einer dünnen Stange zusammengehalten, die durch die Mitte jeder Kugel verläuft. Das = Unten sind speziell ausgelegt, um einen Wert (optional ihre Position) irgendwo aufzuzeichnen, sobald sie mit einer Kugel kollidieren. Nachdem alle Kugeln kollidiert sind, werden wir unsere sortierte Reihenfolge auf der Grundlage der aufgezeichneten Werte basieren.

Answer 16

aus Debilskis Antwort:

Ich werde deine Idee ein wenig anpassen. Wir haben unsere Objekte, aber sie unterscheiden sich nicht in Gewicht, sondern in Geschwindigkeit. Zu Beginn sind alle Objekte an der Startlinie und auf dem Startschuss ausgerichtet, sie werden alle mit ihren jeweiligen Geschwindigkeiten bis zum Ziel bewegen.

Klar genug: Das erste Objekt im Finish wird ein Signal ausstrahlt und sagt, dass es da ist. Sie fangen das Signal und schreiben auf das Ergebnispapier, wer es war

Ich würde es noch einen Schritt weiter vereinfachen und sagen, dass diese Objekte zufällige positive Ganzzahlen sind. Und wir wollen sie in einer aufsteigender Reihenfolge sortieren, wenn sie sich Null nähern, damit sie a haben Distanz von null d was anfangs gleich der Ganzzahl selbst ist.

Angenommen, die Simulation findet in diskreten Zeitschritten statt, dh dh dh Rahmen, In jedem Rahmen wäre die neue Entfernung jedes Objekts: d = d - v und ein Objekt würde der Liste hinzugefügt werden, wenn es ist d ≤ 0. Das ist eine Subtraktion und eine bedingte. Zwei diskrete Schritte für jedes Objekt, so dass die Berechnungen o (n) zu sein scheinen: linear.

Der Haken ist, es ist linear für ein Rahmen nur! Es wird mit der Anzahl der Frames multipliziert f erforderlich, um fertig zu werden. Die Simulation selbst ist O (NF): quadratisch.

Wenn wir jedoch die Dauer eines Rahmens als Argument nehmen t Wir haben die Fähigkeit, die Anzahl der Frames zu beeinflussen f umgekehrt proportional. Wir können erhöhen t reduzieren f Dies geht jedoch auf Kosten der Genauigkeit her, je mehr wir erhöhen t, Je mehr die Wahrscheinlichkeit, dass zwei Objekte im gleichen Zeitrahmen abgeschlossen sind, als gleichwertig aufgeführt, auch wenn dies nicht der Fall ist. Wir erhalten also einen Algorithmus mit einstellbarer Genauigkeit (wie in den meisten Kontexten der Finite -Elemente -Simulation)

Wir können dies weiter verfeinern, indem wir es in einen adaptiven+rekursiven Algorithmus verwandeln. Im menschlichen Code wäre es:

function: FESort: arguments: OriginalList, Tolerance
  define an empty local list: ResultList

  while OriginalList has elements
    define an empty local list: FinishedList
    iterate through OriginalList
      decrement the distance of each object by Tolerance
      if distance is less than or equal to zero, move object from OriginalList to FinishedList

    check the number of elements in FinishedList
      when zero
        set Tolerance to double Tolerance
      when one
        append the only element in FinishedList to ResultList
      when more
        append the result of FESort with FinishedList and half Tolerance to ResultList

  return ResultList

Ich frage mich, ob es eine wirklich ähnliche Implementierung gibt, die für jemanden funktioniert.

Interessantes Thema in der Tat :)

Ps. Der obige Pseudocode ist meine Vorstellung von Pseudocode. Bitte schreiben Sie es auf eine lesbarere oder konformere Weise, wenn es eine gibt.

Answer 17

Vor einigen Wochen habe ich über dasselbe nachgedacht.

Ich dachte zu benutzen Phys2d Bibliothek, um es zu implementieren. Es mag nicht praktisch sein, sondern nur zum Spaß. Sie können den Objekten auch negative Gewichte zuweisen, um negative Zahlen darzustellen. Mit der Phys2D -Bibliothek können Sie die Schwerkraft definieren, sodass Objekte mit negativem Gewicht auf das Dach gehen und Objekte mit positivem Gewicht fallen. Anordnen Sie alle Objekte in der Mitte zwischen Boden und Dach mit gleichem Abstand zwischen Boden und Dach. Angenommen, Sie haben ein daraus resultierendes Array r [] von Länge = Anzahl der Objekte. Dann fügen Sie jedes Mal, wenn ein Objekt das Dach berührt Fügen Sie es am Ende des Array R [R.Length-1] hinzu, wenn Sie es das nächste Mal bei r [R.Length-2] hinzufügen. Am Endobjekten, die sich nicht bewegten (in der Mitte schwebend blieb), können in der Mitte des Arrays hinzugefügt werden (diese Objekte sind die 0er).

Dies ist nicht effizient, kann Ihnen jedoch helfen, Ihre Idee zu implementieren.

Answer 18

1. Ich glaube, es ist schön zu erwähnen/zu beziehen: Wie ist die Beziehung zwischen P vs. NP und der Natur, um NP -Probleme effizient zu lösen?Sortierung ist O(nlog(n)), Warum nicht versuchen, NP-harte Probleme zu lösen?
2. Durch die Gesetze der Physikobjekte fallen mit Proportionen zurGravitationskonstante Die Masse ist vernachlässigbar.
3. Die Simulation eines physischen Prozesses kann die tatsächliche Zeitkomplexität beeinflussen.

Answer 19

Analysieren: (1) Alle Kugelnzentren sind zu Start (2) größere Zahl ==> Masse höher ==> Radius größer ==> Abstand zum Boden niedriger (3) in 'Vakuum' gleiche Beschleunigung = gleiche Geschwindigkeitsentwicklung = => gleiche Entfernung für das Zentrum ==> Wie größer der Radius ... Wie früher wird die Kugel auf den Boden treten ... Wir werden die sortierte Liste praktisch geben ... keine "gute" numerische Technik