如何用NumPy/Pandas加速运算？求该问题名称及高效实现

你这个问题属于预算约束下的迭代最优子集选择，本质是多轮的0-1背包问题变种——每轮在成本（预算）限制内，选择收益最大的完整集合（句子），之后更新集合内元素的属性，重复执行。这类问题在推荐系统、资源分配场景中很常见。

原代码的性能瓶颈在于三层嵌套Python循环，利用NumPy的向量化操作可以大幅提升速度，因为NumPy的底层运算由C实现，避免了Python循环的开销。以下是优化后的代码：

import random
import secrets
import time
import math
import numpy as np

# 生成模拟数据
NUM_WORDS = 10000
NUM_SENTENCES = 10000
MAX_SENTENCE_LENGTH = 25

# 转为NumPy数组，支持向量化操作
word_gain = np.array([math.exp(4*random.random()) for _ in range(NUM_WORDS)])
word_cost = np.array([random.random() for _ in range(NUM_WORDS)])

# 将每个句子存储为NumPy数组，方便后续快速索引
sentences = [
    np.array([secrets.randbelow(NUM_WORDS) for _ in range(3 + secrets.randbelow(MAX_SENTENCE_LENGTH - 3))])
    for _ in range(NUM_SENTENCES)
]

start_time = time.time()
MAX_COST = 6.0

for _ in range(50):
    # 向量化计算所有句子的总收益和总成本
    sentence_gains = np.array([word_gain[sent].sum() for sent in sentences])
    sentence_costs = np.array([word_cost[sent].sum() for sent in sentences])
    
    # 筛选符合成本限制的句子
    valid_mask = sentence_costs <= MAX_COST
    valid_indices = np.where(valid_mask)[0]
    valid_gains = sentence_gains[valid_mask]
    
    # 找到收益最大的句子
    best_valid_idx = valid_gains.argmax()
    best_index = valid_indices[best_valid_idx]
    best_value = valid_gains[best_valid_idx]
    
    assert best_value > 0.0
    print(f"Best {best_index} {best_value}")
    
    # 向量化更新词的分数
    selected_words = sentences[best_index]
    word_gain[selected_words] = -0.01
    word_cost[selected_words] /= 2

end_time = time.time()
print(f"Elapsed time {end_time - start_time}")

如果数据量继续增大，还可以考虑：

• 用稀疏矩阵存储句子与词的关联关系，减少内存占用并加速求和运算
• 预先计算句子的词频矩阵，结合广播操作批量计算收益和成本
• 若允许近似解，可使用启发式算法（如贪心策略的优化版）进一步降低计算量

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