  lua-l archive

• Subject: Re: Speed query
• From: "Javier Guerra" <javier@...>
• Date: Wed, 26 Mar 2008 15:49:11 -0500

```On Wed, Mar 26, 2008 at 1:43 PM, Geoff Leyland
<geoff_leyland@fastmail.fm> wrote:
>  The test I used is insert X items, remove Y, and repeat Z times.
>  For X=10,000, y=7,500 and Z=100 (final queue length 250,000), in lua
>  the sort is slightly faster.  With luajit the heap is slightly faster.
>  For X=1,000, y=750 and Z=1,000 (final queue length 250,000) the heap
>  is about 10 times faster in both cases.
>
>  So I guess the answer is that it depends what you're doing.
>
>  Here's the code with the tests.  No guarantees it works :)

a simpleminded optimization (reduce the use of #self) gains a 20% speedup:

--- orig/binary_heap.lua        2008-03-26 13:48:55.000000000 -0500
+++ binary_heap.lua     2008-03-26 15:45:56.000000000 -0500
@@ -23,7 +23,7 @@
-- info ------------------------------------------------------------------------

function heap:next_key()
-  assert(#self > 0, "The heap is empty")
+  assert(self, "The heap is empty")
return self.key
end

@@ -50,7 +50,7 @@
end

function heap:pop()
-  assert(#self > 0, "The heap is empty")
+  assert(self, "The heap is empty")

local cmp = self.comparison

@@ -58,15 +58,18 @@
local result = self
self = nil

+  local ssize = #self
+
-- push the last element in the heap down from the top
-  local last = self[#self]
+  local last = self[ssize]
local last_key = (last and last.key) or nil
-  self[#self] = nil
+  self[ssize] = nil
+  ssize = ssize-1

local parent_index = 1
-  while parent_index * 2 <= #self do
+  while parent_index * 2 <= ssize do
local child_index = parent_index * 2
-    if child_index+1 <= #self and cmp(self[child_index+1].key,
self[child_index].key) then
+    if child_index+1 <= ssize and cmp(self[child_index+1].key,
self[child_index].key) then
child_index = child_index + 1
end
local child_rec = self[child_index]
@@ -86,11 +89,12 @@

function heap:check()
local cmp = self.comparison
+  local ssize = #self
local i = 1
while true do
-    if i*2 > #self then return true end
+    if i*2 > ssize then return true end
if cmp(self[i*2].key, self[i].key) then return false end
-    if i*2+1 > #self then return true end
+    if i*2+1 > ssize then return true end
if cmp(self[i*2+1].key, self[i].key) then return false end
i = i + 1
end

now, it would be nice to add an in-place 'heapify'...

--
Javier

```