9

在 Python 中，我有 3 个浮点数（角度）列表，范围为 0-360，并且这些列表的长度不同。我需要找到数字最接近的三元组（每个列表中有 1 个数字）。（任何数字都不太可能相同，因为这是真实世界的数据。）我正在考虑使用一种简单的最低标准偏差方法来衡量一致性，但我不确定一个好的方法来衡量一致性实现这一点。我可以遍历每个列表，使用嵌套的 for 循环比较每个可能组合的标准偏差，并有一个临时变量保存最一致的三元组的索引，但我想知道是否有人有更好或更优雅的方法来做这样的事情。谢谢！

4

1 回答 1

6

如果有一个既定的算法可以做到这一点，我不会感到惊讶，如果是这样，你应该使用它。但我不知道一个，所以我要推测一下。

如果我必须这样做，我会尝试的第一件事就是遍历所有数字的所有可能组合，看看需要多长时间。如果你的数据集足够小，就不值得花时间去发明一个聪明的算法。为了演示设置，我将包含示例代码：

# setup
def distance(nplet):
    '''Takes a pair or triplet (an "n-plet") as a list, and returns its distance.
    A smaller return value means better agreement.'''
    # your choice of implementation here. Example:
    return variance(nplet)

# algorithm
def brute_force(*lists):
    return min(itertools.product(*lists), key = distance)

对于大型数据集，我会尝试这样的事情：首先为第一个列表中的每个数字创建一个三元组，并将其第一个条目设置为该数字。然后浏览这个部分填充的三元组列表，并为每个三元组从第二个列表中选择最接近第一个列表中的数字的数字，并将其设置为三元组的第二个成员。然后浏览三元组列表，并为每个三元组从第三个列表中选择最接近前两个数字的数字（根据您的协议指标衡量）。最后，采取最好的一堆。此示例代码演示了如何尝试使运行时与列表的长度保持线性。

def item_selection(listA, listB, listC):
    # make the list of partially-filled triplets
    triplets = [[a] for a in listA]
    iT = 0
    iB = 0
    while iT < len(triplets):
        # make iB the index of a value in listB closes to triplets[iT][0]
        while iB < len(listB) and listB[iB] < triplets[iT][0]:
            iB += 1
        if iB == 0:
            triplets[iT].append(listB[0])
        elif iB == len(listB)
            triplets[iT].append(listB[-1])
        else:
            # look at the values in listB just below and just above triplets[iT][0]
            # and add the closer one as the second member of the triplet
            dist_lower = distance([triplets[iT][0], listB[iB]])
            dist_upper = distance([triplets[iT][0], listB[iB + 1]])
            if dist_lower < dist_upper:
                triplets[iT].append(listB[iB])
            elif dist_lower > dist_upper:
                triplets[iT].append(listB[iB + 1])
            else:
                # if they are equidistant, add both
                triplets[iT].append(listB[iB])
                iT += 1
                triplets[iT:iT] = [triplets[iT-1][0], listB[iB + 1]]
        iT += 1
    # then another loop while iT < len(triplets) to add in the numbers from listC
    return min(triplets, key = distance)

问题是，我可以想象实际上找不到最佳三元组的情况，例如，如果第一个列表中的数字接近第二个列表中的一个，但根本不接近第三个列表中的任何数字。因此，您可以尝试对列表的所有 6 种可能排序运行此算法。我想不出一种无法找到最佳三元组的具体情况，但可能仍然存在。在任何情况下，如果您使用巧妙的实现，假设列表已排序，算法仍然是 O(N)。

def symmetrized_item_selection(listA, listB, listC):
    best_results = []
    for ordering in itertools.permutations([listA, listB, listC]):
        best_results.extend(item_selection(*ordering))
    return min(best_results, key = distance)

另一种选择可能是计算列表 1 和列表 2 之间、列表 1 和列表 3 之间以及列表 2 和列表 3 之间的所有可能的数字对。然后将所有三个对列表一起排序，从两者之间的最佳到最差一致性数字。从最接近的一对开始，逐对遍历列表，任何时候遇到与你已经见过的一个共享数字的一对，将它们合并为一个三元组。对于合适的一致性度量，一旦找到第一个三元组，这将为您提供需要迭代的最大对距离，一旦达到它，您只需选择最接近的三元组成立。我认为应该始终找到最好的三元组，但由于需要对对列表进行排序，它将是 O(N^2 log N)。

def pair_sorting(listA, listB, listC):
    # make all possible pairs of values from two lists
    # each pair has the structure ((number, origin_list),(number, origin_list))
    # so we know which lists the numbers came from
    all_pairs = []
    all_pairs += [((nA,0), (nB,1)) for (nA,nB) in itertools.product(listA,listB)]
    all_pairs += [((nA,0), (nC,2)) for (nA,nC) in itertools.product(listA,listC)]
    all_pairs += [((nB,1), (nC,2)) for (nB,nC) in itertools.product(listB,listC)]
    all_pairs.sort(key = lambda p: distance(p[0][0], p[1][0]))
    # make a dict to track which (number, origin_list)s we've already seen
    pairs_by_number_and_list = collections.defaultdict(list)
    min_distance = INFINITY
    min_triplet = None
    # start with the closest pair
    for pair in all_pairs:
        # for the first value of the current pair, see if we've seen that particular
        # (number, origin_list) combination before
        for pair2 in pairs_by_number_and_list[pair[0]]:
            # if so, that means the current pair shares its first value with
            # another pair, so put the 3 unique values together to make a triplet
            this_triplet = (pair[1][0], pair2[0][0], pair2[1][0])
            # check if the triplet agrees more than the previous best triplet
            this_distance = distance(this_triplet)
            if this_distance < min_distance:
                min_triplet = this_triplet
                min_distance = this_distance
        # do the same thing but checking the second element of the current pair
        for pair2 in pairs_by_number_and_list[pair[1]]:
            this_triplet = (pair[0][0], pair2[0][0], pair2[1][0])
            this_distance = distance(this_triplet)
            if this_distance < min_distance:
                min_triplet = this_triplet
                min_distance = this_distance
        # finally, add the current pair to the list of pairs we've seen
        pairs_by_number_and_list[pair[0]].append(pair)
        pairs_by_number_and_list[pair[1]].append(pair)
    return min_triplet

请注意，我在此答案中编写的所有代码示例比您在实践中所做的更明确一些，以帮助您了解它们的工作原理。但是当真正做到这一点时，你会使用更多的列表推导和类似的东西。

NB2。不能保证代码可以工作:-P，但它应该能让你大致了解一下。

于 2012-09-27T23:40:45.077 回答