array indexing

array indexing

「索引」是電腦的絕技!一個元素存放到陣列之後,不論是在陣列的哪個地方,只要利用索引值(index),就能一瞬間找到元素。大多數的演算法都運用了「索引」的技巧,讓程式執行時間更短。

以下介紹索引的常見運用方式。

一、定位

將物件放入陣列中,array[位置] = 物件。

當元素很多時,我們可以放到陣列裡。我們只要記錄索引值,依舊可以常數時間得到元素。

範例:求最大值

將元素連續地放入陣列,若想記錄一元素,僅需一索引值。

範例:求子字串

將元素連續地放入陣列,若想記錄一區間,僅需頭尾的索引值。

範例:連續數字和

將元素連續地放入陣列,利用問題本身的數學性質以及索引值,快速得到答案。

範例:求中位數

將元素依照大小順序並連續地放入陣列,利用索引值得到位於中間的元素。

範例:二元搜尋法(binary search)

將元素依照大小順序並連續地放入陣列,然後夾擠索引值。

如果元素放入串列,則沒有索引值,無法使用二元搜尋法。

範例:二元樹(binary tree)

元素的索引值對應到樹的結構,是一種特殊的定位。

範例:堆疊(stack)、佇列(queue)

元素連續地放入陣列,然後以改變索引值的方式,來動態增減堆疊及佇列的元素。

二、歸類並標記

物件直接作為陣列的索引值,array[物件] = 物件的屬性。

範例:正整數集合

物件:正整數。物件的屬性:是否在集合裡頭出現。

範例:統計英文字母出現次數

物件:英文字母。物件的屬性:英文字母的出現次數。

範例:計數排序法(counting sort)

索引值的大小順序,恰是元素的大小順序,亦可用於排序。

範例:雜湊表(hash table)

元素的索引值由特殊方法決定,是一種特殊的歸類。

三、轉換

array[物件] = 另一個物件。概念等同數學術語「函數」。

範例:取代(substitution)、移位(transposition)

密碼學的基礎概念。取代是文字的轉換,移位是位置的轉換。

定址的時間複雜度

當索引值大小為N,有人認為定址的時間複雜度是O(log₂N),也有人認為是O(1)。兩種說法都有依據。

數學的觀點:N總共有log₂N個位元,運用二元樹的觀念,依照各個位元的數值是0或是1進行分枝,分枝到底後就完成定址了。所以定址的時間複雜度是O(log₂N)。

電路的觀點:一顆中央處理器可以平行處理32位元(現在已有64位元),只要是介於0到2³²-1的索引值,都可以在1單位時間完成定址,而不必用32單位時間來完成定址。所以定址的時間複雜度是O(1)。

大家傾向假設定址的時間複雜度是O(1)。

定址的範圍

方才提到一顆中央處理器可以平行處理32位元,理論上可以定址到2³²以內的位址。一個位址一般擁有1byte的記憶體大小,所以可以運用的記憶體就有2³²byte = 4GB 這麼多。

但是作業系統會保留一些位址、預留一些記憶體空間以維持系統運作,所以使用者實際可以運用的記憶體其實不到4GB。

當記憶體沒有插到4GB的時候,作業系統利用一種叫做virtual memory的技術,以硬碟空間補足記憶體不足4GB的部份。

位址是連續不斷的,我們寫程式也都直接假設位址對應到的記憶體空間是連續不斷的,然而實際上並不是連續的。作業系統運用一種叫做paging的技術,藉由page table,讓記憶體看起來是連續的。

recursion

recursion

在函式內部呼叫原本的函式,叫做「遞迴」。

遞迴與迴圈一樣,將一件事情重複很多次,每次都改變一點點。遞迴與迴圈一樣,必須設定起始條件、結束條件、改變量,以避免無窮遞迴。

範例:階乘

1乘以2乘以3……乘以n。

範例:兔子數列

0 1 1 2 3 5 8……,求第n項。公式f(n) = f(n-1) + f(n-2)。

迴圈輔以堆疊才能樹狀分枝。遞迴可以輕易地樹狀分枝。

UVa 110 177 183 839

interval

array indexing

數10個數字,一般而言,從1開始,到10結束。

數10格陣列,有些不同,從0開始,到9結束。

陣列索引值,從0開始。原因可能是指標。存取陣列首格,不需要將記憶體位址+1。

loop

迴圈索引值,從0開始,到n-1結束。原因是陣列。

小技巧:為了減少計算步驟-1,於是<= n-1改成< n。

結束條件是等於,明確合理,「這裡就是終點」。

結束條件是小於,不夠直覺,「似乎還沒到終點」。

為了減少計算步驟-1,只好採用不夠直覺的方式。

interval

數字0到9:左閉右閉區間[0,9],左閉右開區間[0,10)。

正統的做法是左閉右閉[0,9]。

為了使用迴圈小技巧,大家習慣採用左閉右開[0,10)。

左閉右開的優點:iterator

有些資料結構,例如串列list,只能單向移動,不能雙向移動。只能+1,不能-1。這種情況只能採用左閉右開,避免-1。

例如C++標準函式庫,循序存取資料結構的功能iterator。當遇到單向移動的資料結構,只能++,不能--。導致iterator的成員begin和end,採用左閉右開。導致內建函式的參數,採用左閉右開。

左閉右開的優點:減少計算步驟-1

許多經典演算法,可以使用左閉右開,減少計算步驟-1。

左閉右開的優點:計算區間大小不必-1

計算區間的數字數量,可以使用左閉右開,減少計算步驟-1。

左閉右開的優點:空區間不會遭遇負數

[0,0]是一個數字0,[0,-1]是沒有數字。

[0,1)是一個數字0,[0,0)是沒有數字。

例如unsigned int,採用左閉右開可以避免向下溢位。

左閉右開的缺點:最大區間不會涵蓋整數最大值

左閉右開也有缺點。

例如涵蓋unsigned int最大值,區間右值會向上溢位。此時只能使用左閉右閉。

例如C++標準函式庫,隨機整數生成器uniform_int_distribution採用左閉右閉,隨機浮點數生成器uniform_real_distribution採用左閉右開,規則無法統一。

metaprogramming

metaprogramming

設計一支程式來製造程式碼,令該程式碼充分運用程式語言自身擁有的能力,輕鬆地、更有效率地完成更多事情。

範例:四則運算式

5 + 8 × (2 - 3) + 7 × -6 / (2 - 1) + 1

身經百戰的演算法設計高手,必然不假思索說出:stack,把所有符號依序放入stack,依照運算符號的優先次序push和pop。聽來簡單,實作起來還是頗麻煩。

這裡要介紹的是更輕鬆、更強悍的方法:寫程式製造一支會進行四則運算的程式。大家都知道C/C++的語法當中,就有四則運算的語法了。現在來設計一支程式,製作出四則運算的程式碼吧!

如果輸入方才的四則運算式,就會產生如下程式碼,檔名為temp.cpp。

然後編譯temp.cpp、執行一下,就有答案了。甚至可以把編譯、執行的指令,統統寫進程式碼當中:

範例:quine

一支程式,其功能是輸出本身程式碼。純娛樂。

template metaprogramming

C有個功能叫macro,可以代換程式碼。C++有個更厲害的功能叫template,可以代換並且遞迴展開程式碼。

運用template,編譯時期即可計算答案,令答案變成程式碼的一部分;執行時期不必花時間計算,直接印出答案!

不過這是個怪招,平常沒人這樣做,大家當作娛樂看看就好。儘管在C++裡面是怪招,但是在Haskell裡面卻是基本功。

範例:階乘