* Yang saya maksud adalah eksekusi operasi yang relatif cepat pada satu elemen array.Struktur data yang mengimplementasikan daftar sudah lengkap. Setiap orang memiliki kelebihan dan kekurangan mereka sendiri. Misalnya, di dunia Java - tergantung pada operasi yang diperlukan - Anda dapat menggunakan:- add (obj), get (obj), set (index, obj): kumpulan dasar dari hampir semua daftar, mis. ArrayList.
- add (index, obj): struktur mirip pohon, mis. TreeList dari koleksi umum apache.
- hapus (indeks): sama seperti di atas.
- berisi (obj), indexOf (obj): Anda dapat menggunakan banyak ArrayList dan HashMap.
- hapus (keberatan): ... Saya merasa sulit untuk menjawab. Dalam beberapa kasus, Anda dapat bertahan dengan LinkedHashSet. Ini diselesaikan dengan sepele di hadapan dua poin sebelumnya, tetapi struktur mana yang bisa keduanya dengan cepat?
Ketika saya membutuhkan struktur dengan quick add (obj), get (index), hapus (index) dan indexOf (obj), google tidak memberikan jawaban. Saya tidak menemukan contoh kode atau deskripsi dari struktur tersebut. Mungkin saya tidak melihat di sana, saya harus menciptakannya sendiri. Tetapi jika seseorang menjatuhkan tautan di komentar, saya akan sangat menghargainya.Mungkin seseorang menyadari bahwa Anda dapat mengambil TreeList, yang dapat dengan cepat menyisipkan / menghapus item di tengah daftar dan menambahkan HashMap dari objek ke indeks di TreeList untuk eksekusi cepat indexOf (obj). Dan itu akan menjadi keputusan yang sederhana, elegan, tetapi salah. Lagi pula, ketika menambahkan ke tengah atau menghapus dari tengah, akan perlu untuk menghitung ulang indeks, rata-rata, untuk setengah elemen. Ini akan menurunkan kinerja ke O (n).Selanjutnya saya akan berbicara tentang struktur data yang dapat melakukan semua hal di atas. Yang melakukan operasi apa pun pada satu elemen dalam waktu O (log (n)). Yah, hampir - untuk logaritma dilakukan dalam kasus ketika semua objek dalam daftar berbeda. Jika daftar berisi objek yang sama, maka dimungkinkan untuk melorot kinerja hingga O (log (n) ^ 2).Saya akan segera memperingatkan Anda bahwa saya tidak akan mengecat kode di sini. Ini bisa sangat rumit untuk artikel ini. Tapi itu, ditulis dalam bahasa Jawa. Berdasarkan kelas TreeList dari apache common-collections. Permintaan tarik sudah ada, tetapi pada saat penulisan, artikel belum dituangkan.Juga, saya tidak akan menjelaskan algoritma yang terkenal. Misalnya, algoritma balancing pohon. Bagi sebagian besar, mungkin cukup untuk menerima begitu saja fakta bahwa pohon itu dapat tetap seimbang. Ini tidak memengaruhi pemahaman akan gagasan umum. Mereka yang ingin tahu lebih banyak dapat dengan mudah menemukan informasi. Tetapi saya akan memberi tahu Anda secara singkat tentang beberapa hal mendasar, karena tanpa sepengetahuan dasar-dasarnya, banyak elemen kunci tidak dapat dipahami.Tautan akan ada di akhir.Mengapa itu perlu?
Faktanya, tidaklah mudah untuk menemukan situasi di mana semuanya dibutuhkan langsung dari daftar. Tidak mungkin bahwa ini adalah semacam struktur yang sangat diperlukan, jika tidak semua orang akan mengetahuinya. Namun, beberapa contoh di mana daftar semacam itu dapat bermanfaat dapat diberikan.Saya menyadari bahwa banyak contoh yang dibuat-buat. Semua atau hampir semuanya bisa diselesaikan dengan cara lain.Caching dan kompresi
Tugas awal saya, karena itu saya mulai meneliti masalah ini. Dimainkan dengan kompresi data tertentu dan memerlukan daftar untuk cache objek.Idenya adalah ini: ketika memproses objek lain, kita mencarinya dalam daftar. Jika tidak ditemukan, simpan objek dan tambahkan ke bagian atas daftar. Jika ditemukan, maka kita ambil indeksnya dalam daftar dan alih-alih objek kita hanya menyimpan indeksnya, setelah itu kita memindahkan objek ke bagian atas daftar. Dengan demikian, objek yang terjadi akan sering menerima indeks kecil, dan objek yang muncul hanya sekali akhirnya akan pindah ke akhir daftar dan dihapus.Belok
Jika alih-alih antrian FIFO biasa, untuk beberapa tugas, struktur serupa digunakan, maka operasi berikut dapat dilakukan:- Jawab pertanyaan: berapa banyak tugas dalam antrian sebelum tugas ini.
- Hapus tugas dari antrian.
Seperti di supermarket. Jika Anda datang untuk cokelat, tetapi Anda melihat bahwa garis bergerak lambat, maka mungkin cokelat tidak terlalu dibutuhkan? :)Tabel skor tinggi
Misalkan kita ingin menyimpan waktu di mana pemain menyelesaikan level dalam permainan. Ada banyak pemain dan mereka semua berlomba, berusaha menunjukkan waktu minimum. Data pemain dapat dimasukkan ke dalam array dan diurutkan berdasarkan waktu. Dengan menggunakan struktur ini, Anda dapat:- Pindahkan pemain lebih tinggi dalam daftar jika mereka menunjukkan hasil yang lebih baik dari sebelumnya.
- Hapus pemain dari daftar, misalnya, dalam kasus larangan curang.
- Tunjukkan setiap pemain di mana dia berada.
- Tampilkan tabel catatan halaman demi halaman.
- Perlihatkan tabel yang jarang di beberapa tempat, misalnya, waktu 1, 2, 3, 5, 10, 20, 50, 100, 1000, 10000 tempat.
Struktur data
Struktur didasarkan pada pohon dengan kunci implisit. Pada pendekatan ini, misalnya, bahwa TreeList di-koleksi umum apache didasarkan. Untuk melanjutkan, Anda perlu memahami cara kerja struktur ini.Pohon Kunci Tersirat
Pohon terdiri dari node (Nodes). Setiap node berisi tautan ke objek yang disimpan di simpul dan 2 tautan ke simpul lain: kiri dan kanan. Node paling atas disebut simpul akar. Dalam kasus paling sederhana, simpul terlihat seperti ini:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
}
Dalam pohon biner klasik untuk setiap node di subtree kiri, semua objek lebih kecil dari pada node saat ini, dan di kanan - besar. Contohnya: [ element: 25 ]
/ \
/ \
[ element: 14 ] [ element: 45 ]
/ \ / \
/ \ / \
[ element: 10 ] [ element: 22 ] [ element: 27 ] [ element: 90 ]
/ \ /
/ \ /
[ element: 17 ] [ element: 23 ] [ element: 80 ]
Tetapi untuk tujuan kita, pohon seperti itu tidak cocok. Kita tidak perlu menyimpan objek yang diurutkan, tetapi kita harus memiliki akses ke mereka dengan indeks, seperti dalam array.Bagaimana saya bisa meletakkan array di pohon? Mari kita pilih elemen dengan indeks i dari tengah array. Tempatkan elemen engan dari array di node root. 2 sub pohon keluar dari simpul akar. Di subtree kiri kita meletakkan setengah array dengan indeks <i, dan di sebelah kanan dengan index> i. Bagaimana cara melakukannya? Dengan cara yang sama: kita memilih elemen dari tengah dalam sebuah subarray, meletakkan elemen ini dalam sebuah node, kita mendapatkan 2 sub-array yang lebih kecil. Jadi sampai kita meletakkan semua elemen array di node pohon.Misalnya, array dengan elemen ["q", "w", "e", "r", "t", "y", "u"] akan terlihat seperti ini: [el: r, size: 7]
/ : \
/ : \
[el: w, size: 3] : [el: y, size: 3]
/ : \ : / : \
/ : \ : / : \
[el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
Elemen tengah dalam array "r", kita letakkan di simpul root. Dua subarrays ["q", "w", "e"] dan ["t", "y", "u"] ditempatkan di sub pohon kiri dan kanan. Untuk ini, elemen-elemen pusat dipilih dari sub-array, dalam kasus kami ini adalah "w" dan "y", dan mereka jatuh ke dalam node dari tingkat berikutnya. Dan seterusnya,dalam kasus kami, pohon seimbang, kedalaman semua sub pohon sama. Tetapi ini tidak harus demikian.Pada gambar di atas, setiap node, selain elemen dan tautan ke node kiri dan kanan, berisi jumlah elemen dari seluruh subtree. Informasi ini harus diperbarui dengan benar ketika pohon berubah.Mari kita lihat bagaimana menemukan, misalnya, elemen dengan indeks = 4 di pohon seperti itu.Kami mulai merangkak dari simpul root (root, dalam kasus kami dengan elemen "r"). Kami memiliki 3 opsi: kami sudah berada di simpul kanan, simpul kanan di kiri, simpul kanan di kanan. Untuk memahami di mana mencari elemen yang diinginkan, Anda perlu membandingkan ukuran subtree kiri (dalam kasus kami left.size = 3) dan indeks saat ini (dalam kasus kami 4). Jika 2 angka ini sama, maka kami menemukan simpul yang diperlukan dan elemen yang diinginkan di dalamnya. Jika ukuran subtree kiri lebih besar, maka simpul yang diperlukan di subtree kiri. Jika kurang, maka Anda perlu melihat di subtree kanan, tetapi Anda perlu mengurangi indeks yang diinginkan: index = index - left.size - 1.Karena dalam kasus kami left.size <index, kami mencari subtree kanan untuk elemen dengan indeks baru 4 - 3 - 1 = 0. Pindah ke simpul dengan elemen “y”.Lalu kami melakukan hal yang sama yang kami lakukan pada simpul root. Bandingkan ukuran kiri dan indeks. Karena 1> 0, kita melihat di subtree kiri, pindah ke node dengan elemen "t".Tidak ada subtree kiri dalam node ini, dan ukurannya adalah 0. index = left.size, yang berarti kami menemukan sebuah node dengan indeks 4 dan kita bisa mendapatkan elemen yang diperlukan "t" dari itu.Dalam kode pseudo, tampilannya seperti ini:function get(node: Node<T>, index: int): T {
val leftSize: int = (node.left == null) ? 0 : node.left.size;
if (leftSize == index) {
return node.obj;
} else if (leftSize > index) {
return get(node.left, index);
} else {
return get(node.right, index — leftSize — 1);
}
}
Saya mencoba menjelaskan prinsip utama cara meletakkan array di pohon. Struktur seperti itu bekerja, tentu saja, lebih lambat daripada array klasik, untuk O (log (n)) versus O (1). Tetapi memiliki keuntungan penting: menambahkan elemen ke tengah atau menghapus dari tengah juga berfungsi untuk O (log (n)) versus O (n) untuk array. Tentu saja, asalkan pohonnya kurang lebih seimbang. Ada banyak algoritma untuk memelihara pohon dengan cara yang hampir seimbang. Misalnya, pohon merah-hitam, pohon AVL, pohon Cartesian. Saya tidak akan menuliskan detail balancing tree, algoritma apa pun cocok untuk kita. Anggap saja pohon itu seimbang rata-rata dan kedalaman maksimumnya tidak jauh berbeda dari minimum.Optimasi sedikit
Pendekatan yang dijelaskan di atas, dengan memeriksa ukuran pohon di sebelah kiri nyaman untuk persepsi, tetapi dapat dilakukan sedikit lebih efisien. Agar tidak melihat ke subtree kiri setiap kali, alih-alih ukuran pohon, seseorang dapat menyimpan di simpul posisinya relatif terhadap posisi simpul induknya. Simpul root menyimpan posisi absolut yang cocok dengan ukuran subtree kiri. [el: r, pos: 3]
/ : \
/ : \
[el: w, pos: -2] : [el: y, pos: +2]
/ : \ : / : \
/ : \ : / : \
[el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
Misalnya, simpul akar "r" memiliki posisi 3. Node "w" memiliki posisi -2 relatif terhadap simpul induk atau posisi absolut 3 + (-2) = 1. Demikian pula, Anda dapat turun satu tingkat lagi, misalnya, simpul "e" memiliki posisi 3 + (-2) + (+1) = 2. Yaitu, indeks simpul adalah jumlah posisi dari akar pohon ke simpul ini.Pengoptimalan ini, selain pencarian yang lebih cepat untuk suatu item dalam daftar, akan menyediakan pencarian yang lebih cepat dan lebih mudah untuk indeks pada node. Tapi, tentu saja, memperbarui posisi dengan benar saat mengganti pohon menjadi sedikit lebih sulit.Tambahkan Pengindeksan
Jadi, di pohon kita dapat mengambil elemen dengan indeks, ubah nilainya, tambahkan elemen ke tengah dan hapus. Pada dasarnya, kita hanya perlu menambahkan pencarian indeks cepat berdasarkan nilai, indexOf (obj). Kemudian berisi (obj) dan menghapus (obj) akan diselesaikan dengan sepele.Tapi pertama-tama, mari sederhanakan tugasnya. Mari kita membuat struktur yang hanya menyimpan elemen unik.Untuk mencari sesuatu dengan cepat, mereka biasanya menggunakan tabel. Di dunia Java, tabel disebut Map, memiliki 2 implementasi utama: HashMap dan TreeMap. Kunci ke tabel akan menjadi tautan ke objek, dan nilainya akan menjadi tautan ke simpulnya:class IndexedTreeListSet<T> {
root: Node<T>
indexMap: Map<T, Node<T>>
}
Itu struktur terdiri dari dua bagian: daftar pohon itu sendiri dan tabel dengan tautan ke objek dan simpul pohon ini. Saat memperbarui pohon, tabel juga harus diperbarui. Saya tidak akan menjelaskan proses secara rinci. Secara intuitif, ini bisa dimengerti: tambahkan sebuah simpul - letakkan di tabel, hapus simpul - hapus dari tabel. Dalam praktiknya, ada nuansa dengan menyeimbangkan pohon: algoritme harus mengubah tautan antara simpul, dan tidak memindahkan objek di antara simpul. Jika tidak, Anda harus melakukan banyak pembaruan di tabel dan kinerja akan turun.Ok, kami akan menganggap bahwa kami dapat dengan cepat menemukan node oleh elemen yang dikandungnya. Terus? Kita perlu menemukan indeksnya, tetapi ini belum dapat dilakukan. Tetapi kita dapat memperumit kelas simpul sehingga tidak hanya berisi tautan ke simpul kiri dan kanan, tetapi juga ke induknya:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
parent: Node<T>
pos: int
}
Tentu saja, memperbarui pohon sedikit lebih rumit, karena sekarang kita perlu memperbarui tautan ke orang tua dengan hati-hati. Tapi sekarang, mengetahui simpul, kita bisa naik pohon dan menghitung indeks dari simpul apa pun. Jika kita menggunakan optimasi dari bab sebelumnya, maka kita hanya perlu menghitung jumlah posisi dari node saat ini ke root.Untuk daftar yang berisi elemen unik, masalah dapat dianggap diselesaikan.Benar, kami punya masalah kecil. Misalkan kita sebut set (index, obj). Kita dapat dengan mudah mengganti satu elemen dalam satu node dengan yang lain, tetapi hanya jika belum ada elemen baru dalam daftar. Dan jika demikian, apa yang harus saya lakukan? Hapus kelebihan item dari posisi lama dan masukkan yang baru? Atau sebaliknya, tambahkan dulu lalu hapus? Hasilnya mungkin berbeda. Dan Anda tidak dapat melakukan apa pun atau melemparkan pengecualian. Tidak ada solusi yang sempurna.Menyortir dengan metode standar daftar seperti itu, kemungkinan besar, tidak akan berfungsi baik. Lagi pula, algoritma pengurutan tidak akan tahu tentang perlunya keunikan objek dan akan membuat duplikat saat memindahkan item dalam daftar.Kami menghapus keunikan
Ok, memperumit lebih jauh, mari kita simpan benda yang sama. Jelas, Anda perlu melakukan sesuatu dengan meja. Gagasan pertama untuk menyimpan daftar node di dalamnya tampaknya tidak terlalu bagus: dengan peningkatan panjang daftar, kinerja akan memburuk. Hingga O (n) jika semua item daftar adalah sama.Kemudian mari kita coba menyimpan pohon node yang diurutkan dalam sebuah tabel alih-alih daftar. Diurutkan berdasarkan posisi dalam daftar.class IndexedTreeList<T> {
root: Node<T>
indexMap: Map<T, TreeSet<Node<T>>>
}
Kemudian penyisipan / penghapusan ke / dari TreeSet <Node> ukuran m akan terjadi selama log (m) perbandingan posisi node, dan setiap perbandingan akan terjadi lebih dari waktu log (n). Kompleksitas terakhir dari memasukkan atau menghapus ke dalam struktur yang sama akan terjadi pada O (log (n) * (1 + log (m))), di mana n adalah jumlah total elemen dalam daftar, dan m adalah jumlah elemen dalam daftar yang sama dengan yang dimasukkan / dihapus. Dalam kasus terburuk, ketika semua elemen sama satu sama lain, kita mendapatkan kompleksitas O (log (n) ^ 2).Seorang pembaca yang penuh perhatian mungkin akan keberatan: tetapi bagaimana dengan kekekalan? Lagi pula, kita tidak dapat mengubah objek jika itu adalah tombol tabel? Secara umum, itu. Namun, untuk pohon yang menyimpan objek yang disortir dalam kunci, selain aturan standar untuk perbandingan, cukup untuk mempertahankan invarian: jika a <b, maka properti ini tidak boleh berubah seiring waktu. Ini hanya kasus kami: jika posisi satu node kurang dari posisi node lain, maka properti ini akan dipertahankan terlepas dari berapa banyak node yang ditambahkan atau dihapus di antara mereka.Apakah mungkin untuk membuat struktur bertahan?
Jawaban singkat: tidak, itu tidak mungkin. Karena hubungan kedua pohon, dari akar ke daun dan kembali, kami memiliki setiap simpul pohon yang terhubung ke masing-masing. Kegigihan tidak dapat dilakukan dengan cara ini, Anda harus membuat ulang seluruh struktur dengan perubahan apa pun.Tetapi saya memiliki pemahaman tentang bagaimana menerapkan struktur persisten untuk kasus-kasus di mana kita tidak perlu memasukkan elemen di tengah daftar. Anda dapat menambahkan elemen ke awal atau akhir, dan Anda dapat menghapus dari tengah. Properti yang tersisa adalah sama.Jika Anda tertarik, maka saya akan mencoba menulis artikel tentang struktur ini. Mungkin saya bahkan mengimplementasikannya di Jawa, Kotlin atau Scala. Tapi, kemungkinan besar, itu tidak akan segera terjadi.Beberapa fitur implementasi
Di sini saya ingin menggambarkan beberapa fitur yang harus saya hadapi.Tentang salah satu optimasi tentang menyimpan posisi simpul dalam daftar, saya tulis di atas. Di sini kekuatan dari Open Source dimanifestasikan: Saya mengambil kode TreeList yang sudah jadi dan tidak menyelidiki rincian dari pohon AVL, rotasi node, pembaruan posisi, dll.Fitur lain yang diwarisi dari TreeList adalah tautan ke sub pohon di daun pohon. Setiap node menyimpan boolean leftIsPrevious dan rightIsNext. Variabel-variabel ini menunjukkan ada atau tidaknya subtree kiri / kanan. Jika tidak ada subtree, maka di kiri / kanan, alih-alih tautan ke subtree, tautan ke node yang sesuai dengan elemen sebelumnya atau berikutnya disimpan. Dalam contoh kita, ["q", "w", "e", "r", "t", "y", "u"] simpul "e" berdaun, ia tidak memiliki sub cabang. Dengan demikian, leftIsPrevious dan rightIsNext benar, dan titik kiri dan kanan ke node "w" dan "r", masing-masing. Pendekatan ini membantu beralih melalui daftar lebih cepat. Dan itu mengganggu pemrograman fitur baru :)Sedikit tentang bekerja dengan objek tabel → node. Idealnya, Anda perlu memasukkan elemen ke tabel sekali saat menambahkannya ke struktur dan menghapusnya sekali ketika menghapus dari struktur. Dalam praktiknya, saya tidak bisa mencapai ini. Ketika Anda menambahkan item, itu ditambahkan ke tabel, semuanya sudah sebagaimana mestinya. Namun, ketika Anda menghapus item, algoritma balancing terkadang memindahkan item di antara node. Hasilnya adalah dua penghapusan dan satu catatan di tabel, bukan satu penghapusan. Ini dapat diperbaiki jika Anda menghapus optimasi dari leftIsPrevious dan rightIsNext. Dan bahkan mendapatkan keuntungan kinerja kecil, dan tidak hanya selama penghapusan. Dalam beberapa tes, peningkatannya adalah 10-20%. Tetapi kecepatan iterasi turun secara signifikan, 1,5-2,5 kali dalam tes saya. Saya memutuskan untuk meninggalkan optimasi untuk saat ini.Di Jawa, jenis tabel utama adalah HashMap dan TreeMap. Untuk tabel, objek → node menggunakan HashMap secara default. Namun, Anda dapat menggunakan TreeMap dengan pembanding khusus tugas. Dalam hal ini, indexOf (obj) dan menghapus (obj) akan mencari / menghapus objek yang sama dengan objek yang ditentukan sesuai dengan kode Comparator. Misalnya, kami menyimpan daftar pengguna, dan pembanding membandingkan pengguna hanya dengan nama. Kemudian kita dapat menjawab pertanyaan "Posisi apa dari daftar tersebut adalah pengguna dengan nama 'Napoleon?'". Atau hapus semua Napoleon dari daftar :).Struktur tidak mendukung null. Anda dapat memperbaikinya, tetapi tidak ada perasaan bahwa itu perlu.Mengenai fakta bahwa struktur “tahu segalanya”, saya, tentu saja, sedikit menyesatkan. Tentu saja, ketika bekerja dengan elemen tunggal, semuanya baik-baik saja dan dalam kondisi tertentu bahkan untuk logaritma. Namun, dia tidak tahu beberapa hal yang struktur lain bisa. Misalnya, pohon Cartesian dengan kunci implisit, ada artikel tentang itu di hub Ia tidak tahu bagaimana cara cepat melakukan indexOf, tetapi ia tahu bagaimana membuat sublist dan menggabungkan dua daftar menjadi satu untuk logaritma (rata-rata, tidak dijamin), ditambah lagi dapat dibuat terus-menerus.Performa
Di Jawa, kinerja biasanya diukur menggunakan kerangka kerja jmh. Tes dilakukan pada MacBook Pro 2017 di bawah Java11.Saya membandingkan kinerja standar ArrayList, TreeList dari kumpulan-umum apache, dan dua kelas saya IndexedTreeList dan IndexedTreeListSet dalam beberapa skenario. Dalam setiap skenario, 1000 operasi dari jenis yang sama dilakukan, sehingga hasilnya harus dikalikan dengan 1000.Kode di bawah spoiler@Fork(1)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public class PerformanceCompare {
public static final Map<String, Class> CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,
ArrayList.class)
.collect(Collectors.toMap(c -> c.getSimpleName(), c -> c));
public static final int ITERATIONS = 1000;
@State(Scope.Benchmark)
public static class Plan {
@Param({"10", "100", "1000", "10000", "100000", "1000000"/*, "10000000"*/})
public int size;
@Param({"ArrayList", "TreeList", "IndexedTreeList", "IndexedTreeListSet"})
public String className;
private Random random;
private List<Integer> list;
@Setup
public void init() throws IllegalAccessException, InstantiationException {
random = new Random();
list = (List<Integer>) CLASSES.get(className).newInstance();
for (int i = 0; i < size; i++) {
list.add(i);
}
}
}
@Benchmark
public void indexOfKnown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value = list.indexOf(random.nextInt(plan.size));
}
blackhole.consume(value);
}
@Benchmark
public void indexOfUnknown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.indexOf(random.nextInt());
}
blackhole.consume(value);
}
@Benchmark
public void addRemoveRandom(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
list.add(random.nextInt(list.size() + 1), random.nextInt());
value += list.remove(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Benchmark
public void get(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.get(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(PerformanceCompare.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
Untuk mulai dengan, saya membandingkan kecepatan mendapatkan item acak dari daftar. Saya akan segera memperingatkan Anda bahwa dalam pengujian ini biaya overhead sangat signifikan. Hasil mendekati 100.000 * 1.000 operasi per detik sangat terdistorsi.Dapatkan hasil tesPerformanceCompare.get ArrayList 10 thrpt 5 79865.412 ± 10145.202 ops/s
PerformanceCompare.get ArrayList 100 thrpt 5 81862.243 ± 983.727 ops/s
PerformanceCompare.get ArrayList 1000 thrpt 5 81033.507 ± 4540.206 ops/s
PerformanceCompare.get ArrayList 10000 thrpt 5 64096.123 ± 1430.361 ops/s
PerformanceCompare.get ArrayList 100000 thrpt 5 41289.491 ± 11286.114 ops/s
PerformanceCompare.get ArrayList 1000000 thrpt 5 8598.944 ± 2048.461 ops/s
PerformanceCompare.get TreeList 10 thrpt 5 33912.275 ± 3754.284 ops/s
PerformanceCompare.get TreeList 100 thrpt 5 21346.854 ± 863.588 ops/s
PerformanceCompare.get TreeList 1000 thrpt 5 14808.414 ± 508.098 ops/s
PerformanceCompare.get TreeList 10000 thrpt 5 8679.384 ± 109.250 ops/s
PerformanceCompare.get TreeList 100000 thrpt 5 4605.998 ± 1028.945 ops/s
PerformanceCompare.get TreeList 1000000 thrpt 5 2241.381 ± 768.147 ops/s
PerformanceCompare.get IndexedTreeList 10 thrpt 5 34054.357 ± 3682.829 ops/s
PerformanceCompare.get IndexedTreeList 100 thrpt 5 21934.002 ± 2339.947 ops/s
PerformanceCompare.get IndexedTreeList 1000 thrpt 5 14626.691 ± 369.893 ops/s
PerformanceCompare.get IndexedTreeList 10000 thrpt 5 7386.863 ± 342.150 ops/s
PerformanceCompare.get IndexedTreeList 100000 thrpt 5 4562.126 ± 352.772 ops/s
PerformanceCompare.get IndexedTreeList 1000000 thrpt 5 2105.718 ± 702.064 ops/s
PerformanceCompare.get IndexedTreeListSet 10 thrpt 5 33317.503 ± 2307.829 ops/s
PerformanceCompare.get IndexedTreeListSet 100 thrpt 5 21247.440 ± 1253.386 ops/s
PerformanceCompare.get IndexedTreeListSet 1000 thrpt 5 14665.557 ± 487.833 ops/s
PerformanceCompare.get IndexedTreeListSet 10000 thrpt 5 7667.214 ± 80.093 ops/s
PerformanceCompare.get IndexedTreeListSet 100000 thrpt 5 3454.023 ± 82.994 ops/s
PerformanceCompare.get IndexedTreeListSet 1000000 thrpt 5 1768.701 ± 35.878 ops/s
Di sini, anehnya, minat terbesar adalah ArrayList standar. Secara teoritis, kecepatan keluarnya harus konstan dan tidak tergantung pada jumlah elemen. Dalam praktiknya, kinerja awalnya menampung sekitar 90.000 * 1000 operasi per detik (ingat biaya overhead), tetapi dengan daftar panjang beberapa ribu item mulai melorot. Hal ini disebabkan oleh semakin banyaknya cache yang hilang: cache prosesor tidak memiliki data yang diperlukan dan semakin sering Anda harus mencari data dalam RAM. Dengan sejuta elemen, kecepatan tes 10 kali lebih rendah, tetapi dalam praktiknya, penurunan kinerja bahkan lebih besar.TreeList, IndexedTreeList, dan IndexedTreeListSet diharapkan menunjukkan hasil yang sama. Diharapkan jauh lebih lambat daripada ArrayList. Bahkan dengan sejumlah kecil elemen, TreeList beberapa kali lebih lambat dari ArrayList, meskipun tes menunjukkan perbedaan hanya 2 kali.Tes selanjutnya adalah addRemoveRandom. Di sini, di setiap tes, saya memasukkan elemen ke posisi acak dan menghapus elemen dari posisi acak.Hasil uji AddRemoveRandomPerformanceCompare.addRemoveRandom ArrayList 10 thrpt 5 12440.764 ± 485.642 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100 thrpt 5 9880.123 ± 464.014 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000 thrpt 5 5288.905 ± 1219.055 ops/s
PerformanceCompare.addRemoveRandom ArrayList 10000 thrpt 5 1024.942 ± 179.366 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100000 thrpt 5 91.219 ± 25.380 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000000 thrpt 5 5.499 ± 0.400 ops/s
PerformanceCompare.addRemoveRandom TreeList 10 thrpt 5 6242.607 ± 350.290 ops/s
PerformanceCompare.addRemoveRandom TreeList 100 thrpt 5 3117.945 ± 116.066 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000 thrpt 5 1829.778 ± 80.516 ops/s
PerformanceCompare.addRemoveRandom TreeList 10000 thrpt 5 1230.077 ± 53.381 ops/s
PerformanceCompare.addRemoveRandom TreeList 100000 thrpt 5 443.571 ± 69.207 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000000 thrpt 5 308.963 ± 84.077 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10 thrpt 5 3556.511 ± 144.596 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100 thrpt 5 2120.777 ± 83.848 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000 thrpt 5 1211.112 ± 92.288 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10000 thrpt 5 789.458 ± 19.450 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100000 thrpt 5 302.989 ± 40.030 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000000 thrpt 5 178.822 ± 92.853 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10 thrpt 5 4138.007 ± 119.943 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100 thrpt 5 2435.803 ± 20.276 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000 thrpt 5 1445.054 ± 276.909 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10000 thrpt 5 972.256 ± 19.987 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100000 thrpt 5 366.608 ± 94.487 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000000 thrpt 5 227.677 ± 48.276 ops/s
Dapat diasumsikan bahwa ArrayList lebih cepat pada daftar kecil. Namun, fakta bahwa ia menang dalam tes ini pada daftar hingga 10.000 elemen terlihat menarik. Rupanya, System.arrayCopy dioptimalkan dengan sangat baik dan menggunakan semua fitur prosesor modern. Mulai dari 10.000 item, struktur data khusus mulai menang. Dengan 1.000.000 elemen, perbedaan kecepatan adalah 30-50 kali.IndexedTreeList dan IndexedTreeListSet diharapkan lebih lambat dari TreeList. Sekitar 1,5 - 2 kali.Sisa 2 tes indexOfKnown dan indexOfUnknown hanya dapat menunjukkan fitur utama dari struktur ini. Perbedaan antara tes adalah bahwa dalam satu kasus kami mencari elemen yang ada dalam daftar, dan dalam kasus lain kami mencari elemen yang tidak ada dalam daftar.Uji hasil indexOfKnown dan indexOfUnknownPerformanceCompare.indexOfKnown ArrayList 10 thrpt 5 41424.356 ± 549.047 ops/s
PerformanceCompare.indexOfKnown ArrayList 100 thrpt 5 17216.477 ± 1444.744 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000 thrpt 5 2296.306 ± 76.372 ops/s
PerformanceCompare.indexOfKnown ArrayList 10000 thrpt 5 233.863 ± 26.926 ops/s
PerformanceCompare.indexOfKnown ArrayList 100000 thrpt 5 23.208 ± 2.776 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000000 thrpt 5 0.919 ± 0.455 ops/s
PerformanceCompare.indexOfKnown TreeList 10 thrpt 5 26740.708 ± 1323.125 ops/s
PerformanceCompare.indexOfKnown TreeList 100 thrpt 5 5670.923 ± 99.638 ops/s
PerformanceCompare.indexOfKnown TreeList 1000 thrpt 5 745.408 ± 26.827 ops/s
PerformanceCompare.indexOfKnown TreeList 10000 thrpt 5 52.288 ± 1.362 ops/s
PerformanceCompare.indexOfKnown TreeList 100000 thrpt 5 4.224 ± 0.855 ops/s
PerformanceCompare.indexOfKnown TreeList 1000000 thrpt 5 0.193 ± 0.052 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10 thrpt 5 34485.128 ± 1582.703 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100 thrpt 5 29209.412 ± 1544.268 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000 thrpt 5 21139.584 ± 1442.867 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10000 thrpt 5 12544.306 ± 312.097 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100000 thrpt 5 3538.201 ± 272.537 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000000 thrpt 5 1420.119 ± 538.476 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10 thrpt 5 39201.995 ± 1887.065 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100 thrpt 5 34204.112 ± 1122.517 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000 thrpt 5 25374.557 ± 1596.746 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10000 thrpt 5 14291.317 ± 391.180 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100000 thrpt 5 4215.898 ± 283.680 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000000 thrpt 5 1729.100 ± 1260.815 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10 thrpt 5 59053.313 ± 1845.665 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100 thrpt 5 10867.572 ± 142.823 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000 thrpt 5 1186.583 ± 28.003 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10000 thrpt 5 120.953 ± 4.146 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100000 thrpt 5 11.936 ± 0.320 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000000 thrpt 5 0.566 ± 0.335 ops/s
PerformanceCompare.indexOfUnknown TreeList 10 thrpt 5 28134.237 ± 2291.670 ops/s
PerformanceCompare.indexOfUnknown TreeList 100 thrpt 5 3153.930 ± 158.734 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000 thrpt 5 322.383 ± 44.245 ops/s
PerformanceCompare.indexOfUnknown TreeList 10000 thrpt 5 25.674 ± 1.787 ops/s
PerformanceCompare.indexOfUnknown TreeList 100000 thrpt 5 1.867 ± 0.291 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000000 thrpt 5 0.093 ± 0.008 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10 thrpt 5 66625.126 ± 5232.668 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100 thrpt 5 70038.055 ± 5803.848 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000 thrpt 5 63240.467 ± 885.956 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10000 thrpt 5 54731.988 ± 3950.150 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100000 thrpt 5 22049.476 ± 821.924 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000000 thrpt 5 9459.862 ± 804.738 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10 thrpt 5 70274.968 ± 15830.355 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100 thrpt 5 71017.685 ± 6920.447 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000 thrpt 5 66405.960 ± 1127.231 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10000 thrpt 5 57983.963 ± 3276.142 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100000 thrpt 5 41277.110 ± 9919.893 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000000 thrpt 5 9840.185 ± 2159.352 ops/s
Di sini, ArrayList dan TreeList hampir tidak memiliki kejutan. Dengan meningkatnya ukuran, kecepatan berkurang hampir secara linear. Pencarian item dari daftar tidak diharapkan 2 kali lebih lambat daripada pencarian item dari daftar, karena Anda harus melalui seluruh array, bukan setengah rata-rata.Tetapi IndexedTreeList dan IndexedTreeListSet di sini menunjukkan hasil yang diharapkan. Struktur data ini menunjukkan kecepatan eksekusi indexOf yang sebanding dengan ArrayList bahkan dengan 10 elemen. Dengan 1000 elemen, struktur ini 10 kali lebih cepat, dengan 1.000.000 lebih cepat 1000 kali. Saat mencari item yang tidak ada dalam daftar, mereka diharapkan untuk memberikan kecepatan yang lebih baik daripada saat mencari item dari daftar.Apa lagi yang menarik untuk diperhatikan adalah penurunan kinerja IndexedTreeList dan IndexedTreeListSet dalam uji indexOfUnknown. Di sini situasinya mirip dengan yang di tes dengan ArrayList.get. Secara teoritis, kita seharusnya tidak mendapatkan penurunan kinerja, tetapi dalam praktiknya, karena cache miss, kita mendapatkannya, terlebih lagi, secara signifikan.Alih-alih sebuah kesimpulan
Saya masih tidak tahu apakah struktur yang diusulkan memiliki hal yang baru atau tidak. Di satu sisi, idenya tidak rumit jika Anda tahu cara kerja pohon dengan kunci implisit. Di sisi lain, saya belum melihat deskripsi struktur dengan properti seperti itu. Dan jika demikian, maka masuk akal untuk membuat struktur lebih terkenal, mungkin berguna bagi seseorang.Tetapi bahkan jika ini adalah motor lain, saya mencoba membuatnya berguna. Permintaan penarikan dalam koleksi umum telah dibuat, tetapi pada saat penulisan artikel ini belum dituangkan. Mengetahui betapa lambatnya segala sesuatu dapat terjadi dalam open source, saya tidak akan terkejut jika proses berlangsung selama berbulan-bulan.Agak kaget dengan hasil membandingkan kinerja ArrayList dan TreeList. Pengujian menunjukkan bahwa TreeList tidak masuk akal untuk menggunakan hingga 10.000 elemen pada ukuran daftar. Akan menarik untuk mencoba b-tree daripada pohon biner. Struktur ini harus menggunakan memori lebih hati-hati dan, kemungkinan besar, bekerja lebih cepat. Dan untuk itu Anda dapat menyesuaikan ide dengan pengindeksan.Dalam kasus apa pun, menyenangkan memiliki instrumen di gudang yang dapat (hampir) melakukan segalanya dengan kompleksitas yang dapat diprediksi.Referensi
Proyek
permintaan Tarik Asli dalam apache-koleksi umumTiket di Jira