[
https://issues.apache.org/jira/browse/ARROW-8543?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17088959#comment-17088959
]
Mayur Srivastava commented on ARROW-8543:
-----------------------------------------
You are right.
I should correct myself. The correct statement is "change 2 pass algorithm
(O(N)) with a constant 2 to 1 pass algorithm (O(N)) with a constant 1".
What do you think?
> [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
> Labels: pull-request-available
>
> 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)
