Author |
Message |
md
|
Posted: Wed Nov 07, 2007 8:37 pm Post subject: Sorting Contest |
|
|
As inspired by rdrake's crappy assignment I am going to run a simple contest.
The Rules
* You can use any language you like, provided I can compile the source on linux. This unfortunately limits Turing unless someone wishes to make an effort to get OpenT running for me.
* You must provide source code
* My workstation will be used for judging.
* I shall post my solution at the end of the contest, as well as the winning entry.
* The contest shall start at 9:00 tonight and run until 12:00 tomorrow night. After that I shall test all programs and announce the winner (most likely friday night/saturday morning).
* The winner(s) shall be the person who can sort each data set fastest. There could be two winners.
The Goal
* You must provide one program capable of sorting single-byte values and one capable of sorting 2-byte integers (shorts, words, whatever).
* Your program must take a filename as the first argument. That file will contain bytes/shorts that are to be sorted. Your program should overwrite this file with sorted data.
* Your program must not use excessive amounts of memory. Reading the entire file into memory to sort it is cheating (and not practical).
* Your program must sort 256MB (give or take) worth of bytes/shorts, and then 1GB worth of bytes/shorts.
The Data
* Data will be generated for the final test with dd and /dev/urandom. Each program will be run with the same file; and the resulting file will be tested to ensure it contains the same numbers as the original. I will not provide such files for download as it's faster for people to generate their own test files.
The Prize
The winner will receive bits equal to the number of seconds faster then the next fastest program they are. This shall be limited to 360 bits. If anyone manages to beat my time they shall receive double bits.
Go Nuts!
Clarifications
* Data files are in binary, not text. One byte of the file is one byte to be sorted.
* There are four data sets to be sorted, a 256mb file containing single-byte values (unsigned char), a 256mb file containing 2-byte values(unsigned short), a 1gb file containing single-byte values (unsigned char) and a 1gb file containing 2-byte values (unsigned short).
* They are to be sorted from least to greatest.
* They are unsigned. So no negative numbers. |
|
|
|
|
|
Sponsor Sponsor
|
|
|
Nick
|
Posted: Wed Nov 07, 2007 8:49 pm Post subject: RE:Sorting Contest |
|
|
lmao i like the limitation on turing due to linux doesnt matter anyways because turing's max intake is 256 chars (even with multiple varibles asigned it would take longer to do making it harder to win) |
|
|
|
|
|
CodeMonkey2000
|
Posted: Wed Nov 07, 2007 8:52 pm Post subject: RE:Sorting Contest |
|
|
momop, do you even know what you are talking about? |
|
|
|
|
|
Nick
|
Posted: Wed Nov 07, 2007 8:55 pm Post subject: RE:Sorting Contest |
|
|
Quote: * Your program must sort 256MB (give or take) worth of bytes/shorts, and then 1GB worth of bytes/shorts.
that means that the intake must be longer than 256 chars
and iunno do u know what im talking about? |
|
|
|
|
|
CodeMonkey2000
|
Posted: Wed Nov 07, 2007 9:00 pm Post subject: RE:Sorting Contest |
|
|
You are sorting an array. Turing can definitely handle more than 256 elements. |
|
|
|
|
|
Nick
|
Posted: Wed Nov 07, 2007 9:31 pm Post subject: RE:Sorting Contest |
|
|
OH!!!!!!!!!!!!!
i thought it gave u numbers and u sorted them :p geuss i didnt know what i was talking about |
|
|
|
|
|
md
|
Posted: Wed Nov 07, 2007 9:59 pm Post subject: RE:Sorting Contest |
|
|
Technically you are sorting a file (or an array stored in a file if you prefer). Sorting a file is harder then sorting an array in memory; especially since loading the entire file into memory is both infeasible and against the rules.
I may also extend this to include Saturday if there are enough people who express an interest. |
|
|
|
|
|
CodeMonkey2000
|
Posted: Wed Nov 07, 2007 10:12 pm Post subject: RE:Sorting Contest |
|
|
So you would be continuously opening and closing the file for every iteration you go through? |
|
|
|
|
|
Sponsor Sponsor
|
|
|
Saad
|
Posted: Wed Nov 07, 2007 10:16 pm Post subject: RE:Sorting Contest |
|
|
Can you please extend the deadline to saturday? as it gives me more time to think |
|
|
|
|
|
md
|
Posted: Wed Nov 07, 2007 11:29 pm Post subject: Re: RE:Sorting Contest |
|
|
CodeMonkey2000 @ 2007-11-07, 10:12 pm wrote: So you would be continuously opening and closing the file for every iteration you go through?
Sure, how you do it doesn't really matter to me.
I give you a file containing 1073741824 bytes. You must sort that file so it's in order. You can do it in any way you want; so long as it ends up sorted from smallest to largest. Likewise for half as many shorts. |
|
|
|
|
|
Clayton
|
Posted: Wed Nov 07, 2007 11:45 pm Post subject: RE:Sorting Contest |
|
|
Please, for the love of god, don't tell me you're going to use 5GB files too. |
|
|
|
|
|
rdrake
|
Posted: Wed Nov 07, 2007 11:50 pm Post subject: Re: RE:Sorting Contest |
|
|
Clayton @ Wed Nov 07, 2007 11:45 pm wrote: Please, for the love of god, don't tell me you're going to use 5GB files too. He said 256 MB and 1 GB in the original post. I'd be surprised if he bothered running all the submissions on 5 GB files. |
|
|
|
|
|
Clayton
|
Posted: Thu Nov 08, 2007 12:00 am Post subject: RE:Sorting Contest |
|
|
Yeah, well...
Clayton wrote:
(11:53:28 PM) Clayton{}: I'm going to use "I'm tired" as an excuse |
|
|
|
|
|
md
|
Posted: Thu Nov 08, 2007 8:38 am Post subject: RE:Sorting Contest |
|
|
I'll extend this to Saturday at midnight; now you got no excuse clayton |
|
|
|
|
|
Saad
|
Posted: Thu Nov 08, 2007 6:03 pm Post subject: Re: Sorting Contest |
|
|
md @ Wed Nov 07, 2007 8:37 pm wrote:
The Goal
* You must provide one program capable of sorting bytes and one capable of sorting 2-byte integers (shorts, words, whatever).
The part underlined i don't understand, how many bytes in each value do you want? |
|
|
|
|
|
|