时间戳

首页 > 解决方案 > 从相同索引处值差异最小的列表中查找对

python - 从相同索引处值差异最小的列表中查找对

问题描述

给定表格列表的列表：

list = [index, number1, number2]
list_of_lists = [list1, list2, list3, ...]

您如何以最 Pythonic 的方式找到在例如 number1 中差异最小的列表对？

例子：

list_of_lists = [[0, 13, 48], [1, 28, 9199], [2, 11, 128], [3, 9, 40]]
pairs = [[[1, 13, 48],[2, 11, 128]], [[2, 11, 128], [3, 9, 40]]]

因为abs(13-11) = abs(11-9) < abs(13-9) < abs(13-28) < abs(28-11) < abs(28-9). 到目前为止，我使用的方法是遍历所有带有循环的列表，检查差异的值并将其与迄今为止的差异值进行比较，希望每个列表只检查一次。

lst = [list1, list2, list3, ...]
diff = 10000000000
candidates = []
for idx, c in enumerate(lst):
    for i in range(idx+1, len(lst)):
        current_diff = abs(c[0] - lst[i][0])
        if current_diff < diff:
            diff = current_diff
            candidates = []
            candidates.append([c, lst[i]])
        elif current_diff == diff:
            candidates.append([c, lst[i]])

由于多种原因，这似乎相当不雅。尤其是“diff”初始值的任意选择。

是否有一种通用且更好的方法来从列表列表中选择列表/列表对，这取决于上面示例中特定值的某种比较？

标签： pythonlistiteration

解决方案

如果我们将您的数据视为矩阵中的行列表，那么您正在寻找同一列中尽可能靠近的数字对。查找列中最接近的两个元素的一种有效方法是对该列进行排序，然后遍历其相邻对。

  • 首先，我们必须构建您要搜索的列。
  • 然后我们必须对列进行排序。这改变了顺序（当然），所以我们将每个元素与它来自的行的索引配对，以便以后可以恢复这些行。
  • zip我们可以使用“领先”一步的迭代器在已排序的列中找到相邻的对。
  • 保持最接近的对的逻辑就像您的原始代码一样，但初始化diff = math.inf而不是一个大的有限数，并通过更改elif为if.

执行：

import math

def closest_pairs(rows, column_index):
    column = sorted((a[column_index], i) for i, a in enumerate(rows))

    candidates = []
    diff = math.inf

    # iterator which is one step ahead
    ahead = iter(column)
    next(ahead)

    for (x, i), (y, j) in zip(column, ahead):
        current_diff = y - x
        if current_diff < diff:
            candidates.clear()
            diff = current_diff
        if current_diff == diff:
            i, j = sorted([i, j])
            candidates.append( (rows[i], rows[j]) )

    return candidates

例子：

>>> lst = [[0, 28, 9199], [1, 13, 48], [2, 11, 128]]
>>> closest_pairs(lst, 1)
[([1, 13, 48], [2, 11, 128])]
>>> closest_pairs(lst, 0)
[([0, 28, 9199], [1, 13, 48]), ([1, 13, 48], [2, 11, 128])]

第 1 列中最接近的对是13, 11; 在第 0 列中，两者0, 1和1, 2都是最接近的。

对于具有n行的矩阵，与原始的 O(n²) 蛮力解决方案相比，此解决方案的时间复杂度为 O( n log n )。

推荐阅读