Uploaded image for project: 'Apache Arrow'
  1. Apache Arrow
  2. ARROW-8543

[C++] IO: single pass coalescing algorithm

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Resolved
    • Major
    • Resolution: Fixed
    • None
    • 1.0.0
    • C++

    Description

      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.

       

      Attachments

        Activity

          People

            mayuropensource Mayur Srivastava
            mayuropensource Mayur Srivastava
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: