#!/home/kragen/devel/luajit-2.0/src/luajit -- Build a balanced binary tree from a sorted input text file, in -- linear time, bottom up, then look up line numbers in it. -- Leaf nodes look like {leftkey = k, val = v}. -- Internal nodes look like {leftkey = kl, left = tl, rightkey = kr, right = tr} -- where kl == tl.leftkey and kr == tr.leftkey. -- The algorithm uses a stack of full perfectly-balanced trees of -- strictly decreasing weight (number of leaves), each a power of -- two. Upon adding a new leaf node to the top of the stack, if the -- sizes of the trees in the stack are not strictly decreasing from -- bottom to top, it merges them into bigger trees until they are. -- Although it indeed seems to be linear-time, it needs about 4500 CPU -- instructions per input line in /usr/share/dict/words, which is only -- about 2× the speed of the Lua interpreter. function repr(obj) function is_identifier(str) return string.match(str, "^[%a_][%w_]*$") end if type(obj) == "table" then local lines = {} for k, v in pairs(obj) do local ks if type(k) == "string" and is_identifier(k) then ks = k else ks = "["..repr(k).."]" end table.insert(lines, ' '..ks.." = "..repr(v)..",\n") end return "{\n"..table.concat(lines).."}" elseif type(obj) == "string" then return string.format("%q", obj) else return tostring(obj) end end local stats = {} function inc(stat) if stats[stat] == nil then stats[stat] = 1 else stats[stat] = stats[stat] + 1 end end -- function inc(stat) end function tree_builder() return {stack = {}, leafnodes = 0} end function pop(stack) local rv = stack[#stack] stack[#stack] = nil return rv end function concatenate_trees(tb) local right = pop(tb.stack) local left = pop(tb.stack) table.insert(tb.stack, {leftkey = left.leftkey, left = left, rightkey = right.leftkey, right = right}) inc("internal nodes created") end function add_string(tb, key, val) if val == nil then print_statistics() error("nil for "..repr(key)) end table.insert(tb.stack, {leftkey = key, val = val}) tb.leafnodes = tb.leafnodes + 1 local x = tb.leafnodes while x % 2 == 0 do concatenate_trees(tb) x = x / 2 end end function finish_tree(tb) while #tb.stack > 1 do concatenate_trees(tb) end return tb.stack[1] end function build_tree(get_input) local tb = tree_builder() local line_no = 1 for str in get_input() do inc("strings read") add_string(tb, str, line_no) line_no = line_no + 1 end return finish_tree(tb) end function search(tree, word) inc("searches done") while true do inc("nodes visited") if tree == nil then return nil elseif tree.val ~= nil then return tree.leftkey, tree.val elseif tree.rightkey > word then tree = tree.left else tree = tree.right end end end function print_statistics() print(repr(stats)) end if #{...} then local tree = build_tree(io.lines) for _, word in ipairs({...}) do print(word, search(tree, word)) end print_statistics() end