算法与计算机科学josephg.com
更快的 CRDT：一次优化冒险
Faster CRDTs: An Adventure in Optimization
2021 — 2024，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
作者 Joseph Gentle（前 Wave 协作编辑开发者）通过一系列优化技巧（如跳过列表、压缩编码、记忆上次插入位置等）将 CRDT 的运行速度提升了数千倍，并详细记录了整个优化过程。文章还顺带批评了一篇声称 CRDT 性能不佳的学术论文，指出其基准测试方法存在严重问题。
为什么经久不衰：它既是 CRDT 优化的实战教程，也是一篇关于如何做严谨基准测试的方法论示范，多年后仍是协作编辑领域的必读参考。
HN 评论精选
资深 CRDT 开发者印证了文中技巧早已存在，并认为 CRDT 性能本就足够、那篇学术论文不足为凭
大约十年前，我用正则表达式和 Unicode 字符串作为存储实现了 Causal Tree CRDT（即 RGA、带时间戳的插入树），后来基于这套代码为 Yandex 做了协作编辑器。它用到了文中描述的许多技巧，甚至包括记住上次插入位置这个优化。所以看到这些被重新发现，我非常高兴。代码在 GitHub 上，我还写了篇文章，可能不太好读就不贴链接了。最近我通过引入 Chronofold 数据结构大幅改进了 CT。至于这篇基准测试文章，我在学术界待过很多年，很熟悉这种内容质量问题——我不把它当回事。CRDT 已经够快了，这不是问题。
gritzko查看英文原文
About a decade ago, I implemented the Causal Tree CRDT (aka RGA, Timestamped Insertion Tree) in regular expressions using a Unicode string as a storage. Later we made a collaborative editor for Yandex based on that code. It used many of the tricks as described in the text, even the optimization where you remember the last insertion point. So I am terribly glad it all gets rediscovered. The code is on GitHub [1] There is also an article which might be a tough reading, so no link. Recently I greatly improved CTs by introducing the Chronofold data structure [2]. Regarding that benchmark article, I spent many years in academia, so the quality of content problem is familiar to me. In other words, I don't take such articles seriously. CRDTs are fast enough, that is not a concern. [1]: https://github.com/gritzko/citrea-model [2]: https://arxiv.org/abs/2002.09511
质疑纯基准测试类论文的同行评审标准，认为公平的算法对比几乎不可能做到
从元层面说，有没有人觉得一篇只是对不同算法做基准测试的同行评审论文，应该在接收前经过非常严格的审查？写好基准测试很难，而且高度依赖上下文，除非你是所有相关算法的专家，否则几乎不可能写出公平的算法（或数据结构）对比。
vanderZwan查看英文原文
On a meta-level, does anyone else think that the whole idea of writing a peer reviewed paper that is just a benchmark of different algorithms should be really rigorously reviewed before being accepted? Writing good benchmarks is hard, and so highly contextual that writing fair comparisons beteen algorithms (or data structures) is almost impossible unless you're an expert in all of the algorithms involved.
建议有异议时直接邮件联系论文作者，作者通常乐于收到反馈
顺便说一句，作为发表过学术论文的人，如果你对某篇论文有疑问或意见，别犹豫，直接给作者发邮件（邮箱都在论文上；尤其联系第一作者，因为工作通常是他们做的）。有人读我们的工作我们很高兴，至少我自己会想知道是否有人发现了论文中的问题。
JW_00000查看英文原文
By the way, as someone who has published academic papers, if you're ever bothered about a paper or have some comments, don't hesitate to mail the authors. (Their e-mail addresses are always on the paper; especially target the first author because they have normally done the work.) We are happy to hear when someone has read our work and I at least would've liked to have known if someone found a problem with my papers.
作者本人现身评论区，表示愿意答疑
大家好，HN！我是文章作者。等澳大利亚这边早上到了，我很乐意回答问题并修正错别字。
josephg查看英文原文
Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选