12

小さなセット (たとえば 1 ～ 100 要素)でのさまざまな Java セット実装のパフォーマンスに関する良い参考文献はありますか、または誰かが詳しく教えてくれますか? O(1) 対 O(log n) の話は、これらのサイズにはほとんど関係ありませんが、これらの小さなセットを何百万も処理する必要があるため、パフォーマンスは確かに重要です。私が見つけたほとんどの参考文献は、これについてあまり言及していません。

これらのセットで次のことを行う必要があります (通常、セットごとに数回のみ)。

  • 新しいセットの初期化および/または古いセットのハードコピー
  • 要素の追加/削除
  • セットの反復
  • hashCode()セット全体の を計算する

これらは比較するための実行可能なオプションだと思います（Tの比較/ハッシュはほとんど無料であると仮定します）：

  • HashSet<T> : 反復が苦手なようです (したがって at hashCode())
  • TreeSet<T> : 途方もなく高いオーバーヘッドがあるようです
  • LinkedHashSet<T> : これについてまったく経験がありません。オーバーヘッドが高いですか?
  • ArrayList<T> : それ自体は高速ですが、セットではないため、必要なような醜いトリックがCollections.sort()必要です...

上記のうち、一般的に好まれているのはどれですか? それとも自分のSmallSet<T>クラスを書くべきですか？

4

2 に答える 2

4

あなたが本当にパフォーマンスを探しているなら、ここであなたを助けるために自分自身でテストする以外に何もありません:

  • 常に新しいものを割り当てていますか? もしそうなら、ガベージコレクションは他の場合よりも関連性があるかもしれません
  • それらを一度割り当てて、すぐにアクセスする必要がありますか? ハッシュ衝突はそれに影響を与えます
  • それらを常に変更していますか？

実際の使用に似たテストケースをセットアップする必要があります - GC が作動し、そこでの効果を確認するのに十分な長さのテストを行ってください。

また、それらの間に重大な違いがあることを検出した場合は、実装が変更される可能性があるため、JVM を更新するたびにテストを再実行してください。

このようなパフォーマンス テストを行うまでは、私の標準的なアドバイスをお伝えします。最も読みやすいオプションを選択し、読みにくいオプションを使用することで明らかな利点がある場合にのみ、それを変更してください。コード管理者 (あなたの将来かもしれません) は、そのことに感謝します。

于 2012-09-10T06:54:23.747 に答える
1

これは、配列としての小さな Set 実装です。

あなたのニーズに適応するのはとても簡単です:)

ソース: https://highlyscalable.wordpress.com/2011/12/29/ultimate-sets-and-maps-for-Java-p1/

public class ArraySet {
    private int[] array;
    private int size = 0;

    public ArraySet(int capacity) {
        array = new int[capacity];
        Arrays.fill(array, -1);
    }

    public boolean add(int key) {
        int index = Arrays.binarySearch(array, 0, size, key);
        if (index < 0) {
            int insertIndex = -index-1;

            if(size < array.length - 1) {
                if(insertIndex < size) {
                    System.arraycopy(array, insertIndex, array, insertIndex + 1, size - insertIndex);
                }
                array[insertIndex] = key;
            } else {
                int[] newArray = new int[array.length + 1];
                System.arraycopy(array, 0, newArray, 0, insertIndex);
                System.arraycopy(array, insertIndex, newArray, insertIndex + 1, array.length - insertIndex);
                newArray[insertIndex] = key;
                array = newArray;
            }

            size++;
            return true;
        }
        return false;
    }

    public int get(int position) {
        return array[position];
    }

    public int size() {
        return size;
    }

    public boolean contains(int key) {
        return Arrays.binarySearch(array, key) >= 0;
    }
}
于 2014-12-08T21:37:14.597 に答える