匹配整数列表的算法

对于每一天,我们有大约50,000个数据结构实例(最终可能会变得更大),这些实例封装了以下内容:

DateTime AsOfDate;
int key;
List 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为一个整数,排序生成的哈希码列表(每天一个列表),遍历两个列表寻找匹配,然后检查相关键是否不同.(还要检查相关列表以确保我们没有哈希冲突.)

有更好的方法吗？

你可能只是散列列表本身,而不是通过String.

除此之外,我认为你的算法几乎是最优的.假设没有哈希冲突,则为O(n log n + m log m),其中n和m是您比较两天中每一天的条目数.(排序是瓶颈.)

如果你使用一个插入哈希的桶数组(基本上是一个哈希表),你可以在O(n + m)中执行此操作.您可以比较O(max(n,m))中的两个桶阵列,假设长度取决于条目的数量(以获得合理的加载因子).

通过使用HashSet.IntersectWith()并编写合适的比较函数,应该可以让库为您执行此操作(看起来您正在使用.NET).

你不能比O(n + m)做得更好,因为每个条目至少需要访问一次.

编辑:误读,修复.