OpenEuphoria

Fast appending and sorting of alot of short strings

• Posted by codepilot Gmail Account <codepilot at gmail.com> Oct 06, 2004
• 536 views

Can somone give me some good theory to get this to go fast?
there is a sequence and it gets searched alot, and also appended to.
I thought that using a hash_find for search was good, but then it has
to be sorted.
So I use hash_append to find where string goes, and split the sequence
in insert the sting inside. The search must return an integer (0 not
found or subscript number). I would like to keep this in euphoria, but
I'm always open to an assembly idea.

Daniel

<code>
global function append_sort(sequence seq, sequence query)
--AKA hash_append
	integer low,high,current,len,comp
	len=length(seq)
	if length(seq)=0 then return {query} end if
	low=0
	high=len-1
	while 1 do
		current=floor((high+low)/2)
		comp=compare(query,seq[current+1])
		if comp=0 then return seq end if
		if high=low then
			if comp<0 then return seq[1..current]&{query}&seq[current+1..len]
			else return seq[1..current+1]&{query}&seq[current+2..len] end if
		end if
		if comp<0 then high=current-1
		else low=current+1 end if
		if high<low then
			if comp<0 then return seq[1..current]&{query}&seq[current+1..len]
			else return seq[1..current+1]&{query}&seq[current+2..len] end if
		end if
	end while
end function

global function findseqhashzero(sequence query, sequence seq)
--AKA hash_find
	integer low,high,current,len,comp
	len=length(seq)
	if length(seq)=0 then return 0 end if
	low=0
	high=len-1
	while 1 do
		current=floor((high+low)/2)
		comp=compare(query,seq[current+1])
		if comp=0 then return current+1 end if
		if high=low then return 0 end if
		if comp<0 then high=current-1
		else low=current+1 end if
		if high<low then return 0 end if
	end while
end function

</code>