Hans Zeit, linearer Raum, ganzzahliger Sortieralgorithmus

Ist jemand mit Yijie Hans , linearem Raum und ganzzahligem Sortieralgorithmus vertraut ? Dieses Ergebnis erscheint in einem relativ kurzen Artikel ( Deterministische Sortierung in Zeit und linearem Raum . J. Alg. 50: 96–105, 2004), der im Grunde genommen viele frühere Ergebnisse mit geeigneten zusammenklebt Anpassungen. Mein Problem ist, dass es eher von Hand geschrieben ist, ohne auf Einzelheiten einzugehen. Es stützt sich stark auf frühere Veröffentlichungen, darunter eine weitere Veröffentlichung von Han ( Verbesserte schnelle Ganzzahlensortierung im linearen Raum) $O(n \log\log n)$ $O(n \log\log n)$ . Information and Computation 170 (1): 81–94) im gleichen Stil geschrieben. Ich habe erhebliche Schwierigkeiten, diese beiden Papiere zu verstehen, insbesondere die Art und Weise, wie sie frühere Ergebnisse anpassen und verwenden. Ich würde mich über jede Hilfe freuen.

Dies ist natürlich zu weit gefasst und vage, um als richtige Frage angesehen zu werden, aber ich hoffe, eine Diskussion über mehrere gezielte, genau definierte Fragen und Antworten zu entwickeln.

Zum Auftakt hier meine erste konkrete Frage. In Lemma 2 der Info. Comp. Papier gibt es einen rekursiven -Zeitalgorithmus zum Finden der m-ten kleinsten Ganzzahl in einer Menge von kleinen Ganzzahlen, die jeweils in RAM-Wörter gepackt sind. In der Beschreibung des Algorithmus wird nicht erwähnt, wie der Basisfall behandelt wird. In diesem Fall muss die Auswahl in . Wie geht das? $O(n/k \log k)$ $n$ $k$ $k=O(n)$ $O(\log k)$

ds.algorithms sorting Ari
quelle

Es wäre durchaus angebracht, ihm zu schreiben: [email protected].

Joseph O'Rourke

Ja. Wir haben dieses allgemeine Problem bereits erörtert, und der richtige Weg, dies zu beheben, besteht darin, dem Autor eine E-Mail zu senden.

Suresh Venkat

Dazu gehört eine spezielle Frage zu einem Artikel, der sieben Jahre alt ist und den Peer-Review-Prozess bereits durchlaufen hat. Obwohl Ari dem Autor eine E-Mail senden konnte, scheint dies eine ideale Frage für diese Site zu sein. Ich verstehe die Ablenkung nicht.

Huck Bennett

Natürlich habe ich zuerst Han geschrieben. Keine Antwort. Dann habe ich mich über einen Kontakt an jemanden gewandt, der Nachforschungen über Ganzzahlensortierung angestellt hat, und er sagte, er habe die Papiere nach Durchsicht als zu unordentlich befunden, um eine weitere Investition seiner Zeit zu verdienen. Dann bin ich hergekommen. Wenn jemand da draußen ist, der Han kennt und seine Aufmerksamkeit für mich auf sich ziehen kann, wäre das auch großartig.

Ari

Die allgemeine Sortierung hat keine Untergrenze von . Ganz im Gegenteil - die Sortierung ist auf Vergleiche beschränkt, die diese Grenze haben. Hier geht es nicht darum, die Eingabe einzuschränken, sondern das Rechenmodell zu verbessern. Mein Rechenmodell ist eine der RAM-Varianten zu Stückkosten, und ich werde alle vernünftigen Annahmen zulassen (z. B. die Verfügbarkeit von Konstanten, die von der Wortlänge abhängen).

Ω (n \log n)

$\Omega(n\log n)$

Ari

Antworten:

Ich habe mich nur das Gleiche gefragt.

Glücklicherweise konnte ich einen im Jahr 2011 veröffentlichten Zeitschriftenartikel finden, der genau dies erklärt. Darüber hinaus benötigen Sie kein Abonnement, um es anzuzeigen: Implementierung und Leistungsanalyse der exponentiellen Baumsortierung

Ich empfehle, den gesamten Artikel zu lesen, um zu lernen, wie er implementiert werden kann und um die zugrunde liegende Theorie besser zu verstehen. Es wird auch gezeigt, wie Exponentialbäume im Vergleich zu Quick-Sort- und Binärbäumen gestapelt werden. Hier ist der relevante Auszug zu Hans Zeit, linearem Raum und ganzzahligem Sortieralgorithmus $\bf O(n \log\log n)$ :

Yijie Han hat eine Idee vorgestellt, die die Komplexität auf die erwartete Zeit im linearen Raum reduziert. [6] Die von ihm verwendete Technik ist die koordinierte Weitergabe von ganzen Zahlen an den exponentiellen Suchbaum von Andersson [8] und die lineare zeitliche Multiplikation der Bits von ganzen Zahlen. Anstatt eine Ganzzahl nach der anderen in den Exponentialsuchbaum einzufügen, hat er alle Ganzzahlen auf einer Ebene des Exponentialsuchbaums nacheinander weitergegeben. Ein solches koordiniertes Übergeben bietet die Möglichkeit, eine Mehrfachteilung in linearer Zeit durchzuführen und daher den Algorithmus zu beschleunigen. Diese Idee kann zu einer Beschleunigung führen, in der praktischen Umsetzung ist es jedoch sehr schwierig, ganze Zahlen in Batches zu verarbeiten.

[6] Y. Han, Deterministische Sortierung in O (n log log n) Zeit und linearem Raum, 34. STOC, 2002.

[8] A. Andersson, Schnelles deterministisches Sortieren und Suchen im linearen Raum, IEEE-Symposium über Grundlagen der Informatik, 1996.

BEIM
quelle

Warum die Gegenstimme?

Suresh Venkat

Ich habe soeben diesen Journal-Artikel-Link zur Wikipedia-Seite des Exponentialbaums hinzugefügt . Zu Ihrer Information: Dieser Artikel wurde möglicherweise veröffentlicht, nachdem die Frage gestellt wurde.

@AT, könnten Sie bitte Ihre Antwort ein wenig erweitern und erklären, wie es die Frage beantwortet. Momentan gibt es nur einen Link zu einem Artikel in einer Zeitschrift.

Kaveh

Nun, ich habe bereits Hans Artikel aufgegeben und bin froh, dass Sie diese Hilfe leisten konnten. Ich habe nicht wirklich damit gerechnet, etwas zu sehen, als ich heute hierher zurückkam. Vielen Dank! Ich werde dieses neue Papier lesen und sehen, ob es mir hilft, Fortschritte auf Hans Papier zu erzielen.

Ari

Nun, ich habe es jetzt gelesen und ich werde zulassen, dass ich es möglicherweise völlig missverstanden habe, aber abgesehen davon scheint es ein kleines Problem zu geben. Die Autoren behaupten, ihr Baum habe die Höhe O , aber wenn der Baum die Höhe , dann hat erBlätter und damit weniger alsKnoten insgesamt. Nehmen wir großzügig an, dass jeder Knoten Schlüssel enthält. Dann enthält der Baum weniger alsSchlüssel. Wenn dann ist . Auch wenn die Autoren korrekt sind, erreichen sie weder eine O- Sortierung noch eine Erklärung für Han, was nicht sinnvoll ist.

(\log \log n)

$(\log\log n)$

h

$h$

(h + 1)!

$(h+1)!$

2 \cdot (h + 1)!

$2\cdot(h+1)!$

h + 2

$h+2$

2 \cdot (h + 2)!

$2\cdot(h+2)!$

2 \cdot (h + 2)! = n

$2\cdot(h+2)!=n$

h = Ω (\log n / \log \log n)

$h=\Omega(\log n/\log\log n)$

(\log \log n)

$(\log\log n)$

Ari

Ich bin mir bei der Antwort nicht sicher (habe noch kein Papier durchgesehen), aber ich denke, das sollte helfen. Die Zahlen werden in ein einzelnes Wort gepackt, sodass Operationen an einem einzelnen Wort 0 (1) Zeit benötigen. Wenn es zum Beispiel k Zahlen von jeweils h Bits gibt, hängt die Wortgröße von k ab, wobei h wiederum auch vom Bereich der Zahlen abhängt. Daher verwenden wir Techniken zur Bereichsreduzierung, mit denen der Bereich der Zahlen reduziert werden kann, sodass viele Zahlen in ein einzelnes Wort passen. Wenn wir dann die richtigen Bitmasken erstellen, können wir größere Ganzzahlen von den kürzeren unterscheiden, wobei wir jeweils zwei Wörter berücksichtigen. Dies kann in O (1) Zeit erfolgen. (Voraussetzung: Jede in einem Wort gespeicherte Zahl ist mit einem Flag-Bit verknüpft. Dann subtrahieren wir zwei Wörter. Wenn das Flag-Bit leer ist, ist es eine kleinere Zahl.)

Ähnlich wie oben können wir auch jedes Wort sortieren, das k Zahlen in O (log k) Zeit enthält (bitonische Sortierung).

Edit: Algorithmus zum Sortieren von 2k Zahlen im Bereich von 0 bis m-1, gepackt in ein Wort, wobei jede Zahl die Größe L von = log (m + k) +2 annimmt.

$K_1$ sei 1: 000000 1: 000000 1: 000000 1: 000000 ....... so weiter, wobei das Bit vor dem Doppelpunkt auch Flagbit genannt wird und jede Sequenz L Bits lang ist und 2k Mal im Wort K_1 wiederholt wird. (Doppelpunkt ist nur zum Verständnis)

$K_2$ ist (2k-1) (2k-2) .... 1 binär geschrieben. Skizze des Algorithmus:

Wiederholen Sie dies für t = log k bis 0.

Teil 1 - Trenne das ursprüngliche Wort Z in zwei Wörter A und B.

Lassen Sie T erhalten, indem Sie , (L-1-t Positionen) nach links verschieben und das Ergebnis mit UND-verknüpfen . Sei M = T- (T hat L-1 Stellen verschoben). $K_2$ $K_1$
Und Z mit M und verschiebe das Ergebnis ( ) nach rechts. Dies gibt A. $2^t L$
B = Z- (Z & amp; M).

Teil 2

M = ((A ODER ) -B) & $K_1$ $K_1$
M = M- (M um L-1 Stellen nach links verschoben).
MIN = (B & M) ODER (A- (A & M))
MAX = (A & M) ODER (B- (B & M))
MAX wird um Stellen verschoben . $2^t L$
Endlich ORING MAX und MIN bekommen wir Z zurück.

Ich habe die Skizze gegeben, hoffe, Sie können die erforderlichen Angaben ergänzen.

singhsumit
quelle

Mir ist nicht klar, was Sie vorschlagen. Die Annahme ist, dass die ganzen Zahlen bereits klein sind und k von ihnen bereits in ein einzelnes Wort gepackt sind. Schlagen Sie vor, ihre Größe weiter zu reduzieren? Wenn ja, was machst du dann? Ich weiß auch, wie man eine bitonische Sequenz sortiert, die in O (log k) -Zeit in ein einzelnes Wort gepackt ist, oder wie man eine allgemeine (nicht bitonische) Sequenz in O (log ^ 2 k) -Zeit sortiert. Wenn Sie einen Algorithmus kennen, der eine allgemeine Sequenz in O (log k) -Zeit sortiert, können Sie ihn bitte genauer beschreiben? (Ein solcher Algorithmus würde natürlich das Auswahlproblem lösen.)

Ari

Ich reduziere die Größe nicht weiter. Ich schlug vor, die Größe zu reduzieren, die in Ihrer Antwort nicht benötigt wurde. Entschuldigung für die Verwirrung.

singhsumit

Sofern ich es nicht falsch verstanden habe, sieht dies wie der Algorithmus zum Sortieren von bitonischen Sequenzen aus. Es werden keine allgemeinen Sequenzen sortiert. Sortiert es zum Beispiel die Sequenz 3,0,2,0, wobei sich die 3 ganz links im (höchstwertigen) Feld befindet?

Ari

3 0 2 0 wird getrennt n wir bekommen A = 3 2 und B = 0 0, dann wird MAX 3 2 und MIN ist 0 0. Dann haben wir neues Z als 3 2 0 0. Jede allgemeine Folge hat eine bitonische Folge der Größe 2. Mit jeder Iteration verdoppeln sich diese Größen und schließlich haben wir in log k Zeit unsere Antwort.

singhsumit

Nein. Die Zahlen werden nicht komprimiert, sondern nur nach unten verschoben. In der ersten Iteration teilen wir Zahlenpaare, die sich im oberen Bit ihrer Position unterscheiden, so dass wir A = 0 3 0 2 und B = 0 0 0 0 erhalten, also MIN = 0 0 0 0, MAX = 0 3 0 2 und Z = 3 0 2 0. In der zweiten Iteration teilen wir Paare, die sich im unteren Bit ihrer Position unterscheiden, so dass wir wieder A = 0 3 0 2, B = 0 0 0 0 und Z unverändert bleiben.

Ari