科学家发现了一种新的计数方法（实际上非常重要）

这对本科生来说很简单，但直到现在还没有人注意到。

“自从我看到它[……]我就忍不住试图向我遇到的几乎每个人解释这些想法，”唐纳德·高德纳 (Donald Knuth) 写道。

图片来源：Ilya Lukichev/Shutterstock.com

科学对于创新和改善我们的生活非常有用，但让我们面对现实：有些事情我们几乎已经习以为常了。例如，你不会期望我们可以改进诸如计数之类的事情。

因此，一群计算机科学家所做的事情可能会让人感到惊讶：找到了一种新方法来解决一个几十年前的问题，这个问题从表面上看似乎是一个非常简单的问题——有多少个不同的问题？东西就在我面前吗？

这是一个比您想象的更难的问题，也是一个更聪明的解决方案。

不同元素问题

计算机可以非常聪明，但它们也可以非常非常……不聪明。只要看看最近人工智能聊天机器人的爆炸式增长就可以找到证据：它们听起来很聪明，但如果将它们放在测试中，你可能会发现自己陷入了废话中的衔尾蛇之中。

有时，对人类来说看似简单得可笑的事情却造成了最大的麻烦。以计数为例，具体来说，就是计数不同的物体。对我们来说，这很简单：我们查看对象的集合，我们的大脑会自动将它们分类为我们的组。我们几乎不需要为此付出努力。

另一方面，对于计算机来说，这是一个已有数十年历史的基本问题。这是一个真正需要回答的问题，因为它在现代世界的应用涵盖了从网络流量分析（想想 Facebook 或 Twitter 监控在任何给定时间有多少人登录）到欺诈检测、生物信息学、文本分析等方方面面。 ， 以及更多。

现在，显然，我们已经能够做这些事情一段时间了，那是因为这个计数问题（正确地称为“不同元素问题”）确实有答案。他们只是不是很好。 

“早期已知的算法都是‘基于哈希的’，算法的质量取决于算法选择的哈希函数的质量，”内布拉斯加大学林肯分校计算学院教授 Vinodchandran Variyam 在最后的一份声明中解释道。年。 

但是，他与印度统计研究所的同事 Sourav Chakraborty 和多伦多大学的 Kuldeep Meel 一起发现了一种大大简化问题的方法：“新算法仅使用采样策略，并且可以使用基本技术来完成质量分析。 ”

它是如何工作的？

这种新方法被命名为 CVM 算法以纪念其发明者，它大大减少了内存需求——这是现代大数据时代的一个重要优势——并且它使用了概率论的巧妙技巧来实现这一点。为了说明这个概念，请考虑 Variyam 和他的同事研究的示例，以及 Quanta 杂志最近的一篇文章：假设您正在计算莎士比亚的哈姆雷特中唯一单词的数量，但您只有足够的内存一次存储 100 个单词。 

首先，您要做的事情很明显：记录您遇到的前 100 个独特单词。你现在已经没有空间了——所以你拿起一枚硬币，然后为每个单词翻转它。头，它留下来；尾巴，你忘了吧。

在此过程结束时，您的列表中将包含大约 50 个独特的单词。你从之前开始重新启动这个过程——但是这一次，如果你遇到一个已经在列表中的单词，你可以再次掷硬币，看看是否要删除它。一旦达到 100 个单词，您将再次浏览列表，为每个单词掷硬币，然后根据提示删除或保留它。

在第二轮中，事情稍微复杂一点：你需要连续两个头来保存列表中的单词，而不是用一个头来保存单词 - 其他任何东西都会被删除。同样，在第三轮中，你需要连续获得三个正面才能保留；第四轮需要连续四个，依此类推，直到你到达《哈姆雷特》的结尾。

疯狂中也有方法——而且也是一种聪明的方法。通过像这样处理文本，您可以确保列表中的每个单词都有相同的出现概率：1/2k，其中 k 是您必须完成列表的次数。因此，假设您花了 6 轮才读到《哈姆雷特》的结尾，并且剩下 61 个不同单词的列表：然后您可以将 61 乘以 26 来估计字数。

我们将省去您打开计算器应用程序的麻烦：答案是 3,904 – 根据 Variyam 和 co 的说法，实际答案是 3,967（是的，他们计算过。）如果您的内存可以存储超过 100 个单词，那么准确度就会下降更进一步：由于能够存储 1,000 个单词，该算法估计答案为 3,964——几乎没有舍入误差——“当然，”Variyam 告诉 Quanta，“如果 [内存] 足够大，可以容纳所有单词，那么我们可以获得 100% 的准确率。 ”

简单的方法

所以，它是有效的——但让该算法更有趣的是它的简单性。马萨诸塞大学阿默斯特分校信息与计算机科学学院教授安德鲁·麦格雷戈 (Andrew McGregor) 告诉广达：“新算法非常简单且易于实现。” “如果这成为实践中处理[不同元素]问题的默认方式，我不会感到惊讶。 ”

事实上，自 2023 年 1 月发布以来（除非期间出现一些小问题和错误），该算法已经吸引了许多其他计算机科学家的关注和钦佩。这意味着，虽然详细介绍该算法的论文尚未经过官方意义上的同行评审，但它肯定已经经过同行评审。事实上，计算机编程艺术一书的作者、所谓的“算法分析之父”Donald Knuth 早在 2023 年 5 月就写了一篇赞扬该算法的论文：“自从我看到它[……]我一直无法抗拒地试图向我遇到的几乎每个人解释这些想法，”他评论道。

与此同时，包括 Chakraborty、Variyam 和 Meel 在内的各个团队在过去的一年里一直在研究和微调该算法。 Variyam 说，有些人已经在计算机科学课程中教授它。

他说：“我们相信，这将成为第一门关于一般算法，特别是概率算法的计算机科学课程中教授的主流算法。”高德纳对此表示同意：“它非常适合教授正在学习计算机科学基础知识的学生，”他在五月份的论文中写道。 “我非常确定这样的事情最终将成为标准教科书主题。 ”

那么，这样一个突破性的算法为何这么长时间都没有引起人们的注意呢？根据 Variyam 的说法，这并不像听起来那么不可能。

“令人惊讶的是，这种简单的算法没有更早被发现，”他说。 “在科学界，多年来忽视简单性的情况并不少见。 ”

该论文已发布在 ArXiv 上，并发表在第 30 届欧洲算法研讨会论文集 (ESA 2022) 中。