Re: [Ocaml-lib-devel] Xarray : resizeable arrays (first cut)

[John M. S. <sk...@oz...>]

Brian Hurt wrote:

> On Fri, 25 Apr 2003, John Max Skaller wrote:
> 
>>-------------------------------------------------------- 
>>one thing I found: I needed 3 arguments not 2:
>>
>>current slots, current used slots, required size
>>
> 
> The inputs xarray has to give the resizer algorithm are:
> 
> - the current number of slots the array has
> 
> - the current number of slots the array needs
 
 
>>The extra argument is necessary for asymmetric growth/shrinkage
>>algorithms, so I recommend you add it: at present you cannot
>>take 'unused space' into account since it cannot be computed.
>>
>>
> 
> Hmm.  Consider the following case.  You have an array, using the doubling 
> algorithm, with a size of 16 and a length (number of used elements) of 10.  
> Now, you add an enumeration with 100 elements in it.
> 
> Currently, the resizer function is called with a currsize of 16 (the 
> current number of spaces in the array when it's called) and a length of 
> 110 (how many elements need to fit into the array).  Exponential_resizer 
> then keeps doubling 16 until it gets a long enough array size- 128 in this 
> case.  It returns 128.
> 
> If I understand you correctly, in this example you also want 10 (call it
> 'oldlength')  passed in as well.  


Yes.

> Certainly not difficult.  I just don't 
> see what you get out of it.  


Suppose you have a rule: when you're increasing the number
of elements in the array, you can resize it, but never
when you're decreasing them. That might be useful,
but it cannot be implemented unless you know the number
of elements in the array -- i don't mean slots of store
but actual occupied slots.

For example: the number of slots is set to the number
of elements on expansion. So for example adding 1 element
at a time to 5 then subtracting, then adding again:

data slots
0     0
1     1
2     2
3     3
4     4
5     5
4     5
3     5
2     5
1     5
0     5
1     1
2     2
3     3
4     4
5     5

The number of slots can shrink, but only
when the number of used slots increases.

Why would you want to do this? I have no idea.
But it is a viable algorithm and it cannot
be implemented without passing the number
of used slots in .. a general rule says
"pass the whole of the state in" and the
state is charactized by both the physical
slot count and the number of used slots.

NOte that one could argue that passing
in the size of a slot (in bytes) also makes
sense, since a strategy may be based on tuning
around memory amounts (Kbytes) due to the finiteness
of this quantity, rather than the more abstract notion
of a slot.

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850