如何高效匹配有序大列表与其子集元素的对应索引？

我有一个包含数亿条64位整数的有序大列表，还有一个包含一千条64位整数的有序小列表，且小列表中的所有元素都存在于大列表中。需要找到小列表元素在大列表中的对应索引。示例代码如下：

large_list = [1, 2, 3, 4, 5, 6, 7]
small_list = [2, 6]
matching_indices = magic_function(large_list, small_list)
print(matching_indices) # 输出 [1, 5]，即元素在large_list中的索引

已考虑两种方案，但都存在缺陷：

• 使用merge join，时间复杂度为O(max(n, m))，但因大列表规模过大，整体耗时过久；
• 对小列表每个元素在大列表中执行二分查找，时间复杂度为O(m log n)，但缓存局部性差导致实际运行速度较慢。

请问有没有更高效的实现方案？

推荐方案：结合有序性优化的二分查找 + 缓存友好分块 #

核心思路

利用两个列表均有序且小列表元素全存在于大列表的特性，从两个方向优化：缩小二分查找范围、提升缓存命中率。

具体实现

1. 基于小列表有序性的二分范围优化
   因为小列表是升序的，找到第i个元素的索引idx_i后，第i+1个元素的索引必然≥idx_i。每次二分查找无需从大列表开头开始，直接从上一个元素的索引位置往后搜索，大幅减少查找的比较次数。

2. 缓存友好的分块加载
   如果大列表无法一次性载入内存，按CPU缓存友好的大小（如64KB-256KB对应的数据量）分块预加载。先定位目标元素所在的块，再在块内二分，减少跨块的内存/磁盘IO，提升缓存命中率。

3. Python下的高效实现
   如果大列表能一次性载入内存，直接用numpy的searchsorted——它内部做了底层优化，比纯Python二分快得多，且天然支持批量处理：

import numpy as np

def magic_function(large_list, small_list):
    large_arr = np.array(large_list, dtype=np.int64)
    small_arr = np.array(small_list, dtype=np.int64)
    # 因元素必存在，searchsorted返回的插入位置即为目标索引
    return np.searchsorted(large_arr, small_arr).tolist()

如果大列表过大无法全量加载，用分块+范围优化的实现：

def magic_function_large(large_iterable, small_list):
    indices = []
    current_start = 0
    remaining_chunk = []
    chunk_size = 1_000_000  # 根据内存调整块大小

    for target in small_list:
        while True:
            # 加载新块（如果当前块已空）
            if not remaining_chunk:
                remaining_chunk = []
                try:
                    for _ in range(chunk_size):
                        remaining_chunk.append(next(large_iterable))
                except StopIteration:
                    pass  # 理论上不会触发，因为小列表元素都存在于大列表
            
            # 在当前块内二分查找
            left, right = 0, len(remaining_chunk)
            while left < right:
                mid = (left + right) // 2
                if remaining_chunk[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            
            if left < len(remaining_chunk) and remaining_chunk[left] == target:
                # 记录索引，更新下一次查找的起始位置
                indices.append(current_start + left)
                current_start += left + 1
                # 保留块中剩余元素，避免重复加载
                remaining_chunk = remaining_chunk[left+1:]
                break
            else:
                # 当前块无目标，移动到下一块
                current_start += len(remaining_chunk)
                remaining_chunk = []
    return indices

方案优势

• 时间复杂度为O(m log k)（k为每次二分的范围，远小于大列表总长度n），实际运行效率远高于普通二分；
• 分块策略提升了缓存局部性，减少不必要的内存/磁盘访问；
• 基于numpy的实现充分利用底层优化，比纯Python代码快数倍甚至数十倍。

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