[
https://issues.apache.org/jira/browse/ARROW-8543?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Antoine Pitrou resolved ARROW-8543.
-----------------------------------
Fix Version/s: 1.0.0
Resolution: Fixed
Issue resolved by pull request 7002
[https://github.com/apache/arrow/pull/7002]
> [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
> Fix For: 1.0.0
>
>
> The current coalescing algorithm is a 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 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.
> Correction: Post sorting, the current algorithm is O(N) and the improvement
> is O(N). I called the current algo O(N^2) due to an oversight.
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
