Re: Speed of #t

[starwing <weasley.wx@...>]

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 :-(