6

在 Java 中，我有一大堆对象（大约 10,000 个对象），比如说Set<Person> cityInhabitants。我还有一大堆谓词（约 1,000 个谓词），可用于过滤掉与这些谓词中的任何一个Person匹配的任何谓词。谓词可以是例如

  • person.getName().equals("ugly name1")
  • person.getName().equals("ugly name2")
  • person.getAge() < 18.

这一要求提出了以下挑战：

  • 过滤应该很快
  • 谓词是“业务定义的”，因此应该很容易添加和删除谓词。这意味着谓词可能不应该在源代码中硬编码，而最好在数据库中维护（？）

这些挑战的解决方案是什么？有什么图书馆可以在这里提供帮助吗？

4

4 回答 4

2

我建议您按照执行速度对谓词进行排序。然后，您可以按速度顺序执行您的谓词，首先使用最快的谓词，这通常意味着较慢的谓词将不得不在较小的集合上运行。

然而，这个假设并不完全正确，您需要计算出删除谓词的百分比与执行速度。然后我们可以看到哪个是删除最高百分比对象的最快谓词。然后我们可以按照对我来说最优化的顺序执行谓词。

您可以轻松实现自己的谓词interface

public interface Predicate<T> {

    boolean filter(T object);

}

然后，您需要为每个规则创建谓词对象。您可以为年龄和姓名检查创建一些更动态的类，这也将减少您需要的代码量。

public class AgeCheck<T> implements Predicate<T> {

    private final int min;
    private final int max;
    public AgeCheck(int min, int max) {
        this.min = min;
        this.max = max;
    }

    @Override
    public boolean filter(T object) {
        // if( t.age() < max && t.age > min) ...
    }

}
于 2013-01-28T23:30:01.657 回答
2

在这种情况下，对于操作本身的复杂性，您无能为力。如果条目很多，谓词很多并且谓词很昂贵，那么您可以尽可能快地优化，但您肯定不会超过某个阈值，因为这里的单个操作可能很昂贵。

您应该测试不同的方法并查看在您的特定情况下表现更好的方法：

  • 通过首先检查应该更宽的谓词对谓词进行排序（这样第一个谓词将过滤掉尽可能多的条目）
  • 根据谓词的复杂性对谓词进行排序（以便首先执行速度更快，条目越少则越慢）
  • 不要更新原始数据结构，而是保留一个包含过滤元素的并行集合 vs
  • 总是更新数据结构，这样你每次都会循环更少的人
于 2013-01-28T23:30:58.850 回答
1

这里有一个替代方案：识别一个类的实例可能具有的所有可能的属性。在您的示例中，您有一个person具有两个属性的类；姓名和年龄。因为您有这些属性的吸气剂，所以 aperson最多可能有两个属性（除非还有其他您没有提到的吸气剂）。您可以实现person将属性保存在一个集合中，这样您实际上对属性的数量没有限制。不管它是如何实现的，确定所有的属性。

现在对于每个属性，关联一个唯一的素数，然后为每个实例person维护与分配给它的那些属性对应的那些素数的乘积person。例如，假设一个人可以是年轻或年老、男性或女性、长相好或长相不佳。这是 6 个属性，让我们按如下方式分配质数：

02: young
03: old
05: male
07: female
11: good looking
13: bad looking

继续这个例子，假设一个人是一个漂亮的年轻女性。素数的乘积将是 2 X 7 X 11 或 154。

现在你想找到所有好看的年轻人，不分性别。与此谓词相关的素数的乘积是 2 X 11 或 22。

因此，您现在可以遍历所有的people，如果与每个相关的素数乘积people可以除以 22 而没有任何余数（在person素数乘积为 154 的情况下可以），那么您就有了匹配项。

您可能希望使用 BigNumber 类来执行素数乘积的乘法、除法和存储。

如果给定 a 并询问它是否匹配所有谓词，则此解决方案非常快person（同样，谓词已简化为唯一的素数，并且谓词的集合现在由这些素数的乘积表示）。

如果您必须遍历整个people查找匹配项的集合，此解决方案可能不会那么快。

于 2015-02-14T17:37:27.603 回答
1

（我没有意识到这个问题已经 2 岁了。我参加这个聚会太晚了！很高兴知道作者最终使用了什么解决方案。）

有什么图书馆可以在这里提供帮助吗？嗯，当然有！

您的数据收集不是很大，但您有大量不成比例的谓词。另外，您希望这些谓词由您的用户管理，并集中存储等。这听起来很适合Drools，它是一个规则引擎，并带有额外的工具来编写、验证和存储这些规则。

但是 Drools 可能很大并且涉及。也许您需要更简单的东西？您的代码示例以及您对速度的第一个要求让我想到了CQEngine，它是一个用于索引对象的库。它索引字段（例如您的“名称”字段），并且可以以各种方式（等于、开头、包含等）搜索这些字段。它速度快而且简单，但它只能索引。您必须自己提出规则定义等。另一方面，CQEngine 支持逻辑谓词，因此您可以将谓词与和/或链接在一起。

还有其他用于规则引擎或对象索引的库。我相信其他人会在他们的答案中列出它们。

于 2015-02-14T18:55:36.840 回答