lucene-java-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Arvind Kalyan <bas...@gmail.com>
Subject Re: Merging ordered segments without re-sorting.
Date Wed, 23 Oct 2013 22:20:12 GMT
On Wed, Oct 23, 2013 at 2:45 PM, Adrien Grand <jpountz@gmail.com> wrote:

> Hi,
>
> On Wed, Oct 23, 2013 at 10:19 PM, Arvind Kalyan <base16@gmail.com> wrote:
> > Sorting is not an option for our case so we will most likely implement a
> > variant that merges the segments in one pass. Using TimSort is great but
> in
> > our case the 2 segments will be highly interspersed and would not benefit
> > from the galloping in TimSort.
>
> I think Shai didn't mention TimSort because of galloping, but because
> it tries to discover the monotonic sequences in your data. In your
> particular case, this means that the sorting would run in linear time
> instead of O(n log(n)) given that the 2 segments to merge are sorted.
>


OK, I went back and read about TimSort and it does appear to be optimized
for this use-case. Apologize for my ignorance :-)

I will benchmark the available approach itself then, in that case. Will
revert back if the performance in unacceptable.

Thanks.

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message