1

我有 N 个 SortedLists，每一个都有一个对象集合，这些对象包含一个它们排序的 int ID。我需要找到所有列表中存在的对象集。

我的第一个想法是按大小对列表进行排序，从最小的子集开始，然后我可以取每个列表和 .Intersect() 其他列表，但对于大型列表和效率，我想利用它们已排序的事实。我猜有一些算法是最优的——也许数据库引擎会使用像哈希连接这样的算法。我只是不知道哪种算法最好。任何帮助表示赞赏。

4

4 回答 4

3

相交或多或少是一个散列连接。如果数据已排序，您可以改为进行嵌套循环合并，但我认为没有任何库方法可以为您执行此操作，并且编写该方法有点麻烦。

另一种基于散列的方法是 Distinct。为什么不连接列表并使用 Distinct？这将把它缩小到一个哈希表。

使用 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

您可以并行遍历列表，为每个列表使用一个索引。从一个列表中的索引处选择一个值，然后只要其他列表在其索引处的值较小，就可以推进其他列表。如果您发现一个列表缺少该值，请从该列表中获取下一个更高的值并开始寻找它。

当您推进所有列表并在所有列表中找到值时，您就有了一个可以添加到结果中的值。推进所有列表并重新开始寻找价值。重复直到到达所有列表的末尾。

这似乎可以完成这项工作：

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

这种方法怎么样？

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 回答
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 回答