Javaで効率的なカウンタ

2918 ワード

プログラミングではカウンターとしてHashMapがよく使われるが,本稿では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つの中で最も効率的な方法であることがわかります