OpenEuphoria

Euphoria\Demo\Tree.ex -- timing is off?

• Posted by S Ns <sw at PARADISE.NET.NZ> Dec 21, 2000
• 498 views

--=====================_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==_--