comparison decision tree和延伸想法

Algo裡提到由 sort 的 comparison decision tree 可得知，任一 decision tree 都存在worst case，其下界為Omega(N*lgN)。

證明的想法很簡單，一個sorting algorithm對 n 個elements來說，會形成一個decision tree，inner nodes是比較的過程，一個由 root 往 leaf 的過程，就是一個排序演算法經歷的步驟。於是，任一 decision tree 對 n 個不同的數來說，至少會有 n! 個 leaves （因為有 n! 種排法）。依tree的性質，有 n! 個 leaves的話，高度至少為 lg(n!)，而對於任意的input來說，這個 decision tree 的高度即為比較次數的 worst case。所以 worst case比較次數的下界是：

Omega(lg(n!)) = Omega(n*lg(n))

記得我第一次看到這證明時，對 decision tree 的想法相當感動，沒想到重讀 Algo 再看到這想法時，還是一樣感動，而且發現我並沒有懂得很透徹。做過習題 8-1 後，我才覺得自己似乎又多了解一些 decision tree 的想法。

若反向思考的話，decision tree 自然也存在最矮的 leaves，也就是當每次比較剛好都能利用到上回的結果時，只要比 n-1 次即可，例如：

第一次拿到最小和次小的數、第二次拿次小和第三小的數比、．．．

那麼，有沒有可能對於任意輸入，找到最佳的比較方式呢？也就是說，這顆 decision tree 並不是固定的形式，而會依輸入的過程改變比法。比方在讀入數字後，以O(n)的時間猜測數字可能的分佈方式，來調整 decision tree 的樣子（即 sorting algorithm 的流程）。在這個想法之下，是否有較高的機率走入較短的 sorting path，而加快排序速度呢？

若能想出借用 Evolutionary Computation 或其它做法在 comparison based 下找出新解法，應該很有趣，先暫記一下這極可能失敗的想法。

或是放鬆使用的限制，在得知資料分佈下，預測比較的方式，比方預測要拿那兩個數來比，就有較高的機率找到較好的比較方式，比方一開始就找到最小和次小的數，那麼，接下來就假定不用拿最小的數來比，於是問題就變成排 n-1 個數，用數學來描述的話，就是做到：

T(n) = T(n-1) + c

上面這式子成立的話，time complexity只有 O(n) 而已。當然，加號後面要猜中才會是常數，也許有可能配合機率分析，了解比成功的機會，我想這是不錯的練習 Randomized Algorihm 的機會，有空來想看看。

ps.

1. 雖然非 comparison based 在給定數值範圍的情況下可打破 worst case的下界，但卻多了 value range 的假設，純comparison based的使用範圍更廣，畢竟只要滿足能比較兩數大小的條件而已。
2. 剛讀大學時，我對 halting problem 或這類證極限的定理有些反感，因為它們證明了「對所有情況來說，不可能有萬能解」，那麼，若對「所有情況減一」呢？很多時候我們不需要考慮所有情況。而以前思考較不清析，讀到這類問題時會被搞混，而弄錯焦點。現在看來，自己似乎有那麼一點成長，可喜可賀。
3. 習題 8.1 告訴我們，透過 comparison decision tree 的分析，符合O(n)的輸入非常少，甚至不到 n!/(2^n) 種。

重讀Dijkstra’s Algorithm有感

首先是確認了Dijkstra的發音，依Wikipedia的定義，要唸[ˈdɛɪkstra]。

以前我一直有兩個疑問：

1. O(E*logV)不是比O(V^2)大嗎？為啥變成O(E*logV)後較好？
2. 當heap內的元素會被更動值時，做起來不是很麻煩嗎？time complexity的影響為何沒有被認真討論？連帶使我懷疑那堆怪異的數字，O(V*logV + E*logV) 之類的。

愚笨的我在重讀Algo時終於想通上面兩件事了，

1. sparse graph的定義：|E| = o(|V|^2)，注意，是small-o，也就是說當 n 趨近於無限大時，|E|/(|V|^2) = 0，於是，E*logV還是比V^2小。若對此感到疑惑的話，不妨想想當|E| = |V|^k，其中 k 可以是比 2 小的任意正實數，也就是說，|V|^(1.9)的情況下，E*logV仍比V^2小。

   小時候自以為有讀懂small-o，第三遍讀到這個符號時，才真的體會到它的含義。如同我以前把worst case和Big-O弄混一樣，Big-O只是方便表示上界的符號，不等同於worst case。所以，average case的Big-O、best case的Big-O都很合理，沒有認合奇怪的地方。

2. 我被heap的insert/delete動作限制住想法，自以為只有insert/delete時才適合做heapify，但當我們更新heap內任一元素時，可以從這被更新的元素開始做heapify，所以heap內的元素可以任意被更新，僅需 O(logV) 的代價。事先用個 array/hash table 就可以記好 heap 內的元素，當要更新特定元素時 (e.g. 某個vertex)，O(1)的時間即能完成值的更新。

   沒想到到今天我才真的弄懂Dijkstra, MST的運作細節，以前碰到 priority queue 的更新維護細節時，都下意識地含糊帶過。也許下次再重讀Algo時，又會發現我還沒真的弄懂吧？

另外最近讀《勇闖資訊新未來：打造資訊科技的幕後英雄》時有讀到Dijkestra的介紹，順便記一下他給年輕科學家的建議：

１．別和你的同事競爭。
２．嘗試你能作的最困難議題。
３．選擇對科學發展有益切題的研究方向，不要與科學界妥協。

現階段來說，第三點可能是我最需要的，要能保有自己的價值觀而不與大環境妥協，相當困難。然而，我想一個可貴且稀少的學者，應該具有這樣的氣魄。若我的觀念錯了，也只不過是少一個一般學者，對大環境來說沒什麼損失。不管前述看法是否正確，目前我還太嫩了，仍需要經驗來確認或修正自己的想法。

快速找中位數演算法和KNN

之前找到kd-tree這個data strucutre，想說可以用它來找KNN (k nearest neighbors)，而且建立kd-tree的速度很快，空間成本又和資料量成線性關係，實在是很讚的資料結構。

實作kd-tree的關鍵在於要能快速找到中位數，而在quick sort的Theta(N*log(N))的證明裡，有經典的找中位數演算法：用Theta(N)的時間找出中位數。不過這個演算法的常數項很大，是理論上很有意思的方法（ 由它證明了quick sort的order可以寫為 Theta(N*log(N)) )，但實務上不會拿來用。

找了一下快速計算中位數的方法，找到一篇有趣的報告：“Fast Median Search: an ANSI C implementation”。這篇報告裡提供幾種找中位數的方法以及時間比較和實務考量的分析，並附有 C source code。這篇報告用的方法都是從沒排序的陣列裡找第 k 小的數字，而找中位數只是這個問題的特殊化罷了。關鍵在於從不同的角度思考中位數的定義：

The median of a list of N values has the property that in the list there are as many greater as smaller values than this element.

很漂亮的出發點，值得學習。

我從中選了差不多最快、且馬上能讀懂的Wirth，將它改成Ruby版，畢竟我其它相關的code都用Ruby寫的（按此觀看Ruby版的Wirth）。Wirth的精神和quick sort一樣，若已學過quick sort的話，看一下code就能明白Wirth的做法。

改完Ruby版的Wirth演算法後，準備要寫kd-tree時，才想到既然我要找KNN，其實找到第 k 近的鄰居後，就可以用它當pivot快速找出前 k-1 個鄰居（掃陣列一遍而已），可以不用實作kd-tree，執行效果應該還可以接受。事實上Wirth的演算法有個副作用(side effect)，它會更動原來陣列內元素的順序，但妙的是，這個副作用在KNN裡反而省下一次線性搜尋的時間，因為找完第 k 近的鄰居後，前 k 個元素就是 KNN 了 (讀一下code立即可以明白）。

有時候意外地把不同時期學的片段記憶整理一下，串成一個完整的觀念，感覺頗爽的。最棒的是，破碎學到的東西，可以更有系統地重新吸收。

ps.

• 當然，網路上可以找到不少kd-tree的實作code，像Weka裡就有Java版的kd-tree，只是功能太雜，code太長了，以我的小規模用途來說，看懂它的code還不如自己寫快一點。
• 真的建出kd-tree的話，應該會更快，因為kd-tree建一次可以找所有元素的KNN，每個元素找的時間是O(N)，但大部份元素應該不會真的要看N個元素。而Wirth的演算法在找各個元素的KNN時，相當於每個元素重算一次，每個都是Omega(N)。有時間的話真想來比較看看kd-tree能比Wirth快多少。

Range Search的演算法

原本找到kd-tree覺得夠威了，沒想到還有很多有趣的相關研究。像是”Data Structures for Range Searching”鞭闢入理地分析了6種方法，針對hyperrectangle range query (或稱orthogonal range search)的time complexity、建data structure的time complexity和所需的space complexity，簡潔易懂。結論是一般來說kd-tree最適用，cell（切成格狀）在特殊條件下最適用。

摘錄自1.8 Comparison of Methods：

Both the cell and k-d tree structures are appropriate in situations where the query restricts several of the attributes. If the approximate size and shape of the queries are roughly constant and known in advance, then cells defined by a fixed grid with size and shape similar to those of the expected queries is most advantageous. For queries with sizes and shapes that differ considerably from the design,

…

For most applications of range searching that are not characterized in the preceding paragraphs, k-d trees are likely to be the method of choice.

但這篇沒提到R-tree，也許那時R-tree還沒發明，得再評估一下R-tree的可能性。

關於演算法的早期研究就是這麼美麗、完備，但現在也沒什麼發展空間，只能拿來用就是了，cite ”Data Structures for Range Searching”的兩篇range query延伸研究分別是“On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures”和”Improving the performance of multidimensional search using fingers”，前者看來像理論分析，後者則是實作分析。

原本感到奇怪，為什麼這些研究都是用orthogonal range search，而不是圓形(球形)的range query，後來才想通，圓形的range query可以先用正方形的range query取出資料，再用圓形的條件去掉多餘的資料即可，效率分析差異不大。

用O(NlogN)的時間比較兩個序列的差異

Problem Definition

• given two sequences of the same item set, compute how many order relations are different
• order relation: a < b < c vs. c < a < b, in this case, there are two different relations which are (a, c) and (b, c)

Sample inputs and their results:

• [a, b, c], [c, b, a] -> 3
• [a, b, c, d], [d, a, b, c] -> 3
• [a, b, c, d], [d, a, c, b] -> 4, the different order relations are (a, d), (b, c), (b, d), (c, d)

Algorithm

想法

展開所有可能的order relation需要C(N, 2)次，N是item set的大小，聽Oshin說有O(NlogN)的方法，用Merge Sort的概念即可。昨天睡不著想了兩個小時，感覺差一環就想通了。今早起來忽然想通關鍵的merge，利用已排好的特性，merge的時間只要O(n)。

Pseudo Code

大概寫寫，邊界沒有算很準，陣列由1開始算，R[1..m]的意思是R的sub sequence，範圍是1..m。

CompSeq(R, R’)
Input：R, R’ which are sequences (e.g. R = [a, b, c], R’ = [b, c, a])
Output：n, the number of different order relations

1. for each c in R, H[c] := index of c in R, where H is a hash table
2. return CompSubSeq(R’)

CompSubSeq(R)

1. return 0 if |R| = 1
2. let m := |R| / 2, R1 := R[1..m], R2 := R[(m+1)..|R|]
3. return CompSubSeq(R1) + CompSubSeq(R2]) + Merge(R1, R2)

Merge(R1, R2)

1. let n := 0, k1 := 1, k2 := 1 and R be a new array
2. for i in 1..(|R1|+|R2|) do:
3. if k2 > |R2| or (k1 < = |R1| and Smaller(R1[k1], R2[k2])),
   then R[i], k1 := R1[k1], k1+1
4. else R[i], k2, n := R2[k2], k2+1, n+|R1|-k1+1
5. end for
6. return n

Smaller(a, b)

1. return true if H[a] < H[b]

雜記

Ruby寫的版本見這裡，原本想寫完整版的測試，寫完演算法後懶了，果然應該先寫test code再開始寫，才不會懶得寫test code啊。

可以利用如下的方法實作test code：產生(a1, a2, …, an) item set的所有排列，在產生排列的同時，可以知道目前產生的是第幾組序列，得到序列值後，可以用O(N)的方法算出差了幾個relation，以(a, b, c, d)和(d, c, a, b)為例，(d, c, a, b)是第23個序列，23 = 3*3! + 2*2! + 0*1! + 1*0!，所以是3 + 2 = 5次；以(c, d, a, b)來說，這是第17個序列，17 = 2*3! + 2*2! + 0*1! + 1*0!，所以是2 + 2 = 4次。利用餘數的技巧，序列數轉成階乘表示只要O(N)。

昨天原本想用這個序列順序轉答案的方法來解這問題，大部份的思考在這裡打轉。雖然成功地將原問題reduce成找序列順序的問題，並且可以用O(N)的方法由序列順序算出答案，但想不到O(NlogN)算出序列順序的方法。