Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Sorting Contest
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
md




PostPosted: 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
Sponsor
sponsor
Nick




PostPosted: 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




PostPosted: Wed Nov 07, 2007 8:52 pm   Post subject: RE:Sorting Contest

momop, do you even know what you are talking about?
Nick




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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
Sponsor
sponsor
Saad




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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 Wink
Saad




PostPosted: 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?
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 30 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: