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 #77218 is a reply to message #77061]

Tue, 16 August 2011 16:01

JDS
Messages: 94
Registered: March 2009

Member

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:

w=where(array eq pat[(c=0)],/NULL)
while keyword_set(w) && ++c lt n_elements(pat) do begin
keep=where(array[w+c<n] eq pat[c],/NULL)
w=w[keep]
endwhile

It also has the advantage on working for any pattern length, and returning the "hits" in sorted order. Finding around 5 8-byte needles in a 100 million byte haystack took about 1/3 sec with this algorithm on my machine (though Lajos' method was close behind at only 0.7s).

JD

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: Mon Oct 27 05:15:21 PDT 2025

Total time taken to generate the page: 0.02800 seconds