OpenEuphoria

Re: Looking for the best "JOIN"

• Posted by Derek Parnell <ddparnell at bigpond.com> Oct 22, 2001
• 399 views

Hi Andy,
Sorry about my offhanded comment before.

Your function, I believe, is the most obvious. However, I've learnt that the
most obvious algorithm is not always the fastest one. Here is the reasoning
behind my first effort...

The obvious algorithm, I guessed, does this sort of thing internally...

> function join (sequence strings)
>    sequence result
>    result = ""
>    for i=1 to length(strings)
        -- Allocate some RAM big enough to hold the current
        -- length of result plus the length of strings[i]
        -- Copy the values in result to the new area
        -- Copy the values in strings[i] to the new area
        -- Return the old area (aka old results) to the system
>       result = result & strings[i]
>    end for
>    return result
> end function

Thus for each element in strings it would do 1 Allocate, 2 Copys, and one
deallocate. Also, the copys would be increasing in size for each iteration.
Meaning that some values would be copied multiple times.

I wrote my function thinking that if I just did the one allocation,
regardless of how many elements in 'strings' then only copy each value once
it would be faster. This would mean I'd have to do a loop through 'strings'
to calc the total length, then loop through again to copy each of the
values.

However, it turns out that the overheads in running two loops through the
elements in 'strings' is more than the allocate/copy/copy/deallocate cycle.
(I guess).
----
Derek.