[
https://issues.apache.org/jira/browse/ARROW-8543?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17088901#comment-17088901
]
Antoine Pitrou commented on ARROW-8543:
---------------------------------------
Can you explain why the current algorithm is O(N^2)? CoalesceUntilLargeEnough()
is called on disjoint subsets of the ranges, so each range is examined only
once.
(however, the algorithm is O(N log N) due to sorting)
> [C++] IO: single pass coalescing algorithm
> ------------------------------------------
>
> Key: ARROW-8543
> URL: https://issues.apache.org/jira/browse/ARROW-8543
> Project: Apache Arrow
> Issue Type: Improvement
> Components: C++
> Reporter: Mayur Srivastava
> Priority: Major
>
> The current coalescing algorithm is a O(N^2) two pass algorithm (where N is
> number of ranges) (first implemented in
> https://issues.apache.org/jira/browse/ARROW-7995). In the first pass, the
> Coalesce() function finds the begin and end of a candidate range that can be
> coalesced. In the second, pass the CoalesceUntilLargeEnough() function goes
> over the ranges from begin to end and adds coalesced range to the result
> (out).
> The proposal is to convert the algorithm to an O(N) single pass algorithm
> that computes coalesced ranges while making the first pass over the ranges in
> the list. This algorithm is also shorter in lines of code and hence
> (hopefully) more maintainable in long term.
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
