Re: Speed of #t

[HyperHacker <hyperhacker@...>]

On Mon, Dec 13, 2010 at 08:08, starwing <weasley.wx@gmail.com> wrote:
>
>
> 2010/12/13 Axel Kittenberger <axkibe@gmail.com>
>>
>> > i think #t can be the *LOWEST* hole of the array-part, or the *HIGHEST*
>> > one.
>> > all is acceptable.
>> > or someone can provide lowerhole() or upperhole() functions to handle
>> > them.
>> > I mean, if implement *LOWEST* or *HIGHEST* is easy, maybe it's the best
>> > choice.
>>
>> I think thats exactly the issue, its not easy to implement. But yes,
>> from a strictly user point of view, lower or highest would both be
>> better than any, if they can be done in acceptable speed compared to
>> any. I dunno the Lua Source, so I cannot tell how easy hard it is. But
>> what I know about hash tables, it is hard to find the lowest key.
>> Thats likely one of the biggest caveats of hashes compared to say
>> trees.
>>
> maybe we can just maintain a field that contain the lowest or highest hole
> of the table?
> insert is easy, just compare the fields and key.
> the difficulty is remove some key.
> we can just find a random-hole and do binary-search.
> but we must do linear search in worst case.
> fortunately, current, we also need do linear search :-(

I feel this is worth pointing out:
> s="ab\0cd"
> =#s
5
> =s
ab

# applied to a string gives the highest valid index, ignoring any
"holes". The consistent thing to do would be to make it do the same
for tables.

-- 
Sent from my toaster.