Tiga hari yang lalu, saya berpikir tentang menggabungkan penghitungan dan penyortiran pohon. Setelah mendiskusikannya dengan seorang kolega, kami sampai pada keputusan berikut: gunakan HashMap alih-alih TreeSet (apa yang harus dilakukan TreeSet dengannya, Anda bisa lihat di bawah). Tetapi bahkan ini tampak sedikit bagi saya, jadi saya memutuskan untuk mengimplementasikan tabel hash saya sendiri dan melihat apa yang terjadi. Hasilnya tampak cukup menarik bagi saya.
Ketiga jenis penyortiran ini bagus untuk kasus-kasus ketika kekuatan banyak elemen unik dalam array relatif kecil (apa yang dimaksud dengan ini akan menjadi jelas setelah kita melihat hasil tes).
Sortir Penghitungan Pohon
Kami membangun pohon Steam (Kunci, Kuantitas), di mana Kunci bertanggung jawab atas elemen array, dan Kuantitas adalah jumlah pengulangan elemen array ini. Pohon itu seimbang secara alami, hitam dan merah, misalnya.
Selanjutnya, semuanya logis. Kami menambahkan semua elemen array ke Pair, dan mencari Pair di pohon (untuk menghindari penciptaan kembali objek, kami menggunakan Pair yang dibuat sebelumnya, dari mana kami mengubah Key. Di sini kami tidak tertarik pada Number, karena kami mencari kecocokan hanya dengan Key). Jika Kunci tersebut sudah ada, tambah Kuantitas, jika tidak tambahkan Pasangan baru (Kunci, 1).
Kami menulis ulang array, menghapus titik setiap kali dan menuliskan Kunci sebanyak Nomornya.
Agar tidak mengimplementasikan pohon itu sendiri, untuk algoritma yang dijelaskan saya menggunakan TreeSet, yang bekerja pada pohon hitam-merah.
Menggunakan HashMap
Kami akan menyimpan elemen array sebagai kunci, dan jumlah pengulangan sebagai nilai kunci.
Menggunakan tabel hash saya sendiri
Saya memutuskan untuk menggunakan metode pengalamatan terbuka. Dalam tabel hash, kami menyimpan objek dari kelas Pair, di mana pertama adalah kuncinya, kedua adalah jumlah pengulangan. Secara alami, sebuah konstruktor ditambahkan yang mengambil ukuran awal tabel dan load factor. Fungsi hash adalah yang paling sederhana: kita mengambil modulo kunci, dalam kasus akses berulang, tambahkan satu (unit bekerja dengan baik di mana array kunci adalah yang paling teratur, dan pada akhirnya kita harus mengurutkan semua kunci dengan pengurutan cepat standar, karena dalam tabel mereka dapat berubah menjadi tidak berurutan. ) Jadi kita dapat mengatakan bahwa ini adalah kombinasi hashing dan jenis lainnya.
Tabrakan
Jelas, tabrakan dapat terjadi dan ini akan berdampak buruk pada waktu menentukan hash dan kecepatan menyortir array hash yang dihasilkan (data yang dipesan atau hampir dipesan diurutkan lebih cepat). Tapi ada satu hal: hash kita berubah saat tabel mengembang. Jadi untuk memilih data seperti itu secara khusus menjadi jauh lebih sulit. Selain itu, dimungkinkan untuk membuat load factor dan koefisien ekspansi secara acak (dalam kisaran tertentu, tentu saja), yang akan membuat tidak mungkin untuk memilih nilai yang mengarah pada awal tabrakan. Nah, jika dalam satu tabel beberapa data menyebabkan collision, maka setelah hash, jumlah collision dapat dikurangi secara signifikan (beberapa kali). Titik lemah akan menjadi faktorial angka, tetapi mereka sangat kecil (hingga 2 ^ 31, misalnya, hanya ada 11 dari mereka (tidak termasuk 0)).
Hash kriptografi tidak cocok untuk kami, dan karena dengan itu Anda dapat melupakan susunan hash yang hampir dipesan (dalam arti memesan dengan kunci).
Waktu kerja
Jenis penghitungan pohon: dalam kasus terburuk, untuk O (n log n), paling-paling, untuk waktu linier.
Penyortiran tabel hash: waktu hashing + kompleksitas pengurutan array hash (dapat bervariasi tergantung pada algoritma dan implementasi yang dipilih, jadi saya tidak akan menunjukkan apa pun di sini). Memperkirakan kerumitan sulit karena penggunaan fungsi hash dan berbagai kemungkinan pendekatan untuk menyortir hash. Pertanyaan ini membutuhkan penelitian tambahan, tetapi jelas bahwa dalam kasus terburuk (ketika data input akan secara sengaja dicocokkan dengan fungsi hash tertentu pada tahap eksekusi tertentu), waktu operasi akan menjadi O (n ^ 2).
Bagaimana dengan ingatan?
Penyortiran hitungan pohon akan membutuhkan memori tambahan O (berbeda (n))
Untuk tabel hash, kita membutuhkan memori O (berbeda (n)) + memori untuk mengurutkan hash (tergantung pada algoritma yang dipilih).
Berikut adalah hasil dalam milidetik yang saya dapatkan pada angka acak ketika mengurutkan array objek menjadi 10 juta elts, dengan kisaran nilai [0; x]:
Pada tes, load factor dalam tabel hash saya = 0,75, kapasitas awal = 20, tabel dua kali lipat setiap kali
Untuk x = 10:
2044 - terintegrasi
285 - penghitungan pohon (sort Usatov)
276 - HashMap (Uringan Usatov-Prokurat)
140 - dengan tabel hash saya (Urutkan Usatov-Prokurat menggunakan MyHashTable)
x = 100:
2406 - built-in
455 - menghitung pohon
283 - HashMap
134 - tabel hash
x = 1_000:
2171 - terintegrasi
930 - menghitung pohon
380 - HashMap
209 - tabel hash
x = 10_000
2879 - terintegrasi
1666 - menghitung pohon
634 - HashMap
326 - tabel hash
x = 100_000
4045 - terintegrasi
2899 - menghitung pohon
866 - HashMap
762 - tabel hash
x = 1_000_000
4997 - terintegrasi
5762 - menghitung pohon
2505 - HashMap
1294 - tabel hash
x = 10_299_000
5083 - terintegrasi
11480 - menghitung pohon
5099 - HashMap
3240 - tabel hash
Seperti yang saya katakan di awal, sortasi ini paling cocok untuk kasus-kasus ketika kekuatan banyak elemen array cukup kecil relatif terhadap ukuran array.
Perlu juga dicatat bahwa pemilahan bawaan berfungsi lebih cepat pada data yang dipesan (hampir dipesan) (atau array dalam urutan terbalik), tetapi metode saya melakukannya lebih cepat pada angka acak.
Sortir Jumlah Pohon:
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)
Sortir melalui 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; }
Sortir tabel hash saya:
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; }
Implementasi tabel hash:
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++; } } }
Kelas uap:
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; } }