[DGD]Resources used by sparse arrays

[Par Winzell]

 > > My questions to the more knowledgeable types are these: first, is more
 > > memory going to be used by that array with 38 empty elements and seven
 > > strings in it, or by an array of seven integers plus an array of seven
 > > strings? Second, would the situation change if the arrays were smaller
 > > (say, 5 out of 22 elements filled, or two five-element arrays) or more
 > > densely packed (say, 15 out of those 45 elements filled)?
 > 
 > The 45 element array with 7 strings will take more memory than the
 > pair of 7 element arrays.

Correct me if I'm wrong -- I skipped a night's sleep -- but I think this
is how the memory consumption plays out...

Given M non-nil elements in an array and a maxmium element index of N;
if we consider each LPC 'value' to be size 1, then by the simple, one-
array method the memory consumption excepting the actual data would be,

	A = 1 + N	(one array value, N array element values)

and for method two, with an array of indices,

	B = 2 + 2*M	(two array values, each with M element values)

and so equilibrium is reached at

	A == B   <->
	1 + N == 2(1 + M)   <->
	N = 2M - 1

It is clear that in the case of N=47 and M=7, Erwin is correct and the
simple solution is the less efficient one. It is equally clear that as
N and M grow large, A/B -> 0.5N/M, and so the more complex solution is
more efficient whenever more than half the elements are nil.

;)

Zell

List config page:  http://list.imaginary.com/mailman/listinfo/dgd