有哪些充滿暴力美學的數據結構或演算法？
最好它還有counterpart，也就是與之相對應的經過精巧設計的數據結構或者演算法，這樣就更有意思啦！
先講一下我對「暴力美學」的認識：就像前蘇聯的米格-25，解決方案簡單粗暴（用不鏽鋼結構而不是其他幻想中的鈦合金等材料），但是效果卻異乎尋常地好（世界上第一種速度超過3馬赫的戰鬥機）。然後舉一個例子：替罪羊樹。作為平衡二叉樹的一種，其他方案（比如AVL樹，紅黑樹等等）都是通過旋轉來實現平衡的，但是要分很多種情況，實現的時候需要相當程度的耐心(with great care= =)。但是替罪羊樹卻是簡單粗暴地通過推倒重建的方法來獲得平衡，竟然具有相同的均攤時間複雜度O(logN)。====================================================1、純暴力的就不要提了，比如"baby step, giant step"，在我看來這就是簡單的空間換時間，外加稍微有一點搜索技巧而已。而且這個演算法本身還是指數的，數據規模變大以後沒法用；
2、盡量不要提蒙特卡洛，是很簡單粗暴，但那是一大票演算法（帶隨機化思想的演算法倒沒問題）；3、限定在經典的數據結構與演算法方面吧，各種智能仿生演算法（SA/GA/PSO等等）和機器學習演算法（SVM/ANN等等）就算了……之前沒說清楚，抱歉。4、麻煩各種神跡般的排序演算法不要來搗亂了……別說什麼量子世界多世界詮釋之類的，等真正的量子計算機出來再談吧！
泥門都開始惡搞了是不是啊哼，我來教你們一個最屌的可以預測未來彩票開獎號碼的演算法，那就是，隨便輸出一組彩票，然後如果沒有得獎，就核彈洗地滅世，這樣在未來時間所有有地球上人類存在的世界，這個演算法都是正確的。
kd-tree：這個嘛。。雖然有一些亂七八糟的數據結構可以做類似的功能。。但是kdtree就是辣么屌辣。
各種隨機增量演算法：不用多說吧。。
treap：比替罪羊無腦多了。。常數又小還能當笛卡爾數用。。
還有啟發式合併相關的演算法？比如並查集的妙用？
大概辛普森積分也算一個吧。。
模擬退火、SVM之類的無腦玄學演算法。
一秒鐘在線變離線（偽）的莫隊以及分塊版莫隊？突然想起來還有csq分治（1/2真）
斯坦那樹
van Emde Boas Tree：分塊哈希暴搞複雜度（理論）意外的好？
後綴自動機：一開始你讓我相信那個構造演算法是線性的時候，我是不相信的，你不能讓我相信我就相信，到時候觀眾會罵我，根本不是線性的。我要先試著證明一下，證明過後發現他果然是線性的，我要讓你們知道，我用的是線性的，你們用的也是！
而且跑得比dc3快多了，功能還屌。單純形：雖然不是多項式複雜度的但是秒殺了一大票多項式複雜度的演算法。。目測這題適合我這種在NOI用暴搜+剪枝混到全國的人，舉三個例子，都算是實踐中碰到並且有自己思考的
第一個是並行和並發gc演算法，很多書都講什麼並發mark-sweep，dijkstra的on-the-fly演算法，其實unix/linux之類系統下有個最簡單的辦法，就是要gc的時候，fork一個子進程去mark，然後把要free的指針通過管道傳給父進程，利用了fork的copy-on-write，實現簡單，實踐中應該也算是有效的（redis的rdb帶IO的都能用，何況gc只是內存操作）……好吧考慮到內存訪問的不可控，這個可能也不是那麼有效哈哈，但是實現簡單，實際工作中需要造輪子時候可以借鑒這個思想，其實上世紀七十年代就有人這麼實驗過gc，但是因為那時候copy-on-write性能差被否決了第二個是二分查找演算法的面試，由於面試很容易出這個題，這題很大難點又是在於二分到最後的邊界判斷，所以給人出了這麼個主意：while start &< end:
if end - start &< 5:
#順序搜索
else:
mid = (start + end) / 2
#二分，略
恩，就是問題規模小於一定量就改順序查找，也是O(lgN)，而且保證不會寫錯，如果面試官問還可以跟他扯，說5個元素順序search的話cache友好之類的，說不定就忽悠成功啦
第三個是實踐中的一個hash表結構，項目之前一直用的一個多階hash，大概意思就是弄N個簡單hash表，第一個衝突了就實驗後面的：def exists(mht, key):
h = hash(key)
for ht in mht:
idx = h % len(ht)
if ht[idx] == key:
return True
return False
mht裡面每個ht的len只要兩兩互質，就可以保證能有很高的裝載率（簡單的測試方法就是不斷插入隨機key，直到失敗時的裝載率，即所有ht都無法插入），這個演算法在內存吃緊的情況下比較有用，一般可以保證裝載率在90%以上才出現插入失敗，而且實現簡單（比如在shm裡面簡單開數組存struct數據就可以這樣做）
不過這個演算法有幾個問題，每個ht的大小分配，很多老項目的實現比較簡單，就是第一個取一個質數，後面每個都是比前一階小的質數，這樣每階差不多大，如果要裝載率比較高，則階數需要比較多，但是階數多了平均訪問一個key需要查找的深度和空查詢時候的消耗也多了所有有人提出，我們把前面的ht搞大，後面的搞小，做成沙漏狀，就減少了平均查詢次數，具體的，如果ht大小是指數遞減，則訪問平均深度平攤下來是常數，但這樣一來，裝載率又成了問題，為了保證裝載率，這個沙漏又不能縮小得太快（通過概率論可以證明）於是我就寫了個測試程序，設定每個ht大小是後面一層的k倍，限定mht的階數最高為N層，然後反覆手測了一個小時，找到了合適的k和N==================================以下隨機補充，想到了補的----------jdk的src裡面，String的indexOf（就是一個字元串裡面找子串），用的是最樸素的暴力演算法，然而這個演算法平均是O(N)的，因為字元串比較的演算法是平均O(1)的，而不管比較的兩個串有多長，想想為什麼？----------
讀寫鎖的實現，如果去看操作系統的書，比如我是從一本windows操作系統原理書上看的，說是用兩個mutex+一個讀計數來做，其實沒必要這麼麻煩，假設我們認為最多同時支持N個讀者，就搞個資源為N的信號量，每個讀者來了，就資源減一，如果寫者來了，就循環N次減一，事實上一個信號量機制就能解決所有同步問題，mutex也可以看做是資源為1的信號量啥？你說循環N次太慢，那提供一次減去盡量多的資源的介面不就行了嘛，其實這個問題是做協程框架時候涉及的，協程之間同步，要自己實現信號量之類的機制，如果是非搶佔調度協程，那這個實現非常簡單，一個整數+兩個介面，而且基於這個可以非常快地實現各種協程間機制，比如channel通訊----------說到協程，這本身也是一個暴力，多線程寫業務流程方便，但是開不了太多，非同步IO寫起來又痛苦，怎麼辦從正面看這個問題，就是進程資源固定，一個線程能消耗什麼資源，從這個角度考慮，因為線程棧占內存，那就調小棧；因為線程搶佔調度頻繁切換，那就用非搶佔調度；因為線程是內核調度耗費資源，那就用戶態調度，所以輪子就這麼造出來了類似的，一個伺服器能維持多少tcp長連接？先看一個連接耗多少資源，把耗費資源調小，不就增加維持數量了嗎，比如tcp buffer，調到非常小就行了，當然這麼小的buffer發數據會有問題，那就只發心跳和通知，有數據要發送就先通知對方一聲，我在ip:port有東東，來拿啊，即控制和數據分開走，互相協調，對於大量在線但是基本都是掛機（比如手機的很多app）的場景非常有用，單伺服器千萬在線不是夢-----------大概是09年時候，當時的公司用postgreSQL，pg的python client庫有個問題，不支持綁定變數，導致資料庫伺服器耗費大量cpu解析sql，有些人在想怎麼升級資料庫和怎麼做分散式的時候，我給client庫加上這個功能，就搞定了（開源的，有源碼咱們就改），當時還針對內部需求改了python的twisted框架當時還有個問題，py的一個xml庫不知道是本身bug還是用法問題，一直崩潰，排查了好久，後面交接給我後花了一下午自己做了個xml解析（300行代碼），後面就再沒出問題了------------------
GitHub - maopao-691515082/larva-lang_4j: The larva programming Language這個例子也算吧，python方便但慢，C++麻煩，java啰嗦，怎麼辦？各取所長就好了嘛，靈感來自於上家公司：「老大，現在java程序員這麼多，我們平台還只能用C，咋辦？」「去寫個編譯器，把java轉成C」「哦」========================總結：所謂暴力，就是在有足夠的技術和理論支持下，正面剛死問題，而不是猥瑣地繞過，或盲目地google，雖然後兩者也重要啦；就好像一群平民玩家討論打boss該怎麼加技能怎麼走位的時候，土豪說上去砍一刀不就搞定了么最後補充說明，我的觀點是工程實踐導向，但不是鼓勵盲目造輪子啦我覺得演算法要符合「暴力美學」的話不但要粗暴還要很好的解決問題，不然就只是「粗暴」了，說兩個逆天的例子：
載波偵聽多路訪問 (CSMA) : 匯流排結構區域網中分配線路資源的演算法。這個演算法讓乙太網打敗所有競爭對手成為區域網的標準，現在乙太網速度達到 100G，傳輸介質也五花八門，分配線路的演算法還是 CSMA。又由於演算法簡單到弱智的程度，它的發明人畢業論文沒有通過。下面就是這個演算法：
- 開始 - 如果線路空閑，則啟動傳輸，否則轉到第4步
- 發送 - 如果檢測到衝突，繼續發送數據直到達到最小報文時間 （保證所有其他轉發器和終端檢測到衝突），再轉到第4步.
- 成功傳輸 - 向更高層的網路協議報告發送成功，退出傳輸模式。
- 線路忙 - 等待，直到線路空閑
- 線路進入空閑狀態 - 等待一個隨機的時間，轉到第1步，除非超過最大嘗試次數
- 超過最大嘗試傳輸次數 - 向更高層的網路協議報告發送失敗，退出傳輸模式
基本就是輪詢一個資源，空閑就用，否則就等，今天的碼農如果用類似的辦法分配共享資源估計第二天就會被解僱卻在特定領域好到無以替代的地步。
TF-IDF: 用來評價一片文章中每個詞的重要程度，而且只是通過簡單的詞頻統計。人腦才能幹的事情也被演算法暴力美學了。 TF-IDF模型的概率解釋說一個有趣的東西。做 sfdhanautohint 的時候，需要做到這個事情：
已知數組
，定義關係「可被插值」：若對某個
，存在
使得
或
，則說數組元素
可被
插值。要求
的子序列
，使得
在此子序列
- 對於任何不在此子序列的項
，其可被其左右最近的，在子序列
當時這個問題是和島娘討論的，然後她給了一個很無腦但是很管用的演算法：
- 找出
和最小值
（此處假定最大值在左，在右相似）。根據可被插值的定義，它倆之間的元素肯定能被它們插值，而它們兩個肯定不能被插值，必定進入子序列
- 對
和
用相同的辦法遞歸處理
搞控制的都知道，滑模控制演算法！讓系統在兩個不穩定的模態中來回切換，使得系統穩定。PS：老毛子發明的！
以下方法或許都算不得演算法，但是卻足夠暴力而有效。
爬取58、神州專車及點評等涉及到本地信息的網站，都會遇到城市對應的問題。國家有標準的省市縣體系，但網站為了各自的用戶體驗及業務特性，又自建體系，一般省和市是嚴格按照國標的，但在縣及縣級市層面就開始各搞一套了。
於是在聯表做數據分析的時候，就遇到了很大的麻煩。最後的暴力解法是，將互聯網公司上面的地級市名或者縣名（A）與國標中的城市名（B）聯合起來做一次搜索，關鍵詞為「A屬於B」，看誰的相關結果最多，就認為是最準確的答案，如下圖的示意，乳山屬於威海市。統計全國各市黃燜雞米飯餐館的數量和加盟商的數量，並研究其兩者關係，數據分別由點評和58同城提供。統計到威海就發生了問題，因為在點評體系，威海=威海其他區域+乳山市；而在58同城體系，威海=威海市區+榮成市+乳山。這時的難點是：發現榮成和乳山不屬於國標的地級市體系，同時判斷出他們屬於哪個市級單位。當然可以查詢政府的標準省市級列表來做判斷，但是有些互聯網公司的名稱各不統一，「乳山」、「乳山市」及「乳山縣」等混在一起。而且要是在內蒙古及新疆地區，名稱就更是千變萬化了。總體來說，要把這些縣級市規整好並不容易
爬蟲獲取信息入門不難，難的是長期高質量的穩定獲取信息。
...更多文章請到數據冰山 - 知乎專欄
...更多回答請看何明科的主頁難道不是LP的simplex嗎？指數演算法跑的比多項式演算法還快。。。
SAT-solver
在分散式系統中，數據同步是個比較煩人的問題。所以就出來了各種一致性演算法。
最簡單的是two phase commit，每個transaction先投票能不能提交改動，都可以的話就開始提交，否則就取消。
然後就是Lamport的paxos演算法。論文虛構了一個叫paxos的希臘城邦進行選舉，按照少數服從多數達成一致意見。演算法不是很好理解，又沒有數學化的證明，還說了一堆關於考古有的沒的東西，也正為此論文卡了九年才被通過。還有就是自稱比paxos簡單很多的raft演算法，也是投票選leader，少數服從多數的模式。果然是燈塔國，搞出來的演算法都那麼民主。直到我後來在sigmod上看到一篇浙江大學和新加坡國立大學合作寫的paper，裡面介紹了一種叫LEAP的演算法，大概原理就是如果一台機器需要用到一個遠程數據，那麼就把那個遠程數據copy到本地，然後刪除原來的。這樣所有需要用到的數據都在本地，並只存在一個版本，然後就不存在共享資源，也就不需要解決一致性問題了。。。
據paper說效果還不錯，完爆其他各種演算法。不知道以後會不會在業界廣泛採用。。。
//------------------------------------------
看來大家對那個演算法都很感興趣就稍微說下吧。演算法原理是維護一個owner table，每個數據都有一台機器作為owner，但可以有多份拷貝防止丟失，需要讀寫數據先從owner table里找到數據所有者，然後request for ownership，成功的話就更新owner table。Paper title 「Towards a Non-2PC Transaction Management in Distributed Database Systems」地址 http://www.comp.nus.edu.sg/~ooibc/OwnerTxn.pdfBogo排序（bogo-sort，猴子排序）是個既不實用又原始的排序演算法，其原理等同將一堆卡片拋起，落在桌上後檢查卡片是否已整齊排列好，否則就再拋一次。
「猴子排序」的名字出自「無限猴子定理」——讓一隻猴子在打字機上隨機地按鍵，當按鍵時間達到無窮時，幾乎必然能夠打出任何給定的文字，比如莎士比亞的全套著作。——只要時間足夠，猴子排序一定能得出正確的答案。
最差時間複雜度為正無窮。
我每每想起這隻執著猴子不厭其煩地拋起一堆寫了數字的卡片，都會覺得這畫面簡直美極了。-----------------------------------------------------------------我的強迫症就是被這個視頻治好的。註：最後高能，猴子出沒。既然bogo sort跟sleep sort都出來了我也來湊熱鬧, （好吧我是來逗比的）
ineffective sorts from xkcd http://xkcd.com/1185/
跳錶？想到用隨機維護鏈表效率的真是神人
我接觸過的影響最深的好像就是DLX演算法整數的多項式除法勉強也算一個用3路快排算SA好像也符合這個標準
KDTree 叫做數據結構的大暴力不怎麼可卡，複雜度即使是錯的也可以過題。。。空間小，常數也很小。。。OldDriverTree 叫做數據結構的大暴力沒人會所以沒人卡，複雜度明顯是錯的但是隨機數據下的期望是O( 1 )的。。。好寫不用調，O( 1 )複雜度的碾壓，可惜是時代的眼淚了。。。Ordered Vector 叫做數據結構的大暴力常熟小不可卡，雖然隨機數據下複雜度就是錯的但是還是沒法卡。。。基本上沒有代碼複雜度。。。RRFGTree 叫做數據結構的大暴力因為有蜜汁常數調節平衡性的原因所以根本不可卡。。。還可以各種魔改，簡直和59一樣。。。
神經網路模型是最暴力無腦的演算法，沒有之一
附上百度百科：神經網路模型dancing links，暴搜 in dancing