Javaで効率的なカウンタ
2918 ワード
プログラミングではカウンターとしてHashMapがよく使われるが,本稿では3つの実装方法を簡単に紹介する
1つ目は、最も直感的なカウンタです.
この方式では、ループごとにMapにKeyが含まれているかどうかをチェックし、含まれている場合は元の値+1を再保存し、存在しない場合は直接保存する1.この方式が最も簡単で直接的な方式であるが、最も有効な方法ではなく、その低効率な原因:
1.キー(a)が既に存在する場合、containsKey()メソッドとget()メソッドはMapを2回スキャンする
2、Integerは可変オブジェクトであるため、ループごとに新しいオブジェクトが作成され、Mapに配置されます.
2つ目は、比較的良いカウンタです
このような理由から、可変のIntegerオブジェクトを作成することが考えられる.これにより、Integerオブジェクトの作成が多すぎることを避けることができる.
可変Integerオブジェクトの定義は次のとおりです.
上のカウンタを最適化して、下のフォーマットに変更します.
3つ目は効率的なカウンタです
2つ目はIntegerオブジェクトの作成が多すぎるという問題を解決しましたが、Mapを2回スキャンし、
実はHashMapには現在の値を返す方法(HashMap.put(key,value))があります.
これに基づいて、Mapを2回スキャンすることなく、元の参照を更新することができます.
以下は、500 W回の操作後、3つの方法で消費される時間です
start test naiveCounter end test naiveCounter,time is:5629
start test betterCounter end test betterCounter,time is:5030
start test efficientCounter end test efficientCounter,time is:4418
最後の方法は確かに3つの中で最も効率的な方法であることがわかります
1つ目は、最も直感的なカウンタです.
public void naiveCounter(String sArr[]) {
HashMap<String, Integer> counter = new HashMap<String, Integer>();
for (String a : sArr) {
if (counter.containsKey(a)) {
int oldValue = counter.get(a);
counter.put(a, oldValue + 1);
} else {
counter.put(a, 1);
}
}
}
この方式では、ループごとにMapにKeyが含まれているかどうかをチェックし、含まれている場合は元の値+1を再保存し、存在しない場合は直接保存する1.この方式が最も簡単で直接的な方式であるが、最も有効な方法ではなく、その低効率な原因:
1.キー(a)が既に存在する場合、containsKey()メソッドとget()メソッドはMapを2回スキャンする
2、Integerは可変オブジェクトであるため、ループごとに新しいオブジェクトが作成され、Mapに配置されます.
2つ目は、比較的良いカウンタです
このような理由から、可変のIntegerオブジェクトを作成することが考えられる.これにより、Integerオブジェクトの作成が多すぎることを避けることができる.
可変Integerオブジェクトの定義は次のとおりです.
class MutableInteger {
private int val;
public MutableInteger(int val) {
this.val = val;
}
public int get() {
return val;
}
public void set(int val) {
this.val = val;
}
public String toString() {
return Integer.toString(val);
}
}
上のカウンタを最適化して、下のフォーマットに変更します.
public void betterCounter(String[] sArr) {
HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();
for (String a : sArr) {
if (newCounter.containsKey(a)) {
MutableInteger oldValue = newCounter.get(a);
oldValue.set(oldValue.get() + 1);
} else {
newCounter.put(a, new MutableInteger(1));
}
}
}
3つ目は効率的なカウンタです
2つ目はIntegerオブジェクトの作成が多すぎるという問題を解決しましたが、Mapを2回スキャンし、
実はHashMapには現在の値を返す方法(HashMap.put(key,value))があります.
これに基づいて、Mapを2回スキャンすることなく、元の参照を更新することができます.
public void efficientCounter(String[] sArr) {
HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
for (String a : sArr) {
MutableInteger initValue = new MutableInteger(1);
MutableInteger oldValue = efficientCounter.put(a, initValue);
//MutableInteger , ,
// , MutableInteger
if (oldValue != null) {
initValue.set(oldValue.get() + 1);
}
}
}
以下は、500 W回の操作後、3つの方法で消費される時間です
start test naiveCounter end test naiveCounter,time is:5629
start test betterCounter end test betterCounter,time is:5030
start test efficientCounter end test efficientCounter,time is:4418
最後の方法は確かに3つの中で最も効率的な方法であることがわかります