首先我使用100,000個elements的random array，range是100,000。
timing for bubble: 40.000000
timing for big one: 12.000000
timing for insertion: 9.000000
timing for insertion(with link list): 48.000000
timing for shell: 0.000000
似乎看不到有什麼差別阿，於是這次就使用400,000個elements，random range400,000。
timing for bubble: 592.000000
timing for big one: 200.000000
timing for insertion: 120.000000
timing for insertion(with link list): 1212.000000
timing for shell: 0.000000
唔，當其他的演算法已經開始以分鐘來計時的時候，我們仍然看不到shell的底線到底在哪裡。而其他的演算法果然是大約是以O(N^2)來增加時間複雜度。當然比較麻煩的就是insertion with link list這種很吃記憶體和cache的memory bandwidth就已經不是用單純的演算法來估計了。還必須加上這種memory transferring bound的問題。
因此一口氣催下去看看shell的底線在哪吧!增加個20倍：8000,000個elements， range 8000,000：
timing for shell: 4.000000
終於是看到它的車尾燈了。其他的就沒有跑測試了，因為照這樣下來的話我要至少跑200個小時以上才能跑完這個測試。
所以用時間複雜度來單純估計insertion，timing大約會是120*20^2 =48000
speed up大約是：48000/4=12000倍....差太多了。
至於shell有沒有可以改進的方法。也許有，比如他的kernel不要用insertion，可以改用其他的。但目前為止最快的方式還是insertion。如果可以的話，等到介紹quick sorting的時候試試看把quick sorting當kernel來嘗試shell sorting。
另一種改進的方法就是不斷的去試d的增長值。目前是d=3*d+1，如果可以的話就試試其他的方式。比如d=3*d+2？
timing for shell: 5
看起來似乎差不多，而且我用的timer很爛，為了減低誤差所以把資料量提高至50000000個：
timing for shell(3*d +1):36
timing for shell(3*d +2): 47
的確目前看起來d=3*d+1是最快的方式 。
接下來再試個d=7*d+3
結果測試:
timing for shell:??
好久...
結果用20個elements一樣做不出來，各位知道為什麼呢？在code裡面把d的value印出來會發現d的value竟然是錯的!因為對於int的value來說，如果d是負的，在記憶體的第一個element會是標示為1，但是現在我們用的d是unsigned，因此對unsigned來說這個1不是負的，而是一個很大的數。因此如果你把它印出來就會發現這個值太大了！
於是把code裡面的unsigned d換成是long int d 再跑一次d=7*d+3
timing for shell(7*d+3):67
好像更久了。
不過呢，這樣做似乎是沒什麼效率，彷彿只是隨便撈兩三個數字來去證明3*d+1是最快速的方式，說服力實在低弱的很。不如就系統化的做下來吧！把程式稍微改寫一下，用迴圈不斷的輸入參數，以下是測試結果：
timing for shell(d=7*d+1): 32.000000
timing for shell(d=7*d+2): 31.000000
timing for shell(d=7*d+3): 32.000000
timing for shell(d=7*d+4): 33.000000
timing for shell(d=7*d+5): 35.000000
timing for shell(d=7*d+6): 33.000000
timing for shell(d=6*d+1): 27.000000
timing for shell(d=6*d+2): 231.000000
timing for shell(d=6*d+3): 217.000000
timing for shell(d=6*d+4): 233.000000
timing for shell(d=6*d+5): 29.000000
timing for shell(d=5*d+1): 26.000000
timing for shell(d=5*d+2): 27.000000
timing for shell(d=5*d+3): 29.000000
timing for shell(d=5*d+4): 28.000000
timing for shell(d=4*d+1): 27.000000
timing for shell(d=4*d+2): 233.000000
timing for shell(d=4*d+3): 29.000000
timing for shell(d=3*d+1): 24.000000
timing for shell(d=3*d+2): 22.000000
timing for shell(d=2*d+1): 26.000000
看起來真奇怪，有某些數時間花的特別的長，大約接近十倍之多。反覆測那些數果然是沒有錯的，的確真的就是需要花比其他的時間還長。怎麼會這樣，如果看規律的話，可以看見那些數有個重要的特點那就是乘數和加數除了加數是一以外，它們會是倍數關係。，所以會有redundant的排列導致大的d和小的d是倍數關係,等於其實大的d是沒有必要的排列。多餘的排列。
舉例：d=6*d+3 當d=9以及d=2073的時候他們剛好是可以整除的倍數關係。那麼當我們排到d=9的時候事實上就等於d=2073也順便排一次了。那麼等於2073那次其實是多餘的排列。
其他時間比較多的數也因此可以做同樣的類推。應該算是合理的。至於為什麼會差十倍之多而不是比較少其實我們光看shell和insertion就可以了解他們的速度是差了十萬八千里。因此如果d少了一兩層的排列會少個十倍的速度我想應該是合理的，否則就不能解釋shell和insertion有時間距大的差異。因此像這種乘數與加數有倍數關係的case會發現d有一些是多餘的sorting就會差個十倍應該會是合理的。如果我們把array的element數再多個一千倍我預估d至少會少個一層，那麼這之間這些關係速度就不會只差十倍了，也許是五十倍又或是一百倍。但礙於時間沒有這麼多，因此只剩預估在這。如果有人有興趣的可以自己去跑看看是否會如我的預料發展。
因此測試我的理論是否是正確的就是測看看這種case: d=5*d 以及比較d=5*d+1, d= 5*d+2....的速度上的比較。我預估d=5*d會是相當劇烈的慢的。但由於我相當的相信我的理論是對的所以就懶的測試了。有興趣的人可以去玩玩看！
沒有留言:
張貼留言