Tech
计算机科学家发明高效计数新方法
想象一下，你被派往原始雨林进行野生动物普查。每当你看到动物时，你就拍一张照片。你的数码相机将跟踪拍摄的总张数，但你只关心独特的动物数量——所有你还没有计数过的动物。最好的方法是什么？“最明显的方法是记住你见过的每只动物，并将每一只新动物与列表进行比较，”伊利诺理工学院的计算机科学家 Lance Fortnow 说。但他补充说，还有更聪明的方法，因为如果你有数千个条目，最明显的方法远非易事。
更糟糕的是，如果你是 Facebook，你想统计每天登录的独特用户数量，即使其中一些用户从多个设备和多次登录？现在我们正在将每个新登录与可能达到数十亿的列表进行比较。
在最近的一篇论文中，计算机科学家描述了一种新的方法来近似长列表中不同条目的数量，该方法只需要记住少量条目。该算法适用于任何条目逐个出现的列表 - 想象一下演讲中的单词、传送带上的货物或高速公路上的汽车。
CVM 算法以其创建者 - 印度统计研究所的 Sourav Chakraborty、内布拉斯加州林肯大学的 Vinodchandran Variyam 和多伦多大学的 Kuldeep Meel 的名字命名 - 是解决称为不同元素问题的重要一步，计算机科学家已经研究了超过 40 年。它要求一种方法来有效地监视元素流 - 其总数可能超过可用内存 - 然后估计独特元素的数量。
“新算法令人惊讶地简单易于实现，”马萨诸塞大学阿默斯特分校的安德鲁·麦格雷戈说。“如果这成为实践中解决 [不同元素] 问题的默认方法，我不会感到惊讶。”
为了说明问题以及 CVM 算法如何解决它，想象一下您正在听哈姆雷特的有声读物。这部戏剧中有 30,557 个单词。有多少是独特的？要找出答案，您可以听戏剧(经常使用暂停按钮)，按字母顺序将每个单词写在笔记本上，并跳过列表中已有的单词。当您到达结尾时，您只需计算列表上的单词数。这种方法可行，但它需要与唯一单词数量大致相同的内存量。
在典型的数据流情况中，可能需要跟踪数百万个项目。“您可能不想存储所有内容，”Variyam 说。这就是 CVM 算法可以提供更简单方法的地方。他说，诀窍是依靠随机性。
让我们回到哈姆雷特，但这次您的工作内存 - 由白板组成 - 只能容纳 100 个单词。戏剧开始后，您写下您听到的前 100 个单词，再次跳过任何重复。当空间已满时，按暂停并为每个单词抛硬币。正面朝上，单词留在列表中；反面朝上，您将其删除。经过这轮初步比赛，您将剩下大约 50 个不同的单词。
现在您继续前进到团队称之为第 1 轮的内容。继续浏览哈姆雷特，添加新单词。如果您遇到列表中已有的单词，请再次抛硬币。如果反面朝上，请删除该单词；正面朝上，单词留在列表中。按照这种方式继续进行，直到白板上出现 100 个单词。然后根据 100 次抛硬币的结果，随机删除大约一半。这结束了第 1 轮。
接下来，转到第 2 轮。继续如第 1 轮所示，但现在我们将使保留单词更加困难。当您遇到重复的单词时，请再次抛硬币。反面朝上，您将其删除，如前所述。但如果正面朝上，您将再次抛硬币。只有在您获得第二次正面朝上的情况下才能保留该单词。一旦您填满棋盘，本轮将以根据 100 次抛硬币的结果再次清除大约一半单词而结束。
在第三轮中，您将需要连续三个正面朝上才能保留一个单词。在第四轮中，您将需要连续四个正面朝上。等等。
最终，在第 k 轮中，您将到达哈姆雷特的结尾。练习的重点是确保每个单词都因为您进行的随机选择而具有相同的出现可能性：1/2k。例如，如果您在哈姆雷特结束时列表上有 61 个单词，并且该过程需要六轮，您可以将 61 除以概率 1/26 来估计不同单词的数量 - 在这种情况下为 3,904。 (很容易理解此过程如何工作：假设您从 100 枚硬币假设您从 100 枚硬币开始，并单独抛掷每一枚硬币，只保留正面朝上的硬币。您最终将剩下大约 50 枚硬币，如果有人将该数字除以概率 ½，他们可以猜出最初大约有 100 枚硬币。
Variyam 和他的同事在数学上证明了该技术的准确性与内存大小成正比。哈姆雷特恰好有 3,967 个独特的单词。(他们计数了。)在使用 100 个单词内存的实验中，五次运行后的平均估计值为 3,955 个单词。使用 1,000 个单词的内存，平均值提高到 3,964。他说：“当然，如果 [内存] 足够大可以容纳所有单词，那么我们可以获得 100％ 的准确性。”
“这是一个很好的例子，说明即使对于非常基本和经过充分研究的问题，有时仍然存在非常简单但并不明显的解决方案等待发现，”哈佛大学的 William Kuszmaul 说。
本文译自 Quanta Magazine，由 BALI 编辑发布。