443,818 Members | 1,262 Online
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
6 Replies

 P: n/a On 19 Sep 2005 00:02:34 -0700, malv 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" wrote: Simple case:In this list, how to find all occurences of intervals of n adjacentindexes having at least one list-member with a value between givenlimits.Visualizing the list as a two-dimensional curve, this is likehorizontally dragging a given rectangle over the curve and finding thex coordinates where the curve passes through the rectangle.(Define sucha 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 fixedmanner. Drag this rectangle pair horizontally over the abovetwo-dimensional curve and list the indexes of the occurences where thecurve passes simultaneously through both rectangles.(Define such a x-index coordinate as the leftmost corner of therectangle pair).These problems can be solved by programming a naive search advancingindex by index. It seems obvious that due to the localized propertiessearched for, much more efficient searches should be possible.After having found the occurence-indexes for one particular rectangleset, how to find the pattern occurences after changing one or morerectangle 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

 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" wrote:Simple case:In this list, how to find all occurences of intervals of n adjacentindexes having at least one list-member with a value between givenlimits.Visualizing the list as a two-dimensional curve, this is likehorizontally dragging a given rectangle over the curve and finding thex coordinates where the curve passes through the rectangle.(Define sucha 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 fixedmanner. Drag this rectangle pair horizontally over the abovetwo-dimensional curve and list the indexes of the occurences where thecurve passes simultaneously through both rectangles.(Define such a x-index coordinate as the leftmost corner of therectangle pair).These problems can be solved by programming a naive search advancingindex by index. It seems obvious that due to the localized propertiessearched for, much more efficient searches should be possible.After having found the occurence-indexes for one particular rectangleset, how to find the pattern occurences after changing one or morerectangle 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

### This discussion thread is closed

Replies have been disabled for this discussion.