lua-users home
lua-l archive

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

Good question. I just tested (b) vs a pure lua binary heap and the binary heap is so much better (the sort version still hasn't finished) that I think I must have got (b) wrong (does table.qsort exist? I can only find table.sort documented. Which is better out of table_insert(t, x) and t[#t+1] = x?)

If you want to try my heap code I can send it, but I think there's one in loop that's bound to be better.


On 26/03/2008, at 11:39 AM, David Given wrote:
Given that Lua is an interpreted language, conventional wisdom dictates that it's most likely going to spend most of its time doing instruction
decodes rather than actual work. Therefore, the fewer the instructions
the better --- no matter what the instructions do.

I want to implement a priority queue. I have two possible strategies
when inserting an item:

(a) binary chop through the array until I find the place to insert the
item, then call table.insert to do it.

(b) append the item at the end of the array and then use table.qsort to
sort the entire array.

(a) involves the least amount of theoretical work. (b) involves the
fewest number of actual instructions. So, which one is faster? And is
the answer still true when using LuaJit?

(Right now I'm going for (b) --- since I can implement it in three lines
of Lua.)

┌─── ───── ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup