Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (576)
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  
  Good sort algorithms  (Read 2224 times)
0 Members and 1 Guest are viewing this topic.
Offline Preston

Senior Duke


Medals: 4



« Posted 2003-10-23 08:58:59 »

To keep Markus' Wurm thread to its topic, I'll try move the "what algorithm is best to sort lists" sub-thread to this location. For a start I copy my last two articles.
Also I'd like to add that of course it always depends on one's task what has to be sorted in order to choose the right algorithm. So the topic's name isn't very accurate.

Quote
Radix sort is the way to go, it's an order of magnitude faster than Collections.sort() and ultimately it sorts in 5 log n speed instead of n log n which I believe Collections manages.
Cas :)

Radix sort ... sounds interesting. Thanks for the hint. I've read a little bit in an algorithm book... basically it says:

The heap sort (of the C++ STL for example) has a worst time O(n*log(n)), with n being the number of elements in the list. It's not stable and the pre-sorting of the list doesn't help.

The Java "Collections.sort()" is a kind of merge sort, which has a worst time O(n*log(n)). It is stable however and it runs substantially faster on nearly sorted lists.

The radix sort has a O(n*s), with s being the size of the key. It is stable and to pre-sorting of the list doesn't help.

Is that correct so far? Hope so. :-)
Well, it depends on whether you've got some kind of pre-sorting in the list, whether you need a stable sort, and how large the list (and the key size) is. :-)  So I'll have to figure out which fits best to my alpha blending sorting.

Some other posters mentioned that memory consumption of a sort algorithm matters, too.


Still, I don't see why the Collection.sort() algorithm is slower than other good sorting algorithms, for example if you want to sort surfaces or particles which have got alpha transparency.
I always thought a O(n*log(n)) was pretty OK? Isn't it?
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #1 - Posted 2003-10-23 09:13:01 »

Quote

The Java "Collections.sort()" is a kind of merge sort, which has a worst time O(n*log(n)). It is stable however and it runs substantially faster on nearly sorted lists.

Still, I don't see why the Collection.sort() algorithm is slower than other good sorting algorithms, for example if you want to sort surfaces or particles which have got alpha transparency.
I always thought a O(n*log(n)) was pretty OK? Isn't it?


O(blah) means "if you remove any multiplicative constants".

So, one O(n*log-n) might take 500*n*log(n), and another might take 2*n*log(n). Therefore, one is 250 times faster than the other, but they are both O(n*log-n).

The point about merge sort is that the variance of it's execution time across different lists is relatively low (although IIRC there are some variants that are even lower variance) - you can guarantee it will always execute about as fast for any list of a given size. Other sorts are much faster for *some* lists, and much slower for others.

Merge sort is nearly always used everywhere as the "generic" sort, because you can guarantee good performance. If you *know* the patterns your data is typically arranged in (can discover this by simple trial and error) you can pick a much better sort algo for your app. But remember that the API has to be good for all cases.

malloc will be first against the wall when the revolution comes...
Offline Preston

Senior Duke


Medals: 4



« Reply #2 - Posted 2003-10-23 09:34:02 »

Interesting article you wrote:

Quote


O(blah) means "if you remove any multiplicative constants".

So, one O(n*log-n) might take 500*n*log(n), and another might take 2*n*log(n). Therefore, one is 250 times faster than the other, but they are both O(n*log-n).

Even on the same data?

For example; optimally you have a class which holds the data (a single 3d-particle in Markus' case) and it has got the right comparable inferface (or a comperator class if this fits better). Assumed the Collection class would hold several sort algorithms, and now you should be able to use the one which fits best, be doing tests.
1  
2  
3  
4  
List thelist; // holds <n> particle objects
// ...
Collections.quicksort(thelist); // measure time.
Collections.heapsort(thelist); // measure time.

Do I understand you correctly that for the quicksort method call this could mean 500*n*log(n), whilst for the heapsort method call it could mean 100*n*log(n) ?

Quote
Merge sort is nearly always used everywhere as the "generic" sort, because you can guarantee good performance. If you *know* the patterns your data is typically arranged in (can discover this by simple trial and error) you can pick a much better sort algo for your app. But remember that the API has to be good for all cases.

I see. That's the point then.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #3 - Posted 2003-10-23 10:14:16 »

Quote
Assumed the Collection class would hold several sort algorithms, and now you should be able to use the one which fits best, be doing tests.
1  
2  
3  
4  
List thelist; // holds <n> particle objects
// ...
Collections.quicksort(thelist); // measure time.
Collections.heapsort(thelist); // measure time.

Do I understand you correctly that for the quicksort method call this could mean 500*n*log(n), whilst for the heapsort method call it could mean 100*n*log(n) ?


Yes. Google for "big o notation" - there should be thousands of good pages for it. You'll find explanation of why O() is a useful metric, and why it deliberately does NOT differentiate between two algorithms which are hundreds of times faster/slower than each other like this. It's a simple concept, so should be easy to grasp.

malloc will be first against the wall when the revolution comes...
Offline princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #4 - Posted 2003-10-23 11:36:50 »

And back to radix sorting: the radix sort is massively useful in 3D rendering as everything you need to sort on is numerical. The radix sorts I use work on both ints and floats, and ideally suited to sorting 10k+ triangles a frame on multiple keys.



Cas Smiley

Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #5 - Posted 2003-10-23 14:51:19 »

Got any code? =) I found some sourceforge site, but there were no releases.

Play Minecraft!
Offline tom
« Reply #6 - Posted 2003-10-23 16:22:14 »

http://cvs.sourceforge.net/viewcvs.py/spgl/spgl/src/com/shavenpuppy/jglib/algorithms/RadixSort.java

I did a quick test, and princec RadixSort is roughly 3 times faster than my Advanced non-recursive quicksort Smiley

Offline Markus_Persson

JGO Wizard


Medals: 16
Projects: 19


Mojang Specifications


« Reply #7 - Posted 2003-10-23 18:24:55 »

Ah, thanks for the link. I'm really bad at sourceforge/cvs. Wink

Play Minecraft!
Offline tortoise

Junior Duke




<3 Shmups


« Reply #8 - Posted 2003-10-23 19:52:13 »

Quote

I always thought a O(n*log(n)) was pretty OK? Isn't it?


It's been proven that if you don't have any preestablished knowledge on what you are sorting (like Radix sort knows its working with numbers, or you don't know how partially sorted your stuff already is, etc), then O(n*logn) is as good as it gets.
Offline altair

Senior Newbie





« Reply #9 - Posted 2003-10-24 05:11:10 »

Correct me if I am wrong but accessing or inserting an element in a balanced (red-black) tree is O(log n). So, using a SortedMap is still faster than using a radix sort. The only advantage of the radix sort (or others) I can see is when basic (non object) types are managed (then again it is possible to write a class that would manage such types).
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline abies

Senior Duke





« Reply #10 - Posted 2003-10-24 07:48:06 »

Trees can be faster if you only add/remove few elements per iteration. If you want to recreate tree every time, you are back to n*log(n) in best case. Frame coherence does not help here much - even slightest change in viewer position will change all distances for all elements - and even if your tree would be correctly sorted from start, you still need to remove and add every element to be sure (probably faster by just recreating it from scratch).

Artur Biesiadowski
Offline MGodehardt

Junior Duke




why does the chicken cross the road?


« Reply #11 - Posted 2003-11-07 08:48:53 »

It depends on what u sort for e.g. if u sort a userlist and u have a maximum length for a username then radixsort is a nice algo.

if u use too many buckets in radix sorts, it maybe slower than any other sorting algo, i learned it at university ( you can go to university and hear some lessons about sorting )

So make some notes about what u sort

1.) has it a fixed length
2.) how many different chars ( numbers have 10 )
    --> for radix this would be 10 buckets

3.) google around and look for what to do when
4.) experiment with different algos, measure them

Sometimes u spend 40 or 80 hours on research and experimental programming, but then u will have the correct sorting algo.

Radix will perform bad on presorted lists , means where 90% of the list is already sorted.
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.

Longarmx (38 views)
2014-10-17 03:59:02

Norakomi (29 views)
2014-10-16 15:22:06

Norakomi (24 views)
2014-10-16 15:20:20

lcass (28 views)
2014-10-15 16:18:58

TehJavaDev (56 views)
2014-10-14 00:39:48

TehJavaDev (55 views)
2014-10-14 00:35:47

TehJavaDev (46 views)
2014-10-14 00:32:37

BurntPizza (64 views)
2014-10-11 23:24:42

BurntPizza (36 views)
2014-10-11 23:10:45

BurntPizza (78 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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