By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,818 Members | 1,262 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,818 IT Pros & Developers. It's quick & easy.

How to program efficient pattern searches in a list of float numbers?

P: n/a
Simple case:
In this list, how to find all occurences of intervals of n adjacent
indexes having at least one list-member with a value between given
limits.
Visualizing the list as a two-dimensional curve, this is like
horizontally dragging a given rectangle over the curve and finding the
x coordinates where the curve passes through the rectangle.(Define such
a x-index coordinate as the left corner of the rectangle.)

More complicated case:
Given a pair of rectangles spaced relatively to each other in a fixed
manner. Drag this rectangle pair horizontally over the above
two-dimensional curve and list the indexes of the occurences where the
curve passes simultaneously through both rectangles.
(Define such a x-index coordinate as the leftmost corner of the
rectangle pair).

These problems can be solved by programming a naive search advancing
index by index. It seems obvious that due to the localized properties
searched for, much more efficient searches should be possible.
After having found the occurence-indexes for one particular rectangle
set, how to find the pattern occurences after changing one or more
rectangle parameters?

Sep 19 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
On 19 Sep 2005 00:02:34 -0700, malv <ma*****@telenet.be> wrote:
Simple case:
In this list, how to find all occurences of intervals of n adjacent
indexes having at least one list-member with a value between given
limits.
Visualizing the list as a two-dimensional curve, this is like
horizontally dragging a given rectangle over the curve and finding the
x coordinates where the curve passes through the rectangle.(Define such
a x-index coordinate as the left corner of the rectangle.)

More complicated case:
Given a pair of rectangles spaced relatively to each other in a fixed
manner. Drag this rectangle pair horizontally over the above
two-dimensional curve and list the indexes of the occurences where the
curve passes simultaneously through both rectangles.
(Define such a x-index coordinate as the leftmost corner of the
rectangle pair).

These problems can be solved by programming a naive search advancing
index by index. It seems obvious that due to the localized properties
searched for, much more efficient searches should be possible.
After having found the occurence-indexes for one particular rectangle
set, how to find the pattern occurences after changing one or more
rectangle parameters?


Make a picture of the problem. From your description, I'm not certain
anything more complicated than a linear search is called for.

Is this the phrasing of the original problem presentation? Seems to me
the word "superimpose" ought to occur here.

Another thought: What is the end result you're after? Often we start
thinking of a solution but lose sight of the end result. Then another
solution will pop into our mind that makes it Oh So Simple.

Sep 19 '05 #2

P: n/a
Have you tried coding even the brute-force naive search? It is far
easier to improve an algorithm when you have someplace relatively
concrete to start from. Plus, the naive approach is most likely to
return a correct result, so that you can regression test your exotic
interval-skipping, second-derivative conjugate interpolation algorithm.
:)

In sum, I started to think through your problem this morning, and yes,
I can visualize the rectangles floating across the 2D curve, and yes, I
can picture that there are likely to be shortcuts and optimizations
over the brute-force "check every index" approach. But really, you
*should* do some of the work yourself...

-- Paul

Sep 19 '05 #3

P: n/a
How about posting example data and results?

Sep 19 '05 #4

P: n/a
I am not interested in doing your homework.

Sep 19 '05 #5

P: n/a
On 19 Sep 2005 00:02:34 -0700, "malv" <ma*****@telenet.be> wrote:
Simple case:
In this list, how to find all occurences of intervals of n adjacent
indexes having at least one list-member with a value between given
limits.
Visualizing the list as a two-dimensional curve, this is like
horizontally dragging a given rectangle over the curve and finding the
x coordinates where the curve passes through the rectangle.(Define such
a x-index coordinate as the left corner of the rectangle.)

More complicated case:
Given a pair of rectangles spaced relatively to each other in a fixed
manner. Drag this rectangle pair horizontally over the above
two-dimensional curve and list the indexes of the occurences where the
curve passes simultaneously through both rectangles.
(Define such a x-index coordinate as the leftmost corner of the
rectangle pair).

These problems can be solved by programming a naive search advancing
index by index. It seems obvious that due to the localized properties
searched for, much more efficient searches should be possible.
After having found the occurence-indexes for one particular rectangle
set, how to find the pattern occurences after changing one or more
rectangle parameters?


for the first problem, maybe (untested beyond the below):
from itertools import groupby
data = [5+i%5 for i in xrange(40)]
data [5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6,
7, 8, 9, 5, 6, 7, 8, 9] [g.next()[0] for k,g in groupby(enumerate(data), lambda t: 6<t[1]<9) if k]

[2, 7, 12, 17, 22, 27, 32, 37]

By the time you figure a more efficient way, this can have solved it for quite a long sequence.
But since an efficient solution seems a lot like homework, I'll leave it to you ;-)
Or is this a bioinfo problem in disguise?

Regards,
Bengt Richter
Sep 19 '05 #6

P: n/a
On Mon, 19 Sep 2005 22:58:40 GMT, bo**@oz.net (Bengt Richter) wrote:
On 19 Sep 2005 00:02:34 -0700, "malv" <ma*****@telenet.be> wrote:
Simple case:
In this list, how to find all occurences of intervals of n adjacent
indexes having at least one list-member with a value between given
limits.
Visualizing the list as a two-dimensional curve, this is like
horizontally dragging a given rectangle over the curve and finding the
x coordinates where the curve passes through the rectangle.(Define such
a x-index coordinate as the left corner of the rectangle.)

More complicated case:
Given a pair of rectangles spaced relatively to each other in a fixed
manner. Drag this rectangle pair horizontally over the above
two-dimensional curve and list the indexes of the occurences where the
curve passes simultaneously through both rectangles.
(Define such a x-index coordinate as the leftmost corner of the
rectangle pair).

These problems can be solved by programming a naive search advancing
index by index. It seems obvious that due to the localized properties
searched for, much more efficient searches should be possible.
After having found the occurence-indexes for one particular rectangle
set, how to find the pattern occurences after changing one or more
rectangle parameters?


for the first problem, maybe (untested beyond the below):
from itertools import groupby
data = [5+i%5 for i in xrange(40)]
data [5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 5, 6,
7, 8, 9, 5, 6, 7, 8, 9] [g.next()[0] for k,g in groupby(enumerate(data), lambda t: 6<t[1]<9) if k]

[2, 7, 12, 17, 22, 27, 32, 37]

By the time you figure a more efficient way, this can have solved it for quite a long sequence.
But since an efficient solution seems a lot like homework, I'll leave it to you ;-)
Or is this a bioinfo problem in disguise?

Wrong problem, sorry. I misread too quickly. I'll try to misread more slowly next time ;-/

Regards,
Bengt Richter
Sep 20 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.