OpenEuphoria

RE: Eu's poor design

• Posted by Matt Lewis <matthewwalkerlewis at yahoo.com> Aug 18, 2003
• 486 views

I don't know what you mean by 'iterative' or 'tail-recursion-optimizations',
but your methodology certainly isn't the only (or best) way to implement a
tree in Eu.  A much quicker way is to use parallel sequences:

sequence left, right, data

Then, you can append in chunks, so you're not always appending just one
element.  You can always tune this to the particular algorithm.  Anyway, if
you look at Mic's lzss library in the archives, you'll see a pretty fast
tree implementation (ported from C).  It's not real clear what you wanted to
do here with put(), since it doesn't really do anything.

My experience is that you need to stop thinking like other languages when
using sequences, since they're more powerful than the native data structures
available in most other languages, and their strong points and weaknesses
aren't always as obvious as they at first appear.  I've had many Eureka
moments where I was able to drastically improve an algorithm because I
wasn't approaching the task in the best way.

Matt Lewis

> From: Andreas Rumpf [mailto:pfropfen at gmx.net]

> 
> How make it iterative? I think the only way to do it iterative (more 
> efficient if you don't have tail-recursion-optimizations, which Eu 
> probably doesn't have) is like this:
> 
> sequence tree -- here all the nodes are stored!
> -- a node is now { index to left subtree, index to right subtree,
> -- data }
> -- index = 0 if there is no subtree
> 
> -- so put becomes:
> integer root
> root = 0
> 
> function put(integer root, object data)
> -- overwrites exisiting data in the tree
>   integer cmp_result
>   integer node
>   node = root
>   while node != 0 do
>     cmp_result = compare(tree[node][DATA], data)
>     if cmp_result = -1 then
>       node = tree[node][LEFT]
>     elsif cmp_result = 1 then
>       node = tree[node][RIGHT]
>     else -- overwrite data
>       tree[node][DATA] = data -- creates a copy of the sequence
>                               -- which stores all our nodes
>     end if
>   end while
>   return tree
> end function
> 
> This works, but it is more difficult. Note also, that 
> inserting requires 
> the tree to append a new node which has a worst efficiency of 
> O(N), so 
> forget about inserting with O(log N)! (Though I must admit that in 
> practice it will probably work fine...)