OmX 自适应排序优化实战：混合排序调度、加权成本度量与阈值调优全解

OmX 自适应排序优化实战：混合排序调度、加权成本度量与阈值调优全解

【免费下载链接】oh-my-codexOmX - Oh My codeX: Your codex is not alone. Add hooks, agent teams, HUDs, and so much more.项目地址: https://gitcode.com/GitHub_Trending/oh/oh-my-codex

导读：本文围绕 OmX（oh-my-codex）仓库中missions/adaptive-sort-optimization/这一 autoresearch 任务，完整讲解如何在确定性混合数据分布下优化自适应排序策略。你将掌握playground/adaptive_sort_demo/评测沙箱的加权成本模型（comparisons + 0.35 × moves）、hybrid_sort的四级调度逻辑与三个可调参数（insertion_threshold、run_detection_min、counting_span_limit），以及如何通过 evaluator 契约与score_improvement保留策略，在不破坏正确性的前提下提升评分。读完即可复现、修改并独立跑通该优化闭环。

一、任务定位：mission.md 说了什么

[mission.md](https://link.gitcode.com/i/33b0935eef134af1908e33719bdceb0c)全文非常精炼，只定义了四件事：目标、目标文件、成功标准。但它所指向的是一套完整可运行的算法工程实验环境，因此本文会以它为骨架，结合沙箱契约、评测脚本与实现代码展开。

任务核心一句话：在多个确定性的输入分布上优化自适应排序策略，并在所有基准用例上保持排序正确。

# Mission Optimize an adaptive sorting strategy across multiple deterministic input distributions. Goal: Improve the evaluator score for `playground/adaptive_sort_demo/` while preserving correct sorting across all benchmark cases. Primary targets: - playground/adaptive_sort_demo/config.json - playground/adaptive_sort_demo/sort_benchmark.py Success means: 1. the weighted cost score improves over the current kept baseline 2. correctness holds for every benchmark case 3. the strategy remains lightweight and deterministic

三条成功标准分别对应：

1. 加权成本分数必须优于当前保留基线（由 evaluator 的keep_policy: score_improvement裁决）；
2. 每个基准用例都必须输出正确排序（evaluate_algorithm中会对每个用例断言out == sorted(values)）；
3. 策略必须保持轻量与确定性（禁止引入随机化、外部依赖或大体积运行时产物）。

主攻目标只有两个文件：[config.json](https://link.gitcode.com/i/8300665fd4724ac793d078989b3d1ade)（参数调优面）与[sort_benchmark.py](https://link.gitcode.com/i/217572fff40e236ce37345b4b3e74889)（调度逻辑优化面）。这决定了任务性质是典型的算法工程（algorithm engineering）：不改数据集、不换环境，只优化"算法如何根据输入特征做决策"。

二、评测沙箱：加权成本模型与计分公式

2.1 成本怎么算：comparisons + 0.35 × moves

与传统的墙钟计时不同，本评测用确定性操作计数衡量算法代价，见 sort_benchmark.py：

@dataclass class Metrics: comparisons: int = 0 moves: int = 0 def score(self) -> float: return self.comparisons + 0.35 * self.moves

每次compare调用（两元素比较）计 1 次比较，每次move调用（元素搬运，含批量move(count)）计 1 次移动，最终成本为comparisons + 0.35 × moves。移动比比较便宜（系数 0.35），这是后续理解计数排序为何"划算"的关键前提。

Ops类把所有读写都纳入计量，因此纯 Python 层的执行效率不影响分数，分数完全由算法层面的操作序列决定，且完全可复现。

2.2 计分公式：score = 10000 / total_cost

Evaluator 脚本 eval-adaptive-sort-optimization.py 从基准脚本的 JSON 输出中取出total_cost，再换算为分数：

payload = json.loads(result.stdout) total_cost = float(payload['total_cost']) score = 10000.0 / total_cost print(json.dumps({'pass': total_cost > 0, 'score': score}))

也就是说：总分与加权总成本成反比，成本越低分数越高。基线（纯归并排序）与当前保留方案的差距可直接从项目文档中查到（详见第六节）。Evaluator 还会把基准脚本的 stdout/stderr 转发到自己的 stderr，便于排查；一旦基准进程非零退出，直接输出{'pass': False, 'score': 0.0}。

2.3 五个确定性分布、三种规模、六档权重

基准用例由build_cases()（sort_benchmark.py）构造，全部由线性同余式生成，无随机种子，任何机器上结果一致：

def build_cases() -> list[tuple[str, list[int], float]]: cases: list[tuple[str, list[int], float]] = [] sizes = [32, 64, 96] for n in sizes: cases.append((f'random-{n}', [((i * 37 + 11) % 101) for i in range(n)], 1.0)) cases.append((f'reverse-{n}', list(range(n, 0, -1)), 1.1)) cases.append((f'nearly-sorted-{n}', [i if i % 9 else max(0, i - 3) for i in range(n)], 1.2)) cases.append((f'duplicates-{n}', [((i * 7) % 8) for i in range(n)], 1.3)) cases.append((f'low-cardinality-{n}', [((i * 13 + 5) % 16) for i in range(n)], 1.15)) return cases

每个用例的加权成本为weight × ops.metrics.score()（sort_benchmark.py），全部累加为total_cost。权重设计很有讲究：重复数据（1.3）与近有序数据（1.2）权重最高，暗示计数排序与插入排序在低基数和长递增段上的收益会被放大；随机数据权重最低，是纯比较类排序的主战场。

三、hybrid_sort：四级调度逻辑与三个参数

3.1 当前保留的混合策略实现

核心调度函数为hybrid_sort（sort_benchmark.py）：

def hybrid_sort(values: list[int], config: dict, ops: Ops) -> list[int]: params = dict(config.get('params', {})) insertion_threshold = int(params.get('insertion_threshold', 12)) run_detection_min = int(params.get('run_detection_min', 10)) counting_span_limit = int(params.get('counting_span_limit', 128)) if len(values) <= insertion_threshold: return insertion_sort(values, ops) if values: min_value = min(values) max_value = max(values) if max_value - min_value <= counting_span_limit: return counting_sort(values, min_value, max_value, ops) if longest_non_decreasing_run(values) >= run_detection_min: return insertion_sort(values, ops) return merge_sort(values, ops)

调度顺序（先判定先执行）：

1. 规模闸门：n <= insertion_threshold→ 插入排序；
2. 值域闸门：max - min <= counting_span_limit→ 计数排序（注意用的是观测值跨度，而非全值域，这是本任务最优解的关键改进）；
3. 结构闸门：最长非递减段长度>= run_detection_min→ 插入排序（近有序数据不必归并）；
4. 兜底：以上都不满足 → 归并排序。

3.2 三个参数的作用域与默认值

参数在 config.json 中显式给出，缺失时由代码回退到默认值：

三个参数彼此独立、组合生效：先看规模，再看值域，再看局部有序性。这恰好覆盖了五种基准分布里的四种——random 走归并兜底，duplicates/low-cardinality 走计数，nearly-sorted 走长段插入，reverse 由于既无长非递减段、值域又大（n=96 时跨度 95 ≤ 128？）——注意reverse-96 的跨度是 95，仍 ≤ 128，因此实际走计数排序，这是当前配置下的一个可优化观察点。

3.3 底层三个子算法的成本画像

• 插入排序（sort_benchmark.py）：比较数 ≈ n²/2 量级，但移动同样为 O(n²)。在近有序/长段数据上，比较与移动都趋近 O(n)，是"结构闸门"下性价比最高的选择；代价是它对每个元素至少执行move()（取 key + 写回），常数较大。
• 归并排序（sort_benchmark.py）：比较与移动均稳定为 O(n log n)，且批量ops.move(len(left)-i)让尾部搬运只计一次。它是无结构随机数据的兜底选项，也是基线算法。
• 计数排序（sort_benchmark.py）：全程零比较，但会为跨度k = max−min+1的计数数组一次性支付ops.move(k)，随后每个元素一次递增计数、展开时按计数批量移动。总移动 ≈ k + 2n。因为移动系数只有 0.35，只要 k 受控（≤ counting_span_limit），计数排序在低基数/重复分布上极具优势。

四、Evaluator 契约与沙箱边界

4.1 sandbox.md 的操作许可

[sandbox.md](https://link.gitcode.com/i/70b7d6defefb4f8b8a5087e55160f3f6)的 front-matter 声明了评测契约：

evaluator: command: python3 scripts/eval-adaptive-sort-optimization.py format: json keep_policy: score_improvement

• command：指向本任务专属的 evaluator 入口（对应 src/scripts/eval/eval-adaptive-sort-optimization.py），输出 JSON；
• format: json：supervisor 按 JSON 解析score字段；
• keep_policy: score_improvement：只有分数严格优于当前保留基线，候选才会被保留（kept），否则discard。

4.2 允许改什么、禁止碰什么

任务被限定在playground/adaptive_sort_demo/之内，边界划分非常明确：

这四条边界本质上是把任务界定为纯算法工程：分数只能来自调度决策与参数组合的改进，不能通过改数据集、加依赖、或让评测"变简单"来作弊。

五、正确性校验与运行方式

5.1 正确性如何被强制保证

无论调度逻辑如何修改，evaluate_algorithm都会对每个用例强制校验（sort_benchmark.py）：

out = algorithm(values, config, ops) if out != sorted(values): raise AssertionError(f'incorrect sort output for {name}')

一旦任何用例输出错误，整个评估直接抛异常终止，evaluator 返回{'pass': False, 'score': 0.0}。因此"优化"永远被约束在保持全用例正确的硬前提下。

5.2 直接运行基准与评测

在仓库根目录下可独立复现（main()会打印 JSON 结果）：

# 直接运行基准脚本，查看各用例加权成本与总成本 python3 playground/adaptive_sort_demo/sort_benchmark.py # 运行 evaluator，得到 {pass, score} python3 src/scripts/eval/eval-adaptive-sort-optimization.py

若要以完整 autoresearch 闭环运行，可参照 missions/README.md 与 playground/README.md 中展示的启动模式（例如omx autoresearch missions/<mission>），对本任务即为：

omx autoresearch missions/adaptive-sort-optimization

运行结束后可在.omx/logs/autoresearch/<run-id>/下查看manifest.json、candidate.json、iteration-ledger.json，观察 supervisor 的 keep/discard/stop 决策。

六、已知最优结果与优化方向参考

6.1 项目文档记载的成绩

playground/README.md 的展示矩阵明确记录了本任务的结果：

Adaptive sorting optimization | Baseline | Kept / best documented result | Delta2.1198297352756628→9.411498969440865|+7.291669234165202

即基线（纯归并排序）分数约 2.12，当前保留方案分数约 9.41，提升约 3.44 倍；按score = 10000 / total_cost反推，加权总成本从约 4717 降到约 1062。README 同时注明了关键改进手段："by switching counting sort to the observed value span"——即把计数排序的跨度判定从"全值域"改为"观测值跨度（max−min）"，这正是 sort_benchmark.py 中min(values)/max(values)逻辑的来源。这一事实同时印证了：调度启发式的小改动，能在混合分布上带来数量级的分数跃迁。

6.2 可继续探索的调优方向（结合代码推断）

从源码结构可以推断出若干后续优化切入点，均属 sandbox 许可范围内：

• 参数扫描：insertion_threshold、run_detection_min、counting_span_limit三者存在耦合（如 reverse-96 的值域跨度恰为 95，收紧counting_span_limit会把它改判为归并排序），可做确定性网格扫描找更优组合；
• 结构启发式增强：longest_non_decreasing_run（sort_benchmark.py）目前以固定长度 10 判定近有序，可考虑按n比例（如n/4）或结合逆序对计数动态判定；
• 计数排序开销权衡：计数数组的ops.move(k)是固定成本，值域接近 128 时是否仍优于归并，取决于重复密度，可作为counting_span_limit之外的二级判定依据。

七、小结：一次完整的算法工程实验闭环

missions/adaptive-sort-optimization/提供的是一个麻雀虽小、五脏俱全的算法工程实验环境：

• 任务定义（mission.md）：目标、主攻文件、三条成功标准；
• 操作边界（sandbox.md）：evaluator 命令、JSON 契约、score_improvement保留策略、允许/禁止清单；
• 可运行基准（playground/adaptive_sort_demo/sort_benchmark.py）：加权成本模型、五分布十五用例、四级混合调度；
• 参数面（playground/adaptive_sort_demo/config.json）：三个阈值参数即优化主战场；
• 评分器（src/scripts/eval/eval-adaptive-sort-optimization.py）：10000 / total_cost换算分数，pass由正确性兜底。

只要遵守"保持确定性、不破坏正确性、不逃逸到沙箱之外"三条铁律，任何阈值组合与调度启发式都可以在这个闭环里快速验证。它既是 OmX autoresearch 能力的一个展示样例，也是一份可直接复用的确定性排序基准与优化工作流模板。

【免费下载链接】oh-my-codexOmX - Oh My codeX: Your codex is not alone. Add hooks, agent teams, HUDs, and so much more.项目地址: https://gitcode.com/GitHub_Trending/oh/oh-my-codex