科学非常适合创新和改善我们的生活，但让我们面对现实吧：有些事情我们已经失望了。例如，您不会期望我们可以改进像……计数之类的东西。
因此，一群计算机科学家做到了这一点，这可能令人惊讶：找到了一种新的方法来解决一个数十年的问题，该问题询问它看起来是一个非常简单的问题 - 我面前有多少个不同的事情？
这是一个比您想象的要困难的问题，也是一个更聪明的解决方案。
独特的元素问题
计算机可能非常聪明，但是它们也可能非常……不聪明。只要看看AI聊天机器人最近的爆炸式爆炸，以便证明这一点：他们是擅长于聪明，但是请“ em”进行测试可能只是找到你自己废话的Ouroboros。
有时候，对人类而言，这似乎几乎是简单的事情，造成了最大的麻烦。以计数为例 - 具体来说，计算不同的对象。对我们来说，这很容易：我们查看对象的集合，我们的大脑只是自动为我们分类。我们几乎不必为此努力。
另一方面，对于计算机来说，这是一个基本且数十年的问题。而且，这确实需要回答，因为它在现代世界中的应用程序涵盖了网络流量分析的所有内容 - 想想在任何给定时间登录多少人，可以欺诈检测，生物信息学，文本分析等等。
现在，显然，我们已经能够做一段时间了，这是因为这个计数问题（正确地称为独特的元素问题）确实有答案。他们不是很好。
“早期已知的算法都是'基于哈希的'，该算法的质量取决于算法选择的哈希功能的质量，”内布拉斯加州大学 - 莱肯大学计算学院的教授Vinodchandran Variyam解释说。陈述去年。
但是，他与印度统计研究所的同事Sourav Chakraborty和多伦多大学的Kuldeep Meel一起，发现了一种大大简化了这个问题的方法：“新算法仅采用抽样策略，并且可以使用基本技术来完成质量分析。”
它如何工作？
由于为了纪念其发明者而命名了CVM算法，因此新方法大大降低了记忆要求 - 这是现代大数据的重要优势 - 它使用概率理论的整洁技巧来做到这一点。为了说明这个概念，请考虑Variyam及其同事研究的示例，以及最近的文章多少杂志：想象一下，您正在计算莎士比亚的独特单词数量村庄，但是您只有足够的内存可以存储100个单词。
首先，您会做一个明显的事情：您记录遇到的前100个独特单词。您现在已经脱空了 - 因此，您要拿一枚硬币并将其翻转为每个单词。头，它留下来；尾巴，你忘了它。
在此过程结束时，您的列表中大约有50个独特的单词。您从以前重新启动该过程 - 但是这次，如果您已经在列表中介绍了一个单词，请再次翻转硬币以查看是否删除它。到达100个单词后，您将再次浏览列表，为每个单词翻转硬币，然后按照提示进行删除或保留它。
在第二回合中，情况更加复杂：您不是一个人在列表中保留一个单词，而是连续需要两个人 - 其他任何东西，并且被删除。同样，在第三轮中，您需要连续三个头才能留下来。第四轮将连续四个，依此类推，直到到达哈姆雷特的尽头。
疯狂中有方法 - 这也是一种聪明的方法。通过这样的文本，您确保列表中的每个单词都具有在那里的概率相同的可能性：1/2k， 在哪里k是您必须在列表中工作的次数。因此，假设您花了六回合才能到达哈姆雷特的尽头，而您列出了61个不同的单词：然后，您可以将61倍乘以26要估计单词数量。
We'll save you opening your calculator app: the answer is 3,904 – and according to Variyam and co, the actual answer is 3,967 (yes, they counted.) If you have a memory that can store more than 100 words, the accuracy goes up further: with the ability to store 1,000 words, the algorithm estimates the answer as 3,964 – barely a rounding error already – and “of course,” Variyam told Quanta, “if the [内存]非常大，以至于它适合所有单词，然后我们可以获得100％的准确性。”
一种简单的方法
因此，这是有效的 - 但是使算法更加有趣的是它的简单性。 “新算法非常简单，易于实施，”阿默斯特马萨诸塞大学信息与计算机科学学院的教授安德鲁·麦格雷戈（Andrew McGregor）告诉Quanta。 “如果这成为[不同的元素]问题在实践中解决的默认方式，我不会感到惊讶。”
的确，自2023年1月发布以来，该算法引起了许多其他计算机科学家的关注和钦佩。这意味着，虽然详细说明算法的论文尚未 在官方意义上进行了同行评审，同龄人肯定已经对其进行了审查。确实，唐纳德·诺斯（Donald Knuth）计算机编程的艺术和所谓的“算法分析之父”赞美算法的论文早在2023年5月：“自从我看到它以来，我一直无法抗拒试图向我遇到的每个人解释这些想法，”他评论道。
同时，Chakraborty，Variyam和Meel在内的各种团队都花在了去年的调查和微调算法上。 Variyam说，有些人已经在他们的计算机科学课程中进行教学。
他说：“我们认为，这将是一种主流算法，该算法是在一般和概率算法的第一个计算机科学课程中教授的。”诺斯同意：“这非常适合教授正在学习计算机科学基础知识的学生，”他在五月论文中写道。 “我很确定这样的事情最终会成为标准的教科书主题。”
那么，如此突破性的算法逃避了这么长时间如何呢？根据Variyam的说法，它听起来不太可能。
他说：“令人惊讶的是，这种简单的算法尚未较早发现。” “在科学中并不少见，几年来简单地错过了。”
该论文发布在arxiv并出现在30号会议录中Th年度欧洲算法研讨会（ESA 2022）。
