這個新方法簡單到連本科生都能理解，但一直沒有人發現它。
科學在創新和改善我們的生活方面很棒，但有些東西我們似乎已經掌握得很牢了。比如，你不會想到我們還能改進像計數這樣簡單的事情。
所以，當一群計算機科學家找到了一種解決一個看似簡單但已有幾十年歷史的問題的新方法時，可能會讓你感到驚訝——這個問題就是：我面前有多少個不同的東西？
這個問題比你想像的要難，而解決方案也比你想像的要聰明得多。
不同元素問題
計算機可以非常聰明，但有時也非常……不聰明。看看最近湧現的AI聊天機械人就知道了：它們聽起來很聰明，但一測試，你可能會發現它們滿嘴跑火車。
有時候，對人類來說幾乎可笑簡單的事情，對計算機卻是最大的難題。比如計數——特別是數不同的物體。對我們來說，這很簡單：我們看看一堆物體，大腦自動把它們分成不同的組，幾乎不費什麼力氣。
但對計算機來說，這是一個基本而且已有幾十年歷史的問題。而且這個問題必須解決，因為它在現代世界中的應用非常廣泛，從網絡流量分析(比如Facebook或Twitter監測有多少人在線)到欺詐檢測、生物信息學、文本分析等等。
顯然，我們已經有了這些問題的解決方案，但它們並不完美。
「以前已知的算法都是基於『哈希』的，算法的質量取決於選擇的哈希函數的質量，」內布拉斯加大學林肯分校計算機學院的教授Vinodchandran Variyam去年在一份聲明中解釋道。
但他和印度統計研究所的Sourav Chakraborty以及多倫多大學的Kuldeep Meel一起，發現了一種極大簡化問題的方法：「新算法只使用採樣策略，並且可以使用基本技術進行質量分析。」
它是如何工作的
這個新方法被命名為CVM算法，以紀念它的發明者。它大大減少了內存需求，這在大數據時代是一個重要的優勢，並且使用了概率論的一個巧妙技巧。為了說明這個概念，考慮Variyam及其同事研究的例子，以及《量子雜誌》最近的一篇文章：假設你在統計莎士比亞《哈姆雷特》中獨特的單詞數量，但你只能存儲100個單詞。
首先，你做顯而易見的事情：記錄你遇到的前100個獨特單詞。現在，你的內存滿了——所以你對每個單詞拋硬幣。正面，就保留；反面，就忘掉。
在這個過程中，你的列表中大約會有50個獨特單詞。然後你重新開始——但這次，如果遇到列表中的單詞，你再次拋硬幣決定是否刪除它。一旦達到100個單詞，你再次遍歷列表，為每個單詞拋硬幣並按提示刪除或保留。
在第二輪中，事情變得稍微複雜一點：這次你需要連續兩次正面才能保留一個單詞；否則，它會被刪除。同樣地，在第三輪中，你需要連續三次正面才能保留；第四輪需要四次，依此類推，直到你讀完《哈姆雷特》。
這個方法有其道理——而且很聰明。通過這樣處理文本，你確保了列表中的每個單詞都有相同的概率：1/2^k，其中k是你遍歷列表的次數。假設你花了六輪讀完《哈姆雷特》，列表中剩下61個不同的單詞：你可以將61乘以2^6來估算單詞總數。
我們幫你算好了：答案是3904——而根據Variyam和他的同事，實際答案是3967(是的，他們數了)。如果你的內存能存儲超過100個單詞，準確度會更高：如果能存儲1000個單詞，算法估算的答案是3964——幾乎沒有誤差——而「當然，」Variyam告訴《量子雜誌》，「如果內存大到可以容納所有單詞，我們就能達到100%的準確度。」
（古人計數示意圖）
一種簡單的方法
這個算法不僅高效，而且它的簡單性更加令人着迷。馬薩諸塞大學阿默斯特分校信息與計算機科學學院的教授Andrew McGregor在接受《量子雜誌》採訪時表示：「這個新算法令人驚訝地簡單，且易於實現。我不會感到意外，如果它成為解決[不同元素]問題的默認方法。」
自從2023年1月發佈以來，儘管期間出現了一些小問題和漏洞，這個算法已經吸引了許多計算機科學家的關注和讚賞。儘管詳細介紹該算法的論文尚未正式經過同行評審，但實際上它已經得到了同行的認可。算法分析領域的「教父」，《電腦程式設計藝術》的作者Donald Knuth，在2023年5月還撰寫了一篇讚揚該算法的文章。他評論道：「自從我看到這個算法以來……我幾乎無法抗拒向我遇到的每個人解釋這些想法。」
與此同時，包括Chakraborty、Variyam和Meel在內的多個團隊在過去一年中一直在研究和優化這個算法。Variyam說，一些人甚至已經在他們的計算機科學課程中教授這個算法。
「我們相信，這將成為在算法和概率算法的基礎課程中教授的主流算法，」他說。Knuth也表示贊同：「它非常適合教授正在學習計算機科學基礎知識的學生，」他在5月的文章中寫道。「我非常確定，這樣的內容最終會成為標準教科書的一部分。」
那麼，這樣一個突破性的算法為何能在這麼長時間內未被發現？根據Variyam的說法，這並不像聽起來那麼不可能。
「這個簡單的算法沒有被更早發現確實令人驚訝，」他說。「在科學領域，簡單的東西多年未被發現並不少見。」
這篇論文已經在ArXiv上發佈，並出現在《第30屆歐洲算法年會論文集》(ESA2022)中。
