[爆卦] 大學生推翻圖靈獎得主40年理論
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年傳統認知
--
嗯嗯跟樓下想的一樣
嗯嗯 指標我也略懂
對跟我想得一樣
代表人類停滯40年的原因找到了？
沒有 我沒看懂
map 取代 vector 的時代要來了
還好他不是出生在台灣
跟我想的差不多，沒想到他找媒體了
我內文看成姚明
中國人的理論被推翻了 會被出征嗎
嗯嗯跟我想的一樣
怎麼都不是亞洲人
沒錯跟我想的一樣
嗯嗯 跟樓上想的一樣
強啊
摁摁我也是這麼想
嗯嗯 樓下幫我翻譯翻譯
真假== HashTable有更快的實作方法
恩恩 綠色是什麼鬼
噢對對對 我就覺得應該是這樣
資料結構課本會改版嗎
我其實也是這樣認為
樓下發現自己得愛滋會怎麼想
跟我想的一樣
姚期智不只在北京清華活躍
在也是中華民國中研院院士吧
就是程式可以變更快且佔用記憶體更少～
跟我
資工：瑪德，又要重背了
嗯嗯 雜湊表嘛 我懂我懂
這篇並沒有寫出做法，只說新方法好棒棒～
先發現當然是申請專利阿，幹嘛寫出做
法
worst case速度變快，這會改變很多事
破解密碼更快了嗎
情...
跟我十年前想的一樣而已
以後可以直接用hash table做nosql了
嗎
我找A片都用這方法 被他提出來了
幹 要得獎了
嗯嗯
人類語言太難懂了
我也覺得應該是這樣
XD
新方法是怎麼做的？
嗯 我也這麼想的
人類停滯最大原因是有人做假
然後後面的人參考做假的文獻
人類對於質疑前人結果這點做太差
show me your code，你的理論實用嗎
嗯嗯果然是這樣
看不懂
能將這個翻譯成中文也是人才...
哇靠
完全看不懂 所以是什麼的猜想？統計？
結論是酷拉皮卡屌打姚明嗎
你是不是在唬爛
所以天網要出來沒
指標我懂不就
不是啊 做法勒？
WTF HASH還能加速 真的假的
嗯嗯沒錯 跟我想的一樣
喔我看到論文了
資工所近年都沒考雜湊表複雜度，頂多考do
uble hashing而已。好像中央吧。
有這種事
嗯嗯 跟我想的一樣
現在大學生都這麼猛的嗎= =
前陣子太忙來不及發表啦
我也有一樣的想法
我那天大便的時候也有想到這個，忘了發表
我之前就講過了
這我國中科展就做過了
小尺寸 貪心 雜湊 庫斯毛~重點整理好了
跟我在小學時候想的一樣
綠成這樣
嗯嗯嗯嗯嗯嗯 原來如此
公三小
資料結構認知大改版中
就是這樣沒錯
大家給我重讀資料結構囉
現在都嘛餵給AI分析
Nerd
申請專利就要寫出做法= =
ai自己左右互搏 等等就推翻了
Hash還能加速 厲害了
這個很猛欸
嗯嗯
我看過了 還好而已
這個真的厲害了
我就說過了吧
神
反正我每次都算不出來 隨便
我每個字都看得懂喔
看的都懂 湊在一起完全不懂
arxiv論文
我看過了，還好而已
這位是劍橋大學的學生 原本只是因為
興趣想研究看看 沒想到把人家40年來
的公式整個推翻了 不知道會不會直接
歷史留名了
怎感覺跟DeepSeek很像 特規化領域應
用
嗯嗯，這個手表我知道
他還不是劍橋的學生吧，現在他還在
這個有點神
哇 真的欸
全部是中文為什麼我一個字都看不懂
很好 rust淘汰c++的機會來了
簡單說新改善架構讓資料查詢速度大幅提升
真的假的O(1) 那麼猛
圖靈超帥長的超像奇異博士
d
蠻不簡單的 有點東西
下一個拍成電影的題材
嗯嗯我也是這樣認為
帥帥帥
羅格斯大學，只是之後會拿邱吉爾獎
學金去劍橋
不可能吧好扯
@108樓 感謝更正 學校是 Rutgers Uni
versity 才對
滿屌的這個
果然是強者
可惡 我昨天開趴替 不然就早就送出論文了
姚期智台灣長大，台大畢業的
對啊 我也是這樣想
leetcode 要被刷新了嗎
能找到原本固有思維以外的框架真是厲害
484論文主旨看完就發文了
有意思
三小？這個是通用的嗎？真的沒缺點？會
不會退化速度較快？媽的如果是真的那光
新的STL release就改變世界了
我認真不信他沒有特殊應用場景
四十年先進都被埋藏了啊 怕嚇到大家 特
斯拉一堆自然能源會讓石油美元爆炸
是真的過一陣子看ai效能就知道了,覺得不
是真的
別擔心 本版連O和o是什麼 都不知道
搜一圈沒代碼 但光是作者演講展示內容
很好寫複雜度又小 應該很好落地
看起來很酷
哇操 剛考資工所的答案該怎麼選
未看先猜是有某種酷酷的建表機制
模坊遊戲?
嗯嗯跟我想的一樣
綠色的字看不清楚...
簡單來說就是先苦後甘，會比原來的好
可以降低最壞情形的發生機率
9
這篇新聞的重點在於 Andrew Krapivin 偶然發現了一種方法，改進了 哈希表（Hash Table），並且推翻了長達 40年 的計算機科學猜想。以下是主要重點與關鍵摘錄： 重點分析 問題背景：指標與哈希表 Krapivin 研究 縮小指標（micro-indicators） 的方法，嘗試提升數據結構的效率。
阿肥試著用白話文解釋，不深入探討。因為阿肥也只是略懂略懂。有大神看不下去的，請輕虐。 Hash 有兩種 set 跟map。map的做法呢一般又分兩種：array 跟 link list。這篇應該是著重在array這邊。一般情況下當array越來越滿，會發生碰撞，需要找出新的空位。40年理論是猜想使用greedy算法，普遍找空位的time complexity是log(n)。 而這篇提出的方法是把array切割為多個小塊，然後給這些小塊起編號以及紀錄；滿/空 的status。所以當碰撞發生時，查找就會快很多，普遍情況下會是O(1)。個人理解是相當於架一個樹在hash table上，進而達到優化查找時間，大guy是醬。 ----- Sent from JPTT on my iPhone
44
[問卦] 諾貝爾經濟學家怎解釋台灣房價不會跌？很多人都說台灣房價只會漲不會跌很神奇 我想以諾貝爾經濟學獎得主的學理知識 應該能充分解釋這個房價市場吧？ 有人知道 諾貝爾經濟學獎得主會用什麼理論解釋台灣房價的情況嗎![[問卦] 諾貝爾經濟學家怎解釋台灣房價不會跌？](https://i.imgur.com/jQTV88Xb.png "[問卦] 諾貝爾經濟學家怎解釋台灣房價不會跌？")
40
[問卦] 清大姚班 北大圖靈班 台大資工 哪個強？近年中國高教在CS領域 偏好小班師徒制 清華姚班 由唯一華人圖靈獎得主姚期智創辦並親自授課 在學期間可赴MIT、Stanford、Princeton、香港大學進行交流和短期課程 只收奧賽獎牌、高考狀元![[問卦] 清大姚班 北大圖靈班 台大資工 哪個強？](https://i.imgur.com/1gdrjl4b.png "[問卦] 清大姚班 北大圖靈班 台大資工 哪個強？")
8
[閒聊] 2020諾貝爾經濟學獎得主幫忙解決幣圈經濟難題今天諾貝爾經濟學獎剛放榜，頒給發展拍賣理論的史丹佛教授 Paul Milgrom 和 Robert Wilson。 Robert 老師接到諾貝爾委員會通知，深夜穿睡衣去對街鄰居兼學生 Paul 家，叫他起床通知他得獎 XD Paul 同時也是 Algorand 加密幣黃金團隊的一員，其熟諳賽局理論並發展的拍賣理論有助於解決 去中心化幣圈經濟中 V 神提過的三難問題：無法兼顧去中心化、安全性、與可擴展性。 讓我們來認識諾貝爾經濟學獎得主與 Algorand 這個計劃吧!4
[問卦] 有在對岸混得異常好的台灣科學家嗎？姚期智 圖靈獎唯一華人得主 北京清華交叉資訊學院院長 在北京清華開設的姚班 奧賽國手、高考狀元才進得去 李開復 創新工場董事長、執行長4
[問卦] 2023圖靈獎公布 Avi Wigderson美國電腦學會ACM決定將資工最高榮譽頒給以色列的Avi Wigderson。 "他重塑了我們對計算中隨機性作用的理解以及數十年來在理論計算機科學領域的學術領導 地位而受到認可。 " Wigderson是新澤西州普林斯頓高等研究院數學學院的赫伯特·H·馬斯教授。 他是計算複 雜性理論、演算法和最佳化、隨機性和密碼學、平行和分散式計算、組合學和圖論以及理 論計算機科學與數學和科學之間的聯繫等領域的領導者。![[問卦] 2023圖靈獎公布 Avi Wigderson](https://awards.acm.org/binaries/content/gallery/acm/ctas/people/avi-wigderson-bw.jpg "[問卦] 2023圖靈獎公布 Avi Wigderson")
4
[問卦] 真的做出來哆啦A夢的話能得圖靈獎嗎？要是真的做出來哆啦A夢 不包含四度空間口袋的話 能得圖靈獎嗎？ 不知道要用多少顆GPU --
Re: [問卦] 物件導向的程式語言是廢物？圖靈獎得主Lesslie Lamport近年來一直在推崇Formal Verification工具 TLA Plus 基本概念就是把軟體架構寫成數學狀態機定義 然後透過Temporal Logic的理論來做到100%的正確性驗證 但是TLA Plus沒有辦法直接轉換成應用程式 所以用的人一直不多3
Re: [問卦] 能力強的博士跟大學就要讀不同領域的掛?圖靈獎得主當中，偏「理論計算機科學」的有很多當初都是念物理的，可能念物理的 比較聰明吧，如下： Donald Knuth（1974年圖靈獎）：大學是拿物理的獎學金，不過後來轉系了，此人著有 The Art of Computer Programming多冊，要放一套在家裡，才會尊爵不凡。 Robert W. Floyd（1978年圖靈獎）：我不是很確定是不是那麼偏理論計算機科學，
[問卦] 姚期智當初要是回台大教書台大會變強嗎？姚期智 圖靈獎得主 台大物理系畢業然後去美國 在哈佛拿了物理博士 後來又在伊利諾伊大學香檳分校拿了
Re: [閒聊] 好懷念以前的PTT是說歷屆版主選舉，本來就是公開資訊，哪有什麼帶風向的問題。 我猜閣下待的圈子，身邊的人都沒有什麼查證能力，才會一下就被風向帶走。 甚至還要被笑"大學生賺輸小學生"，呵... --