Re: TimSort

[Ted Yu]

I found this:
http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/src/share/classes/java/util/TimSort.java.html

First, Comparator is required. But T may implement Comparable.
Second, the API doesn't accept List:
    public static <T> void sort(T[] a, Comparator<? super T> c) {

I wrote a helper Comparator in my local copy for number 1.
I wonder if there is a version which removes the above two constraints ?

Thanks

On Mon, Apr 25, 2011 at 8:44 PM, dg <gil...@gmail.com> wrote:

Things should get better in future; java 7 (should/will/might) include
TimSort, which is much faster on already-sorted arrays.  A google for
"TimSort java" leads to much interesting reading.

-dg

On Apr 22, 12:03 pm, Sean McCauliff <sean.mccaul...@gmail.com> wrote:
> I benchmarked it by calling Collections.sort() on an array of Integer
> of varying length and comparing it a method that iterates over the
> array and calls compareTo on the current and previous array element.
> Running times seems to scale linearly with the array length, but
> Collections.sort() is about 8-15 times slower with an average of about
> 12.3 times slower than just checking that the array is already sorted.
>  The fact that Collections.sort() runs in linear time seems good
> enough for my purposes.  Thanks for mentioning it.
>
> Sean

>
>
>
> On Wed, Apr 20, 2011 at 7:28 AM, Kevin Bourrillion <kev...@google.com> wrote:
> > Rumor has it that sorting an already-sorted array is very nearly as fast as
> > just checking that the array is sorted already, but I haven't benchmarked
> > that yet.  If it proves false by a margin, I'd consider a feature for this
> > in our libraries.
>

> > On Tue, Apr 19, 2011 at 9:27 PM, SeanM <sean.mccaul...@gmail.com> wrote:
>
> >> Is there way to do this without having the Builder do an additional
> >> sort on the data added to the map?  Or does the Builder check that the
> >> data is sorted before doing a sort.
>
> >> Thanks,
> >> Sean
>
> >> --
> >> guava-...@googlegroups.com
> >> Project site:http://guava-libraries.googlecode.com
> >> This group:http://groups.google.com/group/guava-discuss
>
> >> This list is for general discussion.
> >> To report an issue:http://code.google.com/p/guava-libraries/issues/entry
> >> To get help:http://stackoverflow.com/questions/ask(use the tag "guava")
>
> > --
> > Kevin Bourrillion @ Google
> >http://guava-libraries.googlecode.com

--
guava-...@googlegroups.com
Project site: http://guava-libraries.googlecode.com
This group: http://groups.google.com/group/guava-discuss

This list is for general discussion.
To report an issue: http://code.google.com/p/guava-libraries/issues/entry
To get help: http://stackoverflow.com/questions/ask (use the tag "guava")

[Martin Buchholz]

On Tue, Apr 26, 2011 at 12:04, Ted Yu <yuzh...@gmail.com> wrote:
> I found this:
> http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/src/share/classes/java/util/TimSort.java.html

That link is from a time when TimSort was proposed for openjdk7.
It has been integrated in the meantime.
See
http://en.wikipedia.org/wiki/Timsort

Martin

[Ted Yu]

The link at the bottom of the page points to the same source code.

I will proceed and write the version accepting List.

Thanks

[Louis Wasserman]

I'd...assume JDK 7 would have a List implementation, too?  Double-check.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[Ted Yu]

We're using:
java version "1.6.0_24"

[Ted Yu]

Hi,
There're several System.arraycopy() calls in original code.
I want to get some suggestion on how that should be the proper substitute for List type.

I want to avoid calling List.toArray(), call TimSort and convert the array back to List.

Cheers

[Maaartin G]

> First, Comparator is required. But T may implement Comparable.

Use com.google.common.collect.Ordering<T>.natural().

On Wednesday, April 27, 2011 12:20:57 AM UTC+2, Ted wrote:

Hi,
There're several System.arraycopy() calls in original code.
I want to get some suggestion on how that should be the proper substitute for List type.

I want to avoid calling List.toArray(), call TimSort and convert the array back to List.

 

It looks like all methods (including List.addAll) use arraycopy or toArray() internally. Maybe use Lists.newArrayListWithCapacity(to-from) and copy it in a loop. I doubt that it gets any faster.

[Louis Wasserman]

I am strongly of the opinion that if JDK 7 has a nice, new sorting implementation, that there's no reason for Guava to try to re-implement it.  Collections.sort() has been perfectly good for many years, and it's not worth rushing to replace it in Guava before JDK 7 comes out.  

That said, there are better approaches to implementing timsort for general Lists, if you're just interested in doing so for the lulz.  I recommend something along the lines of the following:

int[] indexes = new int[n];

for(int i=0;i<n;i++)

  indexes[i] = i;

timsort(indexes, new Comparator<Integer>(){

  public int compare(Integer i, Integer j){

    return comparator.compare(list.get(i), list.get(j));

  }

}

Object[] sorted = new Object[n];

for(int i=0;i<n;i++)

  sorted[i] = list.get(indexes[i]);

return Arrays.asList((E[]) sorted);

This way, you're sorting an integer array, which lets you use System.arraycopy() as you like, but doesn't use list.toArray().  This is the basis of my Haskell timsort implementation, which is at https://github.com/lowasser/parsort/.  (Note: this also includes my Haskell parallelizations of various other sorting algorithms.)

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[Louis Wasserman]

Okay!  There are other reasons in Haskell why that approach didn't work there, btw, but I certainly believe you.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

On Wed, Apr 27, 2011 at 3:04 PM, Joshua Bloch <j...@google.com> wrote:

Louis,

It's at all clear to me that this will be faster in Java.  List.toArray is really, really fast for the most common List implementation (ArrayList).  Collections.sort has always dumped the List to an array, sorted, and written back to the List since I wrote it in '97. I'd be really interested if anyone could demonstrate better results with an alternative approach.

    Josh