RE: Speed query

["Brian Weed" <brianw@...>]

Not actually answering your question...

With a finite number of priorities, maybe it would be faster to use the priority as a hash into a table of queues.

q = {}

...

q[priority] = q[priority] or {}

table.insert(q[priority], item)

Then you pull items from the "topmost" non-empty queue.

Brian
 

-----Original Message-----
From: lua-bounces@bazar2.conectiva.com.br [mailto:lua-bounces@bazar2.conectiva.com.br] On Behalf Of David Given
Sent: Tuesday, March 25, 2008 6:39 PM
To: Lua list
Subject: Speed query

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.)

--
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── 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 out │ how to use my telephone." --- Bjarne Stroustrup