新智元报道
编辑：桃子
预估一个数组中不重复数字的个数，最简便的方法是什么？计算机科学家们提出了一种全新 CVM 算法，通过利用随机性，预估出数据流中大量不同的对象。
计数，听起来简单，却在实际执行很有难度。
想象一下，你被送到一片原始热带雨林，进行野生动物普查。每当看到一只动物，拍一张照片。
数码相机只是记录追踪动物总数，但你对独特动物的数量感兴趣，却没有统计。
那么，若想获取这一独特动物数量，最好的方法是什么？
这时，你一定会说，从现在开始计数，最后再从照片中将每一种新物种与名单进行比较。
然而，这种常见的计数方法，有时并不适用于高达数十亿条目的信息量。
来自印度统计研究所、UNL、新加坡国立大学的计算机科学家提出了一种新算法——CVM。
它可以近似计算长列表中，不同条目的的数量，而且只需要记住少量条目就可实现。
论文地址：https://arxiv.org/pdf/2301.10191
这一算法适用于任何一次出现一个条目的清单，比如演讲中的文字、传送带上的商品，或州际公路上的汽车。
CVM 算法是以三位作者首字母命名，在解决「不同元素问题」上取得的一个重大进展。
而这一问题，长期困扰计算机科学家 40 多年。
它要求有一种高效的方法来监控一个元素流（其总数可能超过可用内存），并估算出其中独特元素的数量。
那么，CVM 算法究竟是如何解决问题的？
开创性 CVM 算法，秘诀在于「随机化」
假设你在听《哈姆雷特》有声读物。
这部戏剧共有 30557 个字，有多少是不同的？
为了找到答案，你可以边听边暂停，按字母顺序写下每个单词，然后跳过清单上已有的单词，最后，只需要数一下清单上每个单词数。
这种方法是可行的，但太考验一个人的「记忆量」了。
研究者 Vinodchandran Variyam 表示，「在典型的数据流情况中，可能会有数百万个项目需要追踪。你可能不想把所有的信息都存储起来。
这就是，云服务器算法可以提供更简单方法的地方」。
诀窍，就在于「随机化」。
Vinodchandran Variyam 帮助发明了一种估算数据流中不同元素数量的 CVM 算法
「哈姆雷特」有多少个独特词？掷硬币大挑战
再回到《哈姆雷特》，假设你的「有效内存」只能容纳 100 个单词。
一旦音频开始播放，你记下听到的前 100 个单词，并跳过任何重复的单词。
当完成 100 个单词记录后，剩下的就是为每个单词掷硬币——正面，保留单词。若为反面，将其删除。
在这一轮初选之后，你将留下大约 50 个不同的单词。
现在，你继续团队所说的第一轮游戏 Round 1，继续阅读《哈姆雷特》，添加新单词。
如果你再次遇到一个已经在清单上的单词，再次掷硬币决定，一直到你的内存白板中，有 100 个单词。
然后，根据 100 次掷硬币的结果，再次随机删除大约一半的单词。Round 1 到此结束。
接下来，进入第二轮 Round 2。
和第一轮一样，我们要增加一个单词的难度——当你遇到一个重复的单词时，再次掷硬币。
条件是，如果是反面，就像之前一样删除它。但如果是正面，就再掷一次硬币。只有当第二次出现正面时，才保留这个单词。
一旦内存白板写满，结束这一轮，然后根据 100 次抛掷结果，再次删除大约一半的单词。
在第三轮 Round 3 中，你需要连续三次掷硬币正面，才能保留一个单词。
在第四轮中，连续四次正面保留一个单词，以此类推。
最终，在第k轮，你会听完整部《哈姆雷特》戏剧。
这个练习的重点是，确保每个单词都有相同的出现概率：1/2 (k) 。
假设，如果在《哈姆雷特》音频结束时，你的列表中有 61 个单词，用了六轮的时间完成。
你可以用 61 除以概率1/2 (6) 来估计不同单词的数量——最终在这个游戏中的结果是 3904 个。
算法精度与内存量成正比
研究人员 Chakraborty、Variyam 和 Meel 从数学上证明了 CVM 算法的精确度与内存量的大小成比例。
而《哈姆雷特》恰好有 3967 个独特的单词。（通过普通的计数方法）
在使用 100 个单词内存的实验中，5 轮实验结果的平均估计为 3955 个单词。
在 1000 个单词内存忆量下，平均提高到 3964 个。
Variyam 表示，「如果（内存量）大到可以容纳所有单词，那么我们就可以达到 100% 的准确率」。
哈佛大学 William Kuszmau 表示，「这是一个很好的例子，说明即使是非常基础和被广泛研究过的问题，有时也可能存在简单但并不明显的解决方案仍待被发现」。
参考资料：
https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/
