Python 3.x中基于概率直方图高效计算大量变量概率的方法

问题背景 #

我有两个无重叠的概率直方图：一个对应机器正常工作状态，另一个对应异常状态。每个直方图包含M个区间，用两个列表表示：一个存储区间概率，一个存储升序排列的区间边界。现在要处理N个数值，找到每个值所属区间对应的概率，原始实现的时间复杂度是O(N*M)，需要优化。

原始代码示例：

normal_histogram = [0.5, 0.5]
normal_edges_of_histogram = [0,1.5,3]

abnormal_hist = [0.6, 0.4]
abnormal_edges = [5,7,9]

values = [5,1,78,2,6,8,2,9,0]

# 时间复杂度O(N*M)的实现
for x in values:
  l_edge = 0
  r_edge = l_edge+1
  prob = 0
  while r_edge <= len(normal_edges_of_histogram)-1:
    if normal_edges_of_histogram[l_edge] <= x <= normal_edges_of_histogram[r_edge]:
      prob = normal_histogram[l_edge]
      break
    elif abnormal_edges[l_edge] <= x <= abnormal_edges[r_edge]:
      prob = abnormal_hist[l_edge]
      break
    l_edge += 1
    r_edge += 1
  print(prob)

预期输出：

answer = [0.6, 0.5, 0, 0.5, 0.6, 0.4, 0.5, 0.4, 0.5]

优化方案 #

方案1：二分查找（时间复杂度O(N*logM)） #

因为两个直方图的区间边界都是升序排列且无重叠，我们可以先判断数值落在哪个直方图的范围里，再用二分查找快速定位区间索引：

import bisect

normal_histogram = [0.5, 0.5]
normal_edges = [0, 1.5, 3]
abnormal_hist = [0.6, 0.4]
abnormal_edges = [5, 7, 9]

values = [5,1,78,2,6,8,2,9,0]
result = []

for x in values:
    prob = 0
    # 检查是否在正常区间范围内
    if normal_edges[0] <= x <= normal_edges[-1]:
        # 用bisect_right找到插入位置，减1就是对应区间的索引
        idx = bisect.bisect_right(normal_edges, x) - 1
        prob = normal_histogram[idx]
    # 检查是否在异常区间范围内
    elif abnormal_edges[0] <= x <= abnormal_edges[-1]:
        idx = bisect.bisect_right(abnormal_edges, x) - 1
        prob = abnormal_hist[idx]
    result.append(prob)

print(result)  # 输出: [0.6, 0.5, 0, 0.5, 0.6, 0.4, 0.5, 0.4, 0.5]

方案2：预处理合并所有有效区间（时间复杂度O(M + N*logM)） #

把正常和异常的区间合并成一个有序的区间-概率映射表，之后每个数值只需要一次二分查找：

import bisect

normal_histogram = [0.5, 0.5]
normal_edges = [0, 1.5, 3]
abnormal_hist = [0.6, 0.4]
abnormal_edges = [5, 7, 9]

# 预处理：整理所有区间的(左边界, 右边界, 概率)并排序
all_intervals = []
# 添加正常区间
for i in range(len(normal_histogram)):
    all_intervals.append((normal_edges[i], normal_edges[i+1], normal_histogram[i]))
# 添加异常区间
for i in range(len(abnormal_hist)):
    all_intervals.append((abnormal_edges[i], abnormal_edges[i+1], abnormal_hist[i]))
# 按左边界排序（原区间无重叠，也可直接拼接）
all_intervals.sort()
# 提取单独的右边界列表用于二分查找
right_edges = [edge[1] for edge in all_intervals]

values = [5,1,78,2,6,8,2,9,0]
result = []

for x in values:
    prob = 0
    # 找到第一个大于x的右边界索引
    idx = bisect.bisect_right(right_edges, x)
    if idx > 0:
        left, _, p = all_intervals[idx-1]
        if left <= x:
            prob = p
    result.append(prob)

print(result)  # 输出: [0.6, 0.5, 0, 0.5, 0.6, 0.4, 0.5, 0.4, 0.5]

方案说明 #

• 二分查找方案代码简洁直观，适合两个直方图区间范围差异明显的场景，每个数值最多两次二分查找，时间复杂度为O(N*logM)。
• 合并区间方案适合直方图数量较多的场景，预处理一次后每个数值仅需一次二分查找，整体效率更优。

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