Streben nach praktischer Radix-Sortierung

Als schneller Sortieralgorithmus [Count Sort](https://qiita.com/drken/items/44c60118ab3703f7727f#8-%E8%A8%88%E6%95%B0%E3%82%BD%E3%83%BC % E3% 83% 88-% E3% 83% 90% E3% 82% B1% E3% 83% 83% E3% 83% 88% E3% 81% AF% E9% 87% 8D% E8% A6% 81% Ich denke, viele Leute wissen, dass E3% 81% AA% E3% 83% 87% E3% 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0). Bei der Zählsortierung wird der Inhalt eines Arrays überprüft, der Wert des Inhalts in ein Indexarray (Bucket) gezählt und anschließend der Inhalt dieses Buckets in das Array zurückgeschrieben. Wenn die Größe $ n $ ist, kann die Sortierung mit dem Berechnungsbetrag von $ O (n) $ abgeschlossen werden. Die durchschnittliche Berechnungsmenge für die Schnellsortierung mit dem Namen "Schnell" beträgt $ O (n \ log {n}) $. Es handelt sich also um eine schnellere Sortierung. Es gibt jedoch einen Engpass: Wenn der im Array angezeigte Wert groß ist, benötigen Sie einen Bucket für diesen Maximalwert. Wenn der Maximalwert im Array 100.000 beträgt, beträgt die Größe des Buckets ebenfalls 100.000.

Um das Problem der Größe des Buckets zum Zählen der Sortierung und der mangelnden Vielseitigkeit zu lösen, die Größe des zu erstellenden Buckets abhängig vom Maximalwert ändern zu müssen, Basissortierung / drken / items / 44c60118ab3703f7727f # 8-3-% E5% 9F% BA% E6% 95% B0% E3% 82% BD% E3% 83% BC% E3% 83% 88-Radix-Sortierung) Ist gewesen Bei der Radix-Sortierung achten wir darauf, dass der Wert aus mehreren "Ziffern" besteht, und wiederholen die Zählsortierung für jede Ziffer. Zu diesem Zeitpunkt besteht der Trick darin, nach der untersten Ziffer zu sortieren. Die Anzahl der Buckets ist in Ordnung, solange sie in den Ziffern angezeigt wird.

Das häufig verwendete int ist 32 Bit. Wenn Sie es also in 8 Bit aufteilen, können Sie sich int als 4-stellige 256-stellige Zahl vorstellen. Aus diesem Grund sind es beim Programmieren der Radix-Sortierung häufig 8 Bits gleichzeitig. Da der Rechenaufwand für die Radix-Sortierung $ O (n * Anzahl der Ziffern) $ beträgt, scheint die 8-Bit-Zählsortierung schneller zu sein als die schnelle Sortierung, wenn die Arraygröße 16 oder mehr beträgt ($ log {16} = 4). Weil es $ ist). Als ich jedoch tatsächlich ein Programm schrieb und es ausprobierte, war es logisch, dass bei einer kleinen Array-Größe (ca. 100) die Radix-Sortierung schneller war als die Bibliothekssortierung, bei einer großen Array-Größe jedoch die Radix-Sortierung verloren ging. Gibt das gegenteilige Ergebnis. Ich stelle mir vor, dass die in der Bibliothek bereitgestellte Sortierung zu solchen Ergebnissen führt, da sie so konzipiert ist, dass sie selbst dann schnell endet, wenn die Sortierung tatsächlich gestartet wird, selbst wenn die Vorverarbeitung einige Zeit in Anspruch nimmt. Sobald der Mindestwert usw. festgelegt ist, wird meiner Meinung nach nicht mehr auf das Array zugegriffen. Im Vergleich dazu überprüft die 8-Bit-Version der Radix-Sortierung das Ganze immer viermal. Angenommen, der maximale Wert, der ausgegeben wird, beträgt 255 oder weniger, selbst wenn Sie die Prüfung auf einmal abschließen, verlieren Sie, wenn die Arraygröße 300 oder mehr beträgt. Wenn Sie wissen, dass der Maximalwert an erster Stelle klein ist, können Sie die Zählsortierung verwenden, sodass die Auswahl der Radix-Sortierung keinen Sinn macht. Das Sortierprogramm in der Bibliothek ist immer noch gut ausgearbeitet, daher scheint es schwierig zu sein, es zu übertreffen.

Ein weiteres Problem bei der Radix-Sortierung besteht darin, dass ein separater Speicher verwendet wird, der dieselbe Größe wie das ursprüngliche Array hat. Wenn Sie die Radix-Sortierung gehorsam codieren, verwenden Sie eine Einwegliste wie Vector oder ArrayList im Bucket. Da diese Einwegliste jedoch den gesamten Inhalt des ursprünglichen Arrays enthält. Es verbraucht Speicher. Darüber hinaus verbraucht die Methode, nur im Bucket zu zählen, die Ausgabeposition des Arrays aus der Zählung zu ermitteln und den Wert in ein anderes Array zu verschieben, ebenfalls Speicher. Die Verwendung der gleichen Menge an separatem Speicher wie das ursprüngliche Array ist etwas zögerlich, wenn die Arraygröße Hunderttausende beträgt. Verwenden Sie also zunächst keinen anderen Speicher (dies ist der In-Place-Algorithmus. % B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)) Betrachten wir einen Radix-Sortieralgorithmus.

Voraussetzungen

Das Programm verwendet Java.
Der Wert, der sortiert werden kann, ist ein positiver int (negative Zahlen nicht berücksichtigen). Die Anzahl der Ziffern kann eine beliebige Zahl sein, solange sie im Bereich von int liegt.
In aufsteigender Reihenfolge sortieren.

In-Place-Radix-Sortierkonzept

Wenn Sie keinen anderen Speicher verwenden, wird das ursprüngliche Array zerstört und als Sortierergebnis verwendet. Wenn Sie bei der Zählsortierung und Radix-Sortierung von Anfang an ein Array erhalten, wird dieser Array-Index nicht mehr verwendet. Löschen Sie ihn also. Fügen Sie stattdessen einen Wert zum Bucket hinzu. Auf diese Weise ändert sich die Gesamtspeichermenge nicht. Wenn die Prüfung beendet ist, schließen Sie einfach die Eimer an, und das ist das Sortierergebnis.

Um diese Idee zu verwirklichen, muss das ursprüngliche Array eine Einwegliste sein, z. B. ein Vektor oder eine ArrayList. Ich habe mir die API-Dokumentation für Vector und ArrayList angesehen, als ich versucht habe, ein Programm in Java zu schreiben, aber es scheint, dass es keine Funktion gibt, um einfach Einweg-Links zu verbinden (?) Also habe ich beschlossen, selbst einen One-Way-Link zu schreiben.

Datenstruktur

Definieren Sie zunächst die ursprüngliche Datenstruktur. Hier habe ich den Klassennamen TestGoods gewählt und versucht, den Produktnamen und den Preis als Felder zu verwenden. Die Sortierung erfolgt nach Preiswert. Fügen Sie das Feld als Nächstes für eine Einwegverknüpfung zu dieser ursprünglichen Datenstruktur hinzu.

`TestGoods.java`


/**Produktklasse(test) */
public class TestGoods {
	public int price;		///Preis
	public String name;	///Produktname
	public TestGoods next;	///Einweg-Link zu den nächsten TestGoods

	/**Konstrukteur*/
	public TestGoods(int price) {
		this.price = price;
		next = null;
	}
}

Da es zu Testzwecken dient, kann ohne Getter und Setter öffentlich darauf zugegriffen werden. Der Konstruktor ist auch nur für den Preis (dh Name ist nur eine Dekoration).

Array-Klasse (Einwegliste)

Erstellen Sie als Nächstes eine Array-Klasse TestGoodsArray für TestGoods. Die Methode erstellt nur das erforderliche Minimum, add (), clear () und connect (). Es gibt kein get () und Sie können direkt Start usw. berühren. (Es sind schlechte Manieren). Ich werde es diesmal nicht verwenden, aber ich habe auch ein Größenfeld erstellt.

`TestGoodsArray.java`


/**Sequenz von TestGoods*/
public class TestGoodsArray {
	public TestGoods start;	//Start des Einweg-Verbindungsobjekts
	public TestGoods last;	//Das letzte Objekt
	public int size;
	
	/**Konstrukteur*/
	public TestGoodsArray() {
		clear();
	}
	/**Leeren Sie den Inhalt*/
	public void clear() {
		start = null;
		last = null;
		size = 0;
	}
	/**Element hinzufügen*/
	public boolean add(TestGoods goods) {
		size++;
		if (start == null) {
			start = goods;
			last = goods;
			return true;
		}
		last.next = goods;	//Links verbinden
		last = goods;
		return true;		// (Vorerst Sammlung.Nach den allgemeinen Regeln von add)
	}
	/**Elemente verbinden*/
	public void connect(TestGoodsArray link) {
		if (link == null) { return; }
		if (start == null) {
			start = link.start;
			last = link.last;
			size = link.size;
			return;
		}
		size += link.size;
		last.next = link.start;
		last = link.last;
	}
}

Basissortierteil

Die Substanz der Sortierung ist einfach. Wie oben erläutert, ist das int durch 8 Bits getrennt, sodass die Größe des Buckets 256 beträgt. Ich habe bitRadixSort als Dateinamen verwendet, weil ich Bitbegrenzer als Ziffern verwendet habe, aber war das nicht umständlich? Der Rückgabewert der Sortierung ist die Ausführungszeit der Verarbeitung (Nanosekunden).

Anstatt immer alle vier Ziffern in einem Array zu überprüfen, habe ich bei der ersten Prüfung den Maximalwert überprüft und versucht, die Anzahl der Schleifen zu verringern, wenn die obere Ziffer nicht verwendet wurde. Auf diese Weise wird die Verarbeitungszeit für ein Array, das nur einen einstelligen Wert anzeigt, auf etwa 1/6 reduziert. Die Quelle des Teils, der den Maximalwert erst am Anfang findet, ist hässlich (ich habe zwei ähnliche Schleifen geschrieben, weil es bei der Beurteilung der Bedingung in der Schleife langsam zu sein schien), aber bitte verzeihen Sie mir vorerst.

`BitRadixSort.java`


/**
 *Basissortierung (behandeln Sie int als 4 Stellen alle 8 Bits)
 *Im Vergleich zur allgemeinen Radix-Sortierung nimmt es nicht viel Speicher in Anspruch.
 *Der Preis besteht darin, das ursprüngliche Array neu zu schreiben.
 * */
public class BitRadixSort {
	TestGoodsArray[] bucket = new TestGoodsArray[256];	///Ziffernschaufel

	/**Konstrukteur*/
	public BitRadixSort() {
		for (int i = 0; i < 256; i++) {
			bucket[i] = new TestGoodsArray();
		}
	}

	/**
	 * @param array Das Array, das Sie sortieren möchten. Das Array wird direkt neu geschrieben.
	 * @return Zeit für das Sortieren(nano seconds)
	 */
	public long sort(TestGoodsArray array) {
		long stTime = System.nanoTime();		//Zur Verarbeitung der Messung
		int bitShift = 0;
		TestGoods link;
		int maxVal = Integer.MIN_VALUE;
		int i;
		int cnt = 4;		//Maximale Anzahl von Prüfziffern= 4
		do {
			//Eimer löschen
			for (i = 0; i < 256; i++) {
				bucket[i].clear();
			}
			link = array.start;	//Vom Anfang des Arrays
			//Geben Sie einen Eimer für die Ziffer des Werts ein
			if (cnt == 4) {
				//Finden Sie den Maximalwert nur am Anfang der Schleife. Außerdem müssen Sie BitShift am Anfang der Schleife nicht ausführen.
				do {
					int a = link.price;
					if (a > maxVal) { maxVal = a; }
					TestGoods linkOld = link;
					bucket[a & 255].add(linkOld);	//In einen Trägereimer legen
					link = link.next;		//Zum nächsten Link
					linkOld.next = null;	//Schneiden Sie das Glied in den Eimer
				} while (link.next != null);
			} else {
				//Zweite und nachfolgende Schleifen
				do {
					int a = link.price;
					TestGoods linkOld = link;
					bucket[(a >> bitShift) & 255].add(linkOld);	//In einen Trägereimer legen
					link = link.next;		//Zum nächsten Link
					linkOld.next = null;	//Schneiden Sie das Glied in den Eimer
				} while (link.next != null);
			}
			//Verbinden Sie die Buckets, um ein Array zu erstellen
			array.clear();	//Leeren Sie das Array einmal
			for (i = 0; i < 256; i++) {
				if (bucket[i].start != null) {
					array.connect(bucket[i]);
				}
			}
			array.last.next = null; //Nur für den Fall

			bitShift += 8;	//Zu den nächsten 8 Bits

			if (cnt == 4) {		//Wenn es sich um die erste Schleife handelt, reduzieren Sie die Anzahl der Schleifen um den Maximalwert
				if ((maxVal & 0xff000000) == 0) {
					cnt--;
					if ((maxVal & 0xff0000) == 0) {
						cnt--;
						if ((maxVal & 0xff00) == 0) {
							cnt--;
						}
					}
				}
			}
		} while (--cnt > 0);

		return System.nanoTime() - stTime;		//Gibt die benötigte Zeit zurück
	}
}

Wie Sie dieser Quelle entnehmen können, wurde beim Sortieren nie neu verwendet. Es ist nur ein Linkbruch. Das scheint etwas früh zu sein.

Hauptklasse zur Betriebsüberprüfung

Die letzte ist die Hauptklasse für die Betriebsüberprüfung. Nach dem Sortieren testen wir, ob die Werte korrekt ausgerichtet sind (in aufsteigender Reihenfolge). Ich probiere auch Collections.sort für einen Zeitvergleich aus. Gemäß der API-Dokumentation (https://docs.oracle.com/javase/jp/8/docs/api/java/util/Collections.html#sort-java.util.List-) sind die Algorithmen für Collections.sort Wird geändert [Sortierung zusammenführen](https://qiita.com/drken/items/44c60118ab3703f7727f#5-%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3% 83% BC% E3% 83% 88-on-log-n). Die zu sortierenden Werte werden zufällig generiert, aber die gleichen zufälligen Werte werden in der Radix-Sortierung und in Collections.sort verwendet, um die Überlegenheit oder Unterlegenheit der Werte zu verhindern.

`BitRadixTest.java`


import java.util.*;

public class BitRadixTest {
	static final int N = 10000;		///Arraygröße
	static final int VARMAX = 0x01000000;	///Maximal möglicher Wert des Inhalts des Arrays

	/** main */
	public static void main(String[] args) {
		int i;
		TestGoodsArray array_Radix = new TestGoodsArray();	//Ordnen Sie ein Array für die BitRadix-Sortierung zu
		ArrayList<TestGoods> array_Csort = new ArrayList<TestGoods>(N);	// Collections.Ordnen Sie ein Array zum Sortieren zu
		Random rnd = new Random();

		//Testdaten erstellen(Füllen Sie mit zufälligen Werten größer oder gleich 0 und kleiner als VARMAX)
		for (i = 0; i < N; i++) {
			int val = rnd.nextInt(VARMAX);
			array_Radix.add(new TestGoods(val));	//Stellen Sie den gleichen Wert in zwei Testarrays ein
			array_Csort.add(new TestGoods(val));
		}
		
		// BitRadix sort
		BitRadixSort radix = new BitRadixSort();
		long time_bitRadix = radix.sort(array_Radix);

		// Csort
		long stTime = System.nanoTime();
		Collections.sort(array_Csort, new Comparator<TestGoods>() {
			public int compare(TestGoods obj1, TestGoods obj2) {
				return obj1.price - obj2.price;
			}
		});
		long time_Csort = System.nanoTime() - stTime;
		
		//Datenvalidierung
		int lastVal = Integer.MIN_VALUE;
		TestGoods link = array_Radix.start;
		do {
			int val = link.price;
			if (val < lastVal) {
				System.out.println("\nError !! (last=" + lastVal + ", val=" + val);
			}
			//System.out.print(val + ", ");	//Kommentieren Sie aus, wenn Sie den Inhalt des Arrays anzeigen möchten
			lastVal = val;
			link = link.next;
		} while (link != null);
		//System.out.println("");	//Kommentieren Sie aus, wenn Sie den Inhalt des Arrays anzeigen möchten
		System.out.println("Radix time  = " + time_bitRadix + " ns");
		System.out.println("Arrays time = " + time_Csort + " ns");
	}
}

Ausführungsergebnis

Wenn man die Ausführungszeit mit Collections.sort vergleicht, wenn der Maximalwert 0x10000000 ist (dh 4 Stellen in 8-Bit-Radix), ist dies in meiner Umgebung wie folgt (aufgrund der Zufälligkeit des Werts). Die Ausführungszeit ändert sich jedes Mal, daher ist dies nur ein Beispiel.

Arraygröße	Basissortierung	Collections.sort
100	171262	948590
1000	567246	3036774
10000	4531319	17188987
100000	30454387	75877154

Was! Die Ergebnisse zeigen, dass die Radix-Sortierung in allen Fällen schneller ist, unabhängig von der Array-Größe. Wenn Sie den Maximalwert auf 200 festlegen (dh eine Ziffer im 8-Bit-Radix), beträgt die Arraygröße 1/2 für 100 und 1/6 für 100000. Mit anderen Worten, es scheint, dass dieser Algorithmus in Bezug auf positive Ganzzahlen schneller sortieren kann als die Java-Bibliothek. Während die Zeitmessung von Collections.sort die Generierung von Klassen für die Vergleichsberechnung umfasst, gibt es einen Unterschied, dass die Bucket-Generierung der Radix-Sortierung außerhalb der Messzeit liegt. Wenn die Array-Größe jedoch 100.000 beträgt, kann dies ein Fehler sein. Ich denke. Es war verrückt, der Datenstruktur eine Einwegliste hinzuzufügen.

Hausaufgaben

Hausaufgabe Nr. 1: Umgang mit negativen Zahlen

Bei diesem BitRadixSort wird davon ausgegangen, dass alle zu sortierenden Werte positive Ganzzahlen sind. Um die Kompatibilität mit negativen Zahlen zu gewährleisten, verbinden Sie beim Verbinden von Links am Ende der 4. Ziffernsortierung zuerst die Buckets 128 bis 255 und dann 0 bis 127. ist. Dies liegt daran, dass die int-Darstellung ein Komplement von 2 ist und das höchstwertige Bit ein negatives Symbol ist.

Hausaufgabe 2: Verallgemeinerung der TestGoodsArray-Klasse

Die TestGoodsArray-Klasse hat nicht einmal get (), daher ist es besser, sie zu implementieren. Sie müssen die Links durchgehen, um das i-te Element zu erhalten. Es ist auch notwendig, den Fehler zu behandeln, wenn kein i-th vorhanden ist. Es wäre auch unpraktisch, wenn es keinen Iterator zum sequentiellen Abrufen von Objekten aus dem Array gäbe. (Vielleicht gibt Ihnen die Verwendung von ArryList.addAll () zum Verbinden der Links eine gewisse Geschwindigkeit, die nicht überprüft wurde.)

Hausaufgabe Nr. 3: Umgang mit gemeinsamen Gegenständen

Dieses Mal habe ich das Feld der Einwegverknüpfung direkt in TestGoods eingefügt, möchte dies aber auch mit allgemeinen Objekten sortieren können. Ich finde es jedoch ziemlich schwierig, nach Integer [] -Array zu sortieren. Anstatt nur den Einweg-Link herauszuziehen, müssen Sie den Argumenten des Sortierprogramms die Felder geben, nach denen sortiert werden soll.

Übrigens ist es neben der Sortierung in aufsteigender Reihenfolge nur erforderlich, die Art und Weise umzukehren, in der die Eimer verbunden sind, um eine große Reihenfolge zu unterstützen. Es bleibt jedoch nichts anderes übrig, als die umgekehrte Reihenfolge mit dem Argument sort () anzugeben.

An diesem Punkt denke ich, dass viele Leute es als Bibliothek verwenden können, die Ints in kurzer Zeit sortieren kann. Wie Sie der obigen Quelle entnehmen können, bin ich als Programmierer noch nicht ausgereift. Daher möchte ich eine hervorragende Person einschließlich anderer Anpassungen fragen.

Hausaufgabe Nr. 4: Umgang mit Dezimalstellen

Das Gleitkommazahlenformat mit einfacher Genauigkeit in Java hat eine Größe von 32 Bit. Dieses Format ist [IEEE 754](https://ja.wikipedia.org/wiki/%E5%8D%98%E7%B2%BE%E5%BA%A6%E6%B5%AE%E5%8B%95 % E5% B0% 8F% E6% 95% B0% E7% 82% B9% E6% 95% B0 # IEEE_754_% E3% 81% A7% E3% 81% AE% E5% 8D% 98% E7% B2% BE % E5% BA% A6% E6% B5% AE% E5% 8B% 95% E5% B0% 8F% E6% 95% B0% E7% 82% B9% E6% 95% B0% E3% 81% AE% E5 Es wird durch% BD% A2% E5% BC% 8F: _binary32) angegeben und besteht aus 1 Bit Code, 8 Bit Exponententeil und 23 Bit falschem Teil.

Da der Exponententeil höher als der falsche Teil ist, sollte sogar float nach genau demselben Algorithmus wie die Radix-Sortierung sortiert werden können, wenn er mit einer Methode als 4 Byte erhalten werden kann. In diesem Fall kann erwartet werden, dass die Verarbeitungsgeschwindigkeit relativ schnell ist. Gleitkommazahlen mit doppelter Genauigkeit haben 64 Bit, daher stelle ich mir vor, dass die Radix-Sortierung langsam sein wird.

[JAVA] Streben nach praktischer Radix-Sortierung