0

2 つの並べ替えられたリストの交差を構築するアルゴリズムがあります。パフォーマンス テストで java.util.BitSet と比較すると、私のアルゴリズムは遅いです。

    public static List<Integer> intersection(List<Integer> list1, List<Integer> list2) {
            int size1 = list1.size(), size2 = list2.size();
            int capacity = size1 < size2 ? size1 : size2;
            List<Integer> intersection = new ArrayList<Integer>(capacity);
            int i1 = 0, i2 = 0;
            while (i1 < size1 && i2 < size2) {
                if (list1.get(i1) < list2.get(i2))
                    i1++;
                else if (list2.get(i2) < list1.get(i1))
                    i2++;
                else {
                    intersection.add(list2.get(i2++));
                    i1++;
                }
            }
            return intersection;
        }

誰でも改善が見られますか？

ありがとう

4

2 に答える 2

1

関数への入力は常にタイプArrayListですか?

  • もしそうなら、アルゴリズム的にはあなたの方法に何の問題もありません。2 つの変更を行います。
    1. 引数の型をArrayList<Integer> list1, ArrayList<Integer> list2;に変更します。
    2. 私は一度だけ電話list1.get(i1)しlist2.get(i2)ます。これはパフォーマンスに影響を与える場合としない場合がありますが、スタイル的にはこれを考慮に入れることを好みます。
  • リストをサポートする必要がある場合は、関数を 2 つの反復子で書き直します。呼び出しget(index)は非常にコストがかかる可能性があるためです。

最後に、パフォーマンスをテストするときは、 How do I write a correct micro-benchmark in Java?のアドバイスに従ってください。

于 2013-03-26T09:57:08.410 に答える
0

次のことを知っておく必要があります。

List<Integer> intersection = new ArrayList<Integer>(capacity);

size の内部配列を割り当てますcapacity。

list1.size() == 5000、 、list2.size() == 5000、および、メソッドが4997intersection(list1, list2).size() == 3個の役に立たない整数を割り当てるとします。

適切な容量 (メソッドの使用方法に応じて) を使用するか、デフォルト値 (10) のままにしてください。

n(サイズ(または容量)ArrayListの配列を割り当てる複雑さは.) nO(n)

于 2013-03-26T10:20:33.150 に答える