Python中如何最高效计算这类特殊加权求和问题

我需要计算一类特殊求和值，目前尝试的实现策略效率不够理想，希望能获得更优的实现方案。

预计算部分 #

这部分逻辑固定不变，N可调整，定义Uf的f函数也可调整，所有项均预先完成计算：

import time

N = 10000

Uf = ([0]*2) + [1/f for f in range(2,N+1)]

频率数据处理部分 #

实际业务中fs的格式不同，但本质一致：包含多个f值，每个值重复指定次数，例如示例中f=2重复1000次，f=9998重复2次等。我将每个f值的出现频率存入列表Ff，采用列表存储是为了可以直接通过Ff[f]快速获取对应频率，其余位置填充0是因为后续计算中大量f值的频率会频繁增减，预先填充数值可大幅简化操作：

fs = [[2]*1000, [9998]*2, [5]*2000, [9995]*1, [10]*585, [20]*878,
      [50]*2580, [77]*1487, [1100]*5454, [2300]*4047, [3700]*5471]

Ff = [0]*(N+1)

for l in fs:
    Ff[l[0]] = len(l)

初始求和实现 #

需要计算的求和值S如下：

S = sum([(Ff[f]+Ff[N-f])*Uf[f] for f in range(2,N)])
print(S)
# 1085.5709951104413
%timeit S = sum([(Ff[f]+Ff[N-f])*Uf[f] for f in range(2,N)])
# 3.93 ms ± 327 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

优化尝试1：遍历中过滤0值项 #

最初认为性能偏慢是因为累加了大量0值，因此添加了判断条件筛选有效项：

S = sum([(Ff[f]+Ff[N-f])*Uf[f] for f in range(2,N) if (Ff[f] + Ff[N-f] > 0)])
print(S)
# 1085.5709951104413
%timeit S = sum([(Ff[f]+Ff[N-f])*Uf[f] for f in range(2,N) if (Ff[f] + Ff[N-f] > 0)])
# 2.53 ms ± 120 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

该方案有一定优化，但提升幅度不大。改用逻辑或条件判断有效项反而导致性能略降：

S = sum([(Ff[f]+Ff[N-f])*Uf[f] for f in range(2,N) if ((Ff[f] > 0) | (Ff[N-f] > 0))])
print(S)
# 1085.5709951104413
%timeit S = sum([(Ff[f]+Ff[N-f])*Uf[f] for f in range(2,N) if ((Ff[f] > 0) | (Ff[N-f] > 0))])
# 3.02 ms ± 175 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

优化尝试2：预筛选有效f项 #

测试发现预先筛选出所有有效f项后再求和，性能提升非常明显：

f_on = [f for f,_ in enumerate(Ff) if ((Ff[f] > 0) | (Ff[N-f] > 0))]
S = sum([(Ff[f]+Ff[N-f])*Uf[f] for f in f_on])
print(S)
# 1085.5709951104413
%timeit S = sum([(Ff[f]+Ff[N-f])*Uf[f] for f in f_on])
# 6.12 µs ± 327 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

优化尝试3：改用字典存储频率 #

之后尝试放弃列表Ff改用字典存储频率，利用字典的键自动标识有效f值。为避免键不存在报错，封装了取值函数，同时需要将字典键和对应N-f的所有值去重后作为求和遍历范围：

# 字典方法
Fr_dict = dict()
for l in fs:
    Fr_dict[l[0]] = len(l)

def Fr(f):
    if f in Fr_dict:
        Fr = Fr_dict[f]
    else:
        Fr = 0
    return Fr

S = sum([(Fr(f)+Fr(N-f))*Uf[f] for f in set(list(Fr_dict.keys())+[N-f for f in Fr_dict.keys()])])
print(S)
# 1085.570995110441
%timeit S = sum([(Fr(f)+Fr(N-f))*Uf[f] for f in set(list(Fr_dict.keys())+[N-f for f in Fr_dict.keys()])])
# 16.3 µs ± 452 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

待优化问题 #

目前的实现基本满足需求，但担心N变大后性能会出现瓶颈。是否存在其他更优的实现方案，或者对现有方法的优化思路，可以进一步提升计算效率？

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