Apa pustaka Koleksi Java yang paling efisien? [Tutup]

Apa pustaka Koleksi Java yang paling efisien?

Beberapa tahun yang lalu, saya melakukan banyak Java dan mendapat kesan saat itu bahwa trove adalah implementasi Java Collections terbaik (paling efisien). Tetapi ketika saya membaca jawaban atas pertanyaan “ Perpustakaan Java gratis yang paling berguna? ” Saya melihat bahwa harta karun hampir tidak disebutkan. Jadi perpustakaan Koleksi Java mana yang terbaik sekarang?

PEMBARUAN: Untuk memperjelas, saya sebagian besar ingin tahu perpustakaan apa yang akan digunakan ketika saya harus menyimpan jutaan entri dalam tabel hash, dll. (Memerlukan runtime kecil dan jejak memori).

Dari pemeriksaan, tampaknya Trove hanyalah perpustakaan koleksi untuk tipe primitif - ini tidak dimaksudkan untuk menambahkan banyak fungsionalitas di atas koleksi normal di JDK.

Secara pribadi (dan saya bias) saya suka Guava (termasuk proyek Koleksi Google Java sebelumnya). Itu membuat berbagai tugas (termasuk koleksi) jauh lebih mudah, dengan cara yang setidaknya cukup efisien. Mengingat bahwa operasi pengumpulan jarang membentuk hambatan dalam kode saya (menurut pengalaman saya) ini "lebih baik" daripada API koleksi yang mungkin lebih efisien tetapi tidak membuat kode saya dapat dibaca.

Mengingat bahwa tumpang tindih antara Trove dan Guava hampir nihil, mungkin Anda dapat menjelaskan apa yang sebenarnya Anda cari dari perpustakaan koleksi.

Pertanyaannya adalah (sekarang) tentang menyimpan banyak data, yang dapat direpresentasikan menggunakan tipe primitif seperti int, dalam Peta. Beberapa jawaban di sini sangat menyesatkan menurut saya. Mari kita lihat alasannya.

Saya memodifikasi benchmark dari trove untuk mengukur baik runtime maupun konsumsi memori. Saya juga menambahkan PCJ ke benchmark ini, yang merupakan pustaka koleksi lain untuk tipe primitif (saya menggunakannya secara ekstensif). Tolok ukur harta 'resmi' tidak membandingkan IntIntMaps dengan Java Collection Map<Integer, Integer>, mungkin penyimpanan Integersdan penyimpanan intstidak sama dari sudut pandang teknis. Tetapi pengguna mungkin tidak peduli dengan detail teknis ini, dia ingin menyimpan data yang dapat direpresentasikan dengan intsefisien.

Pertama, bagian kode yang relevan:

new Operation() {

     private long usedMem() {
        System.gc();
        return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
     }

     // trove
     public void ours() {
        long mem = usedMem();
        TIntIntHashMap ours = new TIntIntHashMap(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           ours.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("trove " + mem + " bytes");
        ours.clear();
     }

     public void pcj() {
        long mem = usedMem();
        IntKeyIntMap map = new IntKeyIntOpenHashMap(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           map.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("pcj " + mem + " bytes");
        map.clear();
     }

     // java collections
     public void theirs() {
        long mem = usedMem();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(SET_SIZE);
        for ( int i = dataset.size(); i-- > 0; ) {
           map.put(i, i);
        }
        mem = usedMem() - mem;
        System.err.println("java " + mem + " bytes");
        map.clear();
     }

Saya menganggap datanya primitif ints, yang tampaknya waras. Tapi ini menyiratkan hukuman waktu proses untuk java util, karena auto-boxing, yang tidak diperlukan untuk framework koleksi primitif.

Hasil runtime (tanpa gc()panggilan, tentu saja) di WinXP, jdk1.6.0_10:

                      100000 operasi put 100000 berisi operasi 
koleksi java 1938 ms 203 ms
harta karun 234 ms 125 ms
pcj 516 ms 94 ms

Meskipun ini mungkin sudah tampak drastis, ini bukanlah alasan untuk menggunakan kerangka kerja seperti itu.

Alasannya adalah kinerja memori. Hasil untuk Peta yang berisi 100000 intentri:

koleksi java berosilasi antara 6644536 dan 7168840 byte
harta karun 1853296 byte
pcj 1866112 byte

Koleksi Java membutuhkan lebih dari tiga kali memori dibandingkan dengan kerangka kerja koleksi primitif. Yaitu Anda dapat menyimpan data tiga kali lebih banyak dalam memori, tanpa menggunakan disk IO yang menurunkan kinerja runtime menurut besarnya. Dan ini penting. Baca skalabilitas tinggi untuk mencari tahu alasannya.

Menurut pengalaman saya, konsumsi memori yang tinggi adalah masalah kinerja terbesar dengan Java, yang tentu saja menghasilkan kinerja runtime yang lebih buruk juga. Kerangka kerja koleksi primitif dapat sangat membantu di sini.

Jadi: Tidak, java.util bukanlah jawabannya. Dan "menambahkan fungsionalitas" ke koleksi Java bukanlah intinya ketika bertanya tentang efisiensi. Juga koleksi JDK modern tidak "mengungguli bahkan koleksi Trove khusus".

Penafian: Tolok ukur di sini masih jauh dari lengkap, juga tidak sempurna. Ini dimaksudkan untuk menyampaikan poin, yang telah saya alami dalam banyak proyek. Koleksi primitif cukup berguna untuk mentolerir API mencurigakan - jika Anda bekerja dengan banyak data.

Saya tahu ini adalah posting lama dan ada banyak jawaban di sini. Tapi, Jawaban di atas dangkal dan terlalu disederhanakan dalam hal menyarankan perpustakaan. Tidak ada satu perpustakaan pun yang bekerja dengan baik di berbagai tolok ukur yang disajikan di sini. Satu-satunya kesimpulan yang saya peroleh adalah jika Anda peduli dengan kinerja dan memori dan secara khusus berurusan dengan tipe primitif, lebih dari layak untuk melihat alternatif non jdk.

Berikut adalah analisis yang lebih baik, dalam hal mekanisme benchmark dan perpustakaan yang tercakup. Ini adalah utas dalam daftar dev mahout.

Perpustakaan yang tercakup adalah

• HPPC
• Harta karun
• FastUtil
• Mahout (Colt)
• Koleksi Java

Pembaruan Juni 2015 : Sayangnya, tolok ukur asli tidak lagi tersedia dan selain itu agak ketinggalan jaman. Berikut adalah tolok ukur yang cukup baru (Jan 2015) yang dilakukan oleh orang lain. Ini tidak selengkap dan tidak memiliki alat eksplorasi interaktif seperti tautan aslinya.

Seperti yang diketahui oleh para komentator lain, definisi "efisien" mendapat banyak keuntungan. Namun belum ada yang menyebutkan perpustakaan Javolution .

Beberapa sorotan:

• Kelas javolution cepat, sangat cepat (misalnya penyisipan / penghapusan teks di O [Log (n)] daripada O [n] untuk StringBuffer / StringBuilder standar).
• Semua kelas Javolution kompatibel dengan waktu nyata dan memiliki perilaku yang sangat deterministik (dalam kisaran mikrodetik). Lebih jauh lagi (tidak seperti pustaka standar), Javolution adalah RTSJ aman (tidak ada benturan memori atau kebocoran memori saat digunakan dengan ekstensi Java Real-Time).
• Kelas koleksi real-time Javolution (peta, daftar, tabel, dan set) dapat digunakan sebagai pengganti sebagian besar kelas koleksi standar dan menyediakan fungsionalitas tambahan.
• Koleksi Javolution memberikan jaminan konkurensi untuk membuat implementasi algoritme paralel lebih mudah.

Distribusi Javolution menyertakan rangkaian benchmark sehingga Anda dapat melihat bagaimana mereka menumpuk terhadap perpustakaan lain / koleksi bawaan.

Beberapa koleksi libs untuk dipertimbangkan:

• Koleksi Java di java.util
• Harta karun
• Perpustakaan Koleksi Google
• Koleksi Apache Commons
• Lib skala tinggi dari Cliff Click
• Lib koleksi Doug Lea - tidak lagi didukung dan sebagian besar dibuat ulang di JDK

Pertama-tama saya akan meraih perpustakaan koleksi JDK. Ini mencakup hal-hal paling umum yang perlu Anda lakukan dan jelas sudah tersedia untuk Anda.

Koleksi Google mungkin adalah pustaka berkualitas tinggi terbaik di luar JDK. Ini banyak digunakan dan didukung dengan baik.

Apache Commons Collections lebih tua dan mengalami sedikit masalah "terlalu banyak juru masak" tetapi memiliki banyak hal yang berguna juga.

Trove memiliki koleksi yang sangat khusus untuk kasus seperti kunci / nilai primitif. Saat ini kami menemukan bahwa pada JDK modern dan dengan koleksi Java 5+ serta kasus penggunaan bersamaan, koleksi JDK lebih baik daripada koleksi Trove khusus.

Jika Anda memiliki kasus penggunaan konkurensi yang sangat tinggi, Anda harus memeriksa hal-hal seperti NonBlockingHashMap di lib berskala tinggi, yang merupakan implementasi bebas kunci dan dapat menginjak ConcurrentHashMap jika Anda memiliki kasus penggunaan yang tepat untuk itu.

java.util

Maaf untuk jawaban yang jelas, tetapi untuk sebagian besar penggunaan, Koleksi Java default sudah lebih dari cukup.

Untuk menyimpan jutaan Stringdalam satu peta, lihat di http://code.google.com/p/flatmap

Saya pengembang koleksi bahagia dari koleksi bahagia di source-forge

1. Koleksi berbasis acara
2. Tidak dapat dimodifikasi
3. SortedList
4. Cache

ConcurrentHashMap serta java.util.concurrentpaketnya harus disebutkan, jika Anda berencana menggunakan HashMap di banyak utas. footprint memori kecil diasumsikan, karena ini adalah bagian dari java standar.

Tergantung bagaimana kita mendefinisikan "efisien".

Setiap struktur data memiliki perilaku Big-Oh sendiri untuk membaca, menulis, mengulang, footprint memori, dll. Daftar tertaut di satu pustaka kemungkinan besar sama dengan pustaka lainnya. Dan peta hash akan lebih cepat untuk membaca O (1) daripada daftar tertaut O (n).

Tetapi ketika saya membaca jawaban atas pertanyaan "Perpustakaan Java gratis yang paling berguna?" Saya perhatikan bahwa harta karun hampir tidak disebutkan.

Ini tidak terdengar seperti "paling efisien". Kedengarannya seperti "paling populer" bagi saya.

Hanya beberapa umpan balik - Saya belum pernah mendengarnya, dan saya tidak tahu siapa pun yang telah menggunakannya. Koleksi yang dibangun ke dalam JDK, Google, atau Apache Commons sudah saya kenal.

Trove menawarkan beberapa keuntungan.

• footprint memori yang lebih kecil, itu tidak menggunakan objek Map.Entry
• Anda dapat menggunakan strategi hash alih-alih kunci untuk peta, ini menghemat memori dan berarti Anda tidak perlu menentukan kunci baru setiap kali Anda ingin menyimpan objek dalam cache pada set baru atributnya
• itu memiliki jenis koleksi primitif
• pikir itu memiliki beberapa bentuk iterator internal

Meskipun demikian, banyak yang telah dilakukan untuk meningkatkan koleksi jdk sejak trove ditulis.

Ini adalah strategi hashing yang membuatnya menarik bagi saya ... Google untuk mencari harta karun dan membaca ikhtisar mereka.

Jika Anda ingin menyimpan jutaan record dalam tabel hash, kemungkinan besar Anda akan mengalami masalah memori. Ini terjadi pada saya ketika saya mencoba membuat peta dengan 2,3 juta objek String, misalnya. Saya memilih BerkeleyDB , yang sangat matang dan berkinerja baik. Mereka memiliki Java API yang membungkus Collections API, sehingga Anda dapat dengan mudah membuat peta besar yang sewenang-wenang dengan sedikit jejak memori. Akses akan lebih lambat (karena disimpan di disk).

Pertanyaan lanjutan : apakah ada perpustakaan yang layak (dan efisien), terpelihara dengan baik, untuk koleksi yang tidak dapat diubah? Clojure memiliki dukungan yang sangat baik untuk ini, dan alangkah baiknya memiliki sesuatu yang serupa untuk Java.