Data Structure applicable for applying conditions

Question

I have a csv file containing 10k row data as shown below.

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.

Also i have following xml file as shown below

<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
|    |    |    
|    |    |
|    |   
|    
|    

I have apply the above conditions on each line and derive the rates accordingly. Currently the logic iterates sequentially each node and checks whether ID matches value in each line and apply rates. Is there any graph data structure that i can apply to rate quickly?

Answer 1

If you have to look up something the answer is in most cases is a Map. So in your case you have to look up by Id.

So in your case you can create a HashMap<Long, XmlData> (or something like this). Then you iterate over the csv data and look up from the Map using the Id.

This will speed up your alogithm from O(n^2) to O(n) in theory since list lookup is O(n) and you have to do it n times but HashMap's lookup is O(1) (amortized).

If you can't use HashMap for some reason you can try ordering your xml data and use a binary search algorithm. In that case you can end up with O(n log n) which is still better than O(n^2).