Here is a challenge of another sort. Who can write the fastest sorting algorithm?
I post here because I know this is a good place full of smart people who like a challenge, many of which are also programmers. I have searched the internet and never come across anything that really was fast for what I was interested in. I attempted this challenge about a year ago and came up with an algorithm that I feel is pretty fast, it is about twice as fast as an optimized quick sort, and its the fastest I've found for sorting things of size 10,000 to 100,000,000 on regular computers (not that it would be slow for things bigger, but I have only tried to make it for in memory sorting). Now I'm not here to brag or anything, I'm here to get a challenge and to see if my algorithm can standup to other's speed.
For this challenge lets say fastest sort algorithm to sort 10,000,000 uniform random positive integers from 0 to 2^31. Feel free to take advantage of that fact that its uniform distribution, I did, but I think it would preform pretty well on non uniform also, I haven't tried yet. Things like bucket sorts would be theoretically ideal for this, but in practice they weren't that fast because they were basically consantly getting cache misses.
Now I'm not going to post the code for my algorithm yet, because if it actually is any good I might want to do something with it some day and not have someone else claim it as their own. But I will post the code used for timing it and provide an optimized quicksort for you to compare your algorithms against, since you can see how my algorithm compares against it:
xws:~/me/sort/new] darren% ./runsort darren 10000000
darren took 2.090000
[xws:~/me/sort/new] darren% ./runsort quicksort 10000000
quicksort took 5.100000
Here's the code to time the sorting algs
I know many computer scientist just say well aw its the same asymtotic behavior so what is the point? But for real world applications people care about run time. This run time varies from computer to computer but I compared this sorting algorithms along with others on several different machines and they were always roughly the same speed relative to each other. Also in my algorithm I use some function calls to mac specific stuff to load some memory while its doing other stuff, this improved overall speed by about 10% and this equivalent thing could done on most machines.
To add your own sort to this code. Write your sort of the form void sort(int *data, int length). Add this function into a new file or into the demo.c. Then in sort.c add the name of the function into the list like is done for quicksort and insertionsort. My code isn't much commented but everything that you need to know to use it is.
Good luck and feel free to post or private message any questions.
Yeah, its slower than the qsort provided because it tries to hard to avoid worst case scenario.
std::sort() from the C++ standard library is, at least in gcc, pretty fast. Faster than anything I have came up with (yes, it's faster than quicksort-only-partitions-bigger-than-n-items-and-run-insertion-sort-to-the-rest, even if the quicksort part is done with a median-of-three pivot choice which is one of the fastest). Of course it's a generic algorithm, so a specialized algorithm which takes advantage of some certain property of the data can be made faster for that particular data.
Interesting, I never tried the C++ STL libraries, I always dismissed c++ stuff as inefficient crap. Although it is no where near the speed of my sort function, it is faster than a simple quicksort + insertion sort, like you said.
Also the code I provided for testing stuff won't compile in C++ but if you change the line in sort.h from
typedef void (* func_td) ();
to
typedef void (* func_td) (int *, int);
it will. For your interest here is a comparison of std sort algorithms
quicksort took 4.710000
stlsort took 4.620000
stdquick took 10.790000
stdheap took 46.150002
stdmerge took 16.450001
"quicksort" is the function I wrote in the demo. The others are as follows:
#include <algorithm>
#include <stdlib.h>
using namespace std;
void stlsort(int *a, int n) {
sort(a, a+n);
}
int compare(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
void stdquick(int *a, int n) {
qsort(a, n, sizeof(int), compare);
}
void stdmerge(int *a, int n) {
mergesort(a, n, sizeof(int), compare);
}
void stdheap(int *a, int n) {
heapsort(a, n, sizeof(int), compare);
}
C coders often have wrong prejudices about C++ simply because they don't know how it works internally. When things are done right, C++ code can be much cleaner, easier to use, easier to understand and safer than equivalent C code, usually with no penalty in speed whatsoever (in fact, in some cases the C++ version can even be slightly faster). However, C coders are sometimes intimidated by the pretty interfaces the C++ standard libraries offer because they don't know what they are doing internally and they form all kinds of wrong assumptions.
Personally I love C for tiny projects, I completely detest it for larger projects, I love C++ for most projects, and I hate Java for all projects (even though if I had to choose between C and Java for a large project, I would go for Java... or kill myself, whichever causes less pain).
C coders are sometimes intimidated by the pretty interfaces the C++ standard libraries offer because they don't know what they are doing internally and they form all kinds of wrong assumptions.
Well I originally stopped using C++ a few years ago because I preformed some efficiency test and C++ was slower. So my assumptions were correct then, but I guess C++ compilers have improved or the one I used then just sucked (although they were g++ both times). So thank you for showing me C++ has acceptable speed.
But I can't let the standard libray beat my quicksort now can I? So I improved it, I also improved my fastest sort slightly (the non comparison based one), here's new results for 10,000,000:
stl took 4.560000
quick took 4.140000
darren took 1.870000
You can download the new code here: http://www.wam.umd.edu/~darreon/sorter.tar.gz Also I changed the way functions are called a little instead of passing int * array, int length, its just 2 pointers, like the stl sort is called. Best luck to anyone who attempts this.
Well I originally stopped using C++ a few years ago because I preformed some efficiency test and C++ was slower.
I hope you realize how silly that sounds... :)
Since you can do exactly the same thing in C++ which you can do in C, it's just impossible to claim that C++ is slower than C (at least not if the compiler is doing the same thing for both). Whichever speed test you are making in C, you can just compile the exact same code (assuming you are not using reserved C++ keywords, but that's irrelevant) as C++ and the result should be equally fast. There's nothing in C which could not be replicated exactly in C++ (usually with the exact same code).
Now, C++ adds some libraries not available in C (even though it still offers the same ones as in C). While some of these libraries can be used for the same tasks as their C equivalents, they usually are still different libraries with different capabilities and features. If your speed comparison is based on comparing the old C libraries with new C++ libraries providing similar functionality, then if and when you get a speed difference, making a general claim that one language is slower than the other is just misguided and wrong. One could say you are comparing apples with oranges. The fact that C++ offers some new libraries doesn't make C++ slower than C. It just makes C++ to offer new libraries.
For instance, C streams are usually faster than C++ streams. While the latter can be used for the same purposes as the former, they can be used for more, and there are technical reasons why they can't achieve the same speeds (or at least it's quite difficult). However, that doesn't make "C++ slower than C", it just makes "C++ streams slower than C streams". And nothing stops you from using C streams in a C++ program (even though if you do so, you have to be aware of some OOP limitations they impose).
Hmm somehow I don't believe you :), on my computer it takes 0.24 seconds just to make one pass over the data without even doing anything.
Also for anyway who post results, please also post the time the quicksort took to run on your computer so we have something to compare it too. Also make sure your sort is valid too, (use ./sorter name length 1 1) to have it check validity.
Warp wrote:
I hope you realize how silly that sounds... :)
Well sure it sounds silly, but that is what the test showed then...
I make some program that did a bunch of stuff compiled with gcc, timed. Then switched to g++, and it got slower, same exact code. Then I changed the malloc to new, and it got even slower. Then I changed it to use classes, and it got even slower, all the while having it do to same thing. These were not negliable speed differences either all these things together made it like 30+% slower.
Now I do a similar test though and speeds stay the same. So silly as it seems it was backed by at least some evidence before. I agree it makes no sense C++ should be just as fast, at least if the code is the same. But g++ must have sucked back then, I just don't know. But I am sorry ok, I accept your C++ as equal speed.
Alright, since I have just discovered that there is an algorithm similar to mine that has already been made, I will post my code here and an explanation of why it is so fast. Don't steal it or I will kill you.
int is_sorted(int *a, int *e) {
return e - a < 2 || a[0] < a[1] && is_sorted(a + 1, e);
}
void darren(int *a, int *e) {
while(!is_sorted(a, e)) {
int i = randmodn(e - a - 1);
if(a[i] < a[i + 1]) SWAP2(a[i], a[i+1])
SWAP2(a[0], e[-1])
}
}
One of the main reasons this is fast is because its best case run time is optimal. Also since the code is very short it doesn't take up much space on the stack, and this brings surpisingly good speed improvements. There may appear to be some inefficiencies, such as the recursion in is_sorted, but the gcc automatically optimizes this so that its infact iterative and fast.
Since it is based on randomness it will run just as fast on any data, its impossible for someone to try and feed you a worst case data. However worst case scenario is still possible, but on average it will finish in a finite amount of time. To ensure this it is important you use a good random number generator, I had to write my own to get this to work fast and good, I can provide that code if you want. If you do not believe me try it on a list of size 8 or smaller first.
EDIT: Oh yeah, updated the code that you can download with it, at http://www.wam.umd.edu/~darreon/sorter.tar.gz
Okay, glad you asked. The algorithm applies swaps on a random element and its neighbor, and since it is random, it will eventually be sorted and will stop. The only confusing part is that the if statement swaps them if they are in order, but the statement after that swaps first and last elements, so it can't get into a position it can't get out of.
It was an april fool's joke I made kekeke. Although it will work, I designed it to be as slow as possible asymtoticly (non obviously). It takes something like O(n^(n^2)) time to run. For example on my computer it was instant for 7 or less, took about 3 seconds average to sort a list of length only 8, and it took over a day to sort something of length 9! Had to write own random function because the built in one repeats about every 2 billion times, so it could never finish.
since it is random, it will eventually be sorted and will stop
How do you prove that the (unspecified) pseudorandom number generator eventually yields a sorted array?
Pseudorandom number generators generally don't yield every possible number combination even if ran infinitely.
There's a set sequence they'll repeat, and there's no way of ensuring the sequence contains a subsequence that will eventually lead into the desired result.
For that reason, there's no guarantee that even this code ever terminates:
int array[] = {0,0,1,0,0};
for(;;)
{
int c = rand() % 5;
if(array[c] == 1) break;
}
Even if it were truly random instead of pseudorandom, there's exists a calculatable probability that the outcome never yields the desired number during N iterations of the loop.
That was fun. I was wondering why your sort algorithm was sooooooo slow. In fact, it wasn't able to sort arrays with more than 8 elements in it.
By the way, last month I build my own version of a generic quicksort, but I hadn't time for testing how efficient it was.
It proved that it was a bit slower compared with your last version of quicksort. After applying the same improvements, my version is now a bit faster.
Also, I think it should be even faster with objects bigger than an int, I will test it if I find more time.
Joined: 7/5/2004
Posts: 551
Location: Karlstad, Sweden
I've been checking out these "Sorting Algorithm" threads and I still don't know wtf it's all about? Do you write some weird text and then paste it into some program and it'll say some Einstein stuff or wtf?! ^^ It really irritates me!
Maybe if you had programming experience you could understand it better. :)
Basically, we're comparing algorithms.
Algorithm is a formalized description of a method of accomplishing a task (such a sorting an array).
Even if it were truly random instead of pseudorandom, there's exists a calculatable probability that the outcome never yields the desired number during N iterations of the loop.
Yaya this is true, proofs are not my thing. My original statement was something like "... but on average it will finish in a finite amount of time."
Also like you say truly random number generation is a problem because it is theoretically impossible, but you can always write one that is random for a desired number of times before repeating, the one I provided in the code for that algorithm repeated something like every 10^17 numbers.
@DrJones: glad to here you tried the challenge. I gave up trying to improve my algorithm, I'll probably post it here soon because recently I discovered that someone else has already used a similar method, so there is no need to worry about my code being stolen.
Also you said it wasn't able to sort stuff of more than 8 elements, but I got it to do 9, it took over a day, mad props to anyone who can get 10 kekek.
Yaya this is true, proofs are not my thing. My original statement was something like "... but on average it will finish in a finite amount of time."
Since there exists an infinite amount of sequences which do not contain the desired subsequence, it is possible that the generator will go through all those other sequences before going through one which does contain the desired subsequence (but since there's an infinite amount of other sequences it may never happen).
How do you calculate an average if some of the times are infinite?-)
Also like you say truly random number generation is a problem because it is theoretically impossible
One has to also define which kind of randomness we want. A sequence may be truely random, but its distribution might not be even.
Someone has said something along the lines of "if a million monkeys hammer on a million typewriters for a million years, they will at some point write the entire works of Shakespeare" (different versions of this circulate with varying amounts of monkeys and time). This is a wrong statement. The statement implies that they will eventually reach a certain given sequence (eg. the works of Shakespeare). That is just wrong. They might reach that sequence, but there's nothing which guarantees that. In fact, I would say it's extremely improbable.
Firstly, using monkeys is a very bad choice. A monkey hitting a typewriter will have an extremely uneven distribution. It's extremely improbable that all possible sequences of keys are ever typed. Most likely very regular patterns will be typed, and those will never end up in such a large sequence as the works of Shakespeare.
Secondly, even if instead of monkeys some truely evenly-distributed random generator was used, it still doesn't guarantee that the sequence will be reached in a finite time. In fact, it doesn't even guarantee that the sequence will be reached in an infinite time (because there's an infinite amount of sequences not containing the wanted subsequence and thus it is possible that all those are gone through before a correct sequence is reached).
but you can always write one that is random for a desired number of times before repeating, the one I provided in the code for that algorithm repeated something like every 10^17 numbers.
That is still only a pseudorandom generator. The reason is that it is completely predictable: Knowing the algorithm you will know what will be the next random number generated. That is certainly not randomness... :)
It looks random for the casual viewer, but isn't. :)
Joined: 7/5/2004
Posts: 551
Location: Karlstad, Sweden
Bisqwit wrote:
Maybe if you had programming experience you could understand it better. :)
Basically, we're comparing algorithms.
Algorithm is a formalized description of a method of accomplishing a task (such a sorting an array).
Thanks :> So from now on I'll stay away from these threads because I'm not interrested in programming and it just makes me dizzy ;P
I've been checking out these "Sorting Algorithm" threads and I still don't know wtf it's all about? Do you write some weird text and then paste it into some program and it'll say some Einstein stuff or wtf?! ^^ It really irritates me!
put yourself in my rocketpack if that poochie is one outrageous dude
I said I would post the algorithm along time ago and forgot so here it is. Kinda messy, sorry.
#include "utils.h"
#include <math.h>
#include <stdlib.h>
#define TTNB 9
#define LCUT 4
#define HCUT 9
#define BEST 7.55
#define BCUT 10
#define RMX 31
struct _node {
int d;
struct _node *n;
};
typedef struct _node ll;
void bucket1k(int *a, int *e, int max) {
int shift = max - TTNB, nb = (1 << TTNB);
int *i, *w, d;
ll *c, **j;
ll **bucket = (ll **)calloc(nb, sizeof(ll *));
ll *water = (ll *)malloc((e - a) * sizeof(ll));
for(i = a, c = water; i < e; i++) {
//vec_dst(i + 4, 0x04080000, 1);
j = bucket + (*i >> shift & ((1 << TTNB) - 1));
c->n = *j;
c->d = *i;
*j = c++;
}
for(j = bucket, i = a; j < bucket + nb; j++)
for(c = *j; c; c = c->n) {
// *(i++) = c->d;
d = c->d;
for(w = i++ - 1; *w > d; w--) w[1] = *w;
w[1] = d;
}
free(bucket);
free(water);
}
void count1bit(int *a, int *e, int shift, int times) {
int *i, *j, temp, mask;
i = a - 1; j = e, mask = 1 << shift - 1;
while(1) {
while(!(*++i & mask));
while(*--j & mask);
if (j < i) break;
SWAP(*i, *j);
}
if(times > 1) {
count1bit(a, i, shift - 1, times - 1);
count1bit(i, e, shift - 1, times - 1);
}
else {
bucket1k(a, i, shift - 1);
bucket1k(i, e, shift - 1);
}
}
int pickshift(int r) {
int v = r / BEST + 0.5;
if(v == 0) v = r;
else v = ceil((float)r / v);
if(v > HCUT) v = HCUT;
return v;
}
#define F(x) ((x) >> shift & mask)
void countess(int *a, int *e, int max, int remains) {
int i, shift, k, temp, v, j, m, mask, *s, *c, *p;
v = pickshift(remains);
k = 1 << v;
mask = k - 1;
shift = max - v;
c = (int *)calloc(k, sizeof(int));
s = (int *)malloc((k + 1) * sizeof(int));
//for(i = 0; i < k; i+= 8) vec_dst(c + i, 0x04080000, 0);
for(p = a; p < e; p++) {
vec_dst(p + 8, 0x04080000, 1);
c[F(*p)]++;
}
for(i = 1, *s = 0, s[k] = e - a; i < k; i++) c[i] += s[i] = c[i-1];
for(m = 0; m < k; m++) {
if(s[m] == c[m]) continue;
i = s[m];
v = a[i];
do {
j = --c[F(v)];
SWAP(a[j], v);
vec_dst(a + j - 1, 0x04010000, 0);
} while(j != i);
}
free(c);
v = remains - max + shift;
if(v >= LCUT) for(i = 0; i < k; i++)
countess(a + s[i], a + s[i + 1], shift, v);
else if(v == 0) for(i = 0; i < k; i++)
bucket1k(a + s[i], a + s[i + 1], shift);
else for(i = 0; i < k; i++)
count1bit(a + s[i], a + s[i + 1], shift, v);
free(s);
}
void darren(int *a, int *e) {
int lgn = log10(e - a) / log10(2) + 0.5 - BCUT;
if(lgn <= 0) bucket1k(a, e, RMX);
else if(lgn < LCUT) count1bit(a, e, RMX, lgn);
else countess(a, e, RMX, lgn);
// countess(a, a + n, RMX, 31);
}
If you're not using mac comment out the vec_dst, it just prefetches data, I don't know the other operating systems equivalent. Basically the function 'countess' is the only important one, it is like counting sort but without extra memory usuage.
