收藏文章 楼主
计算机科学界的40年共识遭遇了一名本科大学生🤦
网友【好样的】 2025-04-21 03:37:39 分享在【时代发展的印记】版块    1    2

这是一个听起来像是电影剧本的真实故事。

网友分享在meiguo.com上的图片

一个本科生,偶然翻到了一篇论文,随手琢磨着“玩一玩”,结果就顺手推翻了计算机科学界坚持了40年的核心理论。没错,你没有听错,不是博士生,不是某个顶尖实验室的教授,而是一个普普通通的大学生,凭借一时的好奇心,撼动了整个学术界的根基。

这听起来不可思议,但它确实发生了。

故事的主角叫安德鲁·克拉皮文(Andrew Krapivin),那年他还只是罗格斯大学的一名本科生。他无意中读到了一篇题为《Tiny Pointers》的论文,最初没怎么在意,毕竟这只是成千上万篇学术论文中的一篇。可两年后,他出于好奇,重新翻开了那篇论文,“就当是消遣吧”,他后来回忆道。

然后,历史的齿轮就这么悄无声息地转动了。

【01】

那篇论文谈的是指针优化——一种在计算机内存中指向数据位置的技术。说白了,就是让数据存储和查找更高效,节省空间。克拉皮文在阅读过程中突然冒出一个念头:“如果我能让这些指针更小一点,节省的内存会不会更多?”

网友分享在meiguo.com上的图片

但要做到这一点,他需要重新思考指针指向的数据该如何组织。于是,他顺理成章地接触到了计算机科学中最经典的数据结构之一:哈希表(Hash Table)。

哈希表的概念很简单,它就像一间有无数抽屉的档案柜,每个抽屉有自己的编号(哈希值)。你想存或取某个文件,只需要知道它的编号,直接打开对应的抽屉即可。它的高效性让它成为计算机世界的“瑞士军刀”,从数据库到操作系统,甚至你手机里的APP,背后几乎都离不开它。

但克拉皮文并没有止步于使用哈希表,而是开始思考:“我能不能让它更快?”

【02】

他发现了一种全新的哈希表设计,能够比现有技术更快地查找和插入数据。最初,他以为这只是一个有趣的小改进,直到他把这个想法分享给他的导师,著名计算机科学家马丁·法拉赫-科尔顿(Martín Farach-Colton)。

科尔顿一开始并不相信。毕竟,哈希表是计算机科学界研究最透彻的数据结构之一,无数顶尖学者钻研了几十年,能有什么“突破”早就被挖掘干净了。他甚至觉得这不过是一个年轻学生的小聪明。

但出于严谨,他还是找来了自己的老搭档、卡内基梅隆大学的威廉·库兹毛尔(William Kuszmaul)帮忙验证。没想到,库兹毛尔看完后,反应却完全相反:

“你不仅仅设计了一个新的哈希表,你实际上推翻了计算机科学界40年来一直坚信的一个核心猜想!”

【03】

被推翻的,是计算机科学界一个被奉为圭臬的理论——姚氏猜想(Yao’s Conjecture)

这个猜想的提出者,是鼎鼎大名的姚期智教授,图灵奖得主,计算复杂性领域的奠基人之一。他在1985年提出,在特定条件下,哈希表的查询和插入操作无法突破某个效率极限。这个极限简单来说就是:当哈希表越来越满,找到一个空位的时间复杂度,至少是和数据填满程度成正比的。

举个简单的例子:

当你的哈希表填满了99%时,平均可能需要尝试100个位置才能找到一个空位;

当填满99.9%时,你可能需要尝试1000个位置。

这听起来非常合理,几乎符合直觉。毕竟,当停车场只剩下几个空位,你肯定得多绕几圈才能找到空车位,对吧?

问题是,克拉皮文做到了违背直觉的事情。

他发现了一种全新的哈希表结构,在最糟糕的情况下,查询和插入数据的复杂度竟然不是线性的,而是和 (log x)² 成正比。

简单来说:

当填满99%时,你不需要找100次;

当填满99.9%时,你甚至不需要找1000次;

你只需要少得多的尝试,几乎是“轻松找到”。

这是什么概念?这意味着在处理大规模数据时,效率提升可以是指数级的。而且,他们证明了这个结果不仅仅是“更快”,而是理论上的最优解——没有任何算法能比这更快了。

【04】

如果你以为这个故事到这里就结束了,那你低估了这个团队的“魔法操作”。

除了推翻姚氏猜想之外,克拉皮文和他的导师们在同一篇论文中,顺手又解决了另一个计算机科学界的难题——平均查询时间的极限。

姚期智教授在1985年的论文中,还提到了另一个结论:对于一种叫“贪心型哈希表”的结构,平均查询时间的下限是 log x。

意思是,哪怕你优化到极致,平均查询数据的速度也不可能比 log x 更快。这个结论同样被学界视为“铁律”,没人怀疑它的正确性。

结果,克拉皮文团队表示:“不对啊,我们发现可以更快。”

他们找到了一个非贪心型的哈希表,平均查询时间竟然和数据量完全无关,是一个固定的常数。换句话说,不管数据量有多大,哈希表有多满,查询数据的速度始终保持不变。

这个结果震惊了所有人。连研究团队自己都一度不敢相信,反复验证了无数次,才敢将其发表。

【05】

2025年1月,这篇划时代的论文正式发表,学术界的反应可以用“地震”来形容。

康奈尔大学的亚历克斯·康韦表示:“哈希表是计算机科学中最基础的数据结构,能在这个领域取得这样的突破,堪称奇迹。”

卡内基梅隆大学的盖伊·布雷洛赫更是直言:“这不仅仅是推翻一个猜想,而是直接给出了完美答案。”

这项研究或许不会立刻应用到你的手机里,但它已经为未来的技术发展打开了新的大门。无论是大规模数据库、人工智能训练,还是高并发的互联网服务,这种效率提升最终都会影响到每个人的日常生活。

克拉皮文的故事再次验证了一句话:科学的突破,往往来自那些不知道“不可能”的人。

他没有被前人的理论束缚,因为他根本不知道有这个“权威猜想”。正是这种无知带来的纯粹好奇心,成就了这次改变历史的发现。

有时候,改变世界并不需要多么深奥的理论,也不一定要站在最高的学术殿堂。它可能只是一个学生,翻开了一篇旧论文,然后心血来潮地问了自己一句:

“这东西……我好像可以再试试。”

出处:头条号 @再建巴别塔

meiguo.com 发布人签名/座右铭这家伙浪费了“黄金广告位”,啥也没签!
大家都在看
楼主新近贴
回复/评论列表
默认   热门   正序   倒序
meiguo.com 创始人

emotion

2   2025-04-21 03:37:39  回复

回复/评论:计算机科学界的40年共识遭遇了一名本科大学生🤦

暂无用户组 升级
退出
等级:0级
美果:
美过
精华推荐
  1. 华人科学家再次遭遇系统性排查,75%留美学者“萌生去意”!
  2. 中国的中产家庭,送孩子赴美留学就是鸡肋之举?
  3. 【读懂AI Agent】MetaGPT、Mila、斯坦福、耶鲁、谷歌的合作论文
  4. 这小伙年仅25岁,已经是百亿美金公司的创始CEO了!
  5. 美国华人在近期出入境美国,绿卡和签证的持有者须知!
  6. 台湾政府:一场误会呀
  7. “240小时免签”和“离境退税”叠加组合,让美国人感受到了中国人的聪明智慧!
  8. 马斯克的丑闻?和多名女性有染,有上百个孩子?
  9. 川普关税政策可能导致意外后果
  10. 在量子世界“玩儿游戏”?物理学家展示了量子计算机的新前景
  11. AI半壁江山是中国人?黄仁勋“敲警钟”:美国须觉醒!
  12. 关于“跨国婚姻”婚姻绿卡,给配偶申请绿卡的各种细节问题!
  13. 美国《时代》周刊:DeepSeek【梁文锋】
  14. 美国人在凌晨三点排队,不为苹果手机… 竟然是为中国毛绒玩具“拉布布”?
  15. 2025年,必须认识的一个英文单词 ~ tariff
  16. 近半数中国小包裹的接收人是贫困美国百姓?
  17. 遭遇无故吊销学签,藤校的中国留学生起诉且赢了🇺🇸国土安全部!
  18. 川普总统:在未来几周内开始发放“金卡签证”
  19. 美国小伙儿在武当山修行十余年,终于获得“中国绿卡”了!
  20. 中美关税战的最佳写实作品~乌合麒麟发布《就不跪》
  21. 美国驻华大使馆:“赴美生子”一律拒签
  22. BBC:在川普政府的关税打击下,为何中国不低头?
  23. 中美博弈2.0了?川普政府“百日执政”,撤回对华善意!
  24. 哪些关键技术决定了如今大模型格局?Google的首席科学家“万字演讲”回顾AI发展的十年
  25. 美国物价到底贵不贵?近距离窥视一下佛罗里达州的中产家庭的日常消费
  26. 百万民众“上街游行”抗议川普政府的百天?
  27. 在美国生活半年,分享几句扎心实话!
  28. 瞄准美国公民了?川普总统的“驱逐行动”在变本加厉
  29. 独自搭乘美国硬座火车,52小时横穿美国!
  30. 美国“大规模”取消国际留学生的签证
  31. 中方意识到谈判时机已至?迅速派出“王牌代表应邀”和美国财长会面了
  32. 中国“不陪川普玩”了… 从此不理会美方闹剧!
  33. 让人意外!股神【巴菲特】突然宣布退休
  34. 关税战持续了96小时… 突然大反攻?
  35. 这位美国年轻人在中国玩儿一圈,浪费掉美国政府的16亿美金?
  36. 贸易战的结局已定?中美两国“各退一步”?

美国动态 美果搜索

Your IP: 3.133.88.249, 2025-05-18 11:30:26

Processed in 0.0991 second(s)

头像

用户名:

粉丝数:

签名:

资料 关注 好友 消息
已有0次打赏
(2) 分享
分享
取消