1. Euphoria\Demo\Tree.ex -- timing is off?
--=====================_977320304==_
I ran Tree.ex and found the time reported exceeded
what I expected. This is because Tree.ex records
time taken to *enter* the data at the console as well.
I've amended the program to print out where the
timing was *actually* starting and made corrections.
Specifically, a global variable 'g_total_time' now
holds the time and only insertions into the tree
are timed.
These are just quick corrections.
Please see the attachment.
Comments?
Thanks again to Ray Smith who answered my question
on ADTs and referred me to Tree.ex
--=====================_977320304==_
-- Count frequencies of words in standard input.
-- Uses a binary tree to speed lookups and write
-- an alphabetic listing to standard output.
-- usage:
-- ex tree < file1
--
-- You can direct standard output to a file with '>'
-- How it Works:
-- * tree.ex reads in words from a text file and inserts them
-- alphabetically into a Euphoria sequence that is being used
-- as a "tree". The tree data structure is created by nesting
-- sequences inside one another to whatever depth is required.
-- Looking up a word in a tree is generally faster than searching
-- through a linear list, since unless the tree is very lop-sided,
-- we should have fewer comparisons to make.
without type_check
constant EOF = -1
constant TRUE = 1
constant STANDARD_IN = 0,
STANDARD_OUT = 1,
SCREEN = 2
constant NAME = 1,
COUNT = 2,
LEFT = 3,
RIGHT = 4
function next_word()
-- read standard input to get next alphabetic string
integer c
sequence word
word = ""
while TRUE do
c = getc(STANDARD_IN)
if (c >= 'A' and c <= 'Z') or
(c >= 'a' and c <= 'z') then
word &= c
elsif length(word) > 0 then
return word
elsif c = EOF then
return 0
end if
end while
end function
function insert(sequence node, sequence word)
-- Insert new word into tree or increment existing word count by 1.
-- Return modified node.
-- This is quite fast since internally Euphoria is copying
-- pointers to subtrees, *not* all the data as it might appear.
integer x
if length(node) = 0 then
-- couldn't find it - create new node
node = {word, 1, {}, {}}
else
x = compare(word, node[NAME])
if x = 0 then
node[COUNT] += 1 -- found it, increment count
elsif x < 0 then
node[LEFT] = insert(node[LEFT], word) -- insert it on the left
else
node[RIGHT] = insert(node[RIGHT], word)-- insert it on the right
end if
end if
return node
end function
procedure printTree(sequence node)
-- recursively print tree information
-- in alphabetical order
if length(node) = 0 then
return
end if
printTree(node[LEFT])
printf(STANDARD_OUT, "%s:%d\n", {node[NAME], node[COUNT]})
printTree(node[RIGHT])
end procedure
-----------------------------------------------------------------------
atom g_total_time
sequence root -- root of the whole tree
root = {}
g_total_time = 0
procedure word_count()
-- build a binary tree containing words in standard input
object word
atom t -- times each word insertion
while TRUE do
word = next_word()
if atom(word) then
exit
end if
t = time()
root = insert(root, word)
t = time() - t
g_total_time += t -- increment global variable
end while
end procedure
puts(SCREEN, "terminate typed input with: control-Z Enter\n")
puts(SCREEN, "\nTiming was starting here -- too soon\n")
word_count()
printTree(root)
printf(SCREEN, "\n\n%.2f seconds\n\n", g_total_time)
--=====================_977320304==_--
