加载失败
作者在 C99 中实现并开源了来源于 STOC 2025 最佳论文的 DMMSY 算法，目标是在稀疏有向图的单源最短路径（SSSP）问题上将复杂度降至 O(m log^{2/3} n)。实现宣称采用 cache-optimized CSR、零分配预分配工作区与递归子问题分解，并在 25–100 万到 100 万节点规模上报告了极高的加速（20,000×，核心约 800ns）。讨论者基于算法渐近分析、基准方法学和工程实现细节（如堆分配、基线实现来源）展开质疑，认为现实规模的常数因子与基准设计比理论因子更能左右实际性能。另有评论把 2/3 型分数指数与 GNFS 等其他领域的分数指数作类比，表现出对潜在理论联系的好奇，同时有人要求披露 AI 辅助程度与提供可重复的基准说明。
作者在 C99 中实现了 STOC 2025 最佳论文提出的 DMMSY 算法并开源，声称在稀疏有向图的单源最短路径（SSSP）问题上达到 O(m log^{2/3} n) 的复杂度。实现细节包括 cache-optimized CSR 布局以提升空间局部性、zero-allocation 设计配合预分配工作区，以及以递归子问题分解替代全局 priority queues 来减少结构性开销。作者在 25 万到 100 万节点规模的图上报告了 20,000× 以上的加速，且宣称 DMMSY 核心在 1M 节点图上运行约 800ns。项目自述强调以正确性为首并征求对边界情形、分解策略与 cache-oblivious 优化的反馈。
若干评论对这类基础性推进表示热情支持，认为推动算法/实现能改进系统底层并带来下游影响。评论者表达对未来研究和实现机会的向往，并鼓励作者继续推进类似工作。另有实用建议建议下次在标题加 'Show HN' 以提高在 Hacker News 上的曝光度与讨论热度，且有评论对投稿者表示感谢。
多个评论直接质疑报告的 20,000× 加速与 ~800ns 数字是否合理，指出从渐近复杂度角度看 O(log^{2/3} n) 相对 O(log n) 在常见规模下改进有限：在 n=1e6 时两者比值大约 2.7×，仅靠对数因子要达到 10× 需不现实的 n≈2^{1000} 级别。评论提出更可能的解释是基准比较不公平，例如被对比的 Dijkstra 实现可能存在频繁堆分配或其它低效实现细节，从而夸大加速比。有人补充说明真实应用场景下（如按需生成的搜索图或棋局搜索）工作集和生成策略不同，基准设计必须明确这些假设才能判断结果可信度。
有评论注意到复杂度中出现的分数指数（如 2/3）并非孤立现象，提出在其他领域也见到类似分数指数（例如整数分解的 General Number Field Sieve，GNFS，涉及 1/3 型指数的复杂度表达）。评论者将这种跨领域重复出现的分数指数比作 'monstrous moonshine' 式的神秘模式，怀疑是否存在深层数学结构把不同问题的复杂度联系起来。这种类比更多是理论好奇与启发式联想，评论建议关注是否存在真正的数学或结构性共性而非表面巧合。
评论中有人以审稿人视角要求作者披露实现过程中 AI（如 Claude）的具体使用情况与开发流程，并质疑文档与可重复性。提出应与成熟库或广泛接受的实现做对比，而非只对比作者自写的 Dijkstra，以排除实现细节（如堆分配、内存布局）带来的偏差。还有人指出仓库的 README 和 HTML 图表风格、代码注释体现出 AI 生成的典型痕迹，认为这些工程细节会影响对结果可信度的判断并请求更严谨的基准说明与复现指导。
DMMSY: 来自 STOC 2025 的最佳论文所提出的 SSSP 算法核心名，宣称在稀疏有向图上实现 O(m log^{2/3} n) 时间复杂度，开源实现以该名命名。
CSR（Compressed Sparse Row）: 一种稀疏图的紧凑邻接表示法，将边按顶点连续存储以节省空间并改善缓存局部性；实现中提到经过 cache-optimized 的 CSR 布局以降低内存延迟。
SSSP（single-source shortest path，单源最短路径）: 图算法问题：从单一源点求到所有顶点的最短路径或距离；Dijkstra 是经典解法，长期复杂度分析与实现优化是该讨论核心。
STOC（Symposium on Theory of Computing）: 计算理论领域的顶级学术会议，代表理论突破与复杂度新结果；该算法来自 STOC 2025 并获最佳论文。
cache-oblivious（缓存无关算法）: 一种不依赖具体缓存参数（如缓存行大小或层级）的算法设计范式，目标是在各种层次化内存中自动获得良好局部性，评论中被建议作为可能的优化方向。
priority queue（优先队列）: 维护候选最短距离项的数据结构，Dijkstra 依赖全局 priority queue；作者实现宣称用递归子问题分解代替全局优先队列以降低开销。
General Number Field Sieve (GNFS): 目前对大整数因子分解效率最高的经典算法之一，其复杂度表达含有 1/3 型的分数指数，评论者以此作为与 SSSP 中 2/3 指数的类比以探讨潜在联系。
sorting barrier（排序壁垒）: 指长期认为稀疏 SSSP 的复杂度受排序下界影响（如 Dijkstra 的 n log n 项），评论称新算法宣称突破了这 65 年的限制。