適用於條件的數據結構

Question

我有一個包含10k行數據的csv文件，如下所示。

20131210,0,0,00981231231110,0123,123p1. 
20131210,0,0,00981231231120,0123,123p1. 
20131210,0,0,00981231231130,0123,123p1. 
20131210,0,0,00981231231140,0123,123p1. 
20131210,0,0,00981231231150,0123,123p1. 

另外我有下面的XML文件如下所示

<validatecondition> 
<ID> 
    00981231231110 
</ID> 
<SVC_ID> 
    TMC 
</SVC_ID> 
<applyrate> 
    12.0Dollars 
</applyrate> 
<ID> 
    00981231231120 
</ID> 
<applyrate> 
    2.0Dollars 
</applyrate> 
. 
. 
. 
. 
many conditions 
</validatecondition> 


node 
|-- 00981231231110 
| |-- TMC 
| | |-- applyrate 
| | | |-- 1.00 
| | |  
| | | 
| | 
| | 
|  
+-- 00981231231120 
| |-- applyrate 
| | |-- 111.00 
| 
+-- 00981231231130 
| |-- RMC 
| | |-- applyrate 
| | | |-- 11.00 
| | |  
| | | 
| | 
|  
|  

我有適用於各行的上述條件，並相應地導出速率。目前，邏輯依次迭代每個節點並檢查ID是否與每行中的值匹配並應用速率。有沒有我可以快速應用的圖表數據結構？

Answer 1

如果你有查找東西答案是在大多數情況下是Map。所以在你的情況下，你必須通過Id查找。

所以在你的情況下，你可以創建一個HashMap<Long, XmlData>（或類似的東西）。然後您遍歷csv數據並使用Id從Map中查找。

這將因爲列表查找是O(n)在理論上從O(n^2)您alogithm加快O(n)，你必須這樣做n次，但HashMap的查找是O(1)（攤銷）。

如果由於某些原因您不能使用HashMap，您可以嘗試訂購xml數據並使用二進制搜索算法。在這種情況下，您最終可能會得到O(n log n)，這比O(n^2)還要好。