AI 与机器学习2020arxiv.org
比 Quicksort 更强的神经程序员
Neural programmer better than Quicksort
进阶 · 约 25 分钟读完前置知识：排序算法基础、神经网络基础、程序合成/状态机概念
导读
论文提出一种「神经程序员」：用神经网络学习生成一组把程序状态映射到下一状态的函数，从而在排序任务上自动「合成」出算法，并按函数调用/基本操作次数与经典算法比较，声称在开销上优于 Quicksort 与插入排序。作者设想这类模型需要专门的神经逻辑单元硬件才能体现实际速度优势，且模型要针对数据分布进行调优。
HN 关注点：HN 读者争论的焦点是：这个「胜过 Quicksort」的比较口径是否公平（按状态转移/调用次数而非真实 CPU 时间），以及给模型喂入全局比较信息、依赖专用硬件是否让结论失去意义。
HN 评论精选
这几条评论里：质疑 2 补充 2
质疑对只从输入输出学出的程序缺乏信任，但认为「近似排序+收尾插入排序」的思路可能有用。
写出正确的代码真的很难。Java 的排序曾长期存在 bug 而没人发现（见链接论文），Java 的二分查找也一样。所以我很难信任一个只靠输入/输出训练的 ML 算法（我理解「神经程序归纳」就是如此）。那些 bug 之所以被触发，是因为写代码的人没想到溢出；而这个「神经程序员」对输入作了什么假设？我们永远不会知道。另一方面，如果已知数据分布，标准库排序确实可以改进（小整数用桶排序、小数组用排序网络等）。如果这东西能靠更强的模式匹配做到高效地「几乎排好序」，那我们最后再跑一遍插入排序就能用了。
ghj查看英文原文
It's really hard to write correct code. Sorting was broken in java and nobody noticed for a long time: http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf The same was true for java's binary search: https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html So I am not sure I will ever trust an ML algorithm trained on inputs/outputs only (which is what I think "neural program induction" means). The above bugs are only hit because the programmers who wrote it didn't think about overflow. What is this "neural programmer" assuming about their inputs? We'll never know. OTOH the standard library sort can be improved if you know the distribution of the numbers you're sorting (e.g., small numbers can bucket sort, small lists can use a sorting network, etc). If this thing can efficiently almost-correctly-sort because it's better at these types of pattern matching, we can just run a final pass of insertion sort to make it useful!
补充论文最后确实给出了完整可读的伪代码，所谓「快几个百分点」是靠这种状态机式程序实现的。
代码在论文最后一页，比 Quicksort 快几个百分点：随后贴出了 QUICKSORTAGENT 伪代码——它由 Function1（QuickSort）、Function2（Partition）两个子函数构成，通过记录上一步操作（prev）在 AssignVar、MoveVar、Swap、Return 等状态转移间推进，用 i、j 两个索引变量完成划分与递归返回。
xiphias2查看英文原文
The code (which is a few percent faster than quicksort) is on the last page: procedure QUICKSORTAGENT(input state) 2: Let i = 1, j = 2, l = 3, h = 4 3: if FunctionID = None then 4: return vh ← Function1(vl ← vl, vh ← vh) 5: else if FunctionID = 1 then . QuickSort 6: if vl < vh then 7: if prev = None then 8: return vi ← Function2(vl ← vl, vh ← vh) 9: else if prev = (vi ← Function2(vl ← vl, vh ← vh)) then 10: return AssignVar(j, i) 11: else if prev = AssignVar(j, i) then 12: return MoveVar(i, -1) 13: else if prev = MoveVar(i, -1) then 14: if vi > vl then 15: return vi ← Function1(vl ← vl, vh ← vi) 16: else 17: return MoveVar(j, +1) 18: end if 19: else if prev = (vi ← Function1(vl ← vl, vh ← vi)) t hen 20: return MoveVar(j, +1) 21: else if prev = MoveVar(j, +1) and vj < vh then 22: return vh ← Function1(vl ← vj , vh ← vh) 23: else 24: return Return(h) 25: end if 26: else 27: return Return(h) 28: end if 29: else . Function ID = 2, Partition 30: if prev = None then 31: return AssignVar(i, l) 32: else if prev = AssignVar(i, l) then 33: return AssignVar(j, l) 34: else if vj < vh then 35: if prev = Swap(i, j) then 36: return MoveVar(i, +1) 37: else if (prev = AssignVar(j, l) or prev = MoveVar(j, +1)) and A[vj ] < A[vh] then 38: if vi 6= vj then 39: return Swap(i, j) 40: else 41: return MoveVar(i, +1) 42: end if 43: else 44: return MoveVar(j, +1) 45: end if 46: else if prev = MoveVar(j, +1) then 47: return Swap(i, h) 48: else 49: return Return(i) 50: end if 51: end if 52: end procedure
质疑质疑比较口径不公平：把全局相邻比较信息免费提供给模型，再按调用次数「胜过」快排没有意义。
这项研究相当无聊，只是被花哨的措辞包装了。本质上他们生成把一种程序状态映射到另一种状态的函数，然后统计这些函数被调用的次数，拿去和快排等的函数调用次数比较。他们「作弊」的地方在于：每一步都把每个元素与相邻元素的比较结果喂给算法——如果这种输入是白送的，那意义何在？值得注意的是，流行的排序算法都不会在每一步查看整个输入来决定交换哪些元素，它们只依据局部信息；而论文为了实现这个原则，用了一小组与 n 无关的索引变量，并把 A[i] 与 A[i+1]、A[i-1] 的比较结果放进输入。
rightbyte查看英文原文
Quite dull research wrapped in fancy words. Essentially they generate functions that map a program state to another program state and counts those function calls and compares with e.g. the number of function calls in quick sort. They "cheat" by feeding how all elements compares the their neighbours at each step. Like, if you give the algorithm that input for free what's the point. Notably, none of the popular sorting algorithms decide which elements to swap by looking at the whole input at each execution step. On the contrary, the decisions are typically made based on local evidence only. ... We implement this principle for the sorting task by employing a small set of k(independent of n) index variables, and include in the input the information about how A[i] compares with A[i+ 1] and A[i−1]for each index variable i.
补充作者的局限说明：需要专用硬件且依赖调优，短期内无法取代快排。
根据论文自己列出的局限：1）它在现代 CPU 上跑得更慢，需要神经逻辑单元才能看到速度收益；2）模型需要针对数据精细调优才能达到最佳性能。所以它可能在某些场景下优于 Quicksort，但短期内不会取代它。
me551ah查看英文原文
According to the limitations stated in the doc. 1. It runs slower on modern CPUs and you need neural logic units to see the speed benefits 2. Model needs the be fined tuned to the data for best performance. While it may be better than quicksort in certain usecases it isn't going to replace it anytime soon.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2020Hacker News 讨论帖282 分 · 126 评
同领域还值得读
DeepSeek-R1：通过强化学习激励 LLM 的推理能力
DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via RL
研究如何用强化学习激励大语言模型的推理能力，提出 DeepSeek-R1，并探讨 RL 训练对模型推理表现的影响。
AI 与机器学习2025 · 1,351 分 · 1,056 评 · 引用 30进阶 · 约 80 分钟编辑精选1-bit LLM 时代：面向低成本计算的三值参数
The Era of 1-bit LLMs: ternary parameters for cost-effective computing
提出用三值参数 {-1, 0, 1} 替代 LLM 中的浮点权重，即所谓“1-bit LLM”。
AI 与机器学习2024 · 1,040 分 · 447 评 · 引用 19进阶 · 约 45 分钟编辑精选DeepSeek-V3.2：推进开放大语言模型的前沿
DeepSeek-v3.2: Pushing the frontier of open large language models
这是 DeepSeek-V3.2 的技术报告，延续了 DeepSeek 开源权重模型的路线，目标是让开放模型继续逼近甚至追平前沿闭源模型。
AI 与机器学习2025 · 982 分 · 465 评进阶 · 约 90 分钟编辑精选通过自我对弈与通用强化学习掌握国际象棋和将棋（AlphaZero）
Mastering Chess and Shogi by Self-Play with General Reinforcement Learning
DeepMind 的 AlphaZero 论文：用通用强化学习算法（自我博弈 + MCTS + 神经网络），从零开始仅数小时训练便在国际象棋和将棋上击败了世界顶级引擎 Stock…
AI 与机器学习2017 · 539 分 · 270 评 · 引用 13进阶 · 约 90 分钟编辑精选用强化学习发现更快的矩阵乘法算法
Discovering faster matrix multiplication algorithms with reinforcement learning
论文提出 AlphaTensor，用强化学习搜索矩阵乘法算法。
AI 与机器学习2022 · 518 分 · 111 评专业 · 约 90 分钟编辑精选