化合物复合组分净占比计算算法优化方案问询

现有N种编号1至N的化合物，每种化合物包含基础组分（如A、B等）或其他化合物的占比数据，示例数据集如下：

mixes = {
    1: {
        "A": 0.32,
        "B": 0.12,
        "C": 0.15,
        2: 0.41
    },
    2: {
        "C": 0.23,
        "D": 0.12,
        "E": 0.51,
        4: 0.14
    },
    3: {
        "A": 0.24,
        "E": 0.76
    },
    4: {
        "B": 0.13,
        "F": 0.01,
        "H": 0.86
    },
    5: {
        "G": 0.1,
        2: 0.4,
        3: 0.5
    }
}

需要计算每种化合物中各基础组分的净占比，示例输出如下：

mixes = {
    1: {
        "A": 0.32,
        "B": 0.12 + 0.41 * 0.14 * 0.13,
        "C": 0.15 + 0.41 * 0.23,
        "D": 0.41 * 0.12,
        "E": 0.41 * 0.51,
        "F": 0.41 * 0.14 * 0.01,
        "H": 0.41 * 0.14 * 0.86
    },
    2: {
        "B": 0.14 * 0.13,
        "C": 0.23,
        "D": 0.12,
        "E": 0.51,
        "F": 0.14 * 0.01,
        "H": 0.14 * 0.86
    },
    3: {
        "A": 0.24,
        "E": 0.76
    },
    4: {
        "B": 0.13,
        "F": 0.01,
        "H": 0.86
    },
    5: {
        "A": 0.5 * 0.24,
        "G": 0.1,
        "B": 0.4 * 0.14 * 0.13,
        "C": 0.4 * 0.23,
        "D": 0.4 * 0.12,
        "E": 0.4 * 0.51 + 0.5 * 0.76,
        "F": 0.4 * 0.14 * 0.01,
        "H": 0.4 * 0.14 * 0.86
    }
}

当前采用递归方法实现，希望获取更高效的替代方案（比如基于树结构/拓扑排序的实现方式），已知数据集无循环依赖关系。

因为数据集无循环依赖，化合物之间的依赖关系构成一个有向无环图（DAG），可以通过以下步骤实现更高效的计算：

步骤1：构建依赖关系并生成拓扑排序 #

首先，为每个化合物标记它依赖的其他化合物，然后生成拓扑排序序列——确保处理某个化合物时，它依赖的所有化合物已经被处理完毕，避免重复计算。

示例中的依赖关系：

• 1依赖2
• 2依赖4
• 5依赖2和3
• 3、4无依赖

拓扑排序的一个可行序列：4 → 3 → 2 → 1 → 5

步骤2：按拓扑顺序计算每个化合物的净组分占比 #

维护一个结果字典，存储每个化合物已计算好的净组分占比。按拓扑顺序处理每个化合物：

1. 初始化当前化合物的净组分为空字典。
2. 遍历当前化合物的所有成分：
   • 如果是基础组分（如"A"、"B"），直接将占比加到结果中（如果已存在则累加）。
   • 如果是其他化合物（如2、4），取出该化合物已计算好的净组分，将每个组分的占比乘以当前的权重，加到当前化合物的对应组分中（如果已存在则累加）。

代码实现示例 #

def calculate_net_components(mixes):
    # 构建依赖图和入度表
    dependency_graph = {comp: [] for comp in mixes}
    in_degree = {comp: 0 for comp in mixes}
    
    for comp, components in mixes.items():
        for item in components:
            if isinstance(item, int) and item in mixes:
                dependency_graph[item].append(comp)
                in_degree[comp] += 1
    
    # 生成拓扑排序序列
    topo_order = []
    queue = [comp for comp in in_degree if in_degree[comp] == 0]
    
    while queue:
        current = queue.pop(0)
        topo_order.append(current)
        for neighbor in dependency_graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 按拓扑顺序计算净组分
    result = {}
    for comp in topo_order:
        net = {}
        components = mixes[comp]
        for item, ratio in components.items():
            if isinstance(item, str):
                # 基础组分直接累加
                net[item] = net.get(item, 0) + ratio
            else:
                # 依赖化合物的净组分加权累加
                dep_net = result[item]
                for base, base_ratio in dep_net.items():
                    weighted = ratio * base_ratio
                    net[base] = net.get(base, 0) + weighted
        result[comp] = net
    
    return result

# 测试示例
mixes = {
    1: {"A": 0.32, "B": 0.12, "C": 0.15, 2: 0.41},
    2: {"C": 0.23, "D": 0.12, "E": 0.51, 4: 0.14},
    3: {"A": 0.24, "E": 0.76},
    4: {"B": 0.13, "F": 0.01, "H": 0.86},
    5: {"G": 0.1, 2: 0.4, 3: 0.5}
}

net_components = calculate_net_components(mixes)
# 打印数值结果
for comp, components in net_components.items():
    print(f"{comp}: {components}")

方案优势 #

• 避免重复计算：递归方法可能多次计算同一个依赖化合物（比如化合物2被1和5依赖，递归会分别计算两次），拓扑排序后每个化合物只计算一次，效率更高。
• 线性时间复杂度：整体时间复杂度为O(V+E)，其中V是化合物数量，E是所有成分的总数，适合大规模数据集。
• 逻辑清晰：基于DAG的拓扑排序符合依赖关系的自然处理顺序，代码易维护。

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