OpenEuphoria

Re: Collections module for ESL

• Posted by Pete Lomax <petelomax at blueyonder.co.uk> Jul 25, 2005
• 469 views

On Mon, 25 Jul 2005 09:56:09 -0700, "D. Newhall"
<guest at RapidEuphoria.com> wrote:

>Question for everyone: Should we implement the structures using types or hidden
>sequences and have them referenced by ids?
>I vote for the "hidden sequence" style with ids.
I agree.
>Both have their downsides. 
I believe the important thing when using ids (and huge stacks) is eg:

global procedure push(integer id, object x)
sequence onestack
	onestack=stacks[id]
	stacks[id]=0
	onestack=append(onestack,x)
	stacks[id]=onestack
end procedure

rather than:

global procedure push2(integer id, object x)
	stacks[id]=append(stacks[id],x)
end procedure

Because the append is fully optimised only for simple variables.
A simple test:

atom t, t1, t2
	t=time()
	for i=1 to 10000 do
		push(1,i)
	end for
	t1=time()-t
	stacks={{}}
	t=time()
	for i=1 to 10000 do
		push2(1,i)
	end for
	t2=time()-t
?{t1,t2}

shows the latter performing 700 times slower. So, with a little care
and attention, this approach is fine. You could probably optimise this
even further by having a parallel array of used extents and extending
each stacks[i] by say 32 elements as needed, instead of using append.

The functions I would like to see are:
push - add to end of stack
pop - remove from end of stack
pull - remove from start of stack

and possibly:
pump - insert at start of stack
peep - return false if stack is empty

push/pop implements a lifo stack, and
push/pull implements a fifo queue.

Regards,
Pete