You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "Bruno Roustant (Jira)" <ji...@apache.org> on 2021/11/08 13:53:00 UTC
[jira] [Commented] (LUCENE-10225) Improve IntroSelector with 3-way
partitioning
[ https://issues.apache.org/jira/browse/LUCENE-10225?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17440475#comment-17440475 ]
Bruno Roustant commented on LUCENE-10225:
-----------------------------------------
{code:java}
RANDOM
IntroSelector ... 397 422 407 448 395 394 417 390 394 406
IntroSelector2 ... 361 357 372 368 366 363 362 361 361 371
RANDOM_LOW_CARDINALITY
IntroSelector ... 661 724 743 707 830 696 734 711 745 779
IntroSelector2 ... 360 393 355 369 373 359 367 369 344 360
RANDOM_MEDIUM_CARDINALITY
IntroSelector ... 423 394 465 387 398 418 396 393 415 399
IntroSelector2 ... 378 364 371 373 361 360 368 362 369 365
ASCENDING
IntroSelector ... 127 127 128 126 130 127 126 131 127 130
IntroSelector2 ... 137 134 135 133 134 134 135 134 135 137
DESCENDING
IntroSelector ... 209 221 205 212 203 205 210 208 206 211
IntroSelector2 ... 185 184 183 183 184 186 187 184 184 183
STRICTLY_DESCENDING
IntroSelector ... 213 210 208 214 207 213 213 206 209 206
IntroSelector2 ... 184 188 183 186 184 183 182 188 184 184
ASCENDING_SEQUENCES
IntroSelector ... 308 320 493 460 287 374 372 423 391 380
IntroSelector2 ... 201 216 234 218 218 211 211 203 207 236
MOSTLY_ASCENDING
IntroSelector ... 256 298 264 351 255 448 196 353 256 397
IntroSelector2 ... 134 138 139 137 140 138 135 137 138 140 {code}
> Improve IntroSelector with 3-way partitioning
> ---------------------------------------------
>
> Key: LUCENE-10225
> URL: https://issues.apache.org/jira/browse/LUCENE-10225
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Bruno Roustant
> Priority: Major
>
> 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).
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org