比如說一個random的待排序array，目前已經排了第100個了，那麼這第101個數在機率上在這前100個值內的分布理論上來說是均勻的，因此你需要排序的次數的期望值就會是一半：
<次數>=sum_某數 (某數次數*某數機率)
當然這是很naive的推測，重點在於只是為了闡述搬移次數是不容小覷的！
除了搬移次數以外，還有個另外的問題就是比對大小次數。那個while迴圈內是不斷的判斷prev這個位置的值是否比欲排序值還大又或是小，在cpu的層次來看，array的element事實上不是放在register的，而是放在cache甚至更有可能的是放在距離cpu更遠的memory上，真正放在register的是prev和那個欲比較的值。因此這個while迴圈等於是不斷的從memory上拿東西來做比較。但事實上a[j]以及a[j+1]他們的值是很接近的，尤其是排序到某個大小的程度之後是如此。如果每次都一個一個的去比較a_sofar的話是沒有太大意義，浪費一堆時間！
而解決第一個問題的方式很簡單，就是使用link list的資料結構，這樣就不需要在那一個一個搬移資料，直接插入值就行了。
而我們由於在這篇文章: 排序前的準備 已經老早就有現成的link list可以用了，所以不用在那煩惱怎麼把array轉成link list
而解決第二個問題就使用切分來去快速找出符合大小的位置，也就是二元搜尋法。
以下是使用Link list的方法來解決搬移次數的問題：
void insertion_sort_use_LL(int *a)
{
data_node *sofar, *rush, *b4_sofar, *smaller;
int val_sofar;
// previous node of sofar
b4_sofar = head;
// begin sofar at the 2nd node
sofar = head->next;
// run over all elements
while (sofar != NULL) {
val_sofar = sofar->data;
// compare val_sofar from head to sofar
smaller = rush = head;
while (rush != sofar && rush->data <= val_sofar) {
// if data of rush is smaller than val_sofar,
// move to the next element
smaller = rush;
rush = rush->next;
}
// if sofar is in order, then go to next and continue
if (rush == sofar) {
b4_sofar = b4_sofar->next;
sofar = sofar->next;
continue;
}
// de-link of sofar
b4_sofar->next = sofar->next;
// insert sofar between smaller and rush
sofar->next = rush;
// if sofar is the smallest, then put
// it to head, else put it after smaller
if (rush == head)
head = sofar;
else
smaller->next = sofar;
// go to next sofar
sofar = b4_sofar->next;
}/* sofar */
// put the result back to array
list_to_arry(a);
}
由於link list還尚未介紹，但如果你了解link list那便足夠了解這部分的程式邏輯。
最外層的迴圈：
while (sofar != NULL)
就如同我們在普通insertion_sort一樣，sofar是從第2個node開始直到最後。而由於我們一開始程式的link list的tail node接的是NULL，因此我們便用這個方式判斷sofar是不是跑到結尾了。
而接著當我們把我們想要插入sofar的node的value拿出來assign給val_sofar，放到硬體的register上方便運算快速，在這之後便開始跑內迴圈：
while (rush != sofar && rush->data <= val_sofar) {
// if data of rush is smaller than val_sofar,
// move to the next element
smaller = rush;
rush = rush->next;
}
這個內迴圈就是為了找出sofar應該要插入的位置，一樣是和普通的insertion_sort的內迴圈是一樣的對應，其中rush是往下一個node前進,而smaller則是rush前一個node，在此我們先要讓rush終止在sofar，防止他跑向不該跑向的位置。接著開始判斷大小已判定該有的位置，因此在這迴圈過後，會有２種情形。1. rush等於sofar這個pointer跳出迴圈，意思是sofar比前面的都還要大。那麼我們不需要insert sofar, 直接往下一個node邁進，因此在這迴圈底下就會接了一個判斷式：
if (rush == sofar) {
b4_sofar = b4_sofar->next;
sofar = sofar->next;
continue;
}
就是直接往下個node邁進。2.找到適合的位置而跳出迴圈。這種情形我們該做的是:把sofar這個node拔起來:
b4_sofar->next = sofar->next;
然後把sofar的尾端跟rush對接：sofar->next = rush;接著把smaller的尾巴接到sofar上，但如果sofar是最小的點的話，那麼smaller會=rush也就是上面這個while的迴圈連跑都沒有跑，因此這時候sofar就會是這個link list的頭。最後我們朝向下一個sofar前進：
if (rush == head)
head = sofar;
else
smaller->next = sofar;
// go to next sofar
sofar = b4_sofar->next;
最後整個迴圈過後我們在運用早已寫好的 list_to_arry(a);把link list放回array。====================================================================
但是我個人的猜測是，使用Link List的方式其實效率會比原先的方式差。而且沒錯的話應該會差蠻多的。先不跑測試的話，光用分析的方式，我們會發現在找出資料該插入適合的位置的時候，是採取一個node 一個node去trace。她不像是array在記憶體編排上是連續的形式，反而是分散的狀況，每個node和每個node之間其實是不連續的。
我們來看普通的link list 的node的資料結構是：
typedef struct data_node {
int data;
struct data_node *next;
}data_node;
我們來觀察，當我們從一個node到下一個node的時候，會做哪些事情：1. 首先我們需要找出pointer內資料放的address。
2. 從這address中去記憶體提領next這個pointer內的資料，裡面包含了data以及一個pointer。
這樣子會造成什麼樣的問題呢？主要是cache miss的問題，由於每個node放在記憶體中的位置很可能不是連續的，因此cache update的時候從記憶體抓資料的時候很有可能都不會抓到next的node，那麼這樣子下來每次迴圈要跑下一個node的時候，cpu每次就得要等從memory拿資料到cache上，而不是像一般insertion的方法，幾乎資料都是一次抓一把到cache的slot中，使用array能夠有效利用cache update的優勢,即使要搬移資料其實也只需要在cache上搬移而已。因此單從計算的角度看起來，效率非常有差別。
當然普通的insertion有個問題就是資料量大的時候，數學機率考量的話，下一筆資料在每次迴圈比較的時候需要搬移的次數就會相對的大。更不用說要同時處理cpu管線處理的問題。但是由於現在的機器都已經使用預測表技術了，而加上資料會在cache上待命的狀況，其實問題就會小很多。
-----------------------------------------------------------------------------------
以下是使用了60000個elements的random array, range:[0:1000]的測試結果:
timing for insertion: 4 secs
timing for insertion using link list: 13 secs
以下是range:[0:60000]的測試結果:
timing for insertion: 4 secs
timing for insertion using link list: 13 secs
看起來似乎改變range差不多，當然我是用最陽春的timer,不過理論上差別不會太大。
因此預測應該是沒錯的 。雖然link list的方法大大減免了資料搬移的動作，但是畢竟memory bandwidth還是不可能跟得上cpu本身的運算時脈，cache miss的問題還是最能左右結果。因此作演算法的時間複雜度分析其實不能做很簡單的推測，主軸還是要先對硬體的特性有基本的了解才去分析才有真正的意義。
沒有留言:
張貼留言