Posted: 3/10/2010 4:14 AM
Post subject: Sorting Optimization Challenge
Quote
flagitious
Player (201)
Joined: 7/6/2004
Posts: 511
The challenge is to see how fast of a sort you can make. Theoretically sorting is not an interesting problem, as the proven lower bounds (O(n*lg(n)) for comparison and O(n) for integer sorts) have been achieved numerous ways. However in practice there are wide ranges of speeds. I believe I know the fastest way to sort large amounts of integers (flash sort) and small amount of integers (insertion sort), but it seems there are alot of potential methods for medium amount of numbers. So this challenge is to see how fast of a program you can write to sort 1000 uniformly random integers from 0 to 2**30-1. To make it easier to measure, perform it 50000 times and report the sum of time. So that we can all run code on the same computer use http://golf.shinh.org/checker.html the performance checker for shinh's code golf server (accepts like 60+ languages). You can use this c code to generate the numbers, measure the time, and check the validity of your sort (it has a slow version of quicksort included). You can use whatever language and testing script you like. You can pass your sort either a linked list or an array (so long as its returns the same data type). Also it can be inplace or not. Let's say the competition ends in two weeks, march 23. In the meantime please only post times and not the actual algorithm. After this time we can collaborate and combine methods etc. Also this challenge idea is kind of made up without any idea what to expect, so if you have any ideas to change it or suggestions please feel free to post them.
g,o,p,i=1e4,a[10001];main(x){for(;p?g=g/x*p+a[p]*i+2*!o: 53^(printf("%.4d",o+g/i),p=i,o=g%i);a[p--]=g%x)x=p*2-1;}
Posted: 3/11/2010 4:47 PM
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Your time measurement is flawed. If sorting the 1000 integers takes less than one tick of the clock, it will be measured as taking 0 seconds. IIRC the clock() function updates less frequently than 10000 times per second in linux systems, so it's perfectly feasible for a piece of code to run faster than that. And even if it doesn't run faster than that, if the clock ticks only a few times, there will be a rather big rounding error in the timing.
Posted: 3/11/2010 11:38 PM
Quote
flagitious
Player (201)
Joined: 7/6/2004
Posts: 511
Hmm I think it is pretty precise (results vary by 2% for 1 second long test), but you are right the round off could lead to inaccurate times. I will look into this more. Does anyone know how to get more accurate timing (in c)? One way if there is no more accurate function is to generate all random arrays first, sort them all, then check them all, but I rather avoid this as it might reduce cache hits. To get things started my best method so far results in 0.86 seconds (sum of 50k trials). I think there are some methods that can beat it, but that should be hard to beat, I've already put alot of effort into it. Edit: here is a sample version that times it all at once to avoid possible inaccuracy. Time was still 0.86 for my sort though.
g,o,p,i=1e4,a[10001];main(x){for(;p?g=g/x*p+a[p]*i+2*!o: 53^(printf("%.4d",o+g/i),p=i,o=g%i);a[p--]=g%x)x=p*2-1;}
Posted: 3/26/2010 12:50 AM
Quote
flagitious
Player (201)
Joined: 7/6/2004
Posts: 511
Time is up. If anyone cares the fastest method I found was a basic counting sort into 2024 buckets, and after that an insertion sort to clean up, this had a sum of 0.45 seconds for 50k trials.
g,o,p,i=1e4,a[10001];main(x){for(;p?g=g/x*p+a[p]*i+2*!o: 53^(printf("%.4d",o+g/i),p=i,o=g%i);a[p--]=g%x)x=p*2-1;}