中了名為cache-oblivious的毒 -_-

Paste_Image.png

笨人學(xué)到一個高大上的東西铺然,結(jié)果就是花費(fèi)無限的時間還是學(xué)不明白俗孝。。魄健。
比如我聽說了cache-oblivious(CO)這么個概念赋铝,然后就吭哧吭哧費(fèi)了快兩星期了還是沒搞懂。沽瘦。革骨。

基本思想就是在不知道緩存塊大小(在分析中設(shè)為B)的model下,怎么能得到能和知道大小的model(Disk-Access-Model)想媲美的算法和數(shù)據(jù)結(jié)構(gòu)呢析恋?

一開始發(fā)現(xiàn)掃描還是很高效的良哲,即便不知道塊的大小,我掃描N個元素的話助隧,就認(rèn)為即使不知道塊的大小也可以只用 N/B 次塊讀取就能搞定筑凫。

后面就開始鬼畜起來了〔⒋澹基本想法就是依靠分形巍实,或者說遞歸的數(shù)據(jù)結(jié)構(gòu)。把一個結(jié)構(gòu)打碎哩牍,然后把渣渣按一定的順序排列蔫浆,然后只要base case的渣渣可以掃描了,整個結(jié)構(gòu)就相當(dāng)于按順序排列了姐叁。這樣就能保證高效了。

思想很簡單洗显,算法和結(jié)構(gòu)是真難啊外潜。給跪了。
雖然還沒搞明白挠唆,先扯扯淡吧处窥。
1,coarsen base case
因?yàn)閿?shù)據(jù)結(jié)構(gòu)是遞歸的玄组,所以存在base case的數(shù)據(jù)結(jié)構(gòu)滔驾,一般默認(rèn)為一個元素的結(jié)構(gòu)。但是在實(shí)際中俄讹,遞歸到一個元素顯然是不經(jīng)濟(jì)的哆致。可以把遞歸的結(jié)構(gòu)想象成遞歸方法算fib患膛,遞歸到1顯然巨慢無比摊阀。
一般進(jìn)行CO分析都默認(rèn) MT(B) = O(1),所以coarsen時,可以把這個B想象成離CPU最近的cache(L1或者L2)的緩存塊的大小胞此。然后在base-case臣咖,造一個大小為B的特殊結(jié)構(gòu)。

2漱牵,理論上最優(yōu)夺蛇,不一定實(shí)際中跑的最快
圖拷貝自http://users-cs.au.dk/gerth/emF03/slides/cacheoblivious.pdf
原作者保留一切權(quán)利。

Paste_Image.png

Paste_Image.png

vEB layout 里酣胀,每往下跳一部都是個遞歸刁赦,很費(fèi)時。
估算一下灵临,不一定對:logN+1/2log(N)+1/4log(N)+... = O(log(N))截型,好吧,只差一個常數(shù)儒溉,不過DFS就是Log(N)昧谊,看來常數(shù)不小啊喳魏。。。把緩存的優(yōu)勢都搭進(jìn)去了距糖。
要優(yōu)化那個遞歸可以用indirection(memoize base case),這里可以用indirection是因?yàn)镃O的東西都是遞歸的嘛渊鞋,跟分型似的凸克,里面長的都一樣。

就扯這么多蒲障,畢竟還沒學(xué)明白呢歹篓。。揉阎。
丟鏈接

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-videos/lecture-23-cache-oblivious-algorithms-medians-matrices/
(memory hierarchy,def of External memory model,def of cache oblivious model,
why cache-oblivious,scanning,divide & conquer,Median finding,Matrix Multi)

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-videos/lecture-24-cache-oblivious-algorithms-searching-sorting/
(introducing c-o searching and sorting,vEB layout,didn't show exactly how to do them,see them in 6.851)

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/lecture-videos/session-7-memory-hierarchy-models/
(recap mem heirarchy,EMM results,introducing CO model
showing how to make CO B-tree with 5 topics
1,order file maintenance as a black box
2,put a static vEB layout full BST upon ordered file
3,how to update
4,update analysis,finding that it need impovment by a lgN factor
5,using indirection to speed up a lgN factor)

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/lecture-videos/session-8-cache-oblivious-structures-i/
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/lecture-videos/session-9-cache-oblivious-structures-ii/
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/
http://users-cs.au.dk/gerth/emF03/slides/cacheoblivious.pdf
https://github.com/lwu/veb-tree
https://www.youtube.com/results?search_query=cache+oblivious
http://www.cs.cornell.edu/courses/cs612/2005sp/papers/thesis.pdf
http://tudr.thapar.edu:8080/jspui/bitstream/10266/1667/1/Ritika%28800932017%29.pdf
http://www.itu.dk/people/pagh/papers/cohash.pdf

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末庄撮,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子毙籽,更是在濱河造成了極大的恐慌洞斯,老刑警劉巖,帶你破解...
    沈念sama閱讀 219,270評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件坑赡,死亡現(xiàn)場離奇詭異烙如,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)毅否,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,489評論 3 395
  • 文/潘曉璐 我一進(jìn)店門亚铁,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人搀突,你說我怎么就攤上這事刀闷⌒鼙茫” “怎么了?”我有些...
    開封第一講書人閱讀 165,630評論 0 356
  • 文/不壞的土叔 我叫張陵甸昏,是天一觀的道長顽分。 經(jīng)常有香客問我,道長施蜜,這世上最難降的妖魔是什么卒蘸? 我笑而不...
    開封第一講書人閱讀 58,906評論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮翻默,結(jié)果婚禮上缸沃,老公的妹妹穿的比我還像新娘。我一直安慰自己修械,他們只是感情好趾牧,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,928評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著肯污,像睡著了一般翘单。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上蹦渣,一...
    開封第一講書人閱讀 51,718評論 1 305
  • 那天哄芜,我揣著相機(jī)與錄音,去河邊找鬼柬唯。 笑死认臊,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的锄奢。 我是一名探鬼主播失晴,決...
    沈念sama閱讀 40,442評論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼拘央!你這毒婦竟也來了师坎?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,345評論 0 276
  • 序言:老撾萬榮一對情侶失蹤堪滨,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后蕊温,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體袱箱,經(jīng)...
    沈念sama閱讀 45,802評論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,984評論 3 337
  • 正文 我和宋清朗相戀三年义矛,在試婚紗的時候發(fā)現(xiàn)自己被綠了发笔。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,117評論 1 351
  • 序言:一個原本活蹦亂跳的男人離奇死亡凉翻,死狀恐怖了讨,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情,我是刑警寧澤前计,帶...
    沈念sama閱讀 35,810評論 5 346
  • 正文 年R本政府宣布胞谭,位于F島的核電站,受9級特大地震影響男杈,放射性物質(zhì)發(fā)生泄漏丈屹。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,462評論 3 331
  • 文/蒙蒙 一伶棒、第九天 我趴在偏房一處隱蔽的房頂上張望旺垒。 院中可真熱鬧,春花似錦肤无、人聲如沸先蒋。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,011評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽竞漾。三九已至,卻和暖如春皇忿,著一層夾襖步出監(jiān)牢的瞬間畴蹭,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,139評論 1 272
  • 我被黑心中介騙來泰國打工鳍烁, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留叨襟,地道東北人。 一個月前我還...
    沈念sama閱讀 48,377評論 3 373
  • 正文 我出身青樓幔荒,卻偏偏與公主長得像糊闽,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子爹梁,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,060評論 2 355

推薦閱讀更多精彩內(nèi)容