用於在多個鍵上進行近似查找的快速算法

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通用的解決方案。當然，如果你知道你的界限之間有一些關係，你可以使用一個按各個項目值組合排序的列表。