Journal Com2Kid's Journal: Great moments in programming stupidity 3
I am taking this Programming Competitions Preparations class. The problems are all horribly unrealistic and not represenative of Software Engineering at all, but then again, they are not really meant to be.
Problems are solved in a two hour period in a team, typically of 3-5 students.
Well, my team realized that today's problem could be easily solved if we plotted points on a grid.
Hmm, lets see now. The largest a coordinate can be is 40,000. Ok simple, declare a 40,000 X 40,000 array of booleans.
Oh, too large for the stack, ok, declare it on the heap.
Umm, hey why is this taking so long.
Wait, what is 40k * 40k again? Oh crap.
Just for laughs, open up Task Manager and hit "Run", watch the VM usage go up to 1.90GB. Hey, look, I can see principles from my Operating Systems class in action! Awesome!
Hey, wait, did Windows just swap everything out to disk? Wow, everything is taking awhile to get back in order.
So, who here can quickly implement a sparse matrix?
To be fair, such stupidities only occure because there is a hard time limit. Normally I would never hard code in an array of anything near that size. Indeed, I do not know of any students here who would ever hard code in an array and say "That should be enough".
Why not just ... (Score:2)
calloc a 200 meg chunk of memory and use that, instead of an array. Calculate the offset into the memory yourself (actually, you'll need less than 200 meg, 200,000,000 bytes to be exact).
40,000 x 40,000 / 8 = 200,000,000 bytes.
Or if you're got a spare video card with 256 meg of ram, just store it there. Back in the "bad old days" we'd write data to unused pages of video ram as a great way for programs to pass data between each other. One program loads, runs, stores its stuff in the video buffer, then a
Re: (Score:1)
Not to mention that sparse arrays where created just for this sort of problem!
Allocating even 200 megs to store less than 15 bytes[1] of data is still insane overkill.
[1] 15 points, on/off.
Re: (Score:2)
My way would work with any standards-compliant C compiler - no need for C++. It would also have the advantage of not generating a 2 gig swap file, and of allowing up to 40,00x40,000 data points to be stored. Saving to disk would be as simple as writing out the buffer. Ditto for restoring the data to ram.
Also, looking up any data point would be a constant-time operation - a simple offset and a bitwise AND. Setting a data point would also be constant time - a simple offset and a bitwise OR. No problems like