[DGD]Resources used by sparse arrays

[Ludger Merkens]

On Sat, 16 Dec 2000, Par Winzell wrote:

>  > > 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.
> 
> ;)

Bingo - Great Maths ;)


Ludger

But this argumentation is valid for the space problem only. I'd need to
know about the algorithm to estimate your overall performance.




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