笨人學(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)利。
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
