Python中如何有序存储多组二维坐标(R2×n)？非凸函数近似场景

核心需求明确 #

针对可分离函数 g(x) = f1(x1) + f2(x2) + … + fn(xn)，需要维护：

1. 每个分量 fi(xi) 的点集按 x_i 升序排列，包含初始下界点、各迭代生成点、初始上界点
2. 所有分量的顺序严格对应 g(x) 从 f1 到 fn 的顺序，保证后续构建线段、调用线性求解器的逻辑正确性

具体实现方案 #

1. 整体结构选型 #

用**外层列表（数组）**存储所有分量的点集容器，列表索引直接对应分量序号（比如索引0对应f1(x1)，索引1对应f2(x2)），从根本上保证分量顺序不混乱。

2. 单个分量的点集容器 #

每个分量对应一个有序列表，存储该分量的所有点，每个点用元组 (x_i, f_i(x_i), tag) 表示：

• x_i：自变量值
• f_i(x_i)：函数值
• tag：点的类型标记（'lb' 代表下界、'iter_k' 代表第k次迭代点、'ub' 代表上界）

关键操作步骤

• 初始化：每个分量的初始有序列表为 [(x_lb, f_lb, 'lb'), (x_ub, f_ub, 'ub')]，默认按 x_i 升序排列（若初始下界x_lb < 上界x_ub，直接按此顺序即可）。
• 迭代新增点：每次得到一批迭代点后，找到对应分量的有序列表，用二分查找确定新点的插入位置，维持列表按x_i升序的规则。

3. 示例代码片段（Python） #

import bisect

# 模拟3个分量的初始上下界点
n_components = 3
initial_bounds = [
    [(1.0, 2.0), (5.0, 6.0)],   # f1(x1)的上下界
    [(0.5, 1.5), (3.0, 4.0)],   # f2(x2)的上下界
    [(2.0, 3.0), (7.0, 8.0)]    # f3(x3)的上下界
]

# 初始化整体数据结构：外层列表对应分量顺序，内层列表对应分量的有序点集
component_points = []
for lb, ub in initial_bounds:
    points = [(lb[0], lb[1], 'lb'), (ub[0], ub[1], 'ub')]
    component_points.append(points)

# 模拟第1次迭代得到的点：(分量索引, x_i, f_i(x_i))
iter1_points = [
    (1, 2.0, 3.0),  # 对应f2(x2)的迭代点
    (2, 4.0, 5.0)   # 对应f3(x3)的迭代点
]

# 插入迭代点到对应分量的有序列表
for comp_idx, x, f in iter1_points:
    target_list = component_points[comp_idx]
    # 用二分查找确定插入位置（按x值排序）
    insert_pos = bisect.bisect_left([p[0] for p in target_list], x)
    target_list.insert(insert_pos, (x, f, 'iter1'))

# 输出验证结果
for i, points in enumerate(component_points):
    print(f"分量f{i+1}(x{i+1})的有序点集：")
    for p in points:
        print(f"  x={p[0]}, f={p[1]}, 类型={p[2]}")

4. 方案优势 #

• 严格有序：外层列表保证分量顺序，内层有序列表保证单个分量的点按x_i升序排列，完全满足连续线段构建需求。
• 高效维护：二分查找插入的时间复杂度为O(log m)（m为单个分量的点数量），适配多次迭代的场景。
• 灵活扩展：新增迭代点时仅需操作对应分量的列表，不影响其他分量的数据。

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