it-swarm-id.com

Cara paling efisien untuk meningkatkan nilai Peta di Java

Saya harap pertanyaan ini tidak dianggap terlalu mendasar untuk forum ini, tetapi kita lihat saja nanti. Saya bertanya-tanya bagaimana cara memperbaiki beberapa kode untuk kinerja yang lebih baik yang dijalankan beberapa kali.

Katakanlah saya sedang membuat daftar frekuensi Word, menggunakan Peta (mungkin HashMap), di mana setiap kunci adalah String dengan Word yang sedang dihitung dan nilainya adalah Integer yang bertambah setiap kali token Kata ditemukan.

Dalam Perl, menambahkan nilai seperti itu akan mudah:

$map{$Word}++;

Tetapi di Jawa, ini jauh lebih rumit. Di sini cara saya saat ini melakukannya:

int count = map.containsKey(Word) ? map.get(Word) : 0;
map.put(Word, count + 1);

Yang tentu saja bergantung pada fitur autoboxing dalam versi Java yang lebih baru. Saya ingin tahu apakah Anda dapat menyarankan cara yang lebih efisien untuk meningkatkan nilai seperti itu. Apakah ada alasan kinerja yang baik untuk menghindari kerangka kerja Koleksi dan menggunakan sesuatu yang lain sebagai gantinya?

Pembaruan: Saya telah melakukan tes beberapa jawaban. Lihat di bawah.

338
gregory

Beberapa hasil tes

Saya mendapat banyak jawaban yang bagus untuk pertanyaan ini - terima kasih semuanya - jadi saya memutuskan untuk menjalankan beberapa tes dan mencari tahu metode mana yang sebenarnya paling cepat. Lima metode yang saya uji adalah:

  • metode "ContainsKey" yang saya sajikan pertanyaan
  • metode "TestForNull" yang disarankan oleh Aleksandar Dimitrov
  • metode "AtomicLong" yang disarankan oleh Hank Gay
  • metode "Trove" yang disarankan oleh jrudolph
  • metode "MutableInt" yang disarankan oleh phax.myopenid.com

Metode

Inilah yang saya lakukan ...

  1. menciptakan lima kelas yang identik kecuali untuk perbedaan yang ditunjukkan di bawah ini. Setiap kelas harus melakukan operasi khas skenario yang saya sajikan: membuka file 10MB dan membacanya, kemudian melakukan penghitungan frekuensi semua token Word dalam file. Karena ini mengambil rata-rata hanya 3 detik, saya sudah melakukan penghitungan frekuensi (bukan I/O) 10 kali.
  2. menghitung waktu pengulangan 10 iterasi tetapi bukan operasi I/O dan mencatat total waktu yang diambil (dalam detik jam) pada dasarnya menggunakan metode Ian Darwin dalam Java Cookbook .
  3. melakukan semua lima tes secara seri, dan kemudian melakukan ini tiga kali lagi.
  4. rata-rata empat hasil untuk setiap metode.

Hasil

Saya akan mempresentasikan hasil pertama dan kode di bawah ini untuk mereka yang tertarik.

Metode ContainsKey adalah, seperti yang diharapkan, paling lambat, jadi saya akan memberikan kecepatan setiap metode dibandingkan dengan kecepatan metode itu.

  • ContainsKey: 30.654 detik (garis dasar)
  • AtomicLong: 29,780 detik (1,03 kali lebih cepat)
  • TestForNull: 28,804 detik (1,06 kali lebih cepat)
  • Trove: 26,313 detik (1,16 kali lebih cepat)
  • MutableInt: 25,747 detik (1,19 kali lebih cepat)

Kesimpulan

Tampaknya hanya metode MutableInt dan metode Trove yang secara signifikan lebih cepat, hanya mereka yang memberikan peningkatan kinerja lebih dari 10%. Namun, jika threading adalah masalah, AtomicLong mungkin lebih menarik daripada yang lain (saya tidak begitu yakin). Saya juga menjalankan variabel TestForNull dengan variabel final, tetapi perbedaannya dapat diabaikan.

Perhatikan bahwa saya belum membuat profil penggunaan memori dalam berbagai skenario. Saya akan senang mendengar dari siapa pun yang memiliki wawasan yang baik tentang bagaimana metode MutableInt dan Trove akan mempengaruhi penggunaan memori.

Secara pribadi, saya menemukan metode MutableInt yang paling menarik, karena tidak perlu memuat kelas pihak ketiga. Jadi, kecuali saya menemukan masalah dengan itu, itulah cara saya kemungkinan besar pergi.

Kode

Berikut adalah kode penting dari setiap metode.

Berisi kunci

import Java.util.HashMap;
import Java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(Word) ? freq.get(Word) : 0;
freq.put(Word, count + 1);

TestForNull

import Java.util.HashMap;
import Java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(Word);
if (count == null) {
    freq.put(Word, 1);
}
else {
    freq.put(Word, count + 1);
}

AtomicLong

import Java.util.concurrent.ConcurrentHashMap;
import Java.util.concurrent.ConcurrentMap;
import Java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map = 
    new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(Word, new AtomicLong(0));
map.get(Word).incrementAndGet();

Harta karun

import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(Word, 1, 1);

MutableInt

import Java.util.HashMap;
import Java.util.Map;
...
class MutableInt {
  int value = 1; // note that we start at 1 since we're counting
  public void increment () { ++value;      }
  public int  get ()       { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(Word);
if (count == null) {
    freq.put(Word, new MutableInt());
}
else {
    count.increment();
}
348
gregory

OK, mungkin pertanyaan lama, tapi ada cara yang lebih pendek dengan Java 8:

Map.merge(key, 1, Integer::sum)

Kegunaan: jika kunci tidak ada, masukkan 1 sebagai nilai , jika tidak jumlah 1 dengan nilai yang ditautkan ke kunci . Informasi lebih lanjut di sini

190
LE GALL Benoît

Sebuah penelitian kecil pada tahun 2016: https://github.com/leventov/Java-Word-count , kode sumber patokan

Hasil terbaik per metode (lebih kecil lebih baik):

                 time, ms
kolobokeCompile  18.8
koloboke         19.8
trove            20.8
fastutil         22.7
mutableInt       24.3
atomicInteger    25.3
Eclipse          26.9
hashMap          28.0
hppc             33.6
hppcRt           36.5

Hasil waktu\ruang: 

42
leventov

Google Jamb adalah teman Anda ...

... setidaknya dalam beberapa kasus. Mereka memiliki Nice ini AtomicLongMap . Terutama bagus karena Anda berurusan dengan panjang sebagai nilai di peta Anda.

Misalnya.

AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(Word);

Juga dimungkinkan untuk menambahkan lebih dari 1 ke nilai:

map.getAndAdd(Word, 112L); 
33
H6.

@Hank Gay

Sebagai tindak lanjut dari komentar saya (yang agak tidak berguna): Trove sepertinya cara yang harus dilakukan. Jika, untuk alasan apa pun, Anda ingin tetap menggunakan JDK standar, ConcurrentMap dan AtomicLong dapat membuat kode menjadi tiny sedikit lebih baik, meskipun YMMV.

    final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.putIfAbsent("foo", new AtomicLong(0));
    map.get("foo").incrementAndGet();

akan meninggalkan 1 sebagai nilai di peta untuk foo. Secara realistis, peningkatan keramahan terhadap threading adalah semua yang harus direkomendasikan oleh pendekatan ini.

31
Hank Gay

Itu selalu merupakan ide yang baik untuk melihat Perpustakaan Koleksi Google untuk hal semacam ini. Dalam hal ini a Multiset akan melakukan trik:

Multiset bag = Multisets.newHashMultiset();
String Word = "foo";
bag.add(Word);
bag.add(Word);
System.out.println(bag.count(Word)); // Prints 2

Ada metode seperti Peta untuk iterasi kunci/entri, dll. Secara internal implementasi saat ini menggunakan HashMap<E, AtomicInteger>, sehingga Anda tidak akan dikenakan biaya tinju.

25
Chris Nokleberg
Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0);
map.put(key, count + 1);

Dan itulah bagaimana Anda menambah nilai dengan kode sederhana.

Manfaat:

  • Tidak membuat kelas lain untuk int bisa berubah
  • Kode pendek
  • Mudah dimengerti
  • Tidak ada pengecualian pointer nol

Cara lain adalah dengan menggunakan metode penggabungan, tetapi ini terlalu banyak untuk hanya menambah nilai.

map.merge(key, 1, (a,b) -> a+b);

Saran: Anda harus lebih memperhatikan pembacaan kode lebih dari sedikit peningkatan kinerja di sebagian besar waktu.

21
off99555

Anda harus menyadari fakta bahwa upaya awal Anda

int count = map.containsKey (Word)? map.get (Word): 0;

mengandung dua operasi yang berpotensi mahal pada peta, yaitu containsKey dan get. Yang pertama melakukan operasi yang berpotensi sangat mirip dengan yang terakhir, jadi Anda melakukan pekerjaan yang sama dua kali!

Jika Anda melihat API untuk Peta, operasi get biasanya mengembalikan null ketika peta tidak mengandung elemen yang diminta.

Perhatikan bahwa ini akan membuat solusi seperti

map.put (kunci, map.get (kunci) +1);

berbahaya, karena dapat menghasilkan NullPointerExceptions. Anda harus memeriksa null terlebih dahulu.

Juga mencatat, dan ini sangat penting, bahwa HashMaps can mengandung nulls menurut definisi. Jadi tidak setiap null yang dikembalikan mengatakan "tidak ada elemen seperti itu". Dalam hal ini, containsKey berperilaku berbeda dari get dalam memberi tahu Anda apakah ada elemen seperti itu. Lihat API untuk detailnya.

Namun, untuk kasus Anda, Anda mungkin tidak ingin membedakan antara null yang disimpan dan "noSuchElement". Jika Anda tidak ingin mengizinkan nulls Anda mungkin lebih suka Hashtable. Menggunakan perpustakaan pembungkus seperti yang sudah diusulkan dalam jawaban lain mungkin merupakan solusi yang lebih baik untuk perawatan manual, tergantung pada kompleksitas aplikasi Anda.

Untuk menyelesaikan jawaban (dan saya lupa memasukkannya pada awalnya, berkat fungsi edit!), Cara terbaik untuk melakukannya secara native, adalah dengan get menjadi variabel final, periksa null dan put kembali dengan 1. Variabelnya harus final karena tetap tidak bisa diubah. Kompilator mungkin tidak memerlukan petunjuk ini, tetapi lebih jelas seperti itu.

 peta HashMap akhir = menghasilkanRandomHashMap (); 
 kunci Objek akhir = fetchSomeKey (); 
 Integer akhir i = map.get (kunci); 
 if (i ! = null) {
 map.put (i +1); 
} lain {
 // lakukan sesuatu 
} 

Jika Anda tidak ingin mengandalkan autoboxing, Anda harus mengatakan sesuatu seperti map.put(new Integer(1 + i.getValue())); sebagai gantinya.

21

Cara lain akan membuat integer yang bisa berubah:

class MutableInt {
  int value = 0;
  public void inc () { ++value; }
  public int get () { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt> ();
MutableInt value = map.get (key);
if (value == null) {
  value = new MutableInt ();
  map.put (key, value);
} else {
  value.inc ();
}

tentu saja ini menyiratkan membuat objek tambahan tetapi overhead dibandingkan dengan membuat Integer (bahkan dengan Integer.valueOf) seharusnya tidak terlalu banyak.

18
Philip Helger

Anda dapat menggunakan metode computeIfAbsent di antarmuka Map yang disediakan di Java 8 .

final Map<String,AtomicLong> map = new ConcurrentHashMap<>();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("B", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); //[A=2, B=1]

Metode computeIfAbsent memeriksa apakah kunci yang ditentukan sudah dikaitkan dengan nilai atau tidak? Jika tidak ada nilai terkait maka ia mencoba menghitung nilainya menggunakan fungsi pemetaan yang diberikan. Dalam setiap kasus itu mengembalikan nilai saat ini (yang ada atau dihitung) yang terkait dengan kunci yang ditentukan, atau nol jika nilai yang dihitung adalah nol.

Di samping catatan jika Anda memiliki situasi di mana beberapa utas memperbarui jumlah umum Anda dapat melihat LongAdder class. Di bawah pertentangan tinggi, throughput yang diharapkan dari kelas ini secara signifikan lebih tinggi daripada AtomicLong, dengan biaya konsumsi ruang yang lebih tinggi.

10
i_am_zero

Rotasi memori dapat menjadi masalah di sini, karena setiap tinju int yang lebih besar dari atau sama dengan 128 menyebabkan alokasi objek (lihat Integer.valueOf (int)). Meskipun pengumpul sampah sangat efisien menangani benda-benda berumur pendek, kinerja akan sedikit menurun.

Jika Anda tahu bahwa jumlah peningkatan yang dilakukan sebagian besar akan melebihi jumlah kunci (= kata dalam hal ini), pertimbangkan menggunakan int holder sebagai gantinya. Phax sudah menyajikan kode untuk ini. Ini dia lagi, dengan dua perubahan (kelas pemegang dibuat statis dan nilai awal diatur ke 1):

static class MutableInt {
  int value = 1;
  void inc() { ++value; }
  int get() { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt>();
MutableInt value = map.get(key);
if (value == null) {
  value = new MutableInt();
  map.put(key, value);
} else {
  value.inc();
}

Jika Anda membutuhkan kinerja ekstrem, cari implementasi Peta yang langsung disesuaikan dengan tipe nilai primitif. jrudolph disebutkan GNU Trove .

Omong-omong, istilah penelusuran yang bagus untuk subjek ini adalah "histogram".

7
volley

Alih-alih memanggil containKey () lebih cepat hanya untuk memanggil map.get dan periksa apakah nilai yang dikembalikan adalah nol atau tidak.

    Integer count = map.get(Word);
    if(count == null){
        count = 0;
    }
    map.put(Word, count + 1);
5
Glever

Ada beberapa pendekatan:

  1. Gunakan aloritma Bag seperti set yang terdapat di Google Collections.

  2. Buat wadah yang bisa berubah yang dapat Anda gunakan di Peta:


    class My{
        String Word;
        int count;
    }

Dan gunakan put ("Word", new My ("Word")); Kemudian Anda dapat memeriksa apakah ada dan bertambah saat menambahkan.

Hindari menggulung solusi Anda sendiri menggunakan daftar, karena jika Anda mencari dan menyortir innerloop, kinerja Anda akan berbau busuk. Solusi HashMap pertama sebenarnya cukup cepat, tetapi yang tepat seperti yang ditemukan di Google Collections mungkin lebih baik.

Menghitung kata-kata menggunakan Google Collections, terlihat seperti ini:



    HashMultiset s = new HashMultiset();
    s.add("Word");
    s.add("Word");
    System.out.println(""+s.count("Word") );

Menggunakan HashMultiset cukup elegan, karena bag-algoritme hanya yang Anda butuhkan saat menghitung kata-kata.

3
tovare

Google Collections HashMultiset:
- cukup elegan untuk digunakan
- tetapi konsumsi CPU dan memori

Yang terbaik adalah memiliki metode seperti: Entry<K,V> getOrPut(K); (elegan, dan biaya rendah)

Metode seperti itu akan menghitung hash dan indeks hanya sekali, dan kemudian kita bisa melakukan apa yang kita inginkan dengan entri (baik mengganti atau memperbarui nilainya).

Lebih elegan:
- ambil HashSet<Entry>
- perluas sehingga get(K) memasukkan Entri baru jika diperlukan
- Entri bisa menjadi objek Anda sendiri.
-> (new MyHashSet()).get(k).increment();

3
the felis leo

Variasi pada pendekatan MutableInt yang mungkin lebih cepat, jika sedikit peretasan, adalah dengan menggunakan array int elemen tunggal:

Map<String,int[]> map = new HashMap<String,int[]>();
...
int[] value = map.get(key);
if (value == null) 
  map.put(key, new int[]{1} );
else
  ++value[0];

Akan menarik jika Anda bisa mengulang tes kinerja Anda dengan variasi ini. Mungkin yang tercepat.


Sunting: Pola di atas bekerja dengan baik untuk saya, tetapi akhirnya saya berubah menggunakan koleksi Trove untuk mengurangi ukuran memori di beberapa peta yang sangat besar yang saya buat - dan sebagai bonus itu juga lebih cepat.

Satu fitur yang sangat bagus adalah bahwa kelas TObjectIntHashMap memiliki panggilan adjustOrPutValue tunggal, tergantung pada apakah sudah ada nilai pada kunci itu, apakah akan meletakkan nilai awal atau menambah nilai yang ada. Ini sempurna untuk menambah:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);

Saya pikir solusi Anda akan menjadi cara standar, tetapi - seperti yang Anda catat sendiri - itu mungkin bukan cara tercepat yang mungkin.

Anda dapat melihat GNU Trove . Itu adalah perpustakaan yang berisi segala macam Koleksi primitif cepat. Contoh Anda akan menggunakan TObjectIntHashMap yang memiliki metode AdjustOrPutValue yang melakukan apa yang Anda inginkan.

3
jrudolph

Apakah Anda yakin ini adalah hambatan? Sudahkah Anda melakukan analisis kinerja?

Coba gunakan profiler NetBeans (gratis dan dibangun dalam NB 6.1) untuk melihat hotspot.

Akhirnya, peningkatan JVM (katakanlah dari 1,5-> 1,6) seringkali merupakan penambah kinerja yang murah. Bahkan peningkatan jumlah build dapat memberikan peningkatan kinerja yang baik. Jika Anda menjalankan pada Windows dan ini adalah aplikasi kelas server, gunakan -server pada baris perintah untuk menggunakan Server Hotspot JVM. Pada mesin Linux dan Solaris ini terdeteksi secara otomatis.

3
John Wright

Cukup sederhana, cukup gunakan fungsi bawaan di Map.Java sebagai diikuti

map.put(key, map.getOrDefault(key, 0) + 1);
2
sudoz

"put" need "get" (untuk memastikan tidak ada kunci duplikat).
Jadi langsung lakukan "put",
dan jika ada nilai sebelumnya, maka lakukan penambahan:

Map map = new HashMap ();

MutableInt newValue = new MutableInt (1); // default = inc
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
  newValue.add(oldValue); // old + inc
}

Jika hitungan dimulai dari 0, maka tambahkan 1: (atau nilai lainnya ...)

Map map = new HashMap ();

MutableInt newValue = new MutableInt (0); // default
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
  newValue.setValue(oldValue + 1); // old + inc
}

Pemberitahuan: Kode ini bukan utas aman. Gunakan untuk membangun lalu gunakan peta, bukan untuk memperbaruinya secara bersamaan.

Optimasi: Dalam satu lingkaran, pertahankan nilai lama untuk menjadi nilai baru dari loop berikutnya.

Map map = new HashMap ();
final int defaut = 0;
final int inc = 1;

MutableInt oldValue = new MutableInt (default);
while(true) {
  MutableInt newValue = oldValue;

  oldValue = map.put (key, newValue); // insert or...
  if (oldValue != null) {
    newValue.setValue(oldValue + inc); // ...update

    oldValue.setValue(default); // reuse
  } else
    oldValue = new MutableInt (default); // renew
  }
}
2
the felis leo

Jika Anda menggunakan Eclipse Collections , Anda dapat menggunakan HashBag. Ini akan menjadi pendekatan yang paling efisien dalam hal penggunaan memori dan juga akan bekerja dengan baik dalam hal kecepatan eksekusi.

HashBag didukung oleh MutableObjectIntMap yang menyimpan int primitif alih-alih objek Counter. Ini mengurangi overhead memori dan meningkatkan kecepatan eksekusi.

HashBag menyediakan API yang Anda perlukan karena ini Collection yang juga memungkinkan Anda untuk menanyakan jumlah kemunculan suatu item.

Berikut ini contoh dari Eclipse Collections Kata .

MutableBag<String> bag =
  HashBag.newBagWith("one", "two", "two", "three", "three", "three");

Assert.assertEquals(3, bag.occurrencesOf("three"));

bag.add("one");
Assert.assertEquals(2, bag.occurrencesOf("one"));

bag.addOccurrences("one", 4);
Assert.assertEquals(6, bag.occurrencesOf("one"));

Catatan: Saya seorang committer untuk Eclipse Collections.

1
Craig P. Motlin

Saya akan menggunakan Apache Collections Lazy Map (untuk menginisialisasi nilai ke 0) dan menggunakan MutableIntegers dari Apache Lang sebagai nilai di peta itu.

Biaya terbesar adalah harus menyisir peta dua kali dalam metode Anda. Di tangan saya, Anda harus melakukannya sekali saja. Cukup dapatkan nilainya (akan diinisialisasi jika tidak ada) dan tambahkan.

1
jb.

Datastructure Functional Java library TreeMap memiliki metode update di kepala utama terbaru:

public TreeMap<K, V> update(final K k, final F<V, V> f)

Contoh penggunaan:

import static fj.data.TreeMap.empty;
import static fj.function.Integers.add;
import static fj.pre.Ord.stringOrd;
import fj.data.TreeMap;

public class TreeMap_Update
  {public static void main(String[] a)
    {TreeMap<String, Integer> map = empty(stringOrd);
     map = map.set("foo", 1);
     map = map.update("foo", add.f(1));
     System.out.println(map.get("foo").some());}}

Program ini mencetak "2".

1
Apocalisp

Saya tidak tahu seberapa efisien itu tetapi kode di bawah ini juga berfungsi. Anda harus mendefinisikan BiFunction di awal. Plus, Anda dapat membuat lebih dari sekadar peningkatan dengan metode ini.

public static Map<String, Integer> strInt = new HashMap<String, Integer>();

public static void main(String[] args) {
    BiFunction<Integer, Integer, Integer> bi = (x,y) -> {
        if(x == null)
            return y;
        return x+y;
    };
    strInt.put("abc", 0);


    strInt.merge("abc", 1, bi);
    strInt.merge("abc", 1, bi);
    strInt.merge("abc", 1, bi);
    strInt.merge("abcd", 1, bi);

    System.out.println(strInt.get("abc"));
    System.out.println(strInt.get("abcd"));
}

output adalah

3
1
1
MGoksu

Berbagai pembungkus primitif, misalnya, Integer tidak dapat diubah sehingga benar-benar tidak ada cara yang lebih ringkas untuk melakukan apa yang Anda minta kecuali Anda dapat melakukannya dengan sesuatu seperti AtomicLong . Saya bisa mencobanya sebentar lagi dan memperbarui. BTW, Hashtable adalah bagian dari Collections Framework .

1
Hank Gay

@Vantantas Baranauskas: Mengenai jawaban ini, saya akan berkomentar jika saya memiliki poin rep, tapi saya tidak. Saya ingin mencatat bahwa kelas Counter didefinisikan TIDAK ada thread-safe karena tidak cukup hanya menyinkronkan inc () tanpa nilai sinkronisasi (). Nilai panggilan utas lainnya () tidak dijamin untuk melihat nilai kecuali jika hubungan yang terjadi sebelum hubungan telah terjadi dengan pembaruan.

1
Alex Miller