[
https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13492720#comment-13492720
]
Uwe Schindler commented on LUCENE-4546:
---------------------------------------
Hi Stefan,
it is some time ago when I worked on SorterTemplate, so I don't have all the
facts in mind. There are different implementations of QuickSort available, also
those working without any pivot (like yours). But as far as I remember, the
performance tests showed, that the additional swaps and compares added some
slowdown (depending on the order of input data), so the explicit pivot methods
helped. The SorterTemplate quicksort implementation is also the one that was
used in Lucene from the beginning, so I did not want to change the algorithm in
a minor release. We could add some new performance tests with your
implementation and compare the speed, but I think, e.g. CollectionUtil, which
uses Collections.swap() would get much slower by this.
I agree, the class is very nice for sorting of non-array data, but it is
currently marked as @lucene.internal, so the usability for non-lucene code was
never thought of, performance was the only driving force :-) But I checked the
javadocs, it is clearly documented that setPivot(i) has to store the value of
slot i for later comparison with comparePivot(j).
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Assignee: Uwe Schindler
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java,
> TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon
> inconsistent sorting behaviour, of course, only a randomized test caught
> this;)
> Because SorterTemplate.quicksort is used in several places in the code
> (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and
> transitively index and search), I'm a bit puzzled that this either hasn't
> been caught by another higher-level test or that neither my test nor my
> understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0,
> this might even be a more critical issue requiring a higher priority than
> 'major'.
> So, can a second pair of eyes please have a timely look at the attached test
> and patch?
> Basically the current quicksort implementation seems to assume that luckily
> always the median is chosen as pivot element by grabbing the mid element, not
> handling the case where the initially chosen pivot ends up not in the middle.
> Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
