×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Great moments in programming stupidity

Com2Kid (142006) writes | more than 5 years ago

User Journal 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.

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".

3 comments

Why not just ... (1)

tomhudson (43916) | more than 5 years ago | (#19275503)

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 another program loads, grabs the data from the buffer, etc ...

With video cards of a gig out there now, you could store some mighty big datasets ...

Re:Why not just ... (1)

Com2Kid (142006) | more than 6 years ago | (#19296619)

Because the code is compiled and tested on a remote machine of which we have no clue about the specs for, not to mention it has the be pure standards conformant C++ since we also don't know which compiler is being used either!

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:Why not just ... (1)

tomhudson (43916) | more than 6 years ago | (#19297521)

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 associated with linked lists, where you have to walk the nodes.

If you're only going to store a maximum of 15 points, I'd just make an array of 15 long longs, or an array of 15 ints/longs (for the coords) and a single int to hold the various bits.

Just a thought ...

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...