Vor drei Tagen habe ich darüber nachgedacht, Zählen und Baumsortieren zu kombinieren. Nachdem wir es mit einem Kollegen besprochen hatten, kamen wir zu der folgenden Entscheidung: Verwenden Sie HashMap anstelle von TreeSet (was TreeSet damit zu tun hat, sehen Sie unten). Aber selbst das schien mir ein wenig zu sein, also beschloss ich, meine eigene Hash-Tabelle zu implementieren und zu sehen, was daraus wurde. Die Ergebnisse schienen mir ziemlich interessant zu sein.
Alle drei Sortierarten eignen sich hervorragend für Fälle, in denen die Leistung vieler eindeutiger Elemente im Array relativ gering ist (was damit gemeint ist, wird klar, wenn wir uns die Testergebnisse ansehen).
Baumanzahl sortieren
Wir erstellen den Steam-Baum (Schlüssel, Menge), in dem der Schlüssel für das Array-Element verantwortlich ist und die Menge die Anzahl der Wiederholungen dieses Array-Elements ist. Der Baum ist natürlich ausbalanciert, zum Beispiel schwarz und rot.
Außerdem ist alles logisch. Wir fügen alle Elemente des Arrays zum Paar hinzu und suchen im Baum nach dem Paar (um zu vermeiden, dass die Objekte neu erstellt werden, verwenden wir das zuvor erstellte Paar, von dem aus wir den Schlüssel ändern. Hier interessiert uns die Zahl nicht, da wir nur nach einer Übereinstimmung mit dem Schlüssel suchen). Wenn ein solcher Schlüssel bereits vorhanden ist, erhöhen Sie die Menge, andernfalls fügen Sie ein neues Paar hinzu (Schlüssel, 1).
Wir schreiben das Array neu, löschen den Scheitelpunkt jedes Mal und schreiben den Schlüssel so oft wie seine Nummer auf.
Um den Baum selbst nicht zu implementieren, habe ich für den beschriebenen Algorithmus TreeSet verwendet, das auf einem schwarz-roten Baum arbeitet.
Verwenden von HashMap
Wir speichern das Array-Element als Schlüssel und die Anzahl der Wiederholungen als Schlüsselwert.
Verwenden meiner eigenen Hash-Tabelle
Ich entschied mich für die Methode der offenen Adressierung. In der Hash-Tabelle speichern wir Objekte der Pair-Klasse, wobei erstens der Schlüssel und zweitens die Anzahl der Wiederholungen ist. Natürlich wurde ein Konstruktor hinzugefügt, der die anfängliche Größe der Tabelle und den Lastfaktor übernimmt. Die Hash-Funktion ist die einfachste: Wir nehmen das Schlüsselmodulo, fügen bei wiederholtem Zugriff eines hinzu (die Einheit funktioniert gut, da das Schlüsselarray am geordnetsten ist, und am Ende müssen wir alle Schlüssel mit der Standard-Schnellsortierung sortieren, da sie sich in der Tabelle als ungeordnet herausstellen können ) Wir können also sagen, dass dies eine Kombination aus Hashing und einer anderen Art ist.
Kollisionen
Offensichtlich können Kollisionen auftreten, die sich sowohl auf den Zeitpunkt der Ermittlung des Hashs als auch auf die Geschwindigkeit des Sortierens des resultierenden Hashes-Arrays stark auswirken (geordnete oder fast geordnete Daten werden schneller sortiert). Aber hier ist die Sache: Unser Hash ff ändert sich, wenn die Tabelle erweitert wird. Die spezifische Auswahl solcher Daten wird daher viel schwieriger. Darüber hinaus ist es möglich, den Lastfaktor und den Ausdehnungskoeffizienten zufällig zu machen (natürlich in einem bestimmten Bereich), wodurch es unmöglich wird, Werte vorzuwählen, die zu Kollisionen führen. Wenn in einer Tabelle einige Daten zu Kollisionen führten, kann die Anzahl der Kollisionen nach einem erneuten Hash erheblich reduziert werden (mehrmals). Der Schwachpunkt sind Fakultäten von Zahlen, aber sie sind unglaublich klein (bis zu 2 ^ 31 gibt es zum Beispiel nur 11 von ihnen (außer 0)).
Kryptografische Hashs sind für uns nicht geeignet, und weil Sie mit ihnen eine fast geordnete Reihe von Hashes vergessen können (im Sinne einer Bestellung nach Schlüsseln).
Arbeitszeit
Baumzählsortierung: im schlimmsten Fall für O (n log n) bestenfalls für die lineare Zeit.
Hash-Tabellensortierung: Hashing-Zeit + Komplexität beim Sortieren des Hash-Arrays (kann je nach gewähltem Algorithmus und Implementierung variieren, daher werde ich hier nichts angeben). Das Schätzen der Komplexität ist aufgrund der Verwendung einer Hash-Funktion und verschiedener möglicher Ansätze zum Sortieren von Hashes schwierig. Diese Frage erfordert zusätzliche Forschung, aber es ist offensichtlich, dass im schlimmsten Fall (wenn die Eingabedaten in einer bestimmten Ausführungsphase absichtlich an eine bestimmte Hash-Funktion angepasst werden) die Betriebszeit O (n ^ 2) beträgt.
Was aus dem Gedächtnis?
Für die Sortierung der Baumzahl ist O (eindeutiger (n)) zusätzlicher Speicher erforderlich
Für eine Hash-Tabelle benötigen wir O (eindeutiger (n)) Speicher + Speicher, um die Hashes zu sortieren (abhängig vom ausgewählten Algorithmus).
Hier sind die Ergebnisse in Millisekunden, die ich beim Sortieren eines Arrays von Objekten in 10 Millionen Elts mit einem Wertebereich [0; x]:
Bei Tests, Lastfaktor in meiner Hash-Tabelle = 0,75, Anfangskapazität = 20, wird die Tabelle jedes Mal verdoppelt
Für x = 10:
2044 - integriert
285 - Baumzahl (Usatov-Sorte)
276 - HashMap (Usatov-Prokurat-Sortierung)
140 - mit meiner Hash-Tabelle (Usatov-Prokurat-Sortierung mit MyHashTable)
x = 100:
2406 - eingebaut
455 - Baum zählen
283 - HashMap
134 - Hash-Tabelle
x = 1_000:
2171 - integriert
930 - Baum zählen
380 - HashMap
209 - Hash-Tabelle
x = 10_000
2879 - integriert
1666 - Baum zählen
634 - HashMap
326 - Hash-Tabelle
x = 100_000
4045 - integriert
2899 - Baum zählen
866 - HashMap
762 - Hash-Tabelle
x = 1_000_000
4997 - integriert
5762 - Baum zählen
2505- HashMap
1294 - Hash-Tabelle
x = 10_000_000
5083 - integriert
11480 - Baum zählen
5099 - HashMap
3240 - Hash-Tabelle
Wie eingangs erwähnt, eignen sich diese Sortierungen am besten für Fälle, in denen die Leistung vieler Elemente des Arrays im Verhältnis zur Größe des Arrays ausreichend gering ist.
Es ist auch erwähnenswert, dass die integrierte Sortierung bei geordneten (fast geordneten) Daten (oder einem Array in umgekehrter Reihenfolge) viel schneller funktioniert, bei meiner Methode jedoch bei Zufallszahlen.
Baumzahl Sortieren:
static void usatovSort(Integer[] arr) { TreeSet<MyPair> tree = new TreeSet<>(); MyPair temp; MyPair mp = new MyPair(); for (int i : arr) { temp = mp; temp.first = i; temp = tree.ceiling(temp); if (temp != null && temp.first == i)
Sortieren durch HashMap:
static void usatovProkuratSortUsingHashMap(Integer[] arr) { HashMap<Integer, Integer> hm = new HashMap<>(); Integer temp; for (Integer i : arr) { temp = hm.get(i); if (temp == null) hm.put(i, 1); else hm.put(i, temp + 1); } ArrayList<Integer> keys = new ArrayList<>(hm.keySet().size()); keys.addAll(hm.keySet()); keys.sort(Comparator.naturalOrder()); int ptr = 0; for (Integer i : keys) for (int j = 0; j < hm.get(i); j++) arr[ptr++] = i; }
Sortieren Sie meine Hash-Tabelle:
static void usatovProkuratSortUsingMyHashTable(Integer[] arr) { MyHashTable mht = new MyHashTable(); for (Integer i : arr) mht.add(i); MyPair[] res = mht.getPairs(); int ptr = 0; Arrays.sort(res, Comparator.comparingInt(o -> o.first)); for (MyPair mp : res) for (int i = 0; i < mp.second; i++) arr[ptr++] = mp.first; }
Implementierung der Hash-Tabelle:
public class MyHashTable { private MyPair[] hashArr; private double count = 0; private double loadFactor = 0.5; private double expansivity = 2; private static final int DEFAULT_CAPACITY = 20; public MyHashTable() { hashArr = new MyPair[DEFAULT_CAPACITY]; } public MyHashTable(double loadFactor) { hashArr = new MyPair[DEFAULT_CAPACITY]; this.loadFactor = loadFactor; } public MyHashTable(int capacity) { hashArr = new MyPair[capacity]; } public MyHashTable(int capacity, double loadFactor) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; } public MyHashTable(int capacity, double loadFactor, double expansivity) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; this.expansivity = expansivity; } public MyPair[] getPairs() { MyPair[] pairs = new MyPair[(int) count]; int ptr = 0; for (MyPair i : hashArr) if (i != null) pairs[ptr++] = i; return pairs; } public MyPair get(int key) { int add = 0; while (true) if (hashArr[(key + add) % hashArr.length].first == key) { return hashArr[(key + add) % hashArr.length]; } else if (add++ == hashArr.length) return null; } public void add(int key) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(key + add) % hashArr.length] == null) { hashArr[(key + add) % hashArr.length] = new MyPair(key, 1); count++; return; } if (hashArr[(key + add) % hashArr.length].first == key) { hashArr[(key + add) % hashArr.length].second++; return; } add++; } } public void add(MyPair newMP) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(newMP.first + add) % hashArr.length] == null) { hashArr[(newMP.first + add) % hashArr.length] = newMP; count++; return; } if (hashArr[(newMP.first + add) % hashArr.length].first == newMP.first) { hashArr[(newMP.first + add) % hashArr.length].second += newMP.second; return; } add++; } } private void grow() { MyPair[] oldHash = hashArr; hashArr = new MyPair[(int) (expansivity * hashArr.length)]; for (MyPair i : oldHash) if (i != null) innerAdd(i); } private void innerAdd(MyPair mp) { int add = 0; while (true) { if (hashArr[(mp.first + add) % hashArr.length] == null) { hashArr[(mp.first + add) % hashArr.length] = mp; return; } if (hashArr[(mp.first + add) % hashArr.length].first == mp.first) { hashArr[(mp.first + add) % hashArr.length].second += mp.second; return; } add++; } } }
Dampfklasse:
public class MyPair implements Comparable<MyPair> { public int first; public int second; public MyPair() { } public MyPair(int first, int second) { this.first = first; this.second = second; } @Override public int compareTo(MyPair o) { return first - o.first; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MyPair myPair = (MyPair) o; return first == myPair.first; } @Override public int hashCode() { return first; } }