Author: ben
Date: 2007-11-17 18:39:12 -0800 (Sat, 17 Nov 2007)
New Revision: 7308
Added:
sandbox/ben/ruby/linkchecker.rb
Modified:
sandbox/ben/ruby/searching.rb
Log:
building ruby linkchecker for doctools. improved binary search.
Added: sandbox/ben/ruby/linkchecker.rb
Property changes on: sandbox/ben/ruby/linkchecker.rb
___________________________________________________________________
Name: svn:executable
+ *
Name: svn:mime-type
+ text/plain
Name: svn:eol-style
+ native
Modified: sandbox/ben/ruby/searching.rb
===================================================================
--- sandbox/ben/ruby/searching.rb 2007-11-17 02:15:27 UTC (rev 7307)
+++ sandbox/ben/ruby/searching.rb 2007-11-18 02:39:12 UTC (rev 7308)
@@ -145,6 +145,7 @@
f = Finder.new( a )
binary_result = f.find_index_of_binary( target )
assert_equal( target, a[binary_result], "binary search found wrong index
for #{a[pos]}" )
+ Finder.analyze
end
def is_sorted( arr, verbose=false )
@@ -190,9 +191,12 @@
end
class Finder
+ @@frames = Array.new
+ @@num_searches = 0
+
def initialize( arr )
# arr should be sorted
- @arr = arr;
+ @arr = arr;
end
def find_index_of_linear( t )
@@ -205,24 +209,41 @@
end
def find_index_of_binary( t )
- binary_search( t, 0, @arr.length-1 )
+ @@num_searches = @@num_searches + 1
+ binary_search( t, 0, @arr.length-1, 0 )
end
- def binary_search( t, low, high )
+
+ # recursive implementation of binary search
+ def binary_search( t, low, high, depth )
if ( high < low )
return nil
end
mid = low + ( (high-low) / 2 ).floor
if @arr[mid] == t
+ @@frames.push( depth )
return mid
end
if @arr[mid] > t
- return binary_search( t, low, mid - 1 )
+ return binary_search( t, low, mid - 1, depth + 1 )
else
- return binary_search( t, mid + 1, high)
+ return binary_search( t, mid + 1, high, depth + 1)
+ end
+ end
+
+ # the binary_search method above uses tail recursion,
+ # so we can unwind it into an iterative form
+ def binary_search_iterative( t, low, high )
+
+ end
+
+ def Finder.analyze
+ if @@num_searches % 10000 == 0
+ puts "analyze: got #{@@num_searches} searches"
+ total_frames = @@frames.inject {|sum, n| sum + n }
+ puts "total frames is #{total_frames}"
end
-
- end
+ end
end
_______________________________________________
Laszlo-checkins mailing list
[email protected]
http://www.openlaszlo.org/mailman/listinfo/laszlo-checkins
