python - 为另一个数组中的所有 float 查找数组中最接近的 float

Question

我在根据另一个数组中找到的最接近的 float “过滤”一个数组时遇到性能问题。

这是一个 MWE问题:

import numpy as np

def random_data(N):
    # Generate some random data.
    return np.random.uniform(0., 10., N).tolist()

# Data lists.
N1 = 1500
list1 = [random_data(N1), random_data(N1), random_data(N1)]
list2 = random_data(1000)

# Define list1's range.
min_1, max_1 = min(list1[2]), max(list1[2])

# This list will contain the "filtered" list1.
list4 = [[], [], []]

# Go through each element in list2.
for elem2 in list2:

    # If it is located within the list1 range.
    if min_1 <= elem2 <= max_1:

        # Find the closest float in sub-list list1[2] to this float
        # in list2.
        indx, elem1 = min(enumerate(list1[2]), key=lambda x:abs(x[1]-elem2))

        # Store the values in list1 that are associated with the closest float
        # found above.
        list4[0].append(list1[0][indx])
        list4[1].append(list1[1][indx])
        list4[2].append(elem1)

(注意 list2 包含的元素少于 list1[2] ，这是我与之比较的子列表)

此 block 按预期工作，但效率极低。我确信答案在于正确应用 broadcasting和 numpy数组，但我仍然没有充分掌握前者的窍门，无法将其应用于我的问题。

因为我是在增强这段代码的性能之后，任何解决方案都可以(即:我不受必须使用广播的答案的约束)

---

添加

作为引用，在我前段时间提出的类似问题中Fast weighted euclidean distance between points in arrays , 用户 ali_m使用广播实现了惊人的性能提升。

问题并不完全相同(那里的欧几里得距离而不是绝对值，而且该问题中的距离必须加权)但在我看来这个问题比那个问题更简单。

不能将应用于该问题的广播解决方案 ali_m 应用于该问题吗？

---

加2

user2357112 给出的答案以及 Eelco Hoogendoorn 的更正对我最初定义的代码非常有用。我刚刚意识到我过度简化了它，在我的实际代码中列表 list1[2]和 list2 不一定在同一范围内定义。这将是一个更准确的表示(这应该替换上面 MWE 中的第一行):

def random_data(N, xi, xf):
    # Generate some random data.
    return np.random.uniform(xi, xf, N).tolist()

# Data lists.
N1 = 1500
list1 = [random_data(N1, 13., 20.), random_data(N1, -1., 4.), random_data(N1, 2., 7.)]
list2 = random_data(1000, 0., 10.)

现在 list1[2] 的范围不等于 list2 的范围因此给出的答案未能拒绝这些观点i为此 list2[i] > max(list1[2])或 list2[i] < min(list1[2]) .

是否可以修改答案以考虑这种可能性？非常抱歉把原来的代码改成这样，真的是我一时疏忽了。

Answer 1

Kd-tree 在这里实在是太过分了，你需要做的就是对数组进行排序，然后使用二分查找在排序后的数组中找到最接近的值。我写了一个answer前段时间介绍了如何使用 searchsorted 查找数组中目标的最接近值。您可以在这里使用相同的想法:

import numpy as np

def find_closest(A, target):
    #A must be sorted
    idx = A.searchsorted(target)
    idx = np.clip(idx, 1, len(A)-1)
    left = A[idx-1]
    right = A[idx]
    idx -= target - left < right - target
    return idx

def random_data(shape):
    # Generate some random data.
    return np.random.uniform(0., 10., shape)

def main(data, target):
    order = data[2, :].argsort()
    key = data[2, order]
    target = target[(target >= key[0]) & (target <= key[-1])]
    closest = find_closest(key, target)
    return data[:, order[closest]]

N1 = 1500
array1 = random_data((3, N1))
array2 = random_data(1000)
array2[[10, 20]] = [-1., 100]

array4 = main(array1, array2)