You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Yonik Seeley (JIRA)" <ji...@apache.org> on 2016/05/24 15:26:12 UTC
[jira] [Comment Edited] (LUCENE-7299) BytesRefHash.sort() should
use radix sort?
[ https://issues.apache.org/jira/browse/LUCENE-7299?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15298343#comment-15298343 ]
Yonik Seeley edited comment on LUCENE-7299 at 5/24/16 3:25 PM:
---------------------------------------------------------------
bq. So this is just for integers.
No, MSB variations are fine for strings... you go byte-by-byte, just as you would for integers, with each byte determining the appropriate bucket.
I imagine this would have a weakness for large common prefixes. Random strings may be the best case since it equally distributed between buckets (hence does a maximum amount of work on each pass).
edit: I just peeked at Adrien's code, and the common-prefix thing should be handled relatively well:
+ // short-circuit: if all keys have the same byte at offset k, then recurse directly
was (Author: yseeley@gmail.com):
bq. So this is just for integers.
No, MSB variations are fine for strings... you go byte-by-byte, just as you would for integers, with each byte determining the appropriate bucket.
I imagine this would have a weakness for large common prefixes. Random strings may be the best case since it equally distributed between buckets (hence does a maximum amount of work on each pass).
> BytesRefHash.sort() should use radix sort?
> ------------------------------------------
>
> Key: LUCENE-7299
> URL: https://issues.apache.org/jira/browse/LUCENE-7299
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Adrien Grand
> Assignee: Adrien Grand
> Priority: Minor
> Attachments: LUCENE-7299.patch
>
>
> Switching DocIdSetBuilder to radix sort helped make things significantly faster. We should be able to do the same with BytesRefHash.sort()?
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org