[
https://issues.apache.org/jira/browse/ARROW-8543?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated ARROW-8543:
----------------------------------
Labels: pull-request-available (was: )
> [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)
