Calculating parsimonies using Python; performance is lacking

Question

This program takes a very long time to do each and every step, even the very first print statement. Why is this, and what is the best way to diagnosing a problem like this in any language?

Also, I'd appreciate it if you could harshly critique my code and style so I can make it better/more Pythonic.

Description

The Python script takes a list as an input (startingSet) and compares it to all equal-length combinations of the members of the parent set (harmPool). The absolute-value difference between the given set and the equivalent member of the compared set is found, and these differences are summed to create what I’m calling the “parsimony ranking” (PR) of that chord movement. (The PR is a completely arbitrary number that serves to rank all possible combinations of the parent set according to their distance from the starting set.)

For example if the initial set is [a, b, c, d] and the combination set is [e, f, g, h], the PR would be found via

[( | a -/+ e | ) + ( | b -/+ f | ) + ( | c –/+ g | ) + ( | d -/+ h | )].

If the initial set is [50, 55, 60, 64] and the combination set is [50, 52, 60, 65.86], the parsimony ranking (at least in this initial statement of the problem) would be 4.86 (since ( | 55 – 52 | ) + ( | 64 – 65.86 | ) = 4.86 and the two values are shared by the sets.

The Python program works by simply generating a list of sets whose PR is below a specified threshold. One set is then selected from this list using a probability distribution that favors positive numbers close to zero. (An exponential distribution might work well, although the example code uses a triangular distribution with a low mode value.) Once a set is selected from the available options, this set becomes the starting set and the process for deriving the next chord will start all over again. The process repeats until a specified number of chords are generated.

Download link

# =====================================================================
# Imports and timer:

import time
start_time = time.time()

import math
import itertools
from random import triangular
from ast import literal_eval

# =====================================================================
# Define functions:

def chordWidth(chord):
    v1 = len(chord)
    v1 = (v1 - 1)
    v2 = chord[0]
    v3 = chord[v1]
    return abs(v2 - v3)

# The following function gives the distance between each member of the starting set and the corresponding item in
# the derivSet. Each value reprosenting the distance between the elements of startingSet and derivSet is raised to
# to the power of parsimonyPower in order to account for the relative difference in parsimoniesness for
# chord changes incorporating large leaps between elements.

def PR(pow, starting, deriv):
    v1 = tuple(map(lambda x, y: math.pow(abs(x - y), pow), starting, deriv))
    v2 = sum(v1) # Sums the set of distances.
    return int(math.floor(v2)) # Converts "parsimonyRanking" to an int.

startingSet = (76, 77.86, 80, 83.69, 89.86) # Starting chord.
startingSetWidth = chordWidth(startingSet)

# =====================================================================
# Define important variables and get user input:

numChords = input("Please enter the number of chords in the sequence: ") # Number of chords in the whole chord sequence.
parsimonyPower = input("Please enter the leap-penalty power: ")

newSet = []
numNotes = len(startingSet) # Number of notes in each chord.
maxParsRanking = 20 # This is the maximum parsimony rating that will be selected and writen to the file.

print ("=== The Parsimony Tool program has started running. This may take a while. ===")
print startingSetWidth
print ("\n")

harmPool = [28, 33, 36, 38, 40, 43, 45, 47, 48, 50, 52, 55, 55.86, 57, 59, 60, 60.86, 61.69, 62, 63.86, 64, 65.86, 66, 66.69, 
        67, 69, 69.69, 70.86, 71, 71.69, 72, 74, 75.86, 76, 76.69, 77.86, 79, 81, 81.69, 82.86, 83.69, 84, 84.86, 86, 88, 
        88.69, 89.86, 90.69, 91, 93, 95, 95.69, 96.86, 98, 100]

# =====================================================================
# While loop for solving chord chains

j = 0 # For control of the While loop.

while (j < numChords):
    combos = itertools.combinations(harmPool, numNotes)

    i = 0 # For counting number of times the "for loop" has run.
    usable_combos = []
    for derivSet in combos:

        preParsimonyRanking = PR(parsimonyPower, startingSet, derivSet)
        derivSetWidth = chordWidth(derivSet)
        widthDist = startingSetWidth - derivSetWidth
        parsimonyRanking = (preParsimonyRanking + abs(widthDist))

        if parsimonyRanking <= maxParsRanking:

            # Prints the tuple to "parsimonies.txt" if the parsimonyRating is lower than a limit.
        newSet.append([parsimonyRanking, derivSet])

        i += i # Counts the number of times the loop has be exicuted.

    if len(newSet) < 1:
        print("Program ended with no solutions.")
        break

    else:

        newSetLen = len(newSet)
        e = triangular(0, newSetLen, 0) # This selects a value from the ordered list of chords 
                                        # with a low startingSet value based on a triagular distribution.
        e = int(math.floor(e))
        startingSet = newSet[e]
        startingSet = startingSet[1]
        print startingSet # Prints the chord

        newSet = [] # This clears the newSet.
        j += 1

# =====================================================================
# Gives user output when the program stops running. (Important since this file can take many minutes to run.)

print ("\n")
print ("=== The Parsimony Tool program has finished running. ===")
print ("=== The time requiered was %s seconds. ===" % (time.time() - start_time))

Answer 1

harmPool contains 55 elements; numNotes is 5. This means that an inner loop over combos would run approximately 2.5 million times. An obvious way to speed things up is to not test all combinations.

If I am reading your task correctly, you should instead run a BFS in a chord space from the current chord cutting when parsimonyRanking == maxParsRanking.

Answer 2

You have at least one error:

i += i # Counts the number of times the loop has be exicuted.

This should be:

i += 1

and wouldn't need a comment if the variable was named e.g. loop_count (see below on variable naming). Having said that, you never actually use the value of i (which is probably why you never noticed it was always zero), so perhaps you should reconsider including it at all.

---

parsimonyPower = input("Please enter the leap-penalty power: ")

Should be

parsimonyPower = int(raw_input("Please enter the leap-penalty power: "))

to ensure that you are getting the correct type of input. You can add validation, too; see e.g. this SO question.

---

The loop

j = 0 
while (j < numChords):
    ...
    j += 1

could be simplified to

for _ in range(numChords):
    ...

As you don't need the value of j within the loop, and break in the only case where you don't increment.

---

imports should be in a separate block, in alphabetical order (three separate blocks for standard library, third-party and local modules, but that's not relevant here):

from ast import literal_eval
import itertools
import math
from random import triangular
import time

---

Many of your lines are too long:

Limit all lines to a maximum of 79 characters.

For flowing long blocks of text with fewer structural restrictions (docstrings or comments), the line length should be limited to 72 characters.

---

Many of your variable names are unclear (v1? v2? v3?) or don't follow the Python conventions (numChords should be num_chords, for example).

---

Python has standards for documentation strings; your comment blocks don't follow them. Also, better variable names would remove the need for many of your inline comments, some of which are trivial anyway (commenting print, sum and int seems especially pointless):

def parsimony_ranking(parsim_power, start_set, deriv_set):
    """Calculate the distance between the starting and derivative sets.

    Each value representing the distance between the elements of
    start_set and deriv_set is raised to the power of parsim_power, in
    order to account for the relative different in parsimoniesness for
    chord changes incorporating large leaps between elements.

    """
    distances = tuple(map(lambda x, y: math.pow(abs(x - y), parsim_power), 
                      start_set, deriv_set))
    return int(math.floor(sum(distances)))

---

You have far too much code in the body of your script. Almost everything should be wrapped up into separate functions, so that all that is left to run when the script is run directly is something like:

if __name__ == "__main__":
    start_time = time.time()
    print "=== The Parsimony Tool program has started running. This may take a while. ==="
    # a few function calls
    # ...
    print ("\n")
    print ("=== The Parsimony Tool program has finished running. ===")
    print ("=== The time requiered was %s seconds. ===" % (time.time() - start_time))

The if __name__ ... guard means that this won't run when your script is imported elsewhere, making it easier to reuse this functionality in the future.