以下用例的最佳數據結構

我的用例是在多個級別上應用過濾器。把它看作只有2級的樹結構（目前，我的用例只包括2級，但是預期的解決方案應該是有超過2級的可能性）。以下用例的最佳數據結構

*-----------* (Level 1) 
/\  /\ 
/ \  / \ 
* *  *  * (level 2)

用戶可以接受或在1級或級拒絕規則2.
如果用戶接受或拒絕在1級的規則，然後水平以及它所有的孩子應該繼承同樣的財產，這意味着他們也將被接受或拒絕。
用戶可以添加例外。例如，根據上述觀點，如果他拒絕第一級的規則，那麼其子女也將被拒絕。但是，用戶可以選擇專門標記已接受的兒童。這些被稱爲例外。

我想要一個數據結構，它應該能夠有效地存儲這些信息並給出數千個單獨的條目，我應該能夠根據用戶的接受偏好過濾數據。

等級1的大小以千爲單位，而等級1的每個成員又可以擁有數千個孩子。

示例 - 讓我們考慮一個問題，其中有來自2個國家（美國和英國）的千人，我想根據用戶要求過濾人員。考慮到用戶在多個級別上有多個選項。

   US--------------------------UK (Level 1) 
      /\      /\ 
      / \      / \ 
     / \     / \ 
     /  \     /  \ 
     florida texas    london  Manchester 
     /\   |\    /\   /\ 
     /\  | \   /\  /\ 
    / \  | \  / \ / \ 
    Male Female M F  M  F M  F

例一 - 用戶表示，除去所有的人在美國。因此，儘管穿越的人的名單，我會刪除所有的人，其中國家==美國

爲Eg2 - 用戶說，從列表中刪除美國的所有的人，但得克薩斯州的人不應該被刪除。

Eg3 - 用戶說所有美國人都應該包括在內，除了德克薩斯州的男性。

那麼什麼是最好的數據結構來存儲這些類型的規則，並將其應用在列表上，根據用戶的喜好，讓人們。

只需添加它，就可以有數千個國家和數千個城市。

如果你能提出了兩個級別的數據結構，甚至認爲將是巨大的。

來源

2016-11-18 Vivek Kumar

雖然每個級別的大小看起來很大，但是有很多級別嗎？另外，爲什麼這些關卡特別重要？是否有可能設計它，以便如果用戶接受或拒絕某條規則，它會自動移動到頂層（可能存在「已接受」頂部和「已拒絕」頂部）？ –

一個具有六個左右規則的具體例子將有助於理解你想要完成的事情。 –

更新了問題 –

我會建議一個簡單的列表與多個索引。也就是說，你把所有的人的名單，無論他們在。

那麼哪個國家，你決定你要使用過濾器的屬性。你提到了國家，州，城市和性別。所以你有四個哈希映射。

國名，（哈希集合的人）
狀態的名字，（哈希集合的人）
城市名稱，（哈希集合的人）
性別，（哈希集合的人）

所以，如果你想選擇所有居住在美國州所謂的德克薩斯州的男性，你只需交叉列表。那就是：

獲取的一組誰住在美國
相交集誰住在得克薩斯州人的人。
與一組男性相交。

（雖然在這種情況下，你也許可以優化上述被指出的是，大家誰住在得克薩斯州也住在美國，並消除了第一個十字路口。）

不管怎麼說，使用這種技術，你可以有任何數量的選擇標準。

如果你有k選擇標準，那麼運行時間最壞的情況是成正比k * n，其中n是人們在列表中的總數。平均運行時複雜性應該更好。如果您根據哈希集中的條目數量來訂購交叉點，則可以快速縮短運行時間。例如，在上述情況下，您首先要選擇住在德克薩斯州的人數，這大大減少了您的搜索空間。然後與美國，最後是性別相交。

索引的空間複雜度爲O（n * k）。也就是說，每個人在每個哈希映射中都會有一個條目。

來源

2016-11-21 18:04:34

以下用例的最佳數據結構

回答

相關問題