Re: Speed query

["Javier Guerra" <javier@...>]

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[1], "The heap is empty")
   return self[1].key
 end

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

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

   local cmp = self.comparison

@@ -58,15 +58,18 @@
   local result = self[1]
   self[1] = 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