lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Mon, Feb 27, 2017 at 4:41 AM, Xavier Wang <> wrote:
> 2017-02-27 19:12 GMT+08:00 Daurnimator <>:
>> I read this today:
>> I thought it might be interesting reading for many of you.
>> I'm eager to see how lua's algorithm compares, and what lessons might be learnt.
> I feel Lua's implement is much faster than this. it use a limited
> linear search, but Lua's use a linked list into open address. with a
> linked list, Lua's get a free node is much easier than author's.
> when insert, Lua also move the colliding node into it's main position.
> in my amoeba library[1], in a 1000+ elements hash table, the most link
> has only 3 elements. and the lookup loop looks even more compact than
> author's:
> static const am_Entry *am_gettable(const am_Table *t, am_Symbol key) {
>     const am_Entry *e;
>     if (t->size == 0 || == 0) return NULL;
>     e = am_mainposition(t, key);
>     for (; e-> !=; e = am_index(e, e->next))
>         if (e->next == 0) return NULL;
>     return e;
> }
> the most inspired thing is the limited linear search, in Lua it means
> limited search in lastfree, it's not easy to add this change to my
> hashtable, and I will do some research for this change. but in current
> test, the worst case for max loop for lastfree is the whole list
> length. so maybe it will have a big improve.
> it's really a very impressive thing, TIL :-)
> --
> regards,
> Xavier Wang.
Did you mean to add this link as reference [1]:

Very slick. Some months back I found a round robin database for
applicative monitoring here: I didn't
drill in too far but I wonder out loud if your library could be
applied for relative logic in things like object tracking?

I'll keep your library in mind when I am creating my
killer-artificially-intelligent-robot in lua.