[Previous] stuff about computer games and programming | Home | [Next] BBC Nonsense

neat cs trick

found here

u might not follow that explanation though, so i'll write it simpler:

computer data is often stored in arrays (basically a bunch of stuff in a row). arrays have a fixed size in memory. sometimes they get full. the basic solution is you make a new, larger array, and copy all the old data into it.

in comp sci classes they generally teach (or maybe only used to, dunno) that you should make the new array double the size of the old. you want to try not to waste too much memory by making it bigger than needed, but also increase the size enough not to have to do this very often, because copying over all the data is expensive.

anyhow, if your array takes up 1 unit of memory, and you double, the new one takes 2 units of memory, with a gap of 1 empty unit behind you. next doubling, your array takes 4 with a gap of 3. then takes 8 with a gap of 7.

see the problem? the array never fits into the gap.

if you increase the array by a factor of 1.5 instead, it will fit into the gap.

actually works pretty fast. 1.5 with 1 gap. then 2.5 gap and array is 1.5*1.5=2.25 ... already fits.

anyway, it's a neat improvement.


Elliot Temple on January 16, 2004

Comments (4)

That *is* neat (so I thought once I finally understood it...) - thanks for sharing!


Kristen at 6:58 PM on January 17, 2004 | #320

I suppose this is useful if the array is your main data structure and there aren't many other new objects taking up the free space. Otherwise, who cares if the new array will fit in the old space? The space will be free and other things will use it.



But, I suppose if you're designing generic array resizing infrastructure, it is a good idea to handle the worst case if you can do it efficiently, and that's what Microsoft is doing here.



Those Microsoft programmers sure are smart, huh?


Gil at 9:28 AM on January 20, 2004 | #321

anytime the array is resized very little, you lose nothing.



anytime the array is resized a lot (and thus gets very large) it might help.



some of the people at Microsoft are clever, certainly. that doesn't mean the organisation as a whole does a good job.


Elliot at 11:23 AM on January 20, 2004 | #322

thanks to Gil's comment and Elliot's followup I now understand why fitting into the "gap" can be useful. (before i just kept thinking "who cares, the old stuff gets free'd either way...")



always nice to see an application of the golden ratio....


Blixa at 12:36 PM on January 21, 2004 | #323

What do you think?

(This is a free speech zone!)