You are viewing a plain text version of this content. The canonical link for it is here.

Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2020/04/21 18:02:13 UTC

[GitHub] [arrow] mayuropensource opened a new pull request #7002: ARROW-8543: [C++] Single pass coalescing algorithm + Rebase

mayuropensource opened a new pull request #7002:
URL: https://github.com/apache/arrow/pull/7002


   Hi,
   
   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 PR (https://issues.apache.org/jira/browse/ARROW-8543) 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.
   
   Thanks,
   Mayur Srivastava
   


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [arrow] github-actions[bot] commented on issue #7002: ARROW-8543: [C++] Single pass coalescing algorithm + Rebase

Posted by GitBox <gi...@apache.org>.

github-actions[bot] commented on issue #7002:
URL: https://github.com/apache/arrow/pull/7002#issuecomment-617329923


   https://issues.apache.org/jira/browse/ARROW-8543


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [arrow] pitrou commented on issue #7002: ARROW-8543: [C++] Single pass coalescing algorithm + Rebase

Posted by GitBox <gi...@apache.org>.

pitrou commented on issue #7002:
URL: https://github.com/apache/arrow/pull/7002#issuecomment-617339230


   The original PR message is slightly misleading: both algorithms have the same complexity (O(N) except for the sorting step which is O(N log N)). However, it's true that the new algorithm is more compact and not less readable.


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org