2

私はすぐにこのスニペットを書いて仕事をしました

private void map() {
    for (KVPair kvPair : content) {
        String k = kvPair.getKey();
        String v = kvPair.getValue();

        if (mappedContent.containsKey(k)) {
            List<String> values = mappedContent.get(k);
            values.add(v);
        } else {
            List<String> values = new ArrayList<>();
            values.add(v);
            mappedContent.put(k, values);
        }
    }
}

それは動作し、1k、2k、4k、および8kのランダムデータで実行すると、次のパフォーマンスが得られます（平均100,000回の実行）

Running with 1,000 pairs
  [perfRun] 100000 iterations took 3 seconds
  [perfRun] Run time: 3758786000 ns. 1 iteration takes 37 us
Running with 2,000 pairs
  [perfRun] 100000 iterations took 6 seconds
  [perfRun] Run time: 6675544000 ns. 1 iteration takes 66 us
Running with 4,000 pairs
  [perfRun] 100000 iterations took 13 seconds
  [perfRun] Run time: 13337145000 ns. 1 iteration takes 133 us
Running with 8,000 pairs
  [perfRun] 100000 iterations took 27 seconds
  [perfRun] Run time: 27109480000 ns. 1 iteration takes 271 us

大まかに言えば、サイズが2倍になると、時間が2倍になります。私は直線的な成長をとるでしょうが、それでも、私たちはもっとうまくやれるでしょうか？一定の時間を使用して物事をマッピングすることは可能ですか？

4

3 に答える 3

3

私が見ることができるもの、mappedContent.containsKey(k)大まかにかかる不要なもの、チェックでBigO(n)逃げることができます、null

for (KVPair kvPair : content) {
        String k = kvPair.getKey();
        String v = kvPair.getValue();
        List<String> values = mappedContent.get(k);
        if (values!=null) {
            values.add(v);
        } else {
            values = new ArrayList<>();
            values.add(v);
            mappedContent.put(k, values);
        }
}
于 2013-03-08T18:35:08.573 に答える
1

@Quoiの答えに基づいて、nullチェックの後にelseブロックを保存することが違いを生むかどうか正確にはわかりません

for (KVPair kvPair : content) {
    String k = kvPair.getKey();
    List<String> values = mappedContent.get(k);
    if (values == null) {
        values = new ArrayList<>();
        mappedContent.put(k, values);
    }
    values.add(kvPair.getValue());
}

また、リストがどのくらい大きくなるかについていくつかの仮定を立てることができるので、そのサイズをリスト コンストラクターに渡し、リストのサイズ変更に必要な時間を節約します。メモリが問題にならない場合はcontent.size() + 1、リストのサイズとして使用できます。

于 2013-03-08T19:02:25.367 に答える
0

基礎となるデータ構造を変更できない限り、いいえ、線形時間よりもうまくいくことはできません。

これを考慮してください: n 個の一意のエントリを持つリストがあります。それぞれをマップするには、その 1 つにアクセスする必要があります。アクセス コストが 1 であるとします。その場合、n回のアクセスが必要です。したがって、ベンチマークで指摘されているように、 n * 1 = n 、または線形時間の複雑さがあります。

データを共有できるが両方のインターフェイスを提供できるデータ構造があれば、2つの間の切り替えで一定の時間を達成できます。ただし、明らかに、例とは異なる静的タイプがあります。

于 2013-03-08T18:40:17.650 に答える