java - 具有层次结构和多个过滤器的搜索算法

Question

这是我的问题。

假设我们有一个包含多个对象的列表 A，每个对象中都有几个字段。我需要在列表中搜索字段的层次结构。我的问题是执行此操作的最佳优化算法是什么。

我所知道的是:

循环搜索 A，如果没有返回

循环搜索 B，如果没有返回

通过列表循环搜索 C。

等等...

假设 C 从搜索中返回了一些东西，然后我需要应用其他过滤器，将其称为 D 和 E，如果 D 和 E 匹配，则返回 C。

如果不匹配(D 或 E)，我将再次遍历列表以搜索 F，它也可能需要匹配相同的 D 和 E。

考虑到列表 A 的大小可能会发生变化，每个对象中的过滤器也会发生变化。

我的问题是，我正在执行此搜索以匹配两个对象，而对于列表 B 中的每个对象，我在列表 A 中执行此搜索。问题是 B 可以有数千个条目。在某些情况下，完成算法需要数小时。

抱歉抽象的东西，我什至不知道在这里问这个问题是否合适，但我们将不胜感激。

我正在用 JAVA 编程。

谢谢

Answer 1

您所解释的问题目前有点令人费解。如果我弄错了，我很抱歉。我采取的是:

My problem is that I'm doing this search to match two objects, and the for each object in the list B I do this search in list A. Problem is B can have thousands of entries. It takes hours in some cases to complete the algorithm.

您有 2 个列表，您希望根据对象的某些字段查找几乎重复的项。

首先想到的是使用可用的 Java 哈希创建一个哈希函数，该函数为每个对象计算一个仅包含您要比较的字段的哈希。假设您正在寻找共享字段 field_a 和 field_b 而不是 field_c 的对象，那么我的散列函数看起来像 (hash(field_a) * 8) ^ hash(field_b) 或类似的东西。现在您可以使用它来构建 HashMap 或列表数组。

现在要使用它，您可以遍历列表并将对象添加到 HashMap 中。然后你用第二个列表计算你的对象的哈希值，看看你是否得到匹配。如果哈希匹配，您需要比较对象本身，以防万一它是由于哈希冲突导致的错误匹配(这种情况应该很少见，但确实会发生)。

所以现在在这个列表中搜索东西几乎是恒定的 O(1)，(取决于你期望得到多少结果，以及哈希计算变得多么昂贵)。

您应该能够一次计算出所有的哈希值(针对您的所有条件)(由于内存缓存的原因，这比每个哈希值计算一个 pas 稍微快一点)。寻找比赛应该非常快。

注意:如果您看到许多散列冲突(对象具有相同的散列但它们不符合您的要求)，请稍微更改散列函数。