[ https://issues.apache.org/jira/browse/IOTDB-56?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
xiangdong Huang closed IOTDB-56. -------------------------------- > Faster getSortedTimeValuePairList() of Memtable (WritableMemChunk) > ------------------------------------------------------------------ > > Key: IOTDB-56 > URL: https://issues.apache.org/jira/browse/IOTDB-56 > Project: Apache IoTDB > Issue Type: Improvement > Reporter: xiangdong Huang > Assignee: xiangdong Huang > Priority: Major > Labels: pull-request-available > Time Spent: 20m > Remaining Estimate: 0h > > 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: > > {code:java} > // code placeholder > Map<> tmp = new TreeMap(); > tmp.putAll(); > List<> result = new ArrayList(); > tmp.forEach( x -> result.add(x));{code} > 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 > {code:java} > // code placeholder > Map<> tmp = new HashMap(); > tmp.putAll(); > List<> result = new ArrayList(); > tmp.forEach( x -> result.add(x)); > result.sort();{code} > Then, the time complexity is O(N) + O(Nlog(N)). > In my experiments, it can save 1/3 time. > -- This message was sent by Atlassian JIRA (v7.6.14#76016)