基于另一数组的唯一匹配排序：大数组高效实现需求

问题描述 #

给定两个数组：

data_array = [4.4, 7.2, 10.1, 1.1, 5.5, 8.3, 2.2, 6.2, 3.3, 9.1, 1.3]
test_array = [2, 5, 9, 4, 10, 8, 7, 3, 6, 1, 1]

期望输出：

[2.2, 5.5, 9.1, 4.4, 10.1, 8.3, 7.2, 3.3, 6.2, 1.1, 1.3]

核心需求：

• 基于两个数组元素的最小差值进行唯一匹配：test_array中的重复元素（如示例中的两个1）需依次匹配data_array中剩余元素里差值最小的项
• 必须支持千万级长度的大数组，保证执行效率

现有低效方案分析 #

以下两种方法均无法处理大数组，核心原因是时间复杂度过高：

方法1：循环删除匹配元素 #

def method1(A, B):
    result = np.empty_like(A)
    for i, val in tqdm(enumerate(A), desc="Processing", unit="iteration", unit_scale=True):
        closest_idx = np.argmin(np.abs(B- val))
        result[i] = B[closest_idx]
        comp_arr = np.delete(B, closest_idx)
    return result

• 问题：每次循环调用np.delete（O(n)操作），整体时间复杂度O(n²)，千万级数据下完全不可行。

方法2：并行循环重复排序 #

# GPU execution - most efficient method found in stackoverflow!
@nb.njit('int_[:](float32[:],float32[:])', parallel=True)
def method2(A,B):
    mB = B.shape[0]
    output = np.empty(A.shape[0], dtype=np.int_)

    # Parallel loop
    for i in nb.prange(A.shape[0]):
        rowA = A[i]
        rowB = B

        index_rowB = np.argsort(rowB)
        sorted_rowB = rowB[index_rowB]

        idxs = np.searchsorted(sorted_rowB, rowA)
        left = np.fabs(rowA - sorted_rowB[np.maximum(idxs-1, 0)])
        right = np.fabs(rowA - sorted_rowB[np.minimum(idxs, mB-1)])
        prev_idx_is_less = (idxs == mB) | (left < right)

        output[i] = index_rowB[idxs - prev_idx_is_less]

    return output

• 问题：每个循环都对B进行排序（O(n log n)操作），整体时间复杂度O(n² log n)，并行也无法抵消重复排序的开销。

高效实现方案 #

核心思路：先排序+双指针贪心匹配，时间复杂度O(n log n)，完全适配千万级大数组。

Python 实现（基于NumPy） #

import numpy as np

def efficient_match(test_arr, data_arr):
    # 对test数组排序并保留原始索引
    sorted_test, test_indices = np.sort(test_arr), np.argsort(test_arr)
    # 对data数组排序
    sorted_data = np.sort(data_arr)
    
    n = len(sorted_test)
    data_ptr = 0
    # 存储匹配结果，按test数组原始顺序排列
    result = np.empty(n, dtype=data_arr.dtype)
    
    for i in range(n):
        current_test = sorted_test[i]
        # 双指针移动：找到当前test值对应的最小差值data元素
        while (data_ptr + 1 < n) and (abs(sorted_data[data_ptr + 1] - current_test) < abs(sorted_data[data_ptr] - current_test)):
            data_ptr += 1
        # 将匹配的data值放到对应原始索引位置
        result[test_indices[i]] = sorted_data[data_ptr]
        # 标记该data元素已被使用（替换为极大值，避免重复匹配）
        sorted_data[data_ptr] = np.inf
    
    return result

# 测试示例
data_array = np.array([4.4, 7.2, 10.1, 1.1, 5.5, 8.3, 2.2, 6.2, 3.3, 9.1, 1.3])
test_array = np.array([2, 5, 9, 4, 10, 8, 7, 3, 6, 1, 1])
output = efficient_match(test_array, data_array)
print(output.tolist())
# 输出：[2.2, 5.5, 9.1, 4.4, 10.1, 8.3, 7.2, 3.3, 6.2, 1.1, 1.3]

• 原理：
  1. 对两个数组分别排序，同时记录test数组的原始索引
  2. 用双指针遍历排序后的test数组，每次匹配当前最小差值的data元素
  3. 匹配后将data元素标记为已使用（设为无穷大），避免重复匹配
  4. 最后按test数组的原始索引还原结果顺序

MATLAB 实现 #

function result = efficient_match(test_arr, data_arr)
    % 对test数组排序并保留原始索引
    [sorted_test, test_indices] = sort(test_arr);
    % 对data数组排序
    sorted_data = sort(data_arr);
    
    n = length(sorted_test);
    data_ptr = 1;
    result = zeros(n, 1);
    
    for i = 1:n
        current_test = sorted_test(i);
        % 双指针寻找最小差值元素
        while (data_ptr + 1 <= n) && (abs(sorted_data(data_ptr + 1) - current_test) < abs(sorted_data(data_ptr) - current_test))
            data_ptr = data_ptr + 1;
        end
        % 赋值到原始索引位置
        result(test_indices(i)) = sorted_data(data_ptr);
        % 标记已使用
        sorted_data(data_ptr) = inf;
    end
end

% 测试示例
data_array = [4.4, 7.2, 10.1, 1.1, 5.5, 8.3, 2.2, 6.2, 3.3, 9.1, 1.3];
test_array = [2, 5, 9, 4, 10, 8, 7, 3, 6, 1, 1];
output = efficient_match(test_array, data_array);
disp(output);
% 输出：2.2 5.5 9.1 4.4 10.1 8.3 7.2 3.3 6.2 1.1 1.3

• 原理与Python版本一致，利用MATLAB内置的sort函数获取排序索引，双指针贪心匹配。

性能说明 #

• 排序操作的时间复杂度为O(n log n)，双指针遍历为O(n)，整体时间复杂度为O(n log n)
• 千万级数组在现代CPU上的处理时间通常在数秒级别，完全满足需求

内容的提问来源于stack exchange，提问作者Niranjan Ravi