有效百分比查找的數據結構？

Question

假設您有大量的鍵/值對，其中值是一些任意的實數。你想創建支持以下操作的數據結構：

• 插入，還增加了一個新的鍵/值對收集，
• 刪除，從而消除一個鍵/值對從收集，
• 百分，告訴其百分與給定鍵關聯的值是，和
• 告訴百分，其中一個接受百分位數並返回至少在給定百分位數上的值最低的鍵。

例如，可以使用此數據結構來有效地確定給定學生在接收全國測試分數流時所處的百分比，或者識別出具有異常優質或劣質服務質量的醫院。

有沒有辦法讓這些操作高效運行（比如，次線性時間？）來實現這種數據結構

Answer 1

一種可能的方式是使用order statistic tree和hash table的混合體。

的順序統計樹是一種類型的平衡二叉查找樹的是，在除了正常的二叉查找樹的操作，支持兩種多個操作：

• 排名（鍵），它返回數樹中的元素小於給定元素，並且
• 選擇（k），它返回樹中第k個最小元素。

順序統計樹可以通過提高正常平衡的二叉搜索樹建（比方說，一個red/black tree或AVL tree）與被旋轉過程中保留額外的信息。通過這種方式，訂單統計樹上的所有正常BST操作都可以在O（log n）時間內運行，而額外的操作也可以在O（log n）時間內運行。

現在，讓我們假設您純粹存儲值分數，而不是鍵/百分比分數。在這種情況下，實現百分比查找將非常簡單，如下所示。將所有值存儲在順序統計樹中。要確定給定值的百分比分數，請使用訂單統計樹上的排名操作查找該值出現在哪個索引處。這給出了一個數字，範圍從0到n - 1（其中n是樹中元素的數量），表示該分數在順序統計樹中的位置。然後，您可以將該數字乘以99 /（n - 1），以根據需要獲得在0到99範圍內運行的值的百分比分數。

要確定最大值大於某個百分點，可以使用選擇操作如下。給定一個介於0和99之間的百分位數，將該百分位數乘以99 /（n-1）得到一個介於0和n-1之間的實數。以該數字的上限產生0到n-1範圍內的自然數。使用在訂單統計樹上選擇操作，然後可用於查找範圍內等於或高於給定百分位數的第一個值。

但是，這些操作假定我們純粹是數據結構中的值，而不是鍵/值對。相反

1. 不僅僅是存儲的值，我們將鍵/值對存儲在每個節點上：爲了使鍵/值對這種操作的工作，我們將增加我們的數據結構如下。訂單統計樹將純粹按照它們的值對鍵/值對進行排序，並將密鑰作爲衛星數據攜帶。
2. 我們將存儲一個二級散列表，該表將鍵映射到它們的關聯值。

這兩個更改使我們可以爲我們的數據結構實現所需的功能。爲了讓數據結構通過鍵進行百分比查找，我們首先用給定鍵查詢哈希表以查找其關聯值。然後，我們對此值進行百分比查找。爲了讓數據結構告訴我們一個關鍵字，其值等於或高於給定的百分位數，我們對訂單統計樹進行如上所述的正常查找百分位數操作，然後查找與給定值關聯的關鍵字。

• 插入：

  如果我們假設哈希表使用鏈接的散列，然後爲每個操作所需的時間在下面給出O（log n）的時間來插入值/密鑰對成訂單統計樹，加上O（1）分期計算時間以將鍵/值對插入散列表中。總時間爲O（log n）攤銷。

• 刪除：O（log n）從訂單統計樹中刪除值/密鑰對的時間，加上（1）從哈希表中刪除鍵/值對的攤銷時間。總時間爲O（log n）攤銷。
• 百分：O（1）預計的時間來查找與鍵關聯的值，O（log n）的時間做排名操作，以及O（1）額外的時間來映射等級的百分。總時間爲O（log n）。
• 查找 - 百分位數：O（1）將百分位數映射到一個等級所需的時間，以及O（log n）所需的時間來執行選擇操作。總時間是O（log n）最壞的情況。

希望這有助於！

Answer 2

有一個簡單，高效的可能性：

如果你可以只在最終填補了學生結構搜索百分接活：

使用ArrayList動態建立，當你不噸知道元素的數量。
如果你知道它們，那麼直接從數組開始，否則從動態數組中創建數組。 （例如java中的ArrayList）。

insert：不是必須的，換成在末尾添加，然後排序一次。
刪除：不需要，如果你可以住在那。
告訴百分：更簡單：東西非常接近：元素[長*百分]：O（1）

在實踐中，陣列方法將大大快於平衡樹的方法，至少在java， 當你的應用程序可以建立陣列一次（例如，每日學生評估，每天建立它）

我已經實現了（我）以上算法使用自寫ArrayListInt，它與ArrayList相同，但使用原始類型（double，int），而不是對象類型。當所有數據都被讀取後，我將它整理一次。

此外，你想要的關鍵值：
我只是添加一個樹圖（平衡樹）。現在有點懷疑TreeMap和額外百分比數組是否有意義：這取決於搜索的頻率以及內存使用情況與搜索時間。

更新：

結果：TreeSet中VS排序陣列（動態積聚陣列，然後最終排序一次：

num elements: 1000 treeSet: 4.55989 array=0.564159 
num elements: 10000 treeSet: 2.662496 array=1.157591 
num elements: 100000 treeSet: 31.642027 array=12.224639 
num elements: 1000000 treeSet: 1319.283703 array=140.293312 
num elements: 10000000 treeSet: 21212.307545 array=3222.844045 

元件（1E7）的這ammount的現在接近極限（ 1GB堆空間），下一步內存將耗盡（已經在1e7單元修復，但在treeset之後清理內存時，度量1e7的運行也起作用了。

缺少的是搜索時間，但是SOR泰德陣列BINSEARCH是隻能由哈希表

最後不堪一擊： 如果你每天可以建立學生設置一次，e.g，然後用數組的方式給出了一個簡單得多的百分搜索。