时间戳

首页 > 解决方案 > 有没有办法更快地找到列表中的每个元素与该列表中的每个其他元素之间的差异？

python - 有没有办法更快地找到列表中的每个元素与该列表中的每个其他元素之间的差异？

问题描述

我正在尝试获取列表中每个元素之间的拍频，（获取每个元素与每个其他元素之间差异的绝对值。

所以如果列表是

[a,b,c]

我要生成

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

但是我现在正在做的事情（简单地遍历列表中的每个元素然后再次迭代）对于我正在处理的元素数量来说真的很慢，是否有任何其他数据结构或方法可以用来制作这个操作更快？

下面的代码是我现在正在做的。我对python有点陌生，并且在基础知识之外还没有学习过很多数据结构，所以很抱歉，如果解决方案实际上是我没有想到的非常明显的东西！

我与我的处理器交谈，他提到了格，这些是纯粹的数学概念，还是在代码中存在一些可行的实现，或者甚至对我的情况有用的东西？

这是我目前正在运行的代码。它需要一个频率和幅度列表，其中频率 [n] 处的频率幅度位于幅度 [n] 处。一旦找到一个独特的拍频，它就会被添加到列表中，其振幅是输入频率振幅的平均值，因此如果 a = 1 时为 440hz，a = 2 时为 110hz，则拍频将为绝对值(440-110) 在 a = ((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] 这样的输出列表会生成一个非常大的输出列表，所以容差在某种程度上是输出列表大小的限制因素。通常，当输入列表中两个频率的差值刚好在容差之上时，会生成最大的输出列表。

对不起，文字墙，希望我已经足够彻底地解释了一切！

标签： pythonperformancedata-structurestime-complexity

解决方案

我对你的方法的一个问题是它适应了原来的

您可以对频率进行排序，并用于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)
)

频率列表会在每个找到的节拍上更新，但仅比较原始频率。在 OP 的解决方案中，第二个 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)

推荐阅读