Re: [Lua-users-stdlib] Upheaval (blame Jamie Webb!)

[Reuben T. <rr...@sc...>]

> It doesn't really matter that much.  I can always rename any "vector"
> module to "list" and be done.  I'm just lazy, find it easier to type
> "list", and think its natural-language overtones mesh better with the
> word "table".

I strongly agree with this. List is a reasonably vague word, and it's
obvious and nice to type.

> Actually, this reminds me.  What are the times on Lua tables?  I know
> that integer indices are special, but do they get true O(1) access?
> Presumably, other keys are O(log n), as usual.

Integer indices that end up in the array part of the table get O(1) access
(effectively they have space reserved for them). However, which keys are
actually in the array part is a little harder to determine. Basically,
it's all the keys up to N such there are at least half of all possible
keys in the range 1-N, i.e. occupancy of the array is at least 50%. But if
you add bigger keys (>N) then even when occupancy of some larger N becomes
>50%, those keys will be kept in the hash table part until it overflows
and the table is resized. When this happens depends on the table. If you
never put anything but integer keys in a table, then almost all your keys
will almost always have O(1) access time.

> Nah, ASCII representations are for the weak.  You need the funny arrows
> and things.  :-)

Funny thing, I've been reading the docs on K recently, and I'm impressed
(I've been meaning to do it for years...).

-- 
http://www.mupsych.org/~rrt/ | art, n.  romanticized mundanity