On Tue, May 18, 2010 13:53, James Morris wrote: > 3) create an 2d array where each element in the array is either a 1 for > used space, or a 0 for freespace. searches are performed by inspecting > each element in the array. > > X-( using a char array, only 1 bit out of 8 is used, so for a 128 x 128 > array, that's a wastage of 14336 bits (unless my maths is wrong). > > :-) faster than any other method investigated and quite easy to implement > all other placement strategies. > > > 4) create a 2d array much like in 3 but this time directly use the > individual bits of whatever data type is used (ie 64/32/16/8 bit types). > > X-( A PITA to implement, difficult to genericize the placement algorithm, > instead left-to-right and right-to-left are two seperate algorithms. > > :-) faster still, and less memory wastage.
Implementation 3 wins only in terms of code: not only is the row-smart algorithm less lines of code AND more straight-forward code at that, but the same algorithm (or C function) handles all four permuations of placement options: * left-to-right & top-to-bottom * right-to-left & top-to-bottom * left-to-right & bottom-to-top * right-to-left & bottom-to-top Implementation 4 wins in terms of execution speed and memory efficiency, BUT, the implementation of left-to-right is sufficiently different to right-to-left, that to combine the two options would not gain anything and make the implementation more complex. The reason 4 wins out in terms of execution speed and memory efficiency, (despite more lines of code of greater complexity) is because not only are there less array elements to inspect, but because C bit-wise operators (which are used to inspect and manipulate the array data) often translate directly into CPU instructions (as opposed to sequences of CPU instructions). _______________________________________________ NetBehaviour mailing list [email protected] http://www.netbehaviour.org/mailman/listinfo/netbehaviour
