[爆卦] 大學生推翻圖靈獎得主40年理論

[jackliao1990 (j)]

https://arxiv.org/abs/2501.02305
羅格斯大學生安德魯·克拉皮文（Andrew Krapivin）偶然發現了標題《微小指標
》的論文
克拉皮文很快想到能縮小指標尺寸的方法
為了達成這目標
他需要找到更有效的方式來組織指標指向的數據。
於是他轉向了雜湊表hash table
他在改進過程中無意間發明了全新的雜湊表
其運行速度遠超預期
羅格斯大學的馬丁·法拉奇-科爾頓（Martín Farach-Colton）起初很懷疑
畢竟雜湊表是資工研究最透徹的數據結構之一
他請來了《微小指標》論文共同作者—卡內基美隆大學的威廉·庫茲毛（William Kusz
maul）
庫茲毛回應：「你不只是設計了酷炫的雜湊表，你其實完全推翻了一個長達40年的
猜想！」

圖靈獎得主姚期智在1985年的論文中提出
在具有特定屬性的雜湊表（包括均勻探測策略）中
最糟情況下的查詢與插入時間下限是O(x) 
其中x代表哈希表接近滿載的程度
克拉皮文等人證明在新雜湊表中最糟情況下的查詢與插入時間其實是O(logx^2)
這遠比姚的預測快得多
此外姚還曾提出在貪心型雜湊表中
所有查詢操作的平均時間不可能優於O(logx)
但克拉皮文等人發現對於某些非貪心型雜湊表
平均查詢時間甚至可以達到O(1)
竟與雜湊表的填充程度無關，始終保持恆定
這發現進顛覆了40年傳統認知


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.251.137 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1739235596.A.458.html
→ sandiato: 嗯嗯跟樓下想的一樣
※ 編輯: jackliao1990 (223.138.251.137 臺灣), 02/11/2025 09:04:13
推 wei115: 嗯嗯 指標我也略懂
推 smallfan: 對跟我想得一樣
→ joy159357: 代表人類停滯40年的原因找到了？
推 Sabo5566: 沒有 我沒看懂
推 sami012985: map 取代 vector 的時代要來了
推 w2776803: 還好他不是出生在台灣
推 fishouse: 跟我想的差不多，沒想到他找媒體了
推 ms0604203: 我內文看成姚明
推 bengowa: 中國人的理論被推翻了 會被出征嗎
推 zyxx: 嗯嗯跟我想的一樣
推 sushi11: 怎麼都不是亞洲人
推 railman: 沒錯跟我想的一樣
推 LawLawDer: 嗯嗯 跟樓上想的一樣
推 EXPCDR: 強啊
→ z50502: 摁摁我也是這麼想
推 quite: 嗯嗯 樓下幫我翻譯翻譯
推 qwe04687: 真假== HashTable有更快的實作方法
噓 s9234032: 恩恩 綠色是什麼鬼
推 ilove640: 噢對對對 我就覺得應該是這樣
推 tkc7: 資料結構課本會改版嗎
推 JC910: 我其實也是這樣認為
推 Julian9x9x9: 樓下發現自己得愛滋會怎麼想
推 SamMark: 跟我想的一樣
推 NassirLittle: 姚期智不只在北京清華活躍
→ NassirLittle: 在也是中華民國中研院院士吧
→ ad1339: 就是程式可以變更快且佔用記憶體更少～
推 TsaiIngWen: 跟我
推 dovepacket: 資工：瑪德，又要重背了
推 andrew5106: 嗯嗯 雜湊表嘛 我懂我懂
→ ad1339: 這篇並沒有寫出做法，只說新方法好棒棒～
→ andrew5106: 先發現當然是申請專利阿，幹嘛寫出做
→ andrew5106: 法
→ andrew5106: worst case速度變快，這會改變很多事
推 loking: 破解密碼更快了嗎
→ andrew5106: 情...
推 preisner: 跟我十年前想的一樣而已
推 tzouandy2818: 以後可以直接用hash table做nosql了
→ tzouandy2818: 嗎
→ flashseal: 我找A片都用這方法 被他提出來了
→ jupei5566: 幹 要得獎了
推 kikujiro: 嗯嗯
→ hylio7754: 人類語言太難懂了
推 angelaeric24: 我也覺得應該是這樣
推 marke18: XD
推 freedom0116: 新方法是怎麼做的？
推 theta4719: 嗯 我也這麼想的
推 henry1234562: 人類停滯最大原因是有人做假
→ henry1234562: 然後後面的人參考做假的文獻
→ henry1234562: 人類對於質疑前人結果這點做太差
噓 ck960785: show me your code，你的理論實用嗎
推 yuetsu: 嗯嗯果然是這樣
推 RLH: 看不懂
推 KobeNi: 能將這個翻譯成中文也是人才...
推 gn01642884: 哇靠
推 whathefuc: 完全看不懂 所以是什麼的猜想？統計？
推 joker0928: 結論是酷拉皮卡屌打姚明嗎
推 volkov: 你是不是在唬爛
推 q123212: 所以天網要出來沒
推 kaitokid1214: 指標我懂不就
→ kaitokid1214:  https://i.imgur.com/M5sP12Y
推 lianghuwu: 不是啊 做法勒？
推 sssyoyo: WTF HASH還能加速 真的假的
推 mengze3084: 嗯嗯沒錯 跟我想的一樣
推 lianghuwu: 喔我看到論文了
推 zeroBB: 資工所近年都沒考雜湊表複雜度，頂多考do
→ zeroBB: uble hashing而已。好像中央吧。
推 adifdtd: 有這種事
推 WuDhar: 嗯嗯 跟我想的一樣
推 raisn: 現在大學生都這麼猛的嗎= =
推 lponnn: 前陣子太忙來不及發表啦
→ blue155305: 我也有一樣的想法
推 ahb0711: 我那天大便的時候也有想到這個，忘了發表
推 cutegirl68: 我之前就講過了
推 yannicklatte: 這我國中科展就做過了
推 soulivee: 小尺寸 貪心 雜湊 庫斯毛~重點整理好了
推 t19960804: 跟我在小學時候想的一樣
噓 CTUST: 綠成這樣
推 tanchuchan: 嗯嗯嗯嗯嗯嗯 原來如此
噓 ShockHo222: 公三小
推 limbo3014: 資料結構認知大改版中
推 alasdair: 就是這樣沒錯
噓 jknm0510a: 大家給我重讀資料結構囉
推 GABA: 現在都嘛餵給AI分析
→ cc02040326: Nerd
→ cc02040326: 申請專利就要寫出做法= =
→ blueskyqoo: ai自己左右互搏 等等就推翻了
推 leon1757tw: Hash還能加速 厲害了
推 lionel20002: 這個很猛欸
→ Qorqios: 嗯嗯
推 ohrring: 我看過了 還好而已
→ ssccg: 這個真的厲害了
推 rnmrn: 我就說過了吧
推 palapalanhu: 神
推 lulocke: 反正我每次都算不出來 隨便
推 riotssky: 我每個字都看得懂喔
推 j578882: 看的都懂 湊在一起完全不懂
推 lab214b: arxiv論文
→ lab214b: https://arxiv.org/abs/2501.02305
→ oneIneed: 我看過了，還好而已
推 a0952864901: 這位是劍橋大學的學生 原本只是因為
→ a0952864901: 興趣想研究看看 沒想到把人家40年來
→ a0952864901: 的公式整個推翻了 不知道會不會直接
→ a0952864901: 歷史留名了
推 iamstrong706: 怎感覺跟DeepSeek很像 特規化領域應
→ iamstrong706: 用
推 hatephubbing: 嗯嗯，這個手表我知道
推 blackis9ood: 他還不是劍橋的學生吧，現在他還在
推 PhySeraph: 這個有點神
推 jojotrash: 哇 真的欸
推 AbianMa19: 全部是中文為什麼我一個字都看不懂
推 LipaCat5566: 很好 rust淘汰c++的機會來了
推 bitcch: 簡單說新改善架構讓資料查詢速度大幅提升
推 st950127st: 真的假的O(1) 那麼猛
→ azeroth: 圖靈超帥長的超像奇異博士
推 ktw: https://youtu.be/ArQNyOU1hyE?feature=share
→ ktw: d
推 A9226: 蠻不簡單的 有點東西
→ sliverexile: 下一個拍成電影的題材
推 traz04067: 嗯嗯我也是這樣認為
推 cuka: 帥帥帥
推 blackis9ood: 羅格斯大學，只是之後會拿邱吉爾獎
→ blackis9ood: 學金去劍橋
推 cosoa69: 不可能吧好扯
推 a0952864901: @108樓 感謝更正 學校是 Rutgers Uni
→ a0952864901: versity 才對
推 HowLeeHi: 滿屌的這個
推 viwa77068194: 果然是強者
推 kimsman: 可惡 我昨天開趴替 不然就早就送出論文了
推 liaon98: 姚期智台灣長大，台大畢業的
推 LonyIce: 對啊 我也是這樣想
推 v2266514: leetcode 要被刷新了嗎
推 ekaskoso: 能找到原本固有思維以外的框架真是厲害
推 aasssdddd: 484論文主旨看完就發文了
推 yueayase: 有意思
噓 pig2014: 三小？這個是通用的嗎？真的沒缺點？會
→ pig2014: 不會退化速度較快？媽的如果是真的那光
→ pig2014: 新的STL release就改變世界了
→ pig2014: 我認真不信他沒有特殊應用場景
→ eric61446: 四十年先進都被埋藏了啊 怕嚇到大家 特
→ eric61446: 斯拉一堆自然能源會讓石油美元爆炸
推 rafeyu: 是真的過一陣子看ai效能就知道了,覺得不
→ rafeyu: 是真的
推 PeikangShin: 別擔心 本版連O和o是什麼  都不知道
推 hotbread: 搜一圈沒代碼 但光是作者演講展示內容
→ hotbread: 很好寫複雜度又小 應該很好落地
推 shiwa: 看起來很酷
推 Melmetal: 哇操 剛考資工所的答案該怎麼選
推 Melmetal: 未看先猜是有某種酷酷的建表機制
→ IRPT001: 模坊遊戲?
推 sses60802: 嗯嗯跟我想的一樣
→ NEDYA: 綠色的字看不清楚...
推 frakw: 簡單來說就是先苦後甘，會比原來的好
→ frakw: 可以降低最壞情形的發生機率