Performance issue involving large permutation

Question

I'm creating a program that figures out fingerings for chords on string instruments. This is what I have:

from itertools import product

# Returns the notes you get from a certain fingering with a certain tuning
def notes(tuning, fingering):
    return map(lambda x, y: (x+y)%12, tuning, fingering)

# Just a constraint function to filter out chords impossible to finger due to too large spreading. 
def spread(fingering):
    return max(fingering) - min(i for i in fingering if i > 0)

# Get all the possible fingerings for a certain chord
def fingering(tuning, chord):
    return [i for i in product(range(12), repeat=len(tuning)) if
            set(notes(tuning, i)) == set(chord) and
            spread(i) < 5]

Example output:

>>> cf.fingering([0,5,10], [2,7])
[[2, 2, 4], [7, 9, 9]]
>>> cf.fingering([0,1,2], [2,3])
[[2, 1, 1], [2, 2, 0], [2, 2, 1], [3, 1, 0], [3, 1, 1], [3, 2, 0]]

This seems to work so far, with the exception that it's too slow. When I use it for a 7-string guitar (tuning is a list with length 7) it takes around 45 seconds to calculate.

I'd like to bring it down to around where it's perceived as instantaneous for a human, so around 0.1s or so. A few seconds is acceptable.

I suspect the problem is that product generates all possible lists and then filter them afterwards. Filtering before generating would be far more effective, but I don't see how I could achieve this.

user_843953 · Answer

Following my comment:

It should be fairly easy to figure out which frets on each string will play the notes you need for the chord. Then get the product of those sets of frets instead of iterating over all possible combinations.

import itertools

MAX_FRETS = 24
FRETS_PER_OCTAVE = 12
MAX_SPREAD = 5 # Because everyone isn't John Petrucci https://i.stack.imgur.com/tKIKA.png


def fingering(tuning, chord):
    chord = set(chord)
    allowed_frets = [] # {note: [] for note in chord}
    for string_num, open_string_note in enumerate(tuning):
        string_frets = []
        for wanted_note in chord:
            wanted_fret = wanted_note - open_string_note
            while wanted_fret <= MAX_FRETS:
                if wanted_fret >= 0:
                    string_frets.append((wanted_fret, wanted_note))
                wanted_fret += FRETS_PER_OCTAVE
        
        # Now we have all the frets on this string that will give us one of the 
        # notes we need in string_frets
        allowed_frets.append(string_frets)
        
    
    fingerings = []    
    # Now, allowed_frets[i] gives us the frets that are useful on the i-th string
    # You can only select one fret per string, so you'd run product() on these and
    # then check if that product makes the chord.
    for selection in itertools.product(*allowed_frets):
        # Check if selection contains all the required notes
        selection_notes = set()
        selection_frets = []
        for fret, note in selection:
            selection_notes.add(note)
            selection_frets.append(fret)
        
        if chord == selection_notes and max(selection_frets) - min(selection_frets) < MAX_SPREAD:
            fingerings.append(selection)
            
    return fingerings

# Running for your first example:
f = fingering([0, 5, 10], {2, 7})

With print(f), we get:

((2, 2), (2, 7), (4, 2))
((14, 2), (14, 7), (16, 2))
((7, 7), (9, 2), (9, 7))
((19, 7), (21, 2), (21, 7))

Remember, the first element of each tuple is the fret, and the second is the note. This method found the [2, 2, 4] and [7, 9, 9] results of your method, but also the same chord higher up the fretboard. If you don't want to do this, you can change the while wanted_fret <= MAX_FRETS loop to while wanted_fret <= FRETS_PER_OCTAVE + MAX_SPREAD

Timing both functions with three strings, we see a ~25x speedup:

%timeit fingering_yours([0, 5, 10], [2, 7])
2.37 ms ± 294 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit fingering([0, 5, 10], {2, 7})
96.1 µs ± 14.1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

With an actual three-note chord (Cmaj)^{not that it matters} on a standard-tuned^{also irrelevant} six-string guitar, it gives an even bigger speedup of ~50x

%timeit fingering_yours([4, 9, 2, 7, 11, 4], [0, 4, 7])
6.3 s ± 554 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit fingering([4, 9, 2, 7, 11, 4], {0, 4, 7})
127 ms ± 4.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

More optimizations might be possible, but that is left as an exercise for the reader.

If we don't want to enforce the requirement that all strings must be played, we can add None values to the string_frets array to indicate that "no note" is a valid possibility.

# Change this line:
        string_frets = [] 
# to this:
        string_frets = [(None, None)] # Start off allowing "None" to be a valid note played on this string

Next, we need to filter the Nones out when we check each selection in itertools.product(...).

        for fret, note in selection:
            # New condition: Only append if the string is actually being played
            if fret is not None: 
                selection_notes.add(note)
                selection_frets.append(fret)

        # New condition: No strings are being played, so this is not a chord,
        # skip this iteration
        if not selection_frets:
            continue

Trying this out with the dyad on three strings, we get the following combinations, which looks reasonable:

((None, None), (9, 2), (9, 7))
((None, None), (21, 2), (21, 7))
((None, None), (2, 7), (4, 2))
((None, None), (14, 7), (16, 2))
((2, 2), (2, 7), (None, None))
((2, 2), (2, 7), (4, 2))
((14, 2), (None, None), (9, 7))
((14, 2), (9, 2), (9, 7))
((14, 2), (14, 7), (None, None))
((14, 2), (14, 7), (16, 2))
((14, 2), (14, 7), (9, 7))
((7, 7), (None, None), (4, 2))
((7, 7), (9, 2), (None, None))
((7, 7), (9, 2), (4, 2))
((7, 7), (9, 2), (9, 7))
((7, 7), (2, 7), (4, 2))
((19, 7), (None, None), (16, 2))
((19, 7), (21, 2), (None, None))
((19, 7), (21, 2), (16, 2))
((19, 7), (21, 2), (21, 7))
((19, 7), (14, 7), (16, 2))

Performance issue involving large permutation

1 Answers