Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (491)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (556)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Best algorithm to sort semi-sorted arrays?  (Read 4970 times)
0 Members and 1 Guest are viewing this topic.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Posted 2007-05-01 07:07:17 »

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?

Offline fletchergames

Senior Member





« Reply #1 - Posted 2007-05-01 17:33:32 »

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.
Offline ddyer

Senior Member


Medals: 5



« Reply #2 - Posted 2007-05-01 18:34:12 »

qwiksort is so easy and so close to optimal, I never use anything else.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #3 - Posted 2007-05-01 19:11:57 »

Quote
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.

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #4 - Posted 2007-05-01 22:42:56 »

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.

Quote
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.

Quote
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.

Quote
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.

Quote
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.

Quote
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.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #5 - Posted 2007-05-01 22:44:05 »

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.
Offline Linuxhippy

Senior Member


Medals: 1


Java games rock!


« Reply #6 - Posted 2007-05-02 10:34:52 »

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

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #7 - Posted 2007-05-02 12:16:14 »

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

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #8 - Posted 2007-05-03 02:28:28 »

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;
     }
   }
Offline Niwak

Senior Member


Medals: 1
Projects: 1



« Reply #9 - Posted 2007-05-03 06:56:10 »

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!
Legends of Yore - The Casual Retro Roguelike
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #10 - Posted 2007-05-03 07:44:08 »

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


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.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #11 - Posted 2007-05-03 07:46:06 »

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.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #12 - Posted 2007-05-04 07:04:17 »

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




Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2007-05-04 21:23:02 »

Going to give it a try Kiss

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #14 - Posted 2007-05-04 23:14:58 »

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);

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #15 - Posted 2007-05-04 23:23:46 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #16 - Posted 2007-05-04 23:44:13 »

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 Smiley
Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #17 - Posted 2007-05-04 23:57:17 »

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;
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #18 - Posted 2007-05-05 00:05:20 »

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!)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #19 - Posted 2007-05-05 00:06:04 »

Cheers!

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #20 - Posted 2007-05-05 00:42:08 »

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.
Offline tofumayhem

Junior Newbie





« Reply #21 - Posted 2007-05-06 00:31:44 »

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.
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #22 - Posted 2007-05-06 11:47:35 »

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...
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #23 - Posted 2007-05-08 02:10:49 »

Riven, while i was unable to get the code you provided to compile, i think i was able to follow your logic Smiley 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);
      }
   }

Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #24 - Posted 2007-05-08 02:15:02 »

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
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #25 - Posted 2007-05-08 03:42:23 »

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.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #26 - Posted 2007-05-08 06:40:04 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Nickropheliac (15 views)
2014-08-31 22:59:12

TehJavaDev (23 views)
2014-08-28 18:26:30

CopyableCougar4 (29 views)
2014-08-22 19:31:30

atombrot (41 views)
2014-08-19 09:29:53

Tekkerue (39 views)
2014-08-16 06:45:27

Tekkerue (35 views)
2014-08-16 06:22:17

Tekkerue (25 views)
2014-08-16 06:20:21

Tekkerue (36 views)
2014-08-16 06:12:11

Rayexar (72 views)
2014-08-11 02:49:23

BurntPizza (49 views)
2014-08-09 21:09:32
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!