每天我们有大约 50,000 个数据结构实例(这最终可能会变得更大),它们封装了以下内容:
DateTime AsOfDate;
int key;
List<int> values; // list of distinct integers
这可能不相关,但列表
values
是一个不同整数的列表,具有以下属性:对于给定的 AsOfDate
值,values
与 key
的所有值的并集产生一个不同整数列表。也就是说,同一天没有整数出现在两个不同的 values
列表中。列表通常包含很少的元素(1 到 5 之间),但有时长达 50 个元素。
给定相邻的日子,我们试图找到这两天
key
值不同但列表 values
包含相同整数的这些对象的实例。我们正在使用以下算法。通过将列表
values
转换为字符串string signature = String.Join("|", values.OrderBy(n => n).ToArray());
然后将
signature
散列到一个整数,对生成的散列代码列表进行排序(每天一个列表),遍历两个列表以查找匹配项,然后检查关联的键是否不同。 (还要检查关联的列表以确保我们没有哈希冲突。)有没有更好的方法?
最佳答案
您可能只是散列列表本身,而不是通过字符串。
除此之外,我认为你的算法几乎是最优的。假设没有哈希冲突,则为 O(n log n + m log m),其中 n 和 m 是您要比较的两天中每一天的条目数。 (排序是瓶颈。)
如果您使用插入散列的存储桶数组(本质上:哈希表),您可以在 O(n + m) 中执行此操作。您可以在 O(max(n, m)) 中比较两个存储桶数组,假设一个长度取决于条目的数量(以获得合理的负载因子)。
通过使用 HashSet.IntersectWith() 并编写合适的比较函数,应该可以让库为您执行此操作(看起来您正在使用 .NET)。
你不能做得比 O(n + m) 更好,因为每个条目至少需要访问一次。
编辑:误读,已修复。
关于c# - 匹配整数列表的算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/593265/