Lixs 的部落格

[Term Project] Proposal

"

資工三甲

493511151 黃鼎峰
493511589 謝宗錦
493511591 胡中榮

主題: 手機上使用的地圖系統

內容: 除了一般瀏覽地圖的基本功能之外,
      再加上透過使用者對地點所share的markup,
      使得標記某地區的使用者彼此互動以及達到事件發生的功能

實作: 目前是以Google Map為地圖基底來使用,再加上J2ME提供的document來實作

時間: 5月前是熟悉Google Map api的使用,之後的一個月就是要把這部分放到J2ME
      並且建立相對應的資料庫以及網站

"

Term Project - Merge Sort

"資工三甲 493511151 黃鼎峰[@more@]

1. 研究目的:

 

這次想要研究有關於Merge Sort的演算法大致上是想要知道有關於 Merge Sort的種類 , Merge Sort再不同的情況下和其他種類的Sort的比較.

 

2.  Merge Sort:

 

Merge Sort 的原理就是利用 Divide and Conquer 把一整個尚未被排序的數字經由Divide Merge的動作把這串數字排序好. Merge Sort大概的步驟如下:

 

1. 將數列分成(divide)兩個子數列,每一個數列擁有n/2個數字。

2. 除非此子數列夠小(只剩一個數字,因為一個就是排好了),否則再繼續重覆(1)。

3.      merge每一個子數列使之成為單一數列。

 

3. Merge Sort Algorithm 的性質:

 

Merge Sort Algorithm 的解法有分為使用 recursive 和不使用 recursive ,這兩種情況都有其特性和優缺點 , 這兩種類型的Merge Sort最大的差別為 method call的數量 , 使用recursivemethod call 2n-1 , 然而使用 non- recursive就要少的多.

 

一般實作 Merge Sort 的程式都不是寫成in-place sorting , 也就是說如果要sort的數字很龐大的話 , 所需要的memory也就會變的很大 , 但是 Merge sort也是可以寫成 in-place sorting , 但程式相較起來就會變的比較複雜 .

 

Merge Sortworst-case performanceO(n log n) , 如果在sort 一個長度為N的數字 ,其所花的時間為 T(N) = T(n/2)+n .

 

4. Merge Sort Quick Sort 的比較:

 

Quick sort 本身和merge sort 非常的類似 , 它也是把數字分成兩塊 , 直到不能再分再把分開的數字合起來 , 這樣看來好像跟merge sort 沒有差別 ,事實上不是如此 , quick sort 分數字時會做partition這個動作 , 就是把數字分好大小在往下分 , 如此一來當分到最小同時也完成了sort的動作.

 

worst case , Merge sort 大致上比Quick Sort 快上 39% , 然而除了少數的情況 , 大致上Merge Sort都是比 Quick Sort快的 , 再加上Merge Sort Worst-case complexity Quick Sort Best-case complexity 是一樣的 ,也就是說 Merge Sort 理論上 Quick Sort .

 

可是以實際的情況來說 , 如果 Merge Sort Quick Sort都使用 recursive的方法來寫的話 ,Merge Sort Method call 2n-1 , Quick Sort n , Merge Sort多花了一倍的Method call , 如果使用 non-recursive的方式來做 , Merge Sort 有會因為不是in-place sorting而導致花不少時間在Memory上面 , 如果寫成in-place sorting 的類型 , 或許又會因為程式本身變的複雜而影響到執行效率 .

      下面是實際測試數據:

 

 

merge sort雖然worse casequick sort好,但它實務上的速度其實沒有quick sort來的快,但它具備一個很好的特性,就是它是stable sorting,而所謂的stable sorting指的就是 , sort 演算法sort到兩個相同大小的key值後 , 這兩個key值不會改變原本的順序 .

 

Quick sort merge sort 都是Divide and Conquer 的演算法, 只是 quick sort 先苦後樂 (進入遞迴之前的 partition 動作比較麻煩; 遞迴結束之後什麼都不必再做) merge sort 先樂後苦 (進入遞迴之前什麼都不必做; 遞迴結束之後的 merge 動作比較麻煩)

 

5. Merge Sort Heap Sort 的比較:

 

這邊先稍微講解一下heap sort的原理 , Heap在觀念上是一棵 complete binary tree , 每個 node 內的資料比它左右兩側 child nodes 內的資料都小, 一個 heap 內如果有一個元素 x 的資料值改變,因而違反了 heap property,我們可以用 upheap downheap 來修復這個heap tree , 建立 heap 的動作,先把所有元素不分順序直接放入 heap 中。 一開始將整個陣列的後半部看成是一大堆小 heaps,逐層由下往上建立稍大的 heaps,最後建立出一個完整的大 heap

 

理論上,Heap sort是比merge sort還要來的快速,Heap worst-case performance merge sort 相同為 O(n log n) , 但是heap sort in-place sorting , 也就是說它不像merge sort 每次method call 都需要去跟記憶體要一塊位置 , 所以說Heap sort 是比merge sort還要好的 .

 

6. K-way Merge Sort:

 

K-way Merge Sort 就是重覆使用mergesort一個資料流 , 這樣講不是很明白 , 從字面上看 k-way merge sort 就是把一個資料流分成 k stream , 之後先對第一個stream merge sort, sort好後 , 把這個sort完的stream 寫入到下一個stream裡面 , 之後一直重複這個動作直到所有的stream再次結合成一個sort完的output stream .

 

另外 K-way Merge Sort 本身還有一些變化 , 例如: Balanced K-way merge sort ,non Balanced K-way merge sort , 而這些變化也就是input output的不同 .

7.  結論:

 

現在演算法有提到Sort 演算法大概有 , bubble sort , insertion sort , quick sort , merge sort , heap sort 這五種 , 由於 bubble insertion 是屬於效率比較差的部份所以前面就沒有討論 , 但是 merge , quick , heap 這三個演算法之間的爭議就很大 , 因為這三個演算法的複雜度是比較好也比較接近的 , 很多的資料都有比較他們之間的優缺點 , 像是 merge sort雖然是 O(n log n) 但是他所需要的space就是 O(n) , heap sort 也是O(n log n) 同時也沒有space的問題 , 但是他程式的overhead 比較大,在某些情況反而會執行的比較慢 .

 

總而言之 , 比較完這些演算法後 , 可以發現到沒有最好的演算法 , 不同的case , 演算法的表現也不同 , 某些特定的情況下 , 反而是效率比較差的insertion sort 會勝過 merge , quick ,heap 這三個比較好的演算法 , 也就是說一個好的演算法是可以再不同的情況下去判定要使用那一種演算法,使得程式的效率可以達到最高 .

 

8. 參考資料:

 

我的資料來源多半為網路上的資訊 , 以下列出相關網站 .

1.http://en.wikipedia.org/

2.http://www.nist.gov/dads/HTML/

3.http://www.chu.edu.tw/~chh/

4.http://people.ofset.org/~ckhung/

"

期末project製作心得

"

 

這邊分享一下我個人做project的心得

[@more@]

 

這次製作有關web 2.0 的網頁 . 讓我感覺到web 2.0 真的不只是技術層面的應用 ,

web 2.0 主要釋放在觀念上的 , 比如向老師常在課堂說的個人化 , 分享 , 這些都不

是技術層面的問題 ,而是觀念上的革新, 而我在製作網頁時常常會去想如何把這些觀念

實作呢?如何去應用我們所學到的這些觀念呢?我個人的感覺 , 這些觀念的背後的實作部

是異常複雜的 , 這也是我們所碰到的最大問題 , 雖然有不錯的構想 , 可是真正的去

實作後發現東缺一塊西缺一塊 , 可見要把理念實踐 , 技術是一定必要的條件 .

 

"

類神經網路

"

看了課程版的po文分享一下心得

文章在這

 

文章裡看到了有關學習率 , 訓練等名詞 , 感覺類神經網路本身就是一種很龐大的資料 ,

比對到人類的行為模式來看 , 也是經由訓練 , 學習來建立我們的資料 , 可是不知道我們

出生到現在所建立的資料轉換成Byte會是多大的資料量呢 , 我再想如果有一天電腦的

資料庫可以擴充到無限大的話 , 是否透過類神經網路可以達到人類和電腦對談的情況

呢?

"

secondlife

"這邊我也分享一下我玩seconlife的心得記得我ㄧ進去secondlife後第一件至就是找哪裡可以賺錢 , 我想這是之前玩網路遊戲得職業病 ... 從網站和路人得到一些資訊 , 一開始最好的賺錢方法就是去當舞者XD .. 其實也不算是舞者啦 , 就是道一些有開店地方當廉價的勞工 , 幫忙他們衝人氣 , 者要掛網在那邊就可以賺到錢這樣 . 大概賺了10多塊後 , 我就馬上跑到賭場去玩玩看 .... 運氣不錯...賺了5元XD ... 說真的~還滿有趣的"

Urmap +msn

"

把 Urmap的技術加入到msn裡面我個人認為這是一個很不錯的構想

 

如果把Urmap 加入到msn我認為可以使得msn的溝通能力更上一層樓 , 運用這個技術 , 朋友可以很方便的約見面地點 , 我是吃飯的位置 , 但是這會不會也讓網路犯罪更上一層樓呢 , 如果利用msn輕易的透露出自己的住址 , 會不會使得別人更容易加害於你呢,這也是個可以思考的問題.

"

weco是不是發生問題?

"

我這兩天無論是po文和使用trackback功能都會出錯 , po文完後頁面會出現錯誤

但是還是會po上去.... 

 trackback後他雖然說成功了但是我去看原本的文章引用的部分根本沒更新

希望可以快點解決...不然這兩天要po文或是trackback都會出現問題...

拜託了...點近來可以看到出錯的訊息..

[@more@]

這裏附上網頁發生問題出現的訊息:

 

Exception message: BayesianTokens::updateOccurrencesFromTokensArray: Cannot update occurrences of token 'trackback?'.
Error code: 0
-- Backtrace --
c:appservwwwcsie_classclassdaobayesiantokens.class.php(197): throw
c:appservwwwcsie_classclassdaobayesiantokens.class.php(167): bayesiantokens.updateoccurrencesfromtokensarray
c:appservwwwcsie_classclassbayesianbayesianfiltercore.class.php(87): bayesiantokens.incnonspamoccurrencesfromtokensarray
c:appservwwwcsie_classclassbayesianbayesianfiltercore.class.php(108): bayesianfiltercore.train
c:appservwwwcsie_classclassactionadminadminaddpostaction.class.php(148): bayesianfiltercore.trainwitharticle
c:appservwwwcsie_classclasscontrollercontroller.class.php(310): adminaddpostaction.perform
c:appservwwwcsie_classadmin.php(43): admincontroller.process

"

snap

" snap真的不錯使用 ~不用點連結就可以預覽網頁

我最近有看到使用snap的網頁就是卡提諾 , 那時候使用上就感覺非常方便 , 之後有去

snap的官方網站看看 , 發現他也有 Google AJAX search 的功能 , 應該可以應用載

很多地方

"

行動電腦介紹!!

"

     現在的高科技產品都有一定的行動運算能力,現在令我們印象最深刻的就是筆電,可是除

除了筆電外 , 兩公斤重的Tablet PC 和不到200公克的Smartphone都可以叫做行動電腦 

[@more@]

       行動電腦的定義就是可以帶著走的電腦 ,筆電就是一個最佳的例子,可是現在行動電腦

的設計觀念往著更清更小的方向來研發,  這邊要介紹四種很有潛力的行動運算裝置,如下

1. Tablet PC

2. UMPC

3. PDA

4.Smartphone 

        可是雖然這些行動裝置體積很小,但是價錢可不小阿XD

"

WEB API

"

不可否認...WEB API的利用已經是一種趨勢...

 

    利用 WEB API可以使得網站的功能更加多元化 ,善加利用的話網站本身就會進化 ,變成更可以結合日常生活的一項便利工具 ,各大MAP WEB API可以說是最佳的例子!!

 

 

"

頁面