python - 涉及大排列的性能问题

Question

我正在创建一个程序来计算弦乐器和弦的指法。这是我的:

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]

示例输出:

>>> 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]]

到目前为止，这似乎有效，只是它太慢了。当我将它用于 7 弦吉他时(tuning 是一个长度为 7 的列表)，计算大约需要 45 秒。

我想把它降低到人类认为是瞬时的程度，大约 0.1 秒左右。几秒钟是可以接受的。

我怀疑问题是 product 生成所有可能的列表，然后过滤它们。在生成之前进行过滤会更有效，但我不知道如何实现这一点。

Answer 1

根据我的评论:

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 /image/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})

与 print(f) ，我们得到:

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

请记住，每个元组的第一个元素是品格，第二个元素是音符。此方法找到了 [2, 2, 4]和 [7, 9, 9]你的方法的结果，但在指板上也有相同的和弦。如果你不想这样做，你可以改变 while wanted_fret <= MAX_FRETS循环到 while wanted_fret <= FRETS_PER_OCTAVE + MAX_SPREAD

用三个字符串对这两个函数进行计时，我们看到了大约 25 倍的加速:

%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)

在标准调音^{同样无关紧要}的六弦吉他上使用实际的三音和弦 (Cmaj)^无关紧要，它提供了更大的加速~50 倍

%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)

更多优化可能是可能的，但这留给读者作为练习。

---

如果我们不想强制执行必须播放所有字符串的要求，我们可以添加None string_frets 的值数组以指示“无注释”是一种有效的可能性。

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

接下来，我们需要过滤None当我们检查每个 selection 时就出来了在 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

在三根弦上用 dyad 试试这个，我们得到以下组合，看起来很合理:

((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))