comp.lang.idl-pvwave archive: archive » Efficient pattern-matching in a large array

Home » Public Forums » archive » Efficient pattern-matching in a large array

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Re: Efficient pattern-matching in a large array [message #77210 is a reply to message #77061]

Wed, 17 August 2011 06:41

guillermo.castilla.ca is currently offline

guillermo.castilla.ca
Messages: 27
Registered: September 2008

Junior Member

On Aug 16, 8:01 pm, JDS <jdtsmith.nos...@yahoo.com> wrote:
> Using ULONG64's is quite interesting, but the byte offsetting slows performance compared to what you might expect. In the likely case that the byte pattern occurs rarely, a thinned WHERE approach is at least twice as fast in my testing:

Wow, the thinned WHERE approach rocks!!

You are right, shifting or offsetting takes a lot of time (god knows
why). I tried the following approach (looking for sequences of numbers
that yield the same sum than the pattern, and then double checking
that they actually form the sought pattern):

carr=total(array,/cumulative,/integer)
w=where(Shift(carr,-n_elements(pat))-carr eq Total(pat,/integer),count)
+1
if count ne 0 then for j=0,count-1 do $
if ~array_equal(array[w[j]:w[j]+n_elements(pat)-1] eq pat, 1) then
w[j]=-1
w=w[where(w ge 0, count,/null)]

It takes almost 10 times more than JD's method (1.27s vs. 0.13s) when
I set array=byte(lindgen(100000000))and pat=byte([1,2,3,4,5,6,7,8]),
yikes! Half of time is invested in the 2nd line, and a fifth in the
1st line, meaning that TOTAL and SHIFT suck a lot of time. Btw, in
this example, with almost 40k patterns in the array, JD's method is
still twice as fast as Lajos (0.55s), so JD's thinned where approach
is definitely the method of choice for searching for specific
sequences of consecutive numbers in an array.

Guillermo

Report message to a moderator

[Message index]

		Efficient pattern-matching in a large array By: Chris O'Dell on Tue, 02 August 2011 11:05
		Re: Efficient pattern-matching in a large array By: Foldy Lajos on Tue, 02 August 2011 13:04
		Re: Efficient pattern-matching in a large array By: ez569x on Fri, 12 August 2011 05:18
		Re: Efficient pattern-matching in a large array By: Brian Daniel on Fri, 12 August 2011 07:38
		Re: Efficient pattern-matching in a large array By: guillermo.castilla.ca on Tue, 16 August 2011 09:41
		Re: Efficient pattern-matching in a large array By: guillermo.castilla.ca on Wed, 17 August 2011 06:41
		Re: Efficient pattern-matching in a large array By: JDS on Tue, 16 August 2011 16:01
		Re: Efficient pattern-matching in a large array By: Bob[4] on Wed, 17 August 2011 14:14
		Re: Efficient pattern-matching in a large array By: JDS on Thu, 18 August 2011 10:00

Previous Topic:	Re: /RELAXED keyword not allowed?
Next Topic:	Confession

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

]

Current Time: Sun Oct 12 06:25:49 PDT 2025

Total time taken to generate the page: 2.16061 seconds