代码之家 › 专栏 › 技术社区 › jason

整数列表匹配算法

matching algorithm .net c#

jason · 技术社区 · 17 年前

我们每天都有大约50000个数据结构实例(最终可能会变得更大),其中包含以下内容:

DateTime AsOfDate;
int key;
List<int> values; // list of distinct integers

这可能与此无关,但列表 values AsOfDate ,即 价值观 总的来说 key 生成不同整数的列表。也就是说,没有整数出现在两个不同的 价值观 同一天的名单。

列表通常包含很少的元素(1到5个),但有时长达50个元素。

考虑到相邻的几天,我们正试图找到这些对象的实例,其中 钥匙 在这两天是不同的,但名单 价值观 包含相同的整数。

我们使用以下算法。转换列表 价值观 通过

string signature = String.Join("|", values.OrderBy(n => n).ToArray());

然后散列 signature 对于整数,对产生的哈希代码列表进行排序(每天一个列表),遍历两个列表寻找匹配项,然后检查关联的键是否不同。(还要检查相关列表,确保没有哈希冲突。)

有更好的方法吗?

6 回复 | 直到 17 年前

Thomas 17 年前

您可能只需将列表本身进行散列,而不是遍历字符串。

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

如果使用插入哈希的bucket数组(本质上是一个哈希表),可以在O(n+m)中实现这一点。假设长度取决于条目数,可以用O(max(n,m))来比较两个bucket数组(以获得合理的负载系数)。

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

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

编辑:误读,修复。

Renaud Bompuis 17 年前

在其他答案的基础上,您可以通过在每个列表的所有元素之间创建一个简单地由XOR构成的低成本哈希来加快处理过程。你不必为你的清单排序,你只会得到一个 int 这比字符串更容易、更快地存储。

然后,只需将结果的XORed数用作哈希表的键,并在插入之前检查该键是否存在。如果已经存在一个密钥,只有这样,才能对相应的列表进行排序并进行比较。

如果找到匹配项,仍然需要比较它们,因为使用简单的异或可能会发生一些冲突。
我认为,与重新排序数组并将其转换为字符串相比,结果会更快,内存占用也更低。

如果你要自己实现 List<> ,然后可以在其中生成XOR键,以便在列表上的每个操作中重新计算。
这将使检查重复列表的过程更快。

密码

下面是实现这一点的第一次尝试。

Dictionary<int, List<List<int>>> checkHash = new Dictionary<int, List<List<int>>>();

public bool CheckDuplicate(List<int> theList) {
    bool isIdentical = false;
    int xorkey = 0;
    foreach (int v in theList) xorkey ^= v;

    List<List<int>> existingLists;
    checkHash.TryGetValue(xorkey, out existingLists);
    if (existingLists != null) {
        // Already in the dictionary. Check each stored list
        foreach (List<int> li in existingLists) {
            isIdentical = (theList.Count == li.Count);
            if (isIdentical) {
                // Check all elements
                foreach (int v in theList) {
                    if (!li.Contains(v)) {
                        isIdentical = false;
                        break;
                    }
                }
            }
            if (isIdentical) break;
        }
    }
    if (existingLists == null || !isIdentical) {
        // never seen this before, add it
        List<List<int>> newList = new List<List<int>>();
        newList.Add(theList);
        checkHash.Add(xorkey, newList);
    }
    return isIdentical;
}

它不是最优雅的,也不是最容易一眼就能看懂的,它相当“哈奇”,我甚至不确定它的性能是否比Guffa更优雅的版本更好。
不过,它所做的是通过存储 List<int> 在字典里。

如果发现重复的密钥,我们将循环遍历每个以前存储的列表,直到发现不匹配。

该代码的优点在于,在大多数情况下,它应该尽可能快,并且在发生冲突时仍然比编译字符串快。

Guffa 17 年前

为列表实现一个IEqualityComparer,然后可以将列表用作字典中的键。

如果对列表进行了排序,那么就可以这么简单:

IntListEqualityComparer : IEqualityComparer<List<int>> {

   public int GetHashCode(List<int> list) {
      int code = 0;
      foreach (int value in list) code ^=value;
      return code;
   }

   public bool Equals(List<int> list1, List<int> list2) {
      if (list1.Count != list2.Coount) return false;
      for (int i = 0; i < list1.Count; i++) {
        if (list1[i] != list2[i]) return false;
      }
      return true;
   }

}

现在,您可以创建一个使用IEqualityComparer的字典:

Dictionary<List<int>, YourClass> day1 = new Dictionary<List<int>, YourClass>(new IntListEqualityComparer());

将第一天的所有项添加到字典中,然后循环第二天的项,检查字典中是否存在密钥。由于IEQualityCompraer同时处理哈希代码和比较,因此不会得到任何错误匹配。

您可能需要测试一些计算哈希代码的不同方法。本例中的一个很有效,但可能无法为您的特定数据提供最佳效率。字典工作对哈希代码的唯一要求是,同一个列表总是得到相同的哈希代码,所以你几乎可以做任何你想计算它的事情。目标是为字典中的键获取尽可能多的不同哈希代码,以便每个bucket中的项尽可能少(使用相同的哈希代码)。

Calyth 17 年前

订购有关系吗?i、第一天的[1,2]和第二天的[2,1]是相等的吗? 如果是的话,那么散列可能就没那么好用了。您可以使用排序的数组/向量来帮助进行比较。

还有,这是什么样的钥匙?它是否有一个确定的范围(例如0-63)?您可能能够将它们连接成大整数(可能需要超过64位的精度)和散列,而不是转换成字符串,因为这可能需要一段时间。

Ben S 17 年前

将其放在SQL数据库中可能是值得的。如果你不想拥有一个成熟的DBMS,你可以使用sqlite。

这将使唯一性检查和联合以及这些类型的操作变得非常简单,并且非常高效。如果再次需要,它还可以让你轻松地存储信息。

Conrad 17 年前

您是否会考虑对值列表求和以获得一个整数,该整数可用于预检查不同列表是否包含相同的值集?

虽然会有更多的冲突(相同的总和不一定意味着相同的值集),但我认为它可以首先减少大部分人需要的比较集。