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