Есть ли способ быстрее найти разницу между каждым элементом в списке и каждым другим элементом в этом списке?

Question

Я пытаюсь получить частоту ударов между каждым элементом в списке (получить абсолютное значение разницы между каждым элементом и каждым другим элементом.

, поэтому, если список равен

[a, b, c]

Я хочу сгенерировать

[a, b, c, | ab |, | ac |, | bc |]

но то, что я сейчас делаю (просто перебираю каждый элемент в списке и затем снова перебираю), действительно медленно для числа элементов, с которыми я имею дело, есть ли какая-либо другая структура данных или метод, который я мог бы использовать, чтобы сделать эторабота быстрее?

Код ниже - это то, что я делаю сейчас: я немного новичок в python и не изучил много структур данных за пределами основ, поэтому извините, если решение на самом деле является чем-то действительно очевиднымо котором я не думал!

Я говорил с моим процессором, и он упомянул решетки, это чисто математическая концепция или есть какая-то реализация в коде, которую можно использовать, или это даже что-то, что будетusefuЯ для моего случая?

Вот код, который я сейчас запускаю. Он принимает список частот и амплитуд, где амплитуда частоты на частотах [n] равна амплитудам [n]. Как только найдена уникальная частота биений, она добавляется в список с амплитудой, которая является средним значением амплитуд входных частот, поэтому, если у вас 440 Гц при a = 1 и 110 Гц при a = 2, частота биений будет равна abs(440-110) при а = ((1 + 2) / 2).

def beatSet(frequencies, amplitudes, tol) :
        for index_x, x in enumerate(frequencies) :
                for index_y, y in enumerate(frequencies[index_x+1:]) :
                        beat_freq = abs(x - y)
                        if search(frequencies, beat_freq, tol) : #returns true if beat_freq isn't a duplicate, within a tolerance
                                frequencies.append(beat_freq)
                                amplitudes.append((amplitudes[index_y] + amplitudes[index_x])/2) 

и функция поиска выглядит следующим образом:

def search(list_in, search_term, tolerance) :
        for i in list_in :
                if abs(search_term - i) <= tolerance :
                        return False
        return True

Как правило, входной список будет иметь где-то около 10-50 элементов, но выходные данные могут стать действительно большимичто-то вроде [440, 441] сгенерирует выходной список, который будет очень большим, если не было допусков, поэтому допуск является своего рода ограничивающим фактором для размера выходного списка. Как правило, самый большой выходной список генерируется, когда разница двух частот в входном списке чуть выше допуска.

Извините за стену текста, надеюсь, я достаточно подробно все объяснил!

Answer 1

Одна проблема, с которой я столкнулся при использовании вашего метода, заключается в том, что он адаптирует исходные значения

. Вы можете отсортировать частоты и использовать bisect для поиска в отсортированном списке:

import bisect
import itertools
def beat_set(frequencies, amplitudes, tolerance):
    sorted_frequencies = sorted(zip(frequencies, amplitudes))
    results = {}
    for (
        (index_x, (freq_x, ampl_x)),
        (index_y, (freq_y, ampl_y)),
    ) in itertools.combinations(enumerate(sorted_frequencies), 2):
        beat_frequency = abs(freq_x - freq_y)
        if not search_bisect(sorted_frequencies, beat_frequency, tolerance):
            # beat_frequency already in frequencies
            continue
        beat_amplitude = (ampl_x + ampl_y) / 2
        bisect.insort_left(sorted_frequencies, (beat_frequency, beat_amplitude))
    return sorted_frequencies
(beat_set(frequencies, amplitudes, tolerance))

def search_bisect(sorted_frequencies, beat_frequency, tolerance):
    insert_index = bisect.bisect_left(sorted_frequencies, (beat_frequency,))
    if insert_index == 0:
        return abs(sorted_frequencies[0][0] - beat_frequency) > tolerance
    return all(
        abs(sorted_frequencies[insert_index - i][0] - beat_frequency)
        > tolerance
        for i in (0, 1)
)

. список частот обновляется для каждого найденного удара, но сравниваются только исходные частоты. В решении ОП второй цикл for использовал обновленную частоту.

frequencies = 440, 441
amplitudes = 2, 1
tolerance = 0.1

beat_set(frequencies, amplitudes, tolerance)

[(1, 1.5), (440, 2), (441, 1)]

-

сходимость

def search_until_convergence(
    frequencies, amplitudes, tolerance, max_iterations=100
):
    result_new = beat_set(frequencies, amplitudes, tolerance)
    result_old = None
    for i in itertools.count():
        if i >= max_iterations:
            raise ValueError(f"No Convergence after {i} iterations")
        frequencies_new, amplitudes_new = zip(*result_new)
        if result_old == result_new:
            return {
                "frequencies": frequencies_new,
                "amplitudes": amplitudes_new,
                "iterations": i,
            }
        result_old = result_new
        result_new = beat_set(frequencies_new, amplitudes_new, tolerance)