Best algorithm to sort semi-sorted arrays?

[moogie]

I am trying my hand at the hutter prize (http://prize.hutter1.net/)

My current compression algorithm sorts an array of Comparable Objects every main cycle.

-This array of objects can potentically increase by one object per cycle.
-Each object's comparision value can change per cycle, however its order is mostly kept.

This means that the over all order of the objects are similar between cycles.

Is there an sorting algorithm which can take advantage of the semi-sorted state of the array?

I was using the default Arrays.sort() however it does not seem to make much use of the semi-sorted input array and is too slow for my use.

In order to speed up the sorting i have relaxed the need to be in strict order. I.e there can be some objects out of order.

To this end I have developed a BucketSort which i thought should speed up the sorting however it seems to have the opposite effect!

Is there any reason why this implementation is quite slow? (three times as slow as Array.sort() )

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36

private static int MAX_BUCKET=65535;    private static Word[] buckets=new Word[MAX_BUCKET];    public static void bucketSortReverse (Word[] a, int n)    {       int i;       int count=1;       int index;       Word curr;       // fill up the buckets with the input words      for (i=0;i<n;i++)       {          curr=a[i];          index=(int) (curr.probablility*MAX_BUCKET);          curr.next=buckets[index];          buckets[index]=curr;       }             // iterate over the buckets and construct the sorted words      for (i=0;i<MAX_BUCKET;i++)       {          curr=buckets[i];                    if (curr!=null)          {             while (curr!=null)             {                a[n-count++]=curr;                curr=curr.next;             }             buckets[i]=null;          }       }    }

*NOTE* Currently my input Word array contains a maximum of 6000 words.


I have found some Open Source code which by default performs very similarly to Arrays.sort in terms of speed and have modified it to be non-strict in its ordering.

This modified sorting algothim is approximately 15% faster but is still really not fast enough.

By reducing the strict ordering of the sorting algorithm i have also reduced the level of compression. Ultimately i would like to have a fast sorting algothrim which takes into acount semi-sorted objects with out reducing strictness of the sort.

Any ideas?

[fletchergames]

Generally, when you use less memory, an algorithm runs faster.  Clearly, there are counter cases (i.e. using more memory to store computations for reuse), but,  in general, using less resources is faster.

In the code you posted, you create a really big array that you don't use very much of (65535 buckets for 6000 words).  An in-place sort might run faster.

I would also make sure that the words aren't all being stored in the same bucket.  I don't know what "curr.probability" is about, so I don't really know what's going on here.

For bucket sort for something like text, I might do the following.  Have one bucket for each character that can potentially appear in the input.  Put each word in the bucket of its first character.

If you aren't sure what characters appear, you can check the first character of each word when inputting them and store them in a HashSet.  Then just create buckets for the characters used.

Since your data isn't all text, that won't work for you.  But in any case, you probably want to have fewer buckets.

Does the class "Word" happen to store 16-bit pieces of data?  If so, you're not really doing a bucket sort (so far as I can tell).  You're storing each Word directly where it goes.  If the Word class doesn't contain other data, you could just use a boolean array or a bitset.  If the Word class does contain other data, I would only have 255 buckets and store the Words by the first byte.  Then I would sort the contents of each bucket.  That would be an actual bucket sort instead of just putting the data where it belongs.

It's kind of hard to tell without knowing what the Word class is.

[ddyer]

qwiksort is so easy and so close to optimal, I never use anything else.

Games published by our own members! Check 'em out!

[t_larkworthy]

qwiksort is so easy and so close to optimal, I never use anything else.

Well your missing out, quicksort is rubbish on semi-ordered data. Shellsort is much better.

[moogie]

Generally, when you use less memory, an algorithm runs faster.  Clearly, there are counter cases (i.e. using more memory to store computations for reuse), but,  in general, using less resources is faster.

That is very interesting, here i thought reducing the number of comparisions would out weight the loss due to using the large array.

In the code you posted, you create a really big array that you don't use very much of (65535 buckets for 6000 words).  An in-place sort might run faster.

The Array.sort and the modified Open source version of Array.sort are in-place sorting algorithms which do seem to confirm your first statement about less resources=faster.

I would also make sure that the words aren't all being stored in the same bucket.  I don't know what "curr.probability" is about, so I don't really know what's going on here.

The probability is a double value which a predictor has generated for each word which is the probability that this word will be the next word in a sequence.
There are cases where the probability will be words with identical probabilities. In this case a linked list is populated at the bucket.

For bucket sort for something like text, I might do the following.  Have one bucket for each character that can potentially appear in the input.  Put each word in the bucket of its first character.

I have seperated the character-level context from the word-level contex to hopefully achieve better compresstion ratio. I do intend to have at least one predictor for the character-level perform similarly to what you have decribed.

If you aren't sure what characters appear, you can check the first character of each word when inputting them and store them in a HashSet.  Then just create buckets for the characters used.

Since your data isn't all text, that won't work for you.  But in any case, you probably want to have fewer buckets.

I have separated the XML portions from the input text and have also sperated the punctuation leaving only words delimited by a space.

Does the class "Word" happen to store 16-bit pieces of data?  If so, you're not really doing a bucket sort (so far as I can tell).  You're storing each Word directly where it goes.  If the Word class doesn't contain other data, you could just use a boolean array or a bitset.  If the Word class does contain other data, I would only have 255 buckets and store the Words by the first byte.  Then I would sort the contents of each bucket.  That would be an actual bucket sort instead of just putting the data where it belongs.

It's kind of hard to tell without knowing what the Word class is.

The Word class represents a string of characters. True, the bucket sort at the moment is not really a bucket... I thought to remove the entire iterative comparision step by putting the words order directly in the sparsely populated array. In my mind i thought it would be quicker... but i am incorrect.

Thanks for you input.

[moogie]

Well your missing out, quicksort is rubbish on semi-ordered data. Shellsort is much better.

I have used two different versions of shell sort, however they did not perform as well as i had hoped. perhaps they were not optmised as much as Array.sort.

[Linuxhippy]

For almost sorted stuff, Selection Sort isn't that bad either.
it has imho its best-case O(n) for sorted stuff :-)

[moogie]

thanks for the suggestion. i will look into seletion sort.

[moogie]

Am i not understanding how the selection sort works? I cannot seem to see how a semi-sorted array of objects would make the sort any more efficient.

here is the implementation of selection sort i have derived from online sources:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17

public static void selectionSort(Comparable a[], int size)    {      int i, j, min;      Comparable tmp;      for (i = 0; i < size - 1; i++)      {        min = i;        for (j = i+1; j < size; j++)          if (a[j].compareTo(a[min])<0)            min = j;        tmp=a[i];        a[i]=a[min];        a[min]=tmp;      }    }

[Niwak]

I have the same problem but with a different data organization so my solution may not fit your situation.

To sort my objects, I use a red-black tree ; when the sorting key changes, items are removed and re-added to the tree.
This makes the sorting dependent on the number of changes in the tree and not (directly) on the number of items in the tree (it is not fulylm true since the cost of adding/removing is linked to the number of items, and this cost will be fairly higher than in a standard list).

In my situation (state sorting in a game engine) this is very well suited since sorting key almost never change, and node adding/removal is fairly sparse (just a few per frame). On a side note, it happens that optimizing the state sorting algorithm was useless since it was not, and by far, a bottleneck.

    Vincent

Games published by our own members! Check 'em out!

[moogie]

Thanks for your suggestion, i might have to see whether it is suitable for my application...


I thought i would try my hand at creating my own sorting algorithm when i had an flash of inspiration:

I do not know if it has been done before, however in my research of programs i have not been able to find anything similar so who knows?

I dub it "Run Sort"

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129   130   131   132   133   134   135   136   137   138   139   140   141   142   143   144   145   146   147

import java.util.Comparator; public class RunSort implements Comparator {    final static private RunSort defaultComparator=new RunSort();        private RunSort()    {          }    public static void sort(Comparable a[])    {       sort(a,0,a.length,defaultComparator);    }          public static void sort(Comparable a[], int start,int end)    {       sort(a,start,end,defaultComparator);    }    public static void sort(Comparable a[], int start,int end,Comparator comparator)    {       Comparable[] tempArray=new Comparable[end-start];       sort(a,start,end,comparator,tempArray);    }    public static void sort(Comparable a[], int start,int end,Comparator comparator,Comparable[] tempArray)    {       // calculate the dimenstion of objects to sort in the given array      int size=end-start;             // copy the objects to sort into the working temporary array      System.arraycopy(a,start,tempArray,0,size);             int prevIndex=0;       int i;       Comparable tmp=null;       Comparable prev;             Run root=null;       Run currRun;       Run prevRun=null;       Run selectedRun=null;       int runCounts=0;             //      // construct the runs of already sorted objects      //             // iterate over the array creating runs of objects already in order...      prev=tempArray[0];       for (i=1;i<size;i++)       {          tmp=tempArray[i];          if (comparator.compare(tmp,prev)<0)          {             currRun=new Run();             runCounts++;             currRun.parentRun=prevRun;             if (prevRun!=null) prevRun.nextRun=currRun;             else root=currRun;             currRun.startIndex=prevIndex;             currRun.endIndex=i;             prevRun=currRun;             prevIndex=i;          }          prev=tmp;       }       // construct the final run      runCounts++;       currRun=new Run();       currRun.parentRun=prevRun;       if (prevRun!=null) prevRun.nextRun=currRun;       else root=currRun;       currRun.startIndex=prevIndex;       currRun.endIndex=i;       //      // construct the sorted objects      //             i=0;             // while there are still multiple runs...      while (runCounts>1)       {          // select the "first" object from the first run         prev=tempArray[root.startIndex+root.offset];          selectedRun=root;                    // compare this object against the "first" objects from the other existing runs.         currRun=root.nextRun;          while (currRun!=null)          {             tmp=tempArray[currRun.startIndex+currRun.offset];                         // if the current run's "first" object is higher than the current best "first" object then this run now has the            // best "first" object and so update the selected run and best object.            if (comparator.compare(tmp,prev)<0)             {                selectedRun=currRun;                prev=tmp;             }             currRun=currRun.nextRun;          }                    // update the offset into the selected run. This offset determines the "first" object of the run.         selectedRun.offset++;                    // if we have reached the end of a run. i.e. a run with only one object...         if (selectedRun.startIndex+selectedRun.offset==selectedRun.endIndex)          {             // update the list of runs by removing the selected run from the list making sure that the root run            // and the tail run are updated as necessary.                         if (selectedRun==root)             {                root=selectedRun.nextRun;             }             else if (selectedRun.nextRun==null)             {                selectedRun.parentRun.nextRun=null;             }             else             {                selectedRun.parentRun.nextRun=selectedRun.nextRun;                selectedRun.nextRun.parentRun=selectedRun.parentRun;             }             runCounts--;            }         // insert the best ( the next highest object) into the input array.        a[start+i++]=prev;       }             // we now only have one run and so no comparisions are needed and just copy the run into the input array as is.      System.arraycopy(tempArray,root.startIndex+root.offset,a,start+i,size-i);    }    public int compare(Object arg0, Object arg1) {       return ((Comparable) arg0).compareTo(arg1);    } }

1   2   3   4   5   6   7   8

public class Run {    public Run nextRun;    public Run parentRun;    public int startIndex;    public int endIndex;    public int offset; }

I am able to achieve 25% increase in speed over Arrays.sort() for my application.

It is tailored for semi-sorted data. The more in-order the data is, the faster the sort.

I will probably make a bench mark to give repeatable and definite results.

[moogie]

If any of you can think of optimistions to this code please do tell! i would love to make the sort even faster.

I do have an even more specialised version which uses a pool of Run objects, this gives about 1% increase.

[moogie]

I have made some modifications to my sorting algorithm which has has increased the speed some what.

The high-level sorting algorithm:

1. iterate over the input array identifying the runs of in-order objects
2. while we have more than 1 run goto 3 else goto 11
3. iterate over the runs comparing the "first" object of each run to identify the run which has the next sorted object making note of the previously selected run.
4. if the selected run's "last" object is greater than or equal to the previously selected run's "first" object then we can assume that the entire selected run can be added to the sorted output array. goto 5 else goto 6
5. copy all the objects in the selected run into the sorted output array. goto 7
6. copy only the "first" object in the selected run into the sorted output array.
7. remove the "first" object from the selected run.
8. if the selected run has no more objects then goto 9 else 10
9. remove the selected run from the list of runs
10. goto 2
11. there is only one run and so directly copy the run into sorted output array.
12. return the sorted array.

I have made a little benchmark on typical data sets generated from my actual compressor (well converted to integers) and it is pretty pretty good.

The jar file and data sets can be found here: http://javaunlimited.net/hosted/moogie/benchmark.zip (i hope Woogley is ok with that)

The test was on a P4 3Ghz dual core running windows XP with
java version "1.5.0_02"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_02-b09)
Java HotSpot(TM) Client VM (build 1.5.0_02-b09, mixed mode)

- The wikicompress.RunSort.sort1() resuses the same temporary array each sort.
- each sort algorithm was performed 1000 times
- the time is in milliseconds
- source code is included in the jar file.
- the gnu.util.arrays.sort is apparently what is used in the GNU java compiler.

Results:

FILE: data_0.txt
java.util.arrays.sort() 359
gnu.java.util.arrays.sort() 547
wikicompress.RunSort.sort() 188
wikicompress.RunSort.sort1() 141
FILE: data_1.txt
java.util.arrays.sort() 391
gnu.java.util.arrays.sort() 532
wikicompress.RunSort.sort() 203
wikicompress.RunSort.sort1() 219
FILE: data_2.txt
java.util.arrays.sort() 359
gnu.java.util.arrays.sort() 485
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 156
FILE: data_3.txt
java.util.arrays.sort() 453
gnu.java.util.arrays.sort() 516
wikicompress.RunSort.sort() 297
wikicompress.RunSort.sort1() 266
FILE: data_4.txt
java.util.arrays.sort() 375
gnu.java.util.arrays.sort() 531
wikicompress.RunSort.sort() 219
wikicompress.RunSort.sort1() 187
FILE: data_5.txt
java.util.arrays.sort() 375
gnu.java.util.arrays.sort() 500
wikicompress.RunSort.sort() 188
wikicompress.RunSort.sort1() 156
FILE: data_6.txt
java.util.arrays.sort() 391
gnu.java.util.arrays.sort() 516
wikicompress.RunSort.sort() 203
wikicompress.RunSort.sort1() 156
FILE: data_7.txt
java.util.arrays.sort() 579
gnu.java.util.arrays.sort() 625
wikicompress.RunSort.sort() 187
wikicompress.RunSort.sort1() 157
FILE: data_8.txt
java.util.arrays.sort() 344
gnu.java.util.arrays.sort() 469
wikicompress.RunSort.sort() 203
wikicompress.RunSort.sort1() 141
FILE: data_9.txt
java.util.arrays.sort() 563
gnu.java.util.arrays.sort() 594
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 156
FILE: data_10.txt
java.util.arrays.sort() 532
gnu.java.util.arrays.sort() 563
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 140
FILE: data_11.txt
java.util.arrays.sort() 453
gnu.java.util.arrays.sort() 579
wikicompress.RunSort.sort() 297
wikicompress.RunSort.sort1() 250
FILE: data_12.txt
java.util.arrays.sort() 343
gnu.java.util.arrays.sort() 485
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 141
FILE: data_13.txt
java.util.arrays.sort() 359
gnu.java.util.arrays.sort() 469
wikicompress.RunSort.sort() 156
wikicompress.RunSort.sort1() 125
FILE: data_14.txt
java.util.arrays.sort() 406
gnu.java.util.arrays.sort() 532
wikicompress.RunSort.sort() 187
wikicompress.RunSort.sort1() 141
FILE: data_15.txt
java.util.arrays.sort() 438
gnu.java.util.arrays.sort() 531
wikicompress.RunSort.sort() 313
wikicompress.RunSort.sort1() 281
FILE: data_16.txt
java.util.arrays.sort() 375
gnu.java.util.arrays.sort() 485
wikicompress.RunSort.sort() 187
wikicompress.RunSort.sort1() 141
FILE: data_17.txt
java.util.arrays.sort() 344
gnu.java.util.arrays.sort() 469
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 156
FILE: data_18.txt
java.util.arrays.sort() 328
gnu.java.util.arrays.sort() 469
wikicompress.RunSort.sort() 188
wikicompress.RunSort.sort1() 140
FILE: data_19.txt
java.util.arrays.sort() 469
gnu.java.util.arrays.sort() 501
wikicompress.RunSort.sort() 265
wikicompress.RunSort.sort1() 203
FILE: data_20.txt
java.util.arrays.sort() 422
gnu.java.util.arrays.sort() 516
wikicompress.RunSort.sort() 235
wikicompress.RunSort.sort1() 203
FILE: data_21.txt
java.util.arrays.sort() 343
gnu.java.util.arrays.sort() 485
wikicompress.RunSort.sort() 172
wikicompress.RunSort.sort1() 125
FILE: data_22.txt
java.util.arrays.sort() 344
gnu.java.util.arrays.sort() 453
wikicompress.RunSort.sort() 204
wikicompress.RunSort.sort1() 156
FILE: data_23.txt
java.util.arrays.sort() 328
gnu.java.util.arrays.sort() 453
wikicompress.RunSort.sort() 157
wikicompress.RunSort.sort1() 140
FILE: data_24.txt
java.util.arrays.sort() 516
gnu.java.util.arrays.sort() 610
wikicompress.RunSort.sort() 187
wikicompress.RunSort.sort1() 141

[Riven]

Going to give it a try

[Riven]

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129   130   131   132   133   134   135   136   137   138   139   140   141   142   143   144   145   146   147   148   149   150   151   152   153   154   155   156   157   158   159   160   161   162   163   164   165   166   167   168   169   170   171   172   173   174

FILE: E:\sort contest\data_0.txt java.util.arrays.sort() 387 gnu.java.util.arrays.sort() 370 wikicompress.RunSort.sort() 201 wikicompress.RunSort.sort1() 146 riven.offending.indices 117 FILE: E:\sort contest\data_1.txt java.util.arrays.sort() 370 gnu.java.util.arrays.sort() 366 wikicompress.RunSort.sort() 228 wikicompress.RunSort.sort1() 181 riven.offending.indices 83 FILE: E:\sort contest\data_2.txt java.util.arrays.sort() 317 gnu.java.util.arrays.sort() 326 wikicompress.RunSort.sort() 152 wikicompress.RunSort.sort1() 119 riven.offending.indices 82 FILE: E:\sort contest\data_3.txt java.util.arrays.sort() 406 gnu.java.util.arrays.sort() 384 wikicompress.RunSort.sort() 285 wikicompress.RunSort.sort1() 268 riven.offending.indices 82 FILE: E:\sort contest\data_4.txt java.util.arrays.sort() 321 gnu.java.util.arrays.sort() 351 wikicompress.RunSort.sort() 189 wikicompress.RunSort.sort1() 153 riven.offending.indices 81 FILE: E:\sort contest\data_5.txt java.util.arrays.sort() 302 gnu.java.util.arrays.sort() 324 wikicompress.RunSort.sort() 151 wikicompress.RunSort.sort1() 115 riven.offending.indices 79 FILE: E:\sort contest\data_6.txt java.util.arrays.sort() 298 gnu.java.util.arrays.sort() 324 wikicompress.RunSort.sort() 159 wikicompress.RunSort.sort1() 118 riven.offending.indices 79 FILE: E:\sort contest\data_7.txt java.util.arrays.sort() 501 gnu.java.util.arrays.sort() 429 wikicompress.RunSort.sort() 153 wikicompress.RunSort.sort1() 117 riven.offending.indices 78 FILE: E:\sort contest\data_8.txt java.util.arrays.sort() 299 gnu.java.util.arrays.sort() 322 wikicompress.RunSort.sort() 151 wikicompress.RunSort.sort1() 115 riven.offending.indices 82 FILE: E:\sort contest\data_9.txt java.util.arrays.sort() 501 gnu.java.util.arrays.sort() 438 wikicompress.RunSort.sort() 153 wikicompress.RunSort.sort1() 115 riven.offending.indices 83 FILE: E:\sort contest\data_10.txt java.util.arrays.sort() 498 gnu.java.util.arrays.sort() 429 wikicompress.RunSort.sort() 153 wikicompress.RunSort.sort1() 117 riven.offending.indices 84 FILE: E:\sort contest\data_11.txt java.util.arrays.sort() 410 gnu.java.util.arrays.sort() 399 wikicompress.RunSort.sort() 293 wikicompress.RunSort.sort1() 264 riven.offending.indices 81 FILE: E:\sort contest\data_12.txt java.util.arrays.sort() 295 gnu.java.util.arrays.sort() 324 wikicompress.RunSort.sort() 153 wikicompress.RunSort.sort1() 115 riven.offending.indices 81 FILE: E:\sort contest\data_13.txt java.util.arrays.sort() 312 gnu.java.util.arrays.sort() 331 wikicompress.RunSort.sort() 172 wikicompress.RunSort.sort1() 146 riven.offending.indices 81 FILE: E:\sort contest\data_14.txt java.util.arrays.sort() 498 gnu.java.util.arrays.sort() 431 wikicompress.RunSort.sort() 156 wikicompress.RunSort.sort1() 116 riven.offending.indices 82 FILE: E:\sort contest\data_15.txt java.util.arrays.sort() 387 gnu.java.util.arrays.sort() 384 wikicompress.RunSort.sort() 292 wikicompress.RunSort.sort1() 258 riven.offending.indices 84 FILE: E:\sort contest\data_16.txt java.util.arrays.sort() 294 gnu.java.util.arrays.sort() 332 wikicompress.RunSort.sort() 162 wikicompress.RunSort.sort1() 121 riven.offending.indices 81 FILE: E:\sort contest\data_17.txt java.util.arrays.sort() 294 gnu.java.util.arrays.sort() 330 wikicompress.RunSort.sort() 151 wikicompress.RunSort.sort1() 115 riven.offending.indices 81 FILE: E:\sort contest\data_18.txt java.util.arrays.sort() 296 gnu.java.util.arrays.sort() 324 wikicompress.RunSort.sort() 154 wikicompress.RunSort.sort1() 119 riven.offending.indices 80 FILE: E:\sort contest\data_19.txt java.util.arrays.sort() 372 gnu.java.util.arrays.sort() 386 wikicompress.RunSort.sort() 238 wikicompress.RunSort.sort1() 204 riven.offending.indices 82 FILE: E:\sort contest\data_20.txt java.util.arrays.sort() 367 gnu.java.util.arrays.sort() 366 wikicompress.RunSort.sort() 238 wikicompress.RunSort.sort1() 205 riven.offending.indices 82 FILE: E:\sort contest\data_21.txt java.util.arrays.sort() 294 gnu.java.util.arrays.sort() 328 wikicompress.RunSort.sort() 160 wikicompress.RunSort.sort1() 120 riven.offending.indices 81 FILE: E:\sort contest\data_22.txt java.util.arrays.sort() 308 gnu.java.util.arrays.sort() 342 wikicompress.RunSort.sort() 177 wikicompress.RunSort.sort1() 137 riven.offending.indices 82 FILE: E:\sort contest\data_23.txt java.util.arrays.sort() 293 gnu.java.util.arrays.sort() 326 wikicompress.RunSort.sort() 157 wikicompress.RunSort.sort1() 118 riven.offending.indices 80 FILE: E:\sort contest\data_24.txt java.util.arrays.sort() 525 gnu.java.util.arrays.sort() 463 wikicompress.RunSort.sort() 157 wikicompress.RunSort.sort1() 124 riven.offending.indices 113

To remove the array-copy overhead from the timing-results, this is the modified benchmark code:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51

long total;          total = 0;          for (int i = 0; i < 1000; i++)          {             System.arraycopy(array1, 0, array2, 0, array1.length);             long start = System.nanoTime();             Arrays.sort(array2, 0, array1.length, Collections.reverseOrder());             total += System.nanoTime() - start;          }          System.out.println("java.util.arrays.sort() " + total / 1000000);          total = 0;          for (int i = 0; i < 1000; i++)          {             System.arraycopy(array1, 0, array2, 0, array1.length);             long start = System.nanoTime();             gnu.java.util.Arrays.sort(array2, 0, array1.length, gnu.java.util.Collections.reverseOrder());             total += System.nanoTime() - start;          }          System.out.println("gnu.java.util.arrays.sort() " + total / 1000000);          total = 0;          for (int i = 0; i < 1000; i++)          {             System.arraycopy(array1, 0, array2, 0, array1.length);             long start = System.nanoTime();             RunSort.sort(array2, 0, array1.length, Collections.reverseOrder());             total += System.nanoTime() - start;          }          System.out.println("wikicompress.RunSort.sort() " + total / 1000000);          total = 0;          for (int i = 0; i < 1000; i++)          {             System.arraycopy(array1, 0, array2, 0, array1.length);             long start = System.nanoTime();             RunSort.sort(array2, 0, array1.length, Collections.reverseOrder(), array3);             total += System.nanoTime() - start;          }          System.out.println("wikicompress.RunSort.sort1() " + total / 1000000);          total = 0;          for (int i = 0; i < 1000; i++)          {             System.arraycopy(array1, 0, array2, 0, array1.length);             long start = System.nanoTime();             SortContest.sort(array2, array2);             total += System.nanoTime() - start;          }          System.out.println("riven.offending.indices " + total / 1000000);

[Riven]

The algorithm simply does this:

1. find the objects that seem out-of-order
2. null the array-indices of the out-of-order objects
3. put those in another array
4. sort that array (typically 0-2 elements)
5. refill the array with the original indices
5.1 for every null encountered, goto next
5.2 else, if the next sorted out-of-order object is bigger than the next to-be-added-object, add it
5.3 else, add next-to-be-added-object

it takes advangate of the fact that the array is 99.9% sorted, so the out-of-order-array is tiny

[moogie]

Nice!

Could you provide the source code? (it would save me implementing it myself... damn i am lazy!)

 I would love to see the performance in my actual application!

I guess i didnt really mind including the array copying in the benchmark as i assumed that the copy will have constant time for all iterations. Though you know what they say about assumptions

[Riven]

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94

public static void sort(Object[] src, Object[] dst)    {       if (src.length > aux.length)       {          aux = new Wrapper[src.length * 2];          for (int i = 0; i < aux.length; i++)             aux[i] = new Wrapper();       }       // prevent field-access in loops      Wrapper[] aux = SortContest.aux;       Wrapper[] holder = SortContest.holder;       int[] indices = SortContest.indices;       int len = src.length;       // link objects to wrappers, then calc index      for (int i = 0; i < len; i++)       {          aux[i].real = src[i];          aux[i].calcSortIndex();       }       // find offensing indices      int x = aux[0].getSortIndex();       int y = aux[1].getSortIndex();       int count = 0;       for (int i = 2; i < len; i++)       {          int z = aux[i].getSortIndex();          if ((x > y && y < z) || (x < y && y > z))          {             holder[count] = aux[i - 1];             indices[count] = i - 1;             count++;          }          x = y;          y = z;       }       // sort offending indices      for (int a = 0; a < count; a++)       {          for (int b = a; b < count; b++)          {             int ai = holder[a].getSortIndex();             int bi = holder[b].getSortIndex();             if (ai < bi)             {                Wrapper tmp = holder[b];                holder[b] = holder[a];                holder[a] = tmp;                int tmp___ = indices[b];                indices[b] = indices[a];                indices[a] = tmp___;             }          }       }       // zero out offending indices      for (int i = 0; i < count; i++)          aux[indices[i]] = null;       // fill dst with src + offending indices at proper position      int step = 0;       int search = 0;       int filled = 0;       while (step != count)       {          if (aux[search] == null)             search++;          else             dst[filled++] = (aux[search].getSortIndex() < holder[step].getSortIndex()) ? holder[step++].real : aux[search++].real;       }       while (filled < len)       {          if (aux[search] == null)             search++;          else             dst[filled++] = aux[search++].real;       }       // restore offending indices      for (int i = 0; i < count; i++)          aux[indices[i]] = holder[i];    }

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16

public class Wrapper {    public Object real;    public void calcSortIndex()    {       this.sortIndex = ((Integer) real).intValue();    }    private int sortIndex = 0;    public int getSortIndex()    {       return sortIndex;    } }

[Riven]

It is however stunning to see that with the server VM (6.0) your code is beating the crap out of mine (80ms vs 40ms!)

[moogie]

Cheers!

[moogie]

It is however stunning to see that with the server VM (6.0) your code is beating the crap out of mine (80ms vs 40ms!)

! that is a little unexpected... i would have thought mine would have much more over head.

[tofumayhem]

When I have to deal with algorithms I normally take a look at this page at wikipedia:
http://en.wikipedia.org/wiki/Sorting_algorithm

The Big 0 notation gives a good overview of the quality of the algorithms and the descriptions are detailed enough to pick the right one.

[moogie]

When I have to deal with algorithms I normally take a look at this page at wikipedia:
http://en.wikipedia.org/wiki/Sorting_algorithm

The Big 0 notation gives a good overview of the quality of the algorithms and the descriptions are detailed enough to pick the right one.

yep the wiki site is very informative! i had researched there before asking here. all of the sorting algs there are aimed at highly random data. this not the case for my situation unfortunetly...

[moogie]

Riven, while i was unable to get the code you provided to compile, i think i was able to follow your logic and have implemented a sort based on that code.

However it does not seem to improve upon the Runsort.

Perhaps i have implemented your ideas incorrectly? would you be able to take a look?

here is my code:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129   130   131   132   133   134   135   136   137   138   139   140   141   142   143   144   145   146   147   148   149   150   151   152   153   154   155   156   157   158

public static void InOrderSort(Comparable a[], int start,int end,Comparator comparator,Comparable temp1[], Comparable temp2[])    {             Comparable prev=temp1[0]=a[start];       int LIMIT=Math.max(10,(end-start)/5);             Comparable curr;       int inOrderArraySize=1;       int outOfOrderArraySize=0;       int runOneStartIndex=start+1;       int runOneSize=0;             //////////      // Populate the in order and out of order arrays      //             for (int i=start+1;i<end;i++)       {          curr=a[i];                    // if out of order...         if (comparator.compare(curr,prev)<0)          {             // add the previous run of in order elements into the in order array            System.arraycopy(a,runOneStartIndex,temp1,inOrderArraySize,runOneSize);                         // update the related variables            inOrderArraySize+=runOneSize;             runOneSize=0;             runOneStartIndex=i+1;                                     // add the the out of order element into the out of order array            temp2[outOfOrderArraySize++]=curr;                         // check to see if the out of order array is too large. This is indictive of a pathological            // condition where the first element is much larger than the rest of the elements and so            // use the Runsort.sort instead.            if (outOfOrderArraySize>LIMIT)             {                RunSort.sort(a,start,end,comparator,temp1);                return;             }          }          // else we are in order...         else          {             // update the in order run length            runOneSize++;                         // update the previous in order element            prev=curr;          }       }             //////////      // Sort the out of order array      //       // check to see if the input array is already sorted...      if (outOfOrderArraySize==0) return;             // if the last element was not added to the out of order array then we need to finish populating the      // in order array      if (runOneSize>0)       {          System.arraycopy(a,runOneStartIndex,temp1,inOrderArraySize,runOneSize);          inOrderArraySize+=runOneSize;       }             // we need to sort the outOfOrderArray if there are more than one element in the array.      if (outOfOrderArraySize>1)       {          Arrays.sort(temp2,0,outOfOrderArraySize,comparator);       }                   //////////      // Re-populate the input array with the sorted elements      //                   // the current index into the input array to place the next sorted element      int index=start;             // the current indecies into the in order and sorted out of order arrays      int j=0,k=0;             curr=temp1[j++];       prev=temp2[k++];             runOneStartIndex=0;       runOneSize=0;             // re-populate the input array with sorted elements      while (index<end && outOfOrderArraySize>0 && inOrderArraySize>0)       {          // if "first" element in the in order array is smallest...         if (comparator.compare(curr,prev)<0)          {             // update the next "first" element in the in order array            curr=temp1[j++];                         // update the coutn of in order elements left            inOrderArraySize--;                         // update the current in order run length            runOneSize++;                      }          // else the "first" element in the out of order array is smallest...         else          {             // copy the previous run of in order elements into the input array            System.arraycopy(temp1,runOneStartIndex,a,index,runOneSize);                         // update the current index into the input array            index+=runOneSize;                         // update the run's variables            runOneSize=0;             runOneStartIndex=j;                         // copy the element out of the out of order array into the input array            a[index++]=prev;                         // update the next "first" element in the out of order array            prev=temp2[k++];                         // update the count of out of order elements left            outOfOrderArraySize--;          }               }             // if there is a run of in order elements still to be copied into the input array ...      if (runOneSize>0)       {          // copy the previous run of in order elements into the input array         System.arraycopy(temp1,runOneStartIndex,a,index,runOneSize);          index+=runOneSize;       }             // we have no left over elements and so return      if (index==end) return;             // if we have left over sorted out of order elements and we directly copy the elements into the      // input array.      if (inOrderArraySize==0)       {          System.arraycopy(temp2,k-1,a,index,outOfOrderArraySize);       }       // else we have left over in order elements and so we directly copy the elements into the      // input array.      else       {          System.arraycopy(temp1,j-1,a,index,inOrderArraySize);       }    }

[moogie]

Actually i do see an improvement when i compile the test into a native windows executable using gcj.

Interestingly enough the time taken for the InOrderSort is very similar between data sets:

C:\TEMP\oldprojects\WikiCompress>testsort1
FILE: data_0.txt
java.util.arrays.sort() 2235
gnu.java.util.arrays.sort() 2218
wikicompress.RunSort.sort() 610
wikicompress.RunSort.sort1() 203
Utilities.InOrderSort() 203
FILE: data_1.txt
java.util.arrays.sort() 2235
gnu.java.util.arrays.sort() 2234
wikicompress.RunSort.sort() 625
wikicompress.RunSort.sort1() 281
Utilities.InOrderSort() 203
FILE: data_2.txt
java.util.arrays.sort() 2203
gnu.java.util.arrays.sort() 2203
wikicompress.RunSort.sort() 610
wikicompress.RunSort.sort1() 203
Utilities.InOrderSort() 187
FILE: data_3.txt
java.util.arrays.sort() 2313
gnu.java.util.arrays.sort() 2296
wikicompress.RunSort.sort() 657
wikicompress.RunSort.sort1() 375
Utilities.InOrderSort() 203
FILE: data_4.txt
java.util.arrays.sort() 2234
gnu.java.util.arrays.sort() 2219
wikicompress.RunSort.sort() 625
wikicompress.RunSort.sort1() 234
Utilities.InOrderSort() 203
FILE: data_5.txt
java.util.arrays.sort() 2297
gnu.java.util.arrays.sort() 2812
wikicompress.RunSort.sort() 782
wikicompress.RunSort.sort1() 296
Utilities.InOrderSort() 204
FILE: data_6.txt
java.util.arrays.sort() 2203
gnu.java.util.arrays.sort() 2328
wikicompress.RunSort.sort() 657
wikicompress.RunSort.sort1() 218
Utilities.InOrderSort() 204
FILE: data_7.txt
java.util.arrays.sort() 2250
gnu.java.util.arrays.sort() 2515
wikicompress.RunSort.sort() 719
wikicompress.RunSort.sort1() 219
Utilities.InOrderSort() 265
FILE: data_8.txt
java.util.arrays.sort() 2672
gnu.java.util.arrays.sort() 2813
wikicompress.RunSort.sort() 875
wikicompress.RunSort.sort1() 234
Utilities.InOrderSort() 250
FILE: data_9.txt
java.util.arrays.sort() 2594
gnu.java.util.arrays.sort() 2640
wikicompress.RunSort.sort() 625
wikicompress.RunSort.sort1() 204
Utilities.InOrderSort() 203
FILE: data_10.txt
java.util.arrays.sort() 2187
gnu.java.util.arrays.sort() 2219
wikicompress.RunSort.sort() 609
wikicompress.RunSort.sort1() 203
Utilities.InOrderSort() 203
FILE: data_11.txt
java.util.arrays.sort() 2375
gnu.java.util.arrays.sort() 2469
wikicompress.RunSort.sort() 656
wikicompress.RunSort.sort1() 391
Utilities.InOrderSort() 203
FILE: data_12.txt
java.util.arrays.sort() 2297
gnu.java.util.arrays.sort() 2218
wikicompress.RunSort.sort() 610
wikicompress.RunSort.sort1() 187
Utilities.InOrderSort() 313
FILE: data_13.txt
java.util.arrays.sort() 2360
gnu.java.util.arrays.sort() 2390
wikicompress.RunSort.sort() 625
wikicompress.RunSort.sort1() 219
Utilities.InOrderSort() 203
FILE: data_14.txt
java.util.arrays.sort() 2172
gnu.java.util.arrays.sort() 2344
wikicompress.RunSort.sort() 656
wikicompress.RunSort.sort1() 203
Utilities.InOrderSort() 203
FILE: data_15.txt
java.util.arrays.sort() 2375
gnu.java.util.arrays.sort() 2360
wikicompress.RunSort.sort() 671
wikicompress.RunSort.sort1() 391
Utilities.InOrderSort() 203
FILE: data_16.txt
java.util.arrays.sort() 2234
gnu.java.util.arrays.sort() 2235
wikicompress.RunSort.sort() 640
wikicompress.RunSort.sort1() 219
Utilities.InOrderSort() 203
FILE: data_17.txt
java.util.arrays.sort() 2250
gnu.java.util.arrays.sort() 2219
wikicompress.RunSort.sort() 609
wikicompress.RunSort.sort1() 203
Utilities.InOrderSort() 203
FILE: data_18.txt
java.util.arrays.sort() 2234
gnu.java.util.arrays.sort() 2219
wikicompress.RunSort.sort() 610
wikicompress.RunSort.sort1() 203
Utilities.InOrderSort() 187
FILE: data_19.txt
java.util.arrays.sort() 2266
gnu.java.util.arrays.sort() 2265
wikicompress.RunSort.sort() 641
wikicompress.RunSort.sort1() 328
Utilities.InOrderSort() 187
FILE: data_20.txt
java.util.arrays.sort() 2250
gnu.java.util.arrays.sort() 2250
wikicompress.RunSort.sort() 641
wikicompress.RunSort.sort1() 328
Utilities.InOrderSort() 187
FILE: data_21.txt
java.util.arrays.sort() 2235
gnu.java.util.arrays.sort() 2250
wikicompress.RunSort.sort() 640
wikicompress.RunSort.sort1() 203
Utilities.InOrderSort() 203
FILE: data_22.txt
java.util.arrays.sort() 2250
gnu.java.util.arrays.sort() 2266
wikicompress.RunSort.sort() 609
wikicompress.RunSort.sort1() 234
Utilities.InOrderSort() 203
FILE: data_23.txt
java.util.arrays.sort() 2219
gnu.java.util.arrays.sort() 2250
wikicompress.RunSort.sort() 609
wikicompress.RunSort.sort1() 204
Utilities.InOrderSort() 203
FILE: data_24.txt
java.util.arrays.sort() 2172
gnu.java.util.arrays.sort() 2156
wikicompress.RunSort.sort() 625
wikicompress.RunSort.sort1() 219
Utilities.InOrderSort() 265

[moogie]

well, it must be more efficient as when i use this InOrderSort in my actual compression program I am able to save about 1 second in total run time when compressing a 256k sample as compared to using RunSort.

[Riven]

Hm, I'll try to improve it a bit, and provide compilable sourcecode. Sorry..