3

より良いアプローチをマージするための配列の配列を指定して、マージソートアルゴリズムを実装しようとするとします。これは次のとおりです。

public void merge(ArrayList<ArrayList<E>> a) {
    ArrayList<ArrayList<E>> tmp = new ArrayList<ArrayList<E>>() ;
    while (a.size()>1) {
        for (int i=1; i<a.size();i+=2) {
            tmp.add(merge(a.get(i-1),a.get(i)));
        }
        if (a.size()%2==1) tmp.add(a.get(a.size()-1));
        a = tmp;
        tmp = new ArrayList<ArrayList<E>>() ;
    }
}

またはこれ：

public void merge(ArrayList<ArrayList<E>> a) {
    ArrayList<ArrayList<E>> tmp = new ArrayList<ArrayList<E>>(),tmp2  ;
    while (a.size()>1) {
        for (int i=1; i<a.size();i+=2) {
            tmp.add(merge(a.get(i-1),a.get(i)));
        }
        if (a.size()%2==1) tmp.add(a.get(a.size()-1));
        tmp2 = a;
        a = tmp;
        tmp = tmp2;
        tmp.clear();
    }
}

より明確にするために、私が行っていたのは、aの各カップルのネイバーをマージし、結果のマージされた配列を配列の外部配列tmpに配置することです。すべてのカップルをマージした後、1 つのアプローチは a をクリアしてからtmpをaに移動することです次に、クリアされた aをtmpに移動します。 2 番目のアプローチは、古い tmpを再利用する代わりに、古いtmpを「スロー」して新しいtmpを取得することです。

4

2 に答える 2

6

原則として、古いコレクションを再利用しようとしてエネルギーを費やさないでください。コードが読みにくくなるだけです (多くの場合、実際のメリットはありません)。このような最適化は、コードが既に機能しており、アルゴリズムの速度が改善されたという確固たる数値がある場合にのみ試してください。

于 2012-04-17T19:45:28.640 に答える
2

  1. 常に新しいものを割り当ててArrayList埋めると、より多くのガベージ コレクションが発生し、一般的にすべてが遅くなります (マイナー GC は安価ですが、無料ではありません)。

  2. を再利用すると、 内の配列のサイズを変更する必要がある場合に使用されるArrayList結果が少なくなります (サイズ変更は安価ですが、無料ではありません)。Arrays.copyOf()ArrayList

一方clear()、配列の内容も無効にして、GCが未使用のオブジェクトを収集できるようにします。これももちろん解放されていません。

それでも、実行速度が懸念される場合は、ArrayList.

于 2012-04-17T19:48:00.090 に答える