最適合用於鍵值對評估的數據結構

-1

我將預定義的匹配項設置爲：父ENTITY具有與其關聯的鍵值集。下父ENTIRY每個集合可以被定義類似最適合用於鍵值對評估的數據結構

ENTITY A: 
    SET A1. {key1=v11 and key2!=v25} 
    SET A2. {key1=v12 and key3=v31, v33} 
    SET A3. {key1=v15 and key2=v25 and key3=v35} 

Entity B: 
    SET B1. {key1=v16 and key2=v26} 
    SEY B2. {key3!=v39} 
    SET B3. {key1!=v11 and key3=v31}

我將接收的輸入爲：

{ 
    key1 : [v11,v12,v13], 
    key2 : [v23,v24], 
    key3 : [v31,v39] 
}

這意味着KEY1具有3個值，KEY2具有2個值和KEY3只有一個值。

然後我必須返回所有具有至少一個SET的實體，這些SET的所有鍵值匹配都由傳遞的鍵值對滿足。

因此，對於上面提到的實體A，集合A1和集合A2的鍵值對由輸入滿足，而對於實體B，沒有集合的鍵值對滿足。所以只有ENTITY A纔是答案。

可以有200-1000個父實體，每個父實體有20個SET ENTITY & 200個鍵值對。輸入可能包含多達50個鍵值對。

我無法查詢外部數據庫進行評估。但是數據結構應該可序列化以存儲到memcache或redis中。

來源

2014-01-16 Ajay Bodhe

請提供關於實體數量的實體數量的一些細節（上限或期望值）。這可能會對最佳方法產生很大影響。 –

完成，感謝您的建議。 –

爲了簡單，讓我修復python中的符號和寫入。

你稱之爲ENTITY的是一組詞典，由'keys'標記，並以對象列表作爲值。爲簡單起見我們假設值是數字（但我們真正需要的是隻是比較操作）

E1 = { 
    {'k1': [4], 'k2': [20,12]}, 
    {'k4': [2,20,25], 'k3': [2,3]} 
} 

E2 = { 
    {'k2': [2,3,4], 'k4': [2], 'k3': [14]}, 
    {'k3': [1]}, 
    {'k3': [12,23]} 
}

輸入僅僅是一本字典，再由「鑰匙」，並與對象作爲值列表標記。我想你應該保持排列順序的數組數組。這應該允許您以線性時間比較給定密鑰的列表。總的來說，給定輸入的複雜度應該是O（EKL），其中E是實體的數量，K是密鑰的數量，L是列表的長度。同樣，它將需要O（EKL）內存。

我期望在這種情況下，比較你的界限需要幾秒鐘的時間。如果這還不夠那就讓我們進一步認爲:)

編輯：您可以簡單地用一個元組（ENTITY_ID，SET_ID，鍵，值），以平衡BST作爲值的指數。然後搜索應該花費O（log n）。你有沒有想過這樣的結構？

來源

2014-01-16 18:31:48

我想在C中實現這個。比較SET/dictionary中的每個鍵與輸入中的每個鍵將會浪費一些時間。同樣在找到鍵後，將集合/詞典中的鍵的每個值與輸入中接收的相同鍵的每個值進行比較將需要時間。我們能加速嗎？ –

那麼，如果你將它作爲一個Map來實現，那麼查找關鍵字將需要一段時間。比較值最多會花費線性時間O（L）。由於我們不瞭解任何有關元素的更多信息，因此無法改進。您需要檢查每個實體和每個集合，以便提供額外的O（EK）因子。 –

我今天能想到的唯一改進是爲值而不是列表設置結構。這將爲每個鍵進行O（L）查找，而無需排序。 –

最適合用於鍵值對評估的數據結構

回答

相關問題