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

[C++] Implement argsort kernels (sort indices) for integers using O(n) counting sort

    XMLWordPrintableJSON

Details

    Description

      This function requires knowledge of the minimum and maximum of an array. If it is small enough, then an array of size maximum - minimum can be constructed and used to tabulate value frequencies and then compute the sort indices (this is called "grade up" or "grade down" in APL languages). There is generally a cross-over point where this function performs worse than mergesort or quicksort due to data locality issues

      Attachments

        1. e5-2650.png
          111 kB
          Yibo Cai

        Issue Links

          depends upon

          New Feature - A new feature of the product, which has yet to be developed. ARROW-1900 [C++] Add kernel functions for determining value range (maximum and minimum) of integer arrays

          • Major - Major loss of function.
          • Resolved
          relates to

          Improvement - An improvement or enhancement to an existing feature or task. ARROW-7526 [C++][Compute]: Optimize small integer sorting

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Resolved
          links to

          Web Link GitHub Pull Request #6495

          Activity

            People

              yibocai Yibo Cai
              wesm Wes McKinney
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 4h 40m
                  4h 40m