Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-10225

Improve IntroSelector with 3-way partitioning

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 9.1
    • None
    • None
    • New

    Description

      The same way we improved IntroSorter, we can improve IntroSelector with Bentley-McIlroy 3-way partitioning. The gain in performance is roughly the same.

      With this new approach, we always use medians-of-medians (Tukey's Ninther), so there is no real gain to fallback to a slower medians-of-medians technique as an introspective protection (like the existing implementation does). Instead we can simply shuffle the sub-range if we exceed the recursive max depth (this does not change the speed as this intro-protective mechanism almost never happens - maybe only in adversarial cases).

      Attachments

        Issue Links

          Activity

            People

              Unassigned Unassigned
              broustant Bruno Roustant
              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 - 3h 20m
                  3h 20m

                  Slack

                    Issue deployment