I have list of 50000 words, should I implement binary search tree or just use Lua table

Solar2D Lua Language
#1

I’m trying to port my old word game from native Java to Corona SDK.  I use binary search tree in that game since it have good balance between size and speed.

When it comes to Lua, I’m not sure if I should do the same.  I assume Lua table is internally a hash table, but for hash table to have good performance, number of buckets should be way more than the number of keys.

On another hand, if I implement a binary search tree, I will have to use a lot of small Lua tables to represent the nodes of the tree. 

So, I’m not sure which one has smaller overhead.  Please let me know what do you think. Thanks.

#2

PUC-Rio is (rightfully) pretty “proud” of their Lua table implementation.

and with layers of “this is interpreted by that, …by that, …by that” it’s (often) hard to beat an implementation that occurs “more natively” – unless you have a very specific type of access and an algorithm tailored just for it.

i’d say if binary search were known to be optimal (not just “good enough”) for your use case, then it might be worth implementing, otherwise it’s going to be tough to outsmart native lua.

fwiw, hth

#3

PUC-Rio is (rightfully) pretty “proud” of their Lua table implementation.

and with layers of “this is interpreted by that, …by that, …by that” it’s (often) hard to beat an implementation that occurs “more natively” – unless you have a very specific type of access and an algorithm tailored just for it.

i’d say if binary search were known to be optimal (not just “good enough”) for your use case, then it might be worth implementing, otherwise it’s going to be tough to outsmart native lua.

fwiw, hth