[
https://issues.apache.org/jira/browse/ARROW-8543?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17088946#comment-17088946
]
Mayur Srivastava commented on ARROW-8543:
-----------------------------------------
Hi [~apitrou],
Thanks for looking into it!
I agree on O(N log N) due to sorting. My comment was mainly on post sorting
algorithm.
The algorithm is as follows (let me know if I'm making a mistake) (ref:
[https://github.com/apache/arrow/blob/master/cpp/src/arrow/io/interfaces.cc]):
{noformat}
start=ranges.begin(), prev=start, next=prev
while (++next != end) {
if (isLargerThanHole(prev, next)) {
if (next - start > 1) {
CoalesceUtilLargeEnough(start, next, coalesced output)
}
else {
// append start to coalesced output
}
start = next;
}
prev = next;
}
if (next - start > 1) {
CoalesceUtilLargeEnough(start, next, coalesced output)
}
else {
// append start to coalesced output
}{noformat}
To simplify, let's assume there is no hole in the ranges.
Then, we increment 'next' till the end in the 'while' loop. This is the first
pass iterating from start to end in Coalesce().
Then we call CoalesceUtilLargeEnough() which will iterate from start to end and
append coalesced ranges to the result. This is the second pass in
CoalesceUntilLargeEnough().
This is the reason I called it two pass algorithm.
My proposal ([https://github.com/apache/arrow/pull/7002]) is to change it to a
single pass.
Other than single pass benefits, it does less copying and is shorter in number
of lines of code.
Let me know what you think about it.
Thanks,
Mayur
> [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)
