c# - 确定大型整数列表中常见元素计数的最有效方法

Question

我有一个 List<List<int>>我不断添加新的 List<int> .但在添加之前，我需要确保我的新列表包含 小于 n 其他的通用整数 List<int>在我的主要列表中。换句话说，考虑到 ，没有重复。 n 的最小值 元素。

因此，如果我的第一个列表包含 { 1, 2, 3, 4, 5 } 和我的第二个列表 { 1, 3, 2, 6, 4 } - 如果 这将是重复的n = 4

我用过 .Intersect()并得到了 .Count() while 遍历整个列表但当数据集较大时会变得非常慢。

我在这里还有什么其他有效的选择来检查这些重复项？

谢谢!

Answer 1

遍历大型列表可能会很慢，尤其是当您要遍历多个大型列表时。检查所有列表中新列表的每个元素是否存在的速度本质上是 O (n * k) 其中 n 是所有现有列表的计数之和，k 是新列表中的项目数.

您可以通过几种不同的方式解决速度问题，但如果您没有非常严格的内存限制，我认为我的选择是使用额外的 HashSet 来存储任何列表中已有的项目列表并查找新项目在那个 HashSet 中。无论 HashSet 的大小如何，HashSet 只需要一次操作即可找到一个项目……这使得这种查找速度非常快。

Algorithm for this:
1) Get new List to add to List of List
2) Validate that the new list is new enough by:
    A)  Checking the HashSet for .Contains() on each item of the new list
    B) Check that no more than the allowed number of items already exist
3) Add the new List to the list of lists
4) Add each of the items of the new list to the HashSet

我的假设是，您不关心哪个现有列表包含该 Int 并且只要每个新列表不超过其引用，它就可以出现在任意数量的列表中