it-swarm-tr.com

Bir Harita değerini artırmak için en etkili yol Java

Umarım bu soru bu forum için çok basit sayılmaz, ancak göreceğiz. Birkaç kez çalıştırılan daha iyi performans için bazı kodları nasıl yeniden düzenleyeceğimi merak ediyorum.

Diyelim ki her anahtar sayılan bir Kelime ile bir Dize ve değer, her bir Kelime belirteci bulunduğunda artan bir Tamsayıdır.

Perl'de, böyle bir değeri arttırmak çok kolay olacaktır:

$map{$Word}++;

Ancak Java'da, çok daha karmaşık. İşte şu anda yapıyorum yolu:

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

Tabii ki hangisi daha yeni Java sürümlerinde otomatik kutulama özelliğine güveniyor? Böyle bir değeri arttırmanın daha etkili bir yolunu önerebilir misiniz merak ediyorum. Koleksiyonlar çerçevesinden kaçmak ve bunun yerine başka bir şey kullanmak için iyi performans nedenleri var mı?

Güncelleme: Cevaplarından birkaç tanesini test ettim. Aşağıya bakınız.

338
gregory

Bazı test sonuçları

Bu soruya çok iyi cevaplar aldım - millet - bu yüzden bazı testler yapmaya ve hangi yöntemin en hızlı olduğunu bulmaya karar verdim. Test ettiğim beş yöntem şunlardır:

  • 'de sunduğum "ContainsKey" yöntemi sor
  • aleksandar Dimitrov tarafından önerilen "TestForNull" yöntemi
  • hank Gay tarafından önerilen "AtomicLong" yöntemi
  • jrudolph tarafından önerilen "Trove" yöntemi
  • phax.myopenid.com tarafından önerilen "MutableInt" yöntemi

Yöntem

İşte yaptığım şey ...

  1. aşağıda gösterilen farklılıklar dışında aynı olan beş sınıf oluşturdu. Her sınıf, sunduğum senaryonun tipik bir işlemini yapmak zorundaydı: 10 MB'lık bir dosyayı açmak ve okumak, ardından dosyadaki tüm Word belirteçlerinin sıklık sayısını gerçekleştirmek. Bu sadece ortalama 3 saniye sürdüğü için, frekans sayacını 10 kez (I/O değil) gerçekleştirdi.
  2. 10 yinelemeli döngüyü zamanladı, ancak G/Ç işlemini değil ve esasen Ian Darwin'in yöntemindeki Java Yemek Tarifleri .
  3. beş testin tümünü seri olarak gerçekleştirdi ve sonra bunu üç kez daha yaptım.
  4. her yöntemin dört sonucunun ortalaması alındı.

Sonuçlar

İlgilenenler için önce sonuçları ve aşağıdaki kodu sunacağım.

ContainsKey yöntemi beklendiği gibi yavaştı, bu yüzden her yöntemin hızını o yöntemin hızına göre vereceğim.

  • ContainsKey: 30.654 saniye (temel)
  • AtomicLong: 29.780 saniye (en az 1.03 kez)
  • TestForNull: 28.804 saniye (en az 1.06 kez)
  • Cesur: 26.313 saniye (en az 1.16 kez)
  • MutableInt: 25.747 saniye (en az 1.19 kez)

Sonuçlar

Sadece MutableInt yönteminin ve Trove yönteminin, sadece% 10'dan daha fazla bir performans artışı sağladıkları için önemli ölçüde daha hızlı olduğu görülecektir. Ancak, diş açma bir sorun ise, AtomicLong diğerlerinden daha çekici olabilir (Gerçekten emin değilim). Ayrıca TestForNull'u final değişkenleriyle çalıştırdım, ancak fark önemsizdi.

Farklı senaryolarda hafıza kullanımını profillemediğimi unutmayın. MutableInt ve Trove yöntemlerinin bellek kullanımını nasıl etkileyebileceği konusunda iyi bir kavrayışı olan herhangi birinden duymaktan mutluluk duyarım.

Şahsen, MutableInt yöntemini en çekici buluyorum, çünkü herhangi bir üçüncü taraf sınıfı yüklemeyi gerektirmiyor. Bu yüzden onunla sorunları bulamazsam, gitme ihtimalim bu.

Kod

İşte her yöntemden çok önemli bir kod.

ContainsKey

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();

Define

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

Tamam, eski bir soru olabilir, ancak Java 8 ile daha kısa bir yol var:

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

Ne yapar: tuşu yoksa, 1 değerini değer olarak koyun, aksi takdirde sum 1 tuşuna bağlanan değere. Daha fazla bilgi burada

190
LE GALL Benoît

2016'da küçük bir araştırma: https://github.com/leventov/Java-Word-count , referans kaynak kod

Yöntem başına en iyi sonuç (daha küçük daha iyidir):

                 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

Time\space sonuçları: 

42
leventov

Google Guava arkadaşınız ...

... en azından bazı durumlarda. Bu Nice var AtomicLongMap . Özellikle Güzel, çünkü haritanızda değer olarak uzun ile uğraşıyorsunuz.

Örneğin.

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

Ayrıca, değere 1'den fazla eklemek mümkündür:

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

@Hank Gay

Kendi yorumumun takibi olarak (oldukça işe yaramaz) yorum: Trove gitmenin yolu gibi görünüyor. Sebep ne olursa olsun, JDK standartlarına uymak istiyorsanız, ConcurrentMap ve AtomicLong kodu bir küçük yapabilir YMMV olsa biraz daha güzel.

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

foo için haritadaki değer olarak 1 bırakılacaktır. Gerçekçi olarak, diş açmaya karşı daha fazla kolaylık bu yaklaşımın tavsiye ettiği tek şey.

31
Hank Gay

Bu tür şeyler için Google Koleksiyonlar Kütüphanesi 'e bakmak her zaman iyi bir fikirdir. Bu durumda bir Multiset hile yapacak:

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

Anahtarlar/girişler vb. Üzerinde yineleme yapmak için Harita benzeri yöntemler vardır. Dahili olarak şu anda bir HashMap<E, AtomicInteger> kullanır, bu nedenle boks masraflarına maruz kalmazsınız.

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);

Ve bu şekilde basit kodla bir değeri artırıyorsunuz.

Yarar:

  • Mutable int için başka bir sınıf oluşturmuyor
  • Kısa kod
  • Anlaması kolay
  • Boş işaretçi istisnası yok

Başka bir yol birleştirme yöntemi kullanmaktır, ancak bu yalnızca bir değeri artırmak için çok fazla.

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

Öneri: çoğu zaman kod okunabilirliğini az performans elde etmekten daha fazla önemsemelisiniz.

21
off99555

Başka bir yol da değişken bir tamsayı oluşturmak olabilir:

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 ();
}

tabii ki bu, ek bir nesne yaratmayı gerektirir ancak bir Tamsayı oluşturmaya kıyasla ek yük (Integer.valueOf ile bile) çok fazla olmamalıdır.

18
Philip Helger

Java 8 'de sağlanan Map arabiriminde computeIfAbsent yöntemini kullanabilirsiniz.

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]

computeIfAbsent yöntemi, belirtilen anahtarın bir değerle zaten ilişkilendirilmiş olup olmadığını kontrol eder? İlişkilendirilmiş bir değer yoksa, verilen haritalama fonksiyonunu kullanarak değerini hesaplamaya çalışır. Her durumda, belirtilen anahtarla ilişkilendirilmiş geçerli (varolan veya hesaplanan) değeri veya hesaplanan değer null ise null değerini döndürür.

Yan notta, birden fazla iş parçacığının ortak bir toplamı güncellemesi durumu varsa, göz atabilirsiniz LongAdder class. Yüksek çekişme durumunda, bu sınıfın beklenen verimi pahasına AtomicLong değerinden oldukça yüksektir daha yüksek alan tüketimi.

10
i_am_zero

Bellek dönüşü burada bir sorun olabilir, çünkü 128'den büyük veya 128'e eşit bir int kutucuğu nesne tahsisine neden olur (bakınız Integer.valueOf (int)). Her ne kadar çöp toplayıcı kısa ömürlü nesnelerle çok verimli bir şekilde ilgilense de, performans bir dereceye kadar acı çekecektir.

Yapılan artış sayısının, anahtar sayısının (= bu durumda sözcükler) büyük oranda fazla olacağını biliyorsanız, bunun yerine bir int tutucu kullanmayı düşünün. Phax bunun için zaten bir kod sundu. İki değişiklikle tekrar burada (tutucu sınıfı statik ve ilk değer 1 olarak ayarlandı):

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();
}

Aşırı performansa ihtiyacınız varsa, doğrudan ilkel değer türlerine göre düzenlenmiş bir Harita uygulaması arayın. jrudolph bahsetti GNU Trove .

Bu arada, bu konu için iyi bir arama terimi "histogram" dır.

7
volley

İncludeKey () işlevini çağırmak yerine sadece map.get işlevini çağırmak ve döndürülen değerin boş olup olmadığını kontrol etmek daha hızlıdır.

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

Birkaç yaklaşım var:

  1. Google Koleksiyonlar’in içerdiği setler gibi bir Çanta aloritması kullanın.

  2. Harita'da kullanabileceğiniz değişken konteyner oluşturun:


    class My{
        String Word;
        int count;
    }

Ve put kullanın ("Word", yeni My ("Word")); Sonra ekleyip eklemediğini kontrol edebilir ve artırabilirsin.

Listeleri kullanarak kendi çözümünüzü almaktan kaçının çünkü dahili döngüde arama ve sıralama yaparsanız performansınız kötüleşir. İlk HashMap çözümü aslında oldukça hızlı, ancak Google Koleksiyonlar’de bulunanlar gibi daha uygun bir olasılıkla daha iyi.

Google Koleksiyonlar kullanarak kelimeleri saymak, şuna benzer:



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

HashMultiset'i kullanmak oldukça zarif, çünkü sözcükleri sayarken ihtiyacınız olan şey bir çanta algoritması.

3
tovare

Google Koleksiyonlar HashMultiset:
- kullanımı oldukça zarif
- fakat CPU ve hafıza kullan

En iyisi şunun gibi bir yöntemin olması olabilir: Entry<K,V> getOrPut(K); (şık ve düşük maliyetli)

Böyle bir yöntem karma ve indeksi yalnızca bir kez hesaplar ve sonra girişle istediğimizi yapabiliriz (değeri değiştirin veya güncelleyin).

Daha zarif:
- bir HashSet<Entry> al
- gerekirse uzatın get(K) gerekirse yeni bir Giriş girin
- Giriş, kendi nesneniz olabilir.
-> (new MyHashSet()).get(k).increment();

3
the felis leo

MutableInt yaklaşımında biraz daha kesmek daha hızlı olabilecek bir değişiklik, tek elemanlı bir int dizisi kullanmaktır:

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];

Performans testlerinizi bu varyasyonla tekrar başlatabilirseniz ilginç olurdu. En hızlı olabilir.


Düzenleme: Yukarıdaki desen benim için iyi çalıştı, ama nihayetinde oluşturduğum çok büyük haritalarda hafıza boyutunu azaltmak için Trove koleksiyonlarını kullanmak üzere değiştim - ve bonus olarak da daha hızlıydı.

Gerçekten güzel bir özellik, TObjectIntHashMap sınıfının tek bir adjustOrPutValue çağrısına sahip olması, bu anahtarda zaten bir değer olup olmadığına bağlı olarak, başlangıç ​​değerini koyacak veya mevcut değeri artıracaktır. Bu artış için mükemmeldir:

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

Çözümünüzün standart yol olacağını düşünüyorum, ancak - sizin de belirttiğiniz gibi - muhtemelen en hızlı yol bu değildir.

Bakabilirsiniz GNU Trove . Her türlü hızlı ilkel koleksiyon içeren bir kütüphane. Örnekte, tam olarak ne istiyorsan onu yapan adjustOrPutValue yöntemine sahip bir TObjectIntHashMap kullanılır.

3
jrudolph

Bunun bir tıkanıklık olduğundan emin misin? Herhangi bir performans analizi yaptınız mı?

Sıcak noktalara bakmak için NetBeans profilleyicisini (ücretsiz ve NB 6.1 içine yerleştirilmiş) kullanmayı deneyin.

Son olarak, bir JVM yükseltmesi (örneğin 1.5-> 1.6) genellikle ucuz bir performans artırıcısıdır. Yapı sayısındaki bir yükseltme bile iyi performans artışı sağlayabilir. Windows üzerinde çalışıyorsanız ve bu bir sunucu sınıfı uygulamasıysa, Server Hotspot JVM'yi kullanmak için komut satırında -server kullanın. Linux ve Solaris makinelerinde bu otomatik olarak belirlenir.

3
John Wright

Oldukça basit, aşağıdaki gibi Map.Java içindeki yerleşik işlevi kullanın.

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

"put" need "get" (yinelenen anahtar olmadığından emin olmak için).
Öyleyse doğrudan "koymak" yapın,
ve önceki bir değer varsa, o zaman bir ekleme yapın:

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
}

Sayı 0'dan başlıyorsa, 1: ekleyin (veya başka değerler ...)

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
}

Notice: Bu kod güvenli bir konu değil. Oluşturmak için kullanın, ardından eşzamanlı olarak güncellemek için haritayı kullanın.

Optimizasyon: Bir döngüde, bir sonraki döngünün yeni değeri olmak için eski değeri koruyun.

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

Eclipse Collections kullanıyorsanız, HashBag kullanabilirsiniz. Bellek kullanımı açısından en verimli yaklaşım olacak ve aynı zamanda yürütme hızı açısından iyi performans gösterecektir.

HashBag, MutableObjectIntMap nesneleri yerine ilkel girişleri depolayan bir Counter tarafından desteklenir. Bu, bellek ek yükünü azaltır ve yürütme hızını artırır.

HashBag, bir öğenin oluşum sayısını sorgulamanıza izin veren bir Collection olduğundan ihtiyacınız olan API'yi sağlar.

İşte Eclipse Collections Kata'dan bir örnek.

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"));

Not: Eclipse Koleksiyonlar için bir yorumcuyum.

1
Craig P. Motlin

Apache Collections Lazy Map'i kullanırdım (değerleri sıfırlamak için) ve Apache Lang'ten MutableIntegers'i o haritadaki değerler olarak kullanırdım.

En büyük maliyet, yönteminizde haritayı iki kez selamlamak zorunda kalmaktır. Benimki sadece bir kez yapmak zorunda. Sadece (varsa) başlatılacak) değerini alın ve artırın.

1
jb.

Functional Java kütüphanesinin TreeMap veri yapısı en son ana hat başlığında update yöntemine sahiptir:

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

Örnek kullanım:

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());}}

Bu program "2" yazdırır.

1
Apocalisp

Ne kadar etkili olduğunu bilmiyorum ama aşağıdaki kod da işe yarıyor. Başlangıçta BiFunction tanımlamanız gerekiyor. Ayrıca, bu yöntemle artıştan daha fazlasını yapabilirsiniz.

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"));
}

çıktı

3
1
1
MGoksu

Çeşitli ilkel sarmalayıcılar, örneğin, Integer değiştirilemez, bu yüzden ne istediğinizi yapmak için daha özlü bir yol yoktur yapamazsanız AtomicLong gibi bir şeyle yapın. Bir dakika içinde gidip güncelleme yapabilirim. BTW, Hashtable --- Collections Framework 'in bir parçasıdır.

1
Hank Gay

@Vilmantas Baranauskas: Bu cevapla ilgili olarak, eğer puan puanım olsaydı, yorum yapardım, ama bilmiyordum. Orada tanımlanan Counter sınıfının, (() değerini senkronize etmeden sadece inc () 'i senkronize etmek için yeterli olmadığından, iş parçacığı güvenli DEĞİL olduğunu not etmek istedim. Value ile () çağıran diğer iş parçacıklarının, güncelleme ile bir ilişki kurmadan önce, değeri görmesi garanti edilmez.

1
Alex Miller