最大价值组合求解代码优化问询：现有方案能否进一步优化？

存在的缺陷 #

1. 内存占用过高：使用results_dict存储所有组合的计算结果，当行数（ROWS）较大时（比如原需求的400行），组合总数会达到百万甚至千万级，字典会占用大量内存，不符合4GB内存系统的运行要求。
2. 行索引查找效率低且存在错误风险：
   • index_of_row函数通过遍历所有行匹配内容来获取索引，时间复杂度为O(ROWS)，每次组合中的每个行都要调用该函数，累计耗时较多。
   • 当矩阵中存在重复行时，该函数会返回第一个匹配行的索引，导致不同索引的重复行组合被赋予相同的名称，混淆了实际的组合内容。
3. 冗余的字典赋值逻辑：results_dict[name] = max(sum_, results_dict.get(name, -np.inf))中的max操作完全多余，因为每个索引组合都是唯一的，对应的名称不会重复，无需做最大值比较。

进一步优化方向 #

1. 回归堆结构存储Top N结果：放弃存储所有组合结果，重新使用heapq维护一个大小为100的最小堆，仅保留当前计算得到的前100大结果，大幅降低内存占用。堆的插入/替换操作时间复杂度为O(log 100)，几乎可以忽略。
2. 遍历索引组合而非行组合：
   • 改用itertools.combinations(range(ROWS), i)生成索引的组合，而非直接遍历行数组。这样无需查找行索引，生成名称时直接通过chr(65 + idx)转换即可，既避免了重复行导致的名称错误，又省去了大量的行匹配时间。
   • 通过索引取行时，使用random_numbers_matrix[list(combination), :]一次性获取组合中的所有行，再用np.max(axis=0)计算列最大值，利用numpy的向量化操作提升效率。
3. 简化计算逻辑：移除字典赋值中的max操作，直接将计算结果存入堆或字典（如果仍需存储的话）。

优化后的示例代码 #

import itertools
import numpy as np
import heapq

# Constants.
ROWS = 40
COLUMNS = 400
N = 3
ONLY_SHOW_TOP_ITEMS = 100
RANDINT_BOUNDARIES = (-100, +100)

if __name__ == "__main__":
    # Data generation
    random_numbers_matrix = np.random.randint(*RANDINT_BOUNDARIES, (ROWS, COLUMNS))
    
    result_heap = []
    for i in range(1, N+1):
        # 遍历索引组合而非行组合
        for idx_comb in itertools.combinations(range(ROWS), i):
            # 生成组合名称
            sublist_name = ''.join([chr(65 + idx) for idx in idx_comb])
            # 获取组合中的行并计算列最大值之和
            selected_rows = random_numbers_matrix[list(idx_comb), :]
            max_values = np.max(selected_rows, axis=0)
            sum_result = np.sum(max_values)
            
            # 维护最小堆，保留前100大的结果
            if len(result_heap) < ONLY_SHOW_TOP_ITEMS:
                heapq.heappush(result_heap, (sum_result, sublist_name))
            elif sum_result > result_heap[0][0]:
                heapq.heappushpop(result_heap, (sum_result, sublist_name))
    
    # 按降序排序并输出前100项
    sorted_results = sorted(result_heap, key=lambda x: x[0], reverse=True)
    for sum_result, sublist_name in sorted_results:
        print(f"{sum_result} ---> {sublist_name}")

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