Re: Speed of #t

[David Kastrup <dak@...>]

Enrico Colombini <erix@erix.it> writes:

> On 13/12/2010 13.10, David Kastrup wrote:
>>>   t = { 1, 2, 3, nil, 5, 6, 7, ... } -- a very very large table
>>>
>>> #t would be 3.
>>> Now fill the hole:
>>>
>>>   t[4] = 4
>>>
>>> To update #t correctly according to your definition, all the remaining
>>> length of the array would probably have to be traversed sequentially.
>>
>> Why? t[4] = 4 will presumably just increase the array part by one,
>> resulting in #t == 4.
>
> Why? From the user's point of view, the table will then be a proper
> array with non-nil indexes from 1 to (a possibly very large) n, so the
> user will expect #t to return n. Having it return any other value will
> be confusing and, practically speaking, nondeterministic.
> (or maybe I missed your point)

Of course it is "nondeterministic" since the user created a continuous
part discontinuously which would simply be undefined behavior.

The question is how to amortize the cost of

t[#t+1] = x

I see a few approaches here:

a) #t corresponds to the array part always.  When inserting at #t+1,
   check whether there is an entry in the associative part and if present,
   a1) overwrite it, leaving #t where it is
   a2) move it to the array part, bumping #t up
       a21) by one
       222) until we don't find an associative part entry anymore,
            moving associative entries to the array part in the processs 
   otherwise create a new entry in the array part and
   1) bump #t by 1
   2) bump #t until we don't find...
b) Don't let me start...

Things like "bump #t until" are expensive.  Both because they incur
potential large one-time costs, and because even if the "until"
condition is false, every super-correct sequential addition to the array
part requires checking the associative part.

So I lean towards "sane results only for sane users".  Meaning the array
part gets extended when inserting at #t+1, by one.  And shrunk when
deleting at #t.  And those operations don't look at the associative part
at all.  There is one bad consequence to be expected: stuff in the array
part shadowing stuff unwisely placed in the associative part previously,
which will resurface when shrinking the array part properly.

The other solutions apparently incur additional costs.

-- 
David Kastrup