[GitHub] [incubator-iotdb] jixuan1989 opened a new pull request #105: [IOTDB-56] faster memtable.getSortedTimeValuePairList

[GitBox <gi...@apache.org>]

jixuan1989 opened a new pull request #105: [IOTDB-56] faster memtable.getSortedTimeValuePairList
URL: https://github.com/apache/incubator-iotdb/pull/105
 
 
   Now, when we write data into memory, the data is not sorted.
   
   Before we flush data on disk, we need to call getSortedTimeValuePairList() to get the sorted data.
   
   However, current method is implemented by:
   
    
   
   ```
   Map<> tmp = new TreeMap();
   tmp.putAll();
   List<> result = new ArrayList();
   tmp.forEach( x -> result.add(x));
   TreeMap.put() is O(N), the total time complexity is O(N^2), which is not good for this scenario.
   ```
    
   
   We can change it to 
   
   ```
   Map<> tmp = new HashMap();
   tmp.putAll();
   List<> result = new ArrayList();
   tmp.forEach( x -> result.add(x));
   result.sort();
   ```
   Then, the time complexity is O(N) + O(Nlog(N)).
   
   In my experiments, it can save 1/3 time.
   
   

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services