[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Speed query
- From: Geoff Leyland <geoff_leyland@...>
- Date: Wed, 26 Mar 2008 12:03:32 +1300
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
that it's most likely going to spend most of its time doing
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
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
───── http://www.cowlark.com ─────
│ "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
│ how to use my telephone." --- Bjarne Stroustrup