lua-users home
lua-l archive

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


On 22/04/2014 6:39 PM, Coroutines wrote:
Anyway, I don't see how a hash table of the pointer addresses would be
better.  Because they're just numbers a binary search to do an
existence check would seem appropriate, but I'd love to know how a
hash table would be better suited :>  I'm still trying to get a
mastery on data structures so...

A hash table has amortized O(1) insert/lookup.

A binary search has worst-case O(logN) lookup time.

If you care about amortized-time then a hash table might be faster. If you care about worst-case time then your sorted list solution may be faster.

Either way you need to purge old elements. Although leaving them in the table and marking them "dead" when the associated object is deallocated kind-of gets around the problem of accessing deallocated data.

Ross.