OpenEuphoria

find_all_not() and using a pattern sequence

• Posted by euphoric (admin) Sep 29, 2010
• 1467 views

Forked from Re: find_all() And More

Okay, matt gave me an idea last night in chat and here it is: build a sequence so that you can just look up the pattern via a pre-built sequence. For example:

instead of using

a = find_all_but( 0, pattern ) 

using the prior-submitted find_all() algorithms, I would do basically a lookup sequence:

function get_pattern(sequence pat) 
   pat+=1 
   return get_pattern[pattern[1]][pattern[2]][pattern[3]][pattern[4]]  
end function 
a = get_pattern( pattern ) 

The code I used to pre-build the pattern sequence (which could probably be made more elegant):

include std/console.e 
include std/get.e 
 
integer nums=10 
 
sequence s = repeat(repeat({},nums),nums) 
 
function find_all_but( object needle, sequence haystack )   
	integer ix = 1   
	integer jx   
	sequence found = {}   
	while jx with entry do   
		for i = ix to jx - 1 do  
			found = append( found, i ) 
		end for   
		ix = jx + 1   
	entry   
		jx = find( needle, haystack, ix )   
	end while 
	for i = ix to length(haystack) do 
		found = append( found, i ) 
	end for 
	return found   
end function 
 
for a=1 to nums do 
	s[a] = repeat(repeat({},nums),nums) 
	for b=1 to nums do 
		s[a][b] = repeat(repeat({},nums),nums) 
		for c=1 to nums do 
			s[a][b][c] = repeat(repeat({},nums),nums) 
			for d=1 to nums do 
				s[a][b][c][d] = repeat(repeat({},nums),nums) 
			end for 
		end for 
	end for 
end for 
 
for a=1 to 5 do 
	for b=1 to 5 do 
		for c=1 to 5 do 
			for d=1 to 5 do 
				s[a][b][c][d] = find_all_but( 0, {a,b,c,d}-1 ) 
			end for 
		end for 
	end for 
end for 
 
function patt(sequence a) 
	a+=1 
	return s[a[1]][a[2]][a[3]][a[4]] 
end function 
 
sequence fn = sprintf("patterns_%d-%d.txt",{0,nums-1}) 
 
atom fh = open(fn,"w") 
print(fh,s) 
close(fh) 

Here is the test program:

include std/console.e 
include std/get.e 
 
integer nums = 10 -- maximum number of values found in pattern, from 1 to nums 
 
sequence test = repeat( repeat( 0, nums-1 ), 100 ) 
for i = 1 to 10 do 
	for j = 1 to 4 do 
		test[i][j] = rand( 5 ) - 1 
	end for 
end for 
 
function find_all_but( object needle, sequence haystack )   
	integer ix = 1   
	integer jx   
	sequence found = {} 
	while jx with entry do   
		for i = ix to jx - 1 do  
			found = append( found, i ) 
		end for   
		ix = jx + 1   
	entry   
		jx = find( needle, haystack, ix )   
	end while 
	for i = ix to length(haystack) do 
		found = append( found, i ) 
	end for 
	return found   
end function   
  
atom timer = 3 + time()  
sequence x  
atom c = 0  
  
while time() < timer do  
	c+=1  
	for i = 1 to length(test) do 
		x = find_all_but( 0, test[i] )  
	end for 
end while  
?c  
 
function find_all_but_dp( object needle, sequence haystack )  
	integer ix = 1  
	integer jx  
        integer kx = 0  
	while jx with entry do  
		for i = ix to jx - 1 do  
                        kx += 1  
			haystack[kx] = i  
		end for  
		ix = jx + 1  
	entry  
		jx = find( needle, haystack, ix )  
	end while  
          
	for i = ix to length(haystack) do  
                kx += 1  
		haystack[kx] = i  
	end for  
	return haystack[1 .. kx]  
end function  
 
timer = 3 + time()  
c = 0  
while time() < timer do  
	c+=1  
	for i = 1 to length(test) do 
		x = find_all_but_dp( 0, test[i] )  
	end for 
end while  
? c  
 
sequence fn = sprintf("patterns_%d-%d.txt",{0,nums-1}) 
 
atom fh = open(fn,"r") 
sequence patts = get( fh ) 
close(fh) 
patts = patts[2] 
 
function patt( sequence pat ) 
	pat += 1 
	return patts[pat[1]][pat[2]][pat[3]][pat[4]] 
end function 
 
timer = 3 + time()  
c = 0  
while time() < timer do  
	c+=1  
	for i = 1 to length(test) do 
		x = patt( test[i] )  
	end for 
end while  
? c  
 
puts(1,"\ndone") 
wait_key() 

I don't know if these results are 100% accurate nor if they will stand (bugfree), but it's a start.

For cases using a 4-element sequence with values from 0 to N, with the max of N so far being 10, the sequence algorithm is the fastest. With values of 0-4 in the pattern, the pre-built text file is 6KB. With values of 0-10 in the pattern, the pre-built text file is 2.9MB. At what point will sacrificing storage/RAM for speed be no longer viable? :)