1

N 個の SortedLists があり、それぞれに、並べ替えの対象となる int ID を含むオブジェクトのコレクションがあります。すべてのリストに存在するオブジェクトのセットを見つける必要があります。

最初に考えたのは、リストをサイズ順に並べて、最小のサブセットから開始し、それぞれと .Intersect() を他のものにすることですが、大きなリストと効率のために、それらが並べ替えられているという事実を利用したいと思います。最適なアルゴリズムがいくつかあると思います-おそらくデータベースエンジンがハッシュ結合のように使用するものです。どのアルゴリズムが最適かはわかりません。どんな助けでも大歓迎です。

4

4 に答える 4

3

多かれ少なかれ交差するのはハッシュ結合です。データが並べ替えられている場合は、代わりに入れ子ループのマージを行うことができますが、これを行うライブラリ メソッドはないと思います。メソッドを記述するのは少し面倒です。

もう 1 つのハッシュベースの方法は Distinct です。リストを連結して Distinct を使用してみませんか? これにより、1 つのハッシュ テーブルに抑えられます。

Distinct / hash ロジックを使用し、実際にパフォーマンスの問題が発生する場合にのみ最適化を試みます。ネストされたループのアプローチは遅くなる可能性があり、いずれにせよ、Distinct (または他のハッシュベースの) アプローチが十分に速い場合は、それを書くのに多くの時間を費やしたくありません。

例：

var result = list1.Concat(list2).Concat(list3).Distinct();

コンパイル時にリストの数がわからない場合は、これを試してください。

IEnumerable<IEnumerable<T>> lists = // a sequence of lists
var result = lists.Aggregate(Enumerable.Empty<T>(), (a, b) => a.Concat(b)).Distinct();
于 2012-09-14T22:52:08.830 に答える
2

リストごとに 1 つのインデックスを使用して、リストを並列にループできます。1 つのリストからそのインデックスで値を選択し、インデックスでの値が小さい限り、他のリストを進めます。値が不足しているリストを見つけた場合は、そのリストから次に高い値を取得し、代わりにそれを探し始めます。

すべてのリストを進めて、それらすべてに値が見つかったら、結果に追加できる値が得られます。すべてのリストを進めて、値を探し始めます。すべてのリストの最後に到達するまで繰り返します。

これは仕事をしているようです：

public static SortedList<int, T> MultiIntersect<T>(params SortedList<int, T>[] lists) {
  SortedList<int, T> result = new SortedList<int, T>();
  int[] index = new int[lists.Length];
  bool cont;
  do {
    int list = 0;
    int value = lists[list].Keys[index[list]];
    while (list < lists.Length) {
      while (index[list] < lists[list].Count && lists[list].Keys[index[list]] < value) index[list]++;
      if (index[list] == lists[list].Count) {
        return result;
      } else if (lists[list].Keys[index[list]] > value) {
        value = lists[list].Keys[index[list]];
        list = 0;
      } else {
        list++;
      }
    }
    result.Add(value, lists[0].Values[index[0]]);
    cont = true;
    for (var i = 0; i < index.Length; i++) {
      index[i]++;
      cont &= index[i] < lists[i].Count;
    }
  } while(cont);
  return result;
}
于 2012-09-14T22:56:40.093 に答える
0

私が思うのは、コードでのGuffasの提案です。配列については申し訳ありませんが、入力が高速でした。

void Main()
{
var lists = new [] {new[] {1, 1, 2, 3, 4, 5, 6, 9, 11, 13},
                    new[] {1, 1, 5, 6, 7, 13},
                    new[] {1, 1, 6, 8, 9, 13},
                    };

var mergedSet = lists[0];
for(var i = 1; i < lists.Length; i++)
{
    mergedSet = Merge(lists[i], mergedSet);
}
}

int[] Merge (int[] sla, int[] slb)
{
int ixa = 0, ixb = 0;
List<int> result = new List<int>();
while(ixa < sla.Length && ixb < slb.Length)
{
    if (sla[ixa] < slb[ixb]) { ixa++; } 
    else if (sla[ixa] > slb[ixb]) { ixb++; } 
    else { result.Add(sla[ixa]); ixa++; ixb++; }
}

return result.ToArray();
}

サイズで入力を並べ替え、最小のリストから開始すると、パフォーマンスが向上する場合がありますが、最小のリストにセット全体の最小値と最大値が含まれている場合でも、すべてのリストのすべてのアイテムがトラバースされます。

読みやすさは、他の場所で提案されているように、おそらく効率の悪いlinqクエリを使用する方法を支持するかもしれないと思います。

于 2012-09-14T23:12:15.107 に答える
0

このアプローチはどうですか？

HashSet<YourType> hashSet = new HashSet<YourType>(list1);
hashSet.IntersectWith(list2);
hashSet.IntersectWith(list3);
...
hashSet.IntersectWith(listn);
List<YourType> intersection = hashSet.ToList();

私見は十分に効率的でなければなりません。

于 2012-09-14T22:54:37.233 に答える