计数,听起来简单,却在实际执行很有难度。
想象一下,你被送到一片原始热带雨林,进行野生动物普查。每当看到一只动物,拍一张照片。
数码相机只是记录追踪动物总数,但你对独特动物的数量感兴趣,却没有统计。
那么,若想获取这一独特动物数量,最好的方法是什么?
这时,你一定会说,从现在开始计数,最后再从照片中将每一种新物种与名单进行比较。
然而,这种常见的计数方法,有时并不适用于高达数十亿条目的信息量。
来自印度统计研究所、UNL、新加坡国立大学的计算机科学家提出了一种新算法——CVM。
它可以近似计算长列表中,不同条目的的数量,而且只需要记住少量条目就可实现。
论文地址:https://arxiv.org/pdf/2301.10191
这一算法适用于任何一次出现一个条目的清单,比如演讲中的文字、传送带上的商品,或州际公路上的汽车。
CVM算法是以三位作者首字母命名,在解决「不同元素问题」上取得的一个重大进展。
而这一问题,长期困扰计算机科学家40多年。
它要求有一种高效的方法来监控一个元素流(其总数可能超过可用内存),并估算出其中独特元素的数量。
那么,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表示,「这是一个很好的例子,说明即使是非常基础和被广泛研究过的问题,有时也可能存在简单但并不明显的解决方案仍待被发现」。
以上是开创性CVM算法破解40多年计数难题!计算机科学家掷硬币算出「哈姆雷特」独特单词的详细内容。更多信息请关注PHP中文网其他相关文章!