11

のオブジェクトが与えられた場合、そのSetすべての (順序付けされていない) ペアを見ていきたいと思います。

例: セット = {1, 2, 3}、ペア: (1, 2)、(1, 3)、(2, 3)。

を扱う場合Vector<Integer>、各要素のインデックスを使用してこれを実現できます。

for (int i = 0; i < vector.size(); i++)
  for (int j = i + 1; j < vector.size(); j++)
    // Do something with vector.get(i) and vector.get(j)

ただし、 a の要素にはSet<Integer>インデックスがありません。

これまでに見つけた最善の解決策は、Setを aに変換してVector上記の解決策を使用することです。

より効率的で直接的な解決策はありますか?

4

2 に答える 2

10 
List<Integer> list = new ArrayList<Integer>(mySet);
for (int i = 0; i < list .size(); i++)
    for (int j = i + 1; j < list .size(); j++)
        // Do something with vector.get(i) and vector.get(j)
于 2012-12-10T17:21:49.760 に答える
1

このアルゴリズムの複雑さの観点から = n (n -1) / 2、したがって、 O(n^2) が得られる最高のものです（順次）。

ただし、セットが本当に大きい場合は、RAM にしか収まらないセットです。タイル ブロックを使用した行列乗算で行われるのと同様のブロック方式でペアを計算することにより、アルゴリズムを最適化できます。このようにして、キャッシュ ミスの割合を減らし、全体的なパフォーマンスを向上させることができます。

それに加えて、アルゴリズムが恥ずかしいほど並列に見えるため、並列化を導入してスレッド/プロセス間で作業を分割できます。

于 2012-12-10T17:49:48.920 に答える