用于在多个键上进行近似查找的快速算法

Question

我制定了一个解决方案，将问题存储在一组表中，并且我希望能够根据多个条件查找参数。

例如，如果标准1和标准2可各自是A或B，那么我有四个潜在参数 - 每个组合甲& A，A & B，B &甲乙& B.对于这些标准，我可以连接字段或类似的东西，并创建一个唯一的键来快速查找每个值。

不幸的是，并非我所有的标准都是这样的。一些标准是数字的，我只关心结果是否位于边界之上或之下。这也不会是一个问题 - 我可以使用二进制搜索或相对较快的方式找到距离我的值最近或最近的键。

我的问题是我需要在同一个表中包含每个数字。换句话说，我可以有三个标准 - 两个具有A/B条目，另一个具有少于x /大于x类型的条目，其中x不是固定的。所以在这个例子中，我会有一个有8个条目的表。我不能只对边界进行二分搜索，因为由于其他标准，最接近的边界不一定适用。例如，如果前两个标准是A & B，那么最近的边界可能是100，但是如果如果前两个标准是A & A，则最接近的边界可能是50.如果我想查找A，A， 101，那么我想它认识到50是最接近的边界适用 - 不是100.

我有一个程序来做查找，但它变得非常缓慢，随着表变大 - 它基本上贯穿每个标准，检查是否仍有可能进行匹配，如果是，则查看更多条件 - 如果没有，则继续检查表中的下一个条目。换句话说，我的程序要求逐个循环表格条目并检查匹配。我试图通过确保输入到过程中的表尽可能小，并确保它查看最不可能匹配的条件（以便尽可能快地检查每个条目）来优化这一点，但是它仍然很慢。

最大的表格可能是200行，大约有10个标准可以检查，但很多都小得多（可能是10x5）。问题是我需要在应用程序中多次调用该过程，因此具有一些初始开销的算法不一定会让事情变得更好。我确实有一些范围可以在运行前改变表格的格式，但我希望尽可能远离它（尽管认识到它可能是唯一的出路）。

我已经做了相当多的研究，但我没有任何运气。有谁知道任何已经设计来解决这类问题的算法吗？我真的希望能有一些聪明的散列函数或者其他的东西，这意味着我不必在表格中循环，但是从我有限的知识来看，这样的事情会在这里挣扎。我相信我对问题的理解足以逐渐优化我目前的解决方案，但我想确保我没有错过一个更好的解决方案。

对这个问题的漫长而抽象的描述表示歉意 - 希望我很清楚自己想要做什么。如果不清楚，我会修改我的问题。

感谢您的任何帮助。

Answer 1

这基本上是查询优化器在SQL域中执行的操作。为此目的，在内存数据库中有快速，免费的。结帐sqlite https://www.sqlite.org/inmemorydb.html。

这听起来像你正在为每个查询所谓的“全表扫描”，这就像查询优化器的最后手段。

Answer 2

正如我的理解，要通过标准像

A& not B & x1 >= lower_x1 & x1 < upper_x1 & x2 >= lower_x2 & x2 < lower_x2 & ... 

最简单的方法是让他们通过一切可能的喜排序，其中，i = 1,2 ...在不同的设置选择项，和已经分居“字”的A，B，各种组合..

搜索将工作如下：

1. 布尔条件选择合适的组合，世界
2. 对于每个我，找到的lower_xi..upper_xi范围的人口在相应组（该操作是O（日志（N））
3. 选择我那里的人口是最低
4. 虽然通过lower_xi..upper_xi范围迭代实例通过检查其它上限/下限标准筛选结果（对于所有的x Ĵ其中J 1 =我）

注意，该SA通用的解决方案。当然，如果你知道你的界限之间有一些关系，你可以使用一个按各个项目值组合排序的列表。