Sortieren einer Liste von Zeichenfolgen in lexikografischer Reihenfolge der sortierten Zeichenfolgen

8

Sei eine Sammlung von Zeichenfolgen über dem Alphabet , die insgesamt Symbole enthalten .A{0,,m1}n

Ihre Aufgabe ist es, jede der Zeichenfolgen intern zu sortieren und dann die resultierenden Zeichenfolgen in lexikografischer Reihenfolge zu sortieren. (Ihr Algorithmus muss nicht so funktionieren.)

Beispiel:

Eingabe: 33123 15 1 0 54215 21 12

Ausgabe: 0 1 12 12 12333 12455 15

Ich habe einen Weg gefunden, dies in Zeit und Raum zu tun .O(m+n)O(mn)

Der Speicherplatz ist größer als die Zeit, da ich ein intelligentes Array verwende, mit dem Sie ein Array mit der Größe erstellen und allen Zellen in Anfangswerte geben können .nO(1)

Ich habe die Bucket-Sortierung verwendet, um jede Zeichenfolge ( Zeit und Raum) und Wortbäume zu sortieren, um die Sammlung selbst ( Zeit und Raum) zu sortieren . aber meine lösung ist zu kompliziert.O(m+n)AO(m+n)O(mn)

Hat jemand eine bessere Lösung mit Zeit und weniger Platz oder schneller als ?O(m+n)O(m+n)

Die Lösung muss deterministisch sein, damit keine Hash-Maps oder andere statistische Algorithmen verwendet werden


Meine Lösung: Ein Smart Array ist ein Array der Größe das wir in erstellen und "initialisieren" können :mO(1)

Wir erstellen drei Arrays mit der Größe von ohne eines davon zu initialisieren, und wir behalten auch eine einzelne ganzzahlige Variable namens .mC

Das erste Array enthält die Daten. Das zweite Array enthält Zeiger auf eine Zelle im dritten Array. Das dritte Array enthält Zeiger auf eine Zelle im zweiten Array. enthält die Anzahl der bisher initialisierten Zellen.C

Angenommen, wir möchten den Wert von Zelle festlegen (nehmen wir an, es ist das erste Mal, dass wir dies für diese Zelle tun). Dann gehen wir zu Zelle im ersten Array und setzen sie auf den gewünschten Wert.ii

Jetzt gehen wir zu Zelle im zweiten Array und setzen sie so, dass sie auf Zelle im dritten Array zeigt. Stellen Sie die Zelle im dritten Array so ein, dass sie auf die Zelle im zweiten Array zeigt. Erhöhen Sie um 1.iCCiC

Angenommen, wir möchten wissen, ob Zelle Papierkorb ist (das heißt, wir müssen noch etwas darauf einstellen).j

Wir würden zu Zelle im zweiten Array gehen und uns die Zellennummer (im dritten Array) ansehen, auf die Zelle (im zweiten Array) zeigt - wir werden es .jjk

Wenn dann ist Papierkorb (weil wir bisher nur Zellen initialisiert haben und keine davon ist).k>CjCj

Wenn ist, schauen wir uns an, auf welche Zelle (im dritten Array) zeigt. Wenn es nicht dann ist Müll. Sonst ist kein Müllk<Ckjjj

Auf diese Weise können wir bei jedem Schritt feststellen, ob wir diese Zelle initialisiert haben und wenn nicht. Also haben wir ein Array der Größe in -Zeit erstellt und "initialisiert" .mO(1)

Der Haupttrick besteht nicht darin, das gesamte Array zu Beginn zu initialisieren, sondern einen Weg zu finden, um zu wissen, welche Zellen wir bisher initialisiert haben, und eine Zelle nur dann zu initialisieren, wenn wir sie "betrachten". Im RAM-Modell benötigt Zeit, um ein Array beliebiger Größe zu erstellen, ohne es zu initialisieren.O(1)


Ein Wortbaum der Ordnung m ist eine Verallgemeinerung einer TRIE. Jeder Knoten enthält ein Array von Zeigern auf seine Söhne. Die Arraygröße beträgt . Jeder Knoten enthält auch einen Zähler, der angibt, wie viele Sätze von diesem Knoten beschrieben werden.m

Da wir jedes Mal, wenn wir ein Wort (eine Menge) hinzufügen, intelligente Arrays verwenden, werden nur Zeit und Raum benötigt.AO(|A|)O(m|A|)

Ofer Magen
quelle
5
Zeit kann nicht kleiner sein als Raum. Sie betrügen in irgendeiner Weise.
Yuval Filmus
Sicher kann es. Das Erstellen eines Arrays in Größe n ohne Zurücksetzen erfordert O (1). Das gilt für c und c ++. Dann können Sie eine sehr einfache Datenstruktur verwenden, um zu verfolgen, welche Zellen Sie verwendet haben und welche Müll sind
Ofer Magen
3
C und C ++ interessieren mich nicht besonders. Wir analysieren normalerweise Algorithmen unter dem RAM-Maschinenmodell. In diesem Modell kann die Zeit nicht kleiner als der Raum sein. Ich bin etwas besorgt, dass Ihr Smart Array in pro Zugriff nicht wirklich funktioniert . O(1)
Yuval Filmus
1
Das RAM-Modell benötigt O (1), um ein Array mit der Größe n zu definieren (der Computer muss nur die Start- und Endzeiger definieren). Es dauert O (n), um es auf Null zurückzusetzen. C ++ ist eine RAM-Modellsprache, deshalb habe ich dieses Beispiel gebracht
Ofer Magen
@ YuvalFilmus Time cannot be smaller than spacewahr. You are cheating in some wayfolgt nicht aus " Zeit und Raum": Mit , - die räumliche Begrenzung sieht unnötig locker aus. Ö(m+n)Ö(mn)1mnxm+yn+zÖ(mn)
Graubart

Antworten:

0

Sie können dies auch in Zeit und Raum lösen :Ö(nLogn)Ö(n)

  • Sortieren Sie zuerst jedes Wort mit Mergesort. Die Laufzeit hierfür beträgt höchstens , und die Speicherplatznutzung beträgt .Ö(nLogn)Ö(n)

  • Speichern Sie dann alle Wörter in einem Wortversuch. Die Zeit und der Raum dafür sind , wenn Sie das Wort trie richtig implementieren. Insbesondere sollten Sie an jedem Knoten des Versuchs die untergeordneten Gruppen als Hashtabelle (nicht als Array) speichern. Auf diese Weise ist der Speicher an einem Knoten proportional zur Anzahl der untergeordneten Knoten, und die Suche nach einem untergeordneten Element kann in -Zeit erfolgen. Somit ist die Laufzeit dieser Stufe Zeit und Raum.Ö(n)Ö(1)Ö(n)Ö(n)

  • Lesen Sie zum Schluss alle Wörter aus dem Versuch vor. Dazu müssen Sie jede Hashtabelle nehmen und ihren Inhalt sortieren, beispielsweise mithilfe von Mergesort. Alle diese Sortierschritte dauern höchstens .Ö(nLogn)

Die resultierende Datenstruktur scheint recht einfach zu sein. Es ist besonders einfach, wenn Sie in einer Sprache implementieren, die integrierte Unterstützung für Hashmaps bietet (z. B. Javascript, Python).

Alternativ können Sie die Hashmap durch eine ausgeglichene Binärbaumdatenstruktur ersetzen und eine ähnliche Laufzeit erhalten.


Als allgemeine Anmerkung zu "Smart Arrays":

Sie können Ihre Verwendung von "Smart Arrays" durch eine Hashtabelle ersetzen. Auf diese Weise behalten Sie die Fähigkeit, (erwartete) Lese- und Schreibvorgänge durchzuführen. Anstatt , speichern Sie insbesondere den Wert am Schlüssel (dh fügen Sie die Zuordnung zur Hashtabelle hinzu). Wenn Sie den Wert von lesen möchten, suchen Sie stattdessen in der Hashtabelle und geben alles zurück, was Sie dort finden. Auf diese Weise ist die Speicherplatznutzung proportional zur Anzahl der initialisierten Einträge im "Smart Array", und jeder Zugriff benötigt (erwartete) Zeit.Ö(1)EIN[ich]]: =vvkkvEIN[ich]]ichÖ(1)

DW
quelle
Hashtable sind statistische Werkzeuge und ich brauche eine deterministische Lösung. Die Verwendung der Zusammenführungssortierung ist nicht erforderlich. Sie können die Eimersortierung verwenden, da dies ganze Zahlen im Bereich von 1 bis m sind, und diese in O (n + m)
Ofer Magen
Das Smart Array ist jedoch völlig deterministisch
Ofer Magen
4
Sie haben nach schneller als gefragt . ist für einige Parameter schneller als - für andere jedoch nicht. Wenn Sie keine Hashtabelle verwenden möchten, verwenden Sie eine ausgeglichene Binärbaum-Datenstruktur, wie ich in meiner Antwort vorgeschlagen habe. Dadurch werden die gleichen -Laufzeiten und -Raumgrenzen erreicht so total deterministisch. Ö(n+m)Ö(nLogn)Ö(n+m)Ö(nLogn)Ö(n)
DW
@OferMagen Wenn die Sammlung A im Voraus bekannt ist, können Sie ein minimales perfektes Hashing verwenden, also keine Kollisionen.
Gerardo Zinno
0

Sie können eine Menge von Zeichenfolgen über ein ganzzahliges Alphabet der Größe sortieren, indem Sie einen Versuch in Zeit und Raum verwenden, wobei die Unterscheidung ist Präfix von .S.{0,1,,σ- -1}}σÖ(dσ)dS.

Hier ist eine Lösung, bei der keine Hash-Tabellen verwendet werden.

Sei die Länge des kürzesten Präfixes der Zeichenfolge , das sie von den anderen Zeichenfolgen in . Das Unterscheidungspräfix von ist definiert als .dssS.S.S.d=sS.ds

Der Algorithmus zur Lösung des Problems verwendet einen Divide & Conquer-Ansatz. Es handelt sich um einen RadixSort, der von der höchstwertigen Ziffer (char) ausgeht.

1) Erstellen Sie Bucketsσ0,1,,σ- -1

2) Verarbeiten Sie die Zeichenfolgen von Anfang an zeichenweise und verteilen Sie sie mit CountingSort in -Zeit in Buckets .σÖ(1)

3) Wiederholen Sie den Vorgang für Buckets, die mehr als ein Element enthalten, und sortieren Sie sie mit dem nächsten Zeichen.

4) Verketten Sie die Gruppen von links nach rechts, um die geordnete Sequenz zu erhalten.

Dieser Algorithmus erzeugt einen -ary-Versuch, bei dem jeder Knoten ein Array mit Größe ist und die Zeichenfolgen in den Blättern gespeichert sind.σσ

Hier ist ein Beispiel.

Lass seinσ5 und S.={410,013,042,111,001,444}}.

Das Folgende ist der vom Algorithmus erzeugte Versuch: versuchen

Jede Zeichenfolge s formuliert einen Pfad der Größe Ö(ds) vor dem Knoten, der auf zeigt sgeschaffen. Jeder Knoten dieser Pfade nimmtÖ(σ) Raum und Ö(σ) Zeit zuzuteilen.

Gerardo Zinno
quelle
Verwenden Sie diesen Ansatz, aber ersetzen Sie die σBei Knoten mit Größe und Hash-Tabellen, deren Größe proportional zu den vom Knoten ausgehenden Kanten ist, können Sie den Algorithmus ausführen Ö(d lÖGσ) durchschnittliche Zeit und Ö(d)Platz.
Gerardo Zinno