Calculating a pattern-match score on a ten-element array

Question

I have a method in Python that is extremely slow:

def patternRecognition(self):
    patRecStartTime = time.time()
    plotPatAr = []
    patFound = 0

    for eachPattern in self.patternAr:
        sim1 = 100.00 - abs(self.percentChange(eachPattern[0], self.patForRec[0]))

        if sim1 > 50:
            sim2 = 100.00 - abs(self.percentChange(eachPattern[1], self.patForRec[1]))
            if sim2 > 50:
                sim3 = 100.00 - abs(self.percentChange(eachPattern[2], self.patForRec[2]))
                if sim3 > 50 :
                    sim4 = 100.00 - abs(self.percentChange(eachPattern[3], self.patForRec[3]))
                    if sim4 > 50 :
                        sim5 = 100.00 - abs(self.percentChange(eachPattern[4], self.patForRec[4]))
                        if sim5 > 50:
                            sim6 = 100.00 - abs(self.percentChange(eachPattern[5], self.patForRec[5]))
                            if sim6 > 50 :
                                sim7 = 100.00 - abs(self.percentChange(eachPattern[6], self.patForRec[6]))
                                if sim7 > 50 :
                                    sim8 = 100.00 - abs(self.percentChange(eachPattern[7], self.patForRec[7]))
                                    if sim8 > 50:
                                        sim9 = 100.00 - abs(self.percentChange(eachPattern[8], self.patForRec[8]))
                                        if sim9>50:
                                            sim10 = 100.00 - abs(self.percentChange(eachPattern[9], self.patForRec[9]))

                                            howSim = (sim1+sim2+sim3+sim4+sim5+sim6+sim7+sim8+sim9+sim10)/10.00

                                            if howSim > 70:
                                                patFound = 1
                                                plotPatAr.append(eachPattern)


    if patFound == 1:
        for eachPatt in plotPatAr:
            futurePoints = self.patternAr.index(eachPatt)

            if self.performanceAr[futurePoints] > self.patForRec[29]:
                #do something
            else:
                #do something

Does anyone have any suggestions on making this method execute quicker? When the array gets to 50,000 elements, it takes about 1 second to execute and increases as the array patternAr grows. I read that converting the for loop into a map would make it quicker, however, I have not been able to figure it out.

I should mention that percentChange is very simple:

def percentChange(self, startPoint,currentPoint):
    try:
        x = ((float(currentPoint)-startPoint)/abs(startPoint))*100.00
        if x == 0.0:
            return 0.000000001
        else:
            return x
    except:
        return 0.0001

Initial code with sample data here.

Answer 1

This whole approach is completely bogus and not worth your time.

A "pattern" is simply an array of percentage changes. For simplicity let's use a pattern size of 5. So a pattern might look like:

pat1 = [ 1%, 3%, -2%, 1.6%, 2.1% ]

meaning that the price difference (from the price at time 0) at time 1 was 1%, at time 2 was 3%, at time 3 was -2%, etc.

Given another pattern we want to compute how "similar" they are. This is done componentwise using a similarity function for percentages whose definition is:

sim(p,q) = 100 - abs (percentageChange(p,q))

where percentageChange is the percent change between p and q with an absolute value in the denominator:

percentChange(p,q) = 100 * (p-q)/abs(q)

So in python, sim is:

def sim(p,q):
  """Compute the similarity between two percentage changes."""
  pc = 100 * (p-q) / abs(q)
  return 100 - abs(pc)

Note since we are multiplying everything by 100 that the 1% value in pat1 is just the value 1, not the conventional 0.01.

Given two patterns, pat1 and pat2, we say they are close if

sim( pat1[i], pat2[i] ) >= 70   for each i in 0..4

The big idea

The idea behind these patterns and similarity measures is that given historical data we compute a pattern and a future price change with the idea that the pattern implies the future price change.

Then given current data we compute the current pattern and search for a similar pattern in our database from which we can deduce the corresponding price change.

The main problem is that the sim function is not symmetrical in its arguments, i.e. sim(p,q) and sim(q,p) may have wildly different values. Consider these examples:

sim(1.200, 2.000)   = 60.000000
sim(2.000, 1.200)   = 33.333333

sim(-1.000, 2.000)  = -50.000000
sim(2.000, -1.000)  = -200.000000

sim(-1.000, -2.000) = 50.000000
sim(-2.000, -1.000) = 0.000000

sim(-1.000, 1.000)  = -100.000000  # guess these are actually the same!
sim(1.000, -1.000)  = -100.000000

sim(-1.000, -0.100) = -800.000000
sim(-0.100, -1.000) = 10.000000

sim(-1.000, 0.100) = -1000.000000
sim(0.100, -1.000) = -10.000000

A better definition for sim(p,q) would simply be:

sim(p,q) = abs(p-q)

and then to define two patterns to be close if

sum of sim(pat1[i], pat2[i]) for i in 0..4
  is LESS THAN a certain number

The prediction algorithm then boils down to a nearest neighbor search in a high number of dimensions (e.g. the length of the pattern array.)

Answer 2

Here is a way to write the main loop in a more concise way. It won't necessarily execute any quicker, though:

  for eachPattern in self.patternAr:
    totalSim = 0
    for i in range(0,10):
      sim = 100 - abs(self.percentChange(eachPattern[i]), sef.patForRec[i])
      totalSim += sim
      if sim <= 50:
        break
    if i >= 10:
      howSim = totalSim / 10.00
      if homSim > 70
        patFound = 1
        plotPatAr.append(eachPattern)

One thing this approach makes possible, however, is that we can substitute the percentChange function with one that is tailored for this computation.

For instance, since we are only checking if the percent change is > 50, we can skip the if x == 0 check. Moreover, we can also inline the call to avoid the cost of method dispatching:

    ...
    for i in range(0,10):
      if eachPattern[i] == 0:
        sim = 100 - 0.0001
      else:
        p = float(self.patForRec[i])
        if eachPattern[i] == p:
          sim = 100 - 0.000000001
        else:
          sim = 100 - (p - eachPattern[i])/abs(eachPattern[i]) * 100
      totalSim += sim
      if sim <= 50:
        break
    ...

The checking of eachPattern[i] against 0 serves the same purpose of the try...except... block in percentChange.

Note: If there is a way to rule out those patterns which have a zero somewhere then you can skip the check if eachPattern[i] == 0

Finally, another thing to note is that you are calling float(self.patForRec[i]) multiple times - once for each of your 50,000 patterns. I would do that conversion outside the loop like this:

floatPatForRec = [ float(self.patForRec[i]) for i in range(0,10) ]

and then in the main loop use floatPatForRec[i]:

...
for i in range(0,10):
  if eachPattern[i] == 0:
    sim = 100 - 0.0001
  else:
    if eachPattern[i] == floatPatForRec[i]:
      sim = 100 - 0.000000001
    else:
      sim = 100 - (floatPatForRec[i] - eachPattern[i]) / eachPattern[i])*100
...

Answer 3

Here is some more advice based on this part of your code:

...
                                        if howSim > 70:
                                            patFound = 1
                                            plotPatAr.append(eachPattern)


if patFound == 1:
    for eachPatt in plotPatAr:
        futurePoints = self.patternAr.index(eachPatt)
...

The method .index is relative slow but indexing using [] is very quick. Instead of appending each wanted pattern and then calling .index to find it again, just append the index to plotPatAr:

for i in xrange(len[self.patternAr]):
    eachPattern = self.patternAr[i]
...
     if howSim > 70:
       plotPatAr.append(i)
...
if plotPatAr:
  for i in plotPatAr:
    futurePoints = self.patternAr[i]
    ...

Now you've avoided the possibly expensive .index method call.