Strict Weak Ordering of C++ std::sort

I have been investigating “strict weak ordering" of C++ std::sort this afternoon, and would like to take some notes.

The definition of “strict weak ordering" is quite complicated, so I do not want to go into it and, furthermore, you can find it on the Wikipedia website. There are 3 questions I want to clarify:

  1. What is the definition of std::sort with a Compare?
  2. What if the Compare is not strict weak ordering?
  3. Is strict weak ordering better than other methods?

What is the definition of std::sort with a Compare?

A long time ago, I thought std::sort sorts the elements in the following order:

cmp(A[i], A[i+1]) is true, where i in [0, sizeof(A)-1)

So if we write the cmp as below, we can get an increasing sequence.

bool cmp(int x, int y) {
    return x < y;
}

Well, what if all the elements of A are the same? cmp(A[i], A[j]) only returns false, right? So I realized I was wrong.

In stl_algo.h or /usr/include/c++/7/bits/stl_algo.h, the comment before the sort with a Compare is as below,

05226   /**
05227    *  @brief Sort the elements of a sequence using a predicate for comparison.
05228    *  @ingroup sorting_algorithms
05229    *  @param  first   An iterator.
05230    *  @param  last    Another iterator.
05231    *  @param  comp    A comparison functor.
05232    *  @return  Nothing.
05233    *
05234    *  Sorts the elements in the range @p [first,last) in ascending order,
05235    *  such that @p comp(*(i+1),*i) is false for every iterator @p i in the
05236    *  range @p [first,last-1).
05237    *
05238    *  The relative ordering of equivalent elements is not preserved, use
05239    *  @p stable_sort() if this is needed.
05240   */
05241   template<typename _RandomAccessIterator, typename _Compare>
05242     inline void
05243     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05244      _Compare __comp)
05245     {

So the definition of std::sort with a Compare will sort the elements in the following order:

cmp(A[i+1], A[i]) is false, where i in [0, sizeof(A)-1)

What if the Compare is not strict weak ordering?

It might crash depending on the inputs! How does it happen?

Briefly, in the implementation of std::sort, it assumes that the Compare is strict weak ordering. If the assumption is not fulfilled, the result is undefined.

I used gdb to trace the source code to find the line that causes the crash out of curiosity. My testing array has 30 elements that are the same and I use “<=" in the Compare so the return value of the Compare is always true.

In the quicksort of introsort, I found that it choose a pivot as below:

   |1938      template<typename _RandomAccessIterator, typename _Size, typename _Compare>                                               │
   │1939        void                                                                                                                    │
   │1940        __introsort_loop(_RandomAccessIterator __first,                                                                         │
   │1941                         _RandomAccessIterator __last,                                                                          │
   │1942                         _Size __depth_limit, _Compare __comp)                                                                  │
   │1943        {                                                                                                                       │
   │1944          while (__last - __first > int(_S_threshold))                                                                          │
   │1945            {                                                                                                                   │
   │1946              if (__depth_limit == 0)                                                                                           │
   │1947                {                                                                                                               │
   │1948                  std::__partial_sort(__first, __last, __last, __comp);                                                         │
   │1949                  return;                                                                                                       │
   │1950                }                                                                                                               │
B+ │1951              --__depth_limit;                                                                                                  │
  >│1952              _RandomAccessIterator __cut =                                                                                     │
   │1953                std::__unguarded_partition_pivot(__first, __last, __comp);                                                      │
   │1954              std::__introsort_loop(__cut, __last, __depth_limit, __comp);                                                      │
   │1955              __last = __cut;                                                                                                   │
   │1956            }                                                                                                                   │
   │1957        }

   │1915      template<typename _RandomAccessIterator, typename _Compare>                                                               │
   │1916        inline _RandomAccessIterator                                                                                            │
   │1917        __unguarded_partition_pivot(_RandomAccessIterator __first,                                                              │
   │1918                                    _RandomAccessIterator __last, _Compare __comp)                                              │
   │1919        {                                                                                                                       │
B+ │1920          _RandomAccessIterator __mid = __first + (__last - __first) / 2;                                                       │
  >│1921          std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,                                                  │
   │1922                                      __comp);                                                                                  │
   │1923          return std::__unguarded_partition(__first + 1, __last, __first, __comp);                                              │
   │1924        }

   │75        /// Swaps the median value of *__a, *__b and *__c under __comp to *__result                                               │
   │76        template<typename _Iterator, typename _Compare>                                                                           │
   │77          void                                                                                                                    │
   │78          __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,                                                 │
   │79                                 _Iterator __c, _Compare __comp)                                                                  │
   │80          {                                                                                                                       │
B+ │81            if (__comp(__a, __b))                                                                                                 │
   │82              {                                                                                                                   │
  >│83                if (__comp(__b, __c))                                                                                             │
   │84                  std::iter_swap(__result, __b);                                                                                  │
   │85                else if (__comp(__a, __c))                                                                                        │
   │86                  std::iter_swap(__result, __c);                                                                                  │
   │87                else                                                                                                              │
   │88                  std::iter_swap(__result, __a);                                                                                  │
   │89              }                                                                                                                   │
   │90            else if (__comp(__a, __c))                                                                                            │
   │91              std::iter_swap(__result, __a);                                                                                      │
   │92            else if (__comp(__b, __c))                                                                                            │
   │93              std::iter_swap(__result, __c);                                                                                      │
   │94            else                                                                                                                  │
   │95              std::iter_swap(__result, __b);                                                                                      │
   │96          }

Among 3 elements *__a, *__b and *__c, it will swap the median with the value of the “first" position. The first position is in front of __a, __b and __c.

Then the flow goes into std::__unguarded_partition,

   │1894      template<typename _RandomAccessIterator, typename _Compare>                                                               │
   │1895        _RandomAccessIterator                                                                                                   │
   │1896        __unguarded_partition(_RandomAccessIterator __first,                                                                    │
   │1897                              _RandomAccessIterator __last,                                                                     │
   │1898                              _RandomAccessIterator __pivot, _Compare __comp)                                                   │
   │1899        {                                                                                                                       │
b+ │1900          while (true)                                                                                                          │
   │1901            {                                                                                                                   │
B+>│1902              while (__comp(__first, __pivot))                                                                                  │
   │1903                ++__first;                                                                                                      │
   │1904              --__last;                                                                                                         │
   │1905              while (__comp(__pivot, __last))                                                                                   │
   │1906                --__last;                                                                                                       │
   │1907              if (!(__first < __last))                                                                                          │
   │1908                return __first;                                                                                                 │
   │1909              std::iter_swap(__first, __last);                                                                                  │
   │1910              ++__first;                                                                                                        │
   │1911            }                                                                                                                   │
   │1912        }

Well, we find the problem.

B+>│1902              while (__comp(__first, __pivot))                                                                                  │
   │1903                ++__first;  

__comp always returns true in the range of the array and ++__first will access the data out of range finally.

If the Compare is strict weak ordering, there must be at least one element x in the range of [__first, __last), where __comp(x, *__pivot) is false. So it will not crash if the Compare is strict weak ordering in line 1900~1911.

Is strict weak ordering better than other methods?

Some articles say that strict weak ordering is good because all of the logical operators can be implemented in terms of it.

logical operatorimplemented in terms of strict weak order (<)
<(a, b)
(a < b)
<=(a, b)
!(b < a)
==(a, b)
!(a < b) && !(b < a)
!=(a, b)
(a < b) || (b < a)
>(a, b)
(b < a)
=(a, b)!(a < b)

But, how about partial ordering (≤)?I can implement the logical operator < as below:

logical operatorimplemented in terms of partial order (≤)
<(a, b)
!(b ≤ a)

Because < can be implemented in terms of ≤, all of the logical operators can be implemented in terms of ≤, too.

If < is good for the reason, ≤ is also good for the same reason. I think the main reason that strict weak ordering is used in STL is for coding and performance issues. If partial ordering is used, the definition of sorting has to be changed for the case that there are equivalent elements. The definition might be as below:

cmp(A[i], A[i+1]) is true, where i in [0, sizeof(A)-1)

Except the reason that strict weak ordering might have clear logic in coding, what are the other pros? Actually, there are other implementation methods. In Java, the Comparator returns an int instead of a bool. A negative value means a<b, a positive value means b>a, and zero value means a equals b. So is strict weak ordering really good? It seems to me that it is a little complicated and not intuitive.

廣告

軟體設計 (三)擴充性與遠見

軟體總是不停地變動,功能越加越多,除了可讀性之外,擴充性亦是軟體設計的另一大重點。

原本有一個api如下:

void func(int x, int y, int z)

因為需求的增加,參數從3個變成5個,5個變成8個,再變成13個,之後也許還會再增加,參數多到呼叫的時候還要數數看是第幾個!而且因為已經有很多地方呼叫這個API,refactor是一個大工程,這不只是一個例子,是真實實務上遇到的事。

如果我們當初知道會有後續的變化,也許一開始的版本就應該傳一個物件,又或者以別的方式設計API。

要在哪個部分增加擴充性,設計者必須要對產品的未來變化有所了解,這與domain knowledge或是對軟體發展的遠見習習相關。不必要的彈性就像是把每個用到整數的地方都令其支援大數一般無用。但目光短淺的無彈性設計則像是毒瘤,會逐漸浸蝕軟體結構。

寫LeetCode如何分析時間複雜度(一)

本篇文的code將以最平易近人的python來撰寫。

特別強調LeetCode,而不是廣義的演算法分析,是因為LeetCode解法的時間複雜度分析較為容易,學會它並不需要花太多時間,而且對解題非常有幫助,試著分析個20題左右,應該就能慢慢掌握要領。

分析時間複雜度的目的是以一個客觀的方式來估計一個演算法的速度,如果不知道怎麼分析,寫LeetCode時很可能花一堆時間coding、debug,最後還是得到Time Limit Exceeded,所以寫LeetCode一定要會分析時間複雜度。

客觀的分析就是讓我們說明演算法的速度有「多快」,而不是主觀地說「我覺得這樣比較快」。客觀的說法是,「這個新的演算法時間複雜度是O(N),而舊的是O(N^2),所以新的比較快」。客觀,就是只要分析的方式正確,所有人都會分析出同樣的結果,如果有2個人分析出不同的時間複雜度,絕對至少有1個人是錯的。

關於表示時間複雜度的符號Big-O以及其它符號,其嚴格定義可參考wiki,wiki上寫得非常數學,但網路上還有很多資源,例如Google「初學者學演算法」,可以找到詳細圖文解說時間複雜度。本篇文著重在分析LeetCode解法的時間複雜度,所以直接進入範例。

從最簡單的題目開始,1題:Two Sum,給定一個整數陣列,找出2個索引其對應的數相加為target。題目有點繞口,因為它是輸出索引而不是數值本身。

def twoSum(self, nums, target):

    for i in range(0, len(nums)): #以每個數為主角

        for j in range(i+1, len(nums)): #和其它的數加加看有沒有等於target

            if nums[i]+nums[j] == target:

                return [i,j]

上面這段code是一個最暴力最直接的解法,依序以每個數為主角,然後找其它的數有沒有和主角相加等於target的,有就直接輸出。分析LeetCode的解法時,我們只看演算法中重覆最多次的「步驟」,以上面的寫法而言就是第4行。若陣列有10個元素,此演算法的第4行總共被執行的次數是1+2+…+8+9=45次 ,若陣列有N個元素,第4行總共被執行的次數是1+2+…+(N-2)+(N-1)=N*(N-1)/2次,而第4行的if只要O(1)就能判斷,因此這個演算法的時間複雜度是O(N^2)。

等等,等等!我們之所以想要分析時間複雜度,就是想要在寫程式碼之前就知道這樣寫能不能過關,如果等到程式碼寫完才去分析不就晚一步了嗎?沒錯!所以實際上我們真的要分析的是尚未實作前的「想法」中的時間複雜度,也就是「依序以每個數為主角,然後找其它的數有沒有和主角相加等於target的」的時間複雜度,這個想法中最重要的概念就是「檢查所有的兩兩成對的數對」,數對總共有\binom{N}{2} 這麼多,這樣的時間複雜度就是O(N^2)了。

但是要能這樣快速地以更高的層次來分析一個想法的時間複雜度時,對想法中的細節要非常清楚。必須清楚了解怎樣才能算是一個「步驟」?對電腦來說,執行一道CPU的指令就是一個步驟,一道CPU的指令能做的事不多,例如讀取或寫入某個記憶體位置的值,比較2個值的大小,加減乘除等等。但寫高階語言時,需要搞清楚高階語言的一行程式碼背地裡是否偷偷藏著一個迴圈或是其它繁雜的動作。

第一個馬上可以探討的問題是,為什麼第4行是O(1)?加法、比較相等很容易理解,因為這是CPU的基本指令。但nums[i]是O(1)嗎?沒錯,因為nums是python中的list,python的list其內部實作是動態陣列(dynamic array),動態陣列取索引位置的值只要O(1)。

注意,python中最常用的資料結構就是list和dictionary,了解python的list是動態陣列這件事是重要的,否則很可能會誤判其它操作的時間複雜度!

例如:

if k in nums: # 查nums裡面有沒有k這個值

    print("k is in nums")

    nums.insert(0, 123) # 在nums的索引0的位置插入整數123

若nums中有N個整數,這裡的第1行和第3行,其時間複雜度都是O(N),如果以為是O(1),寫LeetCode很容易就Time Limit Exceeded。所謂的動態陣列,很像是一般陣列,其元素是一個接一個排在記憶體中,當你問k有沒有在nums裡面,python就會一個一個檢查nums中有沒有元素是k,也就相當於N個CPU指令,因此第1行是O(N)。那第三行不就在最一開頭前面加1個整數就好嗎?怎麼也會是O(N)呢?這個就要講得非常細了,動態陣列中除了那些連續放置的元素之外還有其它資訊,例如現在元素數與容量等。

其它資訊元素0元素1最後的元素預留空間預留空間…

通常各語言內部實作上都把其它資訊放在最前面,接著才是元素,最後面是新增元素用的預留空間,在「其它資訊」的前面和「預留空間」的後面都是給別人用的,因此動態陣列只適合從後面增加元素,在前面insert就需要把要插隊的位置的後面所有元素往後推一格,越靠近前面insert就越慢。

如果有人問「預留空間」後面是給別人用的,那如果我一直insert把預留空間都用完了怎麼辦?這是一個非常好的問題,答案就在動態陣列的實作方式當中。把相關的問題都追究下去會是不短的篇幅,有興趣的人可自行Google。

下方是第一題的另一個解法,基本的想法就是每看過一個數a,就去查target-a是否有被記錄,有的話就輸出答案,若沒有就連同其索引記錄在一個dictionary中:

class Solution(object):

    def twoSum(self, nums, target):

        table = {} # dictionary,存放「數=>索引」的鍵值

        for i in range(0, len(nums)):

            a = nums[i]

            b = target - a

            if b in table:

                return [table[b], i]

            table[a] = i # 加入到table中,a這個key可能已經有了,但對此題不影響

這個寫法只有一個迴圈,但重點是第7行查b有沒有在table內,和8~9行table[b]與table[a]的時間複雜度是多少?Python的dictionary實作方式是hash table,hash table的查找和加入都是O(1),所以這3行都是O(1),這整個解法時間複雜度就是O(N)。

有人也許開始感到疑惑,不論查找和加入,怎麼dictionary(hash table)都比list(dynamic array)要來的快,那我就都用dictionary就好了呀?事實上,雖然時間複雜度看起來都一樣O(1),但list的nums[k]會比dictionary的table[k]要來的快很多!有時候用list可以過關的code,改成dictionary硬寫是有可能變Time Limit Exceeded的,而且用list時可以做sort、slicing等等,所以2者還是要有所選擇。

同樣地,我們完全不用實作出程式碼再去分析,「每看過一個數a,就去查target-a是否有被記錄,有的話就輸出答案,若沒有就連同其索引記錄在一個dictionary中」這個想法就足以分析,nums中的數都看過1次,每看1次就是做查dictionary和可能加進dictionary,整個解法就是O(N)。要能分析地這麼快的前提就是對常用的資料結構非常熟悉。

注意一點:嚴格來說,hash的查找和加入不真的是O(1),因為它可能會有collision的問題,但寫LeetCode時就當它是O(1)吧。另外,並非所有關聯陣列(如python的dictionary)都是用hash實作,C++中的std::map內部是以紅黑樹實作,查找的時間複雜度是O(lgN),而紅黑樹有其優點,它的內部已經依鍵值大小排序,若需要快速找到一個range中的鍵值,使用紅黑樹是較為方便的。

動態形別語言的AND與OR

以下只是我個人的觀察

  • 邏輯運算子都有考量Short-circuit evaluation,動態形別的語言其邏輯運算子AND與OR會回傳第一個可確定expression結果的值。NOT運算子則一樣回傳布林值。
  • # python
    result = "ABC" and (1+5) # result is 4
    result = "ABC" and (1+5) and None # result is None
    result = 0 or None or 5>10 or "XYZ" or True # result is "XYZ"
    
    // javascript
    alert( null || 1 ); // 1
    alert( null || 0 || 1 ); // 1
    alert( undefined || null || 0 ); // 0
    alert( 1 && 0 ); // 0
    alert( 1 && "ABC" ); // ABC
    
  • 待續

軟體設計 (四)語言與表達

(網路上看到的非常好的一篇文章「程式語言沒什麼好學的?」)
(這也許要等我寫更多的程式語言之後再來寫這篇會比較適合,但先紀錄目前的部份想法,這一篇會開始講到程式語言的語法特性,如有錯誤請不吝指教)

各國的語言都有不同的特性,從我以中文為母語的角度來看,英語句子有各種時式,假設語句可以明顯表達出有可能的和不可能發生的,日語有各式各樣各種程度的敬語,法語的名詞多有性別之分,這些都是語言特性。不同的語言在表達同一件事情時有不同的方式,但如果該語言本身沒有類似的概念,就會變得很迂迴,例如要用英文表達中文裡學長、小吃、熱鬧、默契……等等,並沒有簡單的字彙可以直接使用。

程式語言也是如此,不同的語言有不同的適用範圍與不同的表達方式。例如想要寫一些簡單小程式parse一些檔案,那麼用c++可能會比python、perl等多寫好幾行。想將相關的資料與動作放在一起,寫出物件導向的程式,如果用C語言來寫,可以寫出類似的概念,但寫法上不是很方便。如果想要表達某個東西在初始化完成了之後就不會改變,python因為沒有c++的const,很難表達這個概念,python class中的function也沒有分public與private。注意這裡所說的表達力是語言內建的功能,一旦寫錯compiler就會回報錯誤,而不是一種大家同意的約定(convention),約定只是靠著額外的人力去維持正確性。

不同的程式語言有不同的特性,大家的喜好也都不同,喜好這件事是很主觀的,我也來談談主觀上的愛好,因為最熟悉的是c++與python,下面列出我認為c++優於python的一些特點。

  • 速度快,不做多餘的事,甚至可以細緻到用union或bit field節省記憶體,看程式碼的時候可以直接想到在記憶體中的配置情形,讓人擁有對程式碼速度與記憶體用量的直覺。
  • 宣告式靜態形別語言。所有變數都需要宣告,如果沒有宣告就使用會出現compile error。使用變數時形別必須正確,同樣也使得一些打字錯誤可以在compile time時直接檢查出來。
  • 可以表達出「不可變」的概念,如c++中的const關鍵字,這個資訊對於變數的定義影響重大,例如
    
    int apple_count = get_apple_count(plate);
    
    
  • 這一行的意思是取得盤子上的蘋果數,但apple_count是否會再變動呢?也許之後會再把其它盤子上的蘋果累加進去,但光看這一行我們無法得知,因此apple_count的定義並無法馬上確定,它的定義和後面程式碼的邏輯產生耦合性。如果是
  • 
    const int apple_count = get_apple_count(plate);
    
    
  • 我們可以立即確定apple_count為plate上的蘋果數,而不用去懷疑它是否為一個計算中的數值。因為「不可變」比「可變」更加安全,現在許多新的語言,變數預設是不可變的,如果希望它可變還需要多打一些字,如Rust的mut。c++的const還有許多使用方式,例如可以利用const來表示一個member function不會改變該物件的內容。
  • 支援物件導向的寫法,並有compiler幫忙保證區分public與private,使得介面一目了然。
  • 支援泛型設計,可以在編譯期知道型別資訊產生效率更高的機器碼。(c++的泛型博大精深,我只使用最基本的)

Python的語法簡單直覺易記,又有非常多好用的第三方模組,通常我會使用Python來寫一些幫助工作的小程式。

大多數軟體設計的思維是通用的,如果已經學了一門語言,那在學其它新語言時,只要查尋新語言相對應的表達方式就能寫出程式。通常最先接觸的是程序設計的基本程式邏輯元件,如基本型別、陣列、條件判斷式、迴圈、函式、自訂型別……等。接著依據各種語言會學到較進階的物件導向、泛型、泛函編程等思維方式,這時有機會從中領略出一些通用的概念,因此學習一種新的語言很可能會提升整體的程式設計能力。

無論使用哪個語言都要追求定義精確與鬆散耦合。深入學習一門語言(或是框架)除了使用有趣的語法糖之外,更重要的是體會到它整體的設計哲學與表達方式,從其中領略出一些通用的概念,我認為這才是學一門語言最重要的事。

(個人才疏學淺,這只是目前的體會,等以後學了rust、haskell等,有其它心得再多補充一些內容)

軟體設計 (二)耦合性與權責

耦合性

所謂知識的耦合度,我想最簡單的解釋就是「想了解某件事時,需要研究清楚其它相關事情所需要的努力」,如果相關的事情很多,耦合度就高。舉幾個例子:

  • 定義篇中提及的isFullScreen、isFullScreen2,想知道isFullScreen是什麼,那要看看isFullScreen2,想知道isFullScreen2是什麼,那要先看isFullScreen。這2個必須一起看才有意義。
  • 程式中用了一堆可被讀寫的全域變數,這些全域變數把所有涉及到它們的程式碼全部關聯在一起,必須要對這些全域變數在各處的影響與變化才能徹底了解相關的程式碼。
  • 一個龐大的物件中塞滿各種成員變數,成員函式都隨意地讀寫這些變數,所以其本質也跟全域變數一樣了。
  • 冗長的函式加上程式碼隨意命名,並且也沒有任何文件,無法看出用途,後繼的維護者必須從前後文的邏輯來推敲其目的。
  • 有一個難以想到的bug,當時只以workaround的方式處理,沒有在程碼中下註解,沒有加進迴歸測試,從命名與邏輯也看不出道理,幾乎只有問人才知道,這使得code和人之間產生了耦合。

這些例子,有些屬於個人的看法,例如我認為code和人也能產生耦合,這往往是很糟糕的狀況,代表要看懂某段code的代價極大,必須要請教某個人,如果當初的設計者離開了呢?若從wiki上看程式的耦合性,其定義指的是模組之間的關聯性。但我認為程式碼即知識的抽象形態,廣義的耦合可包含我所舉的例子。

除了定義和命名之外,寫程式的一大重點就是解除耦合,因為閱讀耦合性高的程式碼人腦的負擔很大。寫程式是為了讓電腦解決問題,有時問題本身就很複雜,其子問題互相牽涉。然而在程式中,我們仍然要盡力減少耦合,這也是程式寫得好或不好的一大區別。想必軟體工程師都有經驗,一個同樣目的、500行的小程式,有人用了一堆全域變數,寫出超長的函式,有人卻可以寫成許多小物件與函式,權責分明,邏輯清楚。

軟體設計中最基本的、具有最低耦合性的單位是「Pure Function」,這樣的函數其輸出完全取決於參數,相同的參數必可得到固定對應的輸出,與外部完全絕緣,只要了解其中的程式邏輯就完全掌握這個函數。以LeetCode為例,其大部份的題目都可以寫成Pure Function。從Pure Function的概念出發,寫程式時應該儘可能減少「類全域變數」的使用,這包含真的全域變數以及不必要的物件成員。通常物件成員應該要是物件狀態的一部份,絕不是一個懶得傳遞參數而加的東西。

處理耦合問題,如果從小地方來看,就是上述所說的函數與小物件的範疇。放大到更高的層次來看則變成了物件與模組的權責劃分。

權責

權責和定義(或規則)不同之處在於權責是更概略地描述事物,它具有某些程度的模糊性,規畫得越好,模糊性就越低。權責劃分很像是規劃一個公司甚至政府機關各個部門的運作,如果權責劃分不好會發生以下情況:

  • 很難說清楚一個部門主要在處理什麼,它很可能處理各種五花八門的事情。
  • 各部門之間的關係很模糊,一件事情不知道是哪個部門處理。
  • 各部門都需要不斷互相溝通,互相干涉對方內部的事物。
  • 部門容易受到外部干涉,所以內部小組一有小變動就出錯。

上述用詞中的「部門」只要改成「物件」或「模組」,「小組」改成「函式」,就變成高耦合的軟體結構。

要避免高層次的耦合需依靠謹慎的事前規劃。設計模式中有個觀察者模式是個很好的解耦示範,以一個GUI設計為例,假設現在畫面上有5個widgets,另有6種事件,每個事件會更新2-5個widgets的狀態,我們當然可以為每個事件撰寫widgets的更新方式,這樣code的複雜度是O(6*5)(當然,這是假想上的複雜度),而運用觀察者模式,在事件與widgets中間加上一個協調的角色,code複雜度會變成O(6+5)。從觀察者模式中可以看到一個很實際的去耦合概念,當2個結構形成乘法的複雜度時,可以設法在2者中加上一層中介,看看能否將複雜度從乘法降為加法。

然而,軟體需求與結構千變萬化,去耦合這件事沒有一個萬用的技巧,通常是不斷思考加上從別人的巧思中慢慢學習與體會。

附-知識耦合的個人看法

知識耦合我會把它分為2種:先備與密合。先備就是學習某部份的知識時,要先具有的背景知識,例如要學代數運算,基本的加減乘除是一定要會的,要參與stackoverflow的討論,一定程度的英文讀寫能力是必要的;密合則代表一群緊密相關的知識,無法各各擊破,必須要一口氣全盤了解才能繼續進行,在理解之前必須記憶許多相關的事物。如果從資料結構中的圖(graph)來做類比,先備的結構很像是Directed Acyclic Graph(DAG),而密合就像是Complete Graph,密合關系所形成的知識結構要比先備關系更加難以了解。知識的結構也並非單純是先備或密合,往往是兩者交織而成。

軟體設計 (一)定義與命名

想要以一系列的文章來紀錄自己對軟體設計的想法,第一篇就來談談定義這件事。

定義

在學習一項知識時,我們一定要了解用來闡述此類知識所用的文字。閱讀程式碼就像是學習一門知識,學習者絕對不希望其中的文字艱澀難懂,因此在寫程式時,最重要的就是讓程式碼中所使用的文字定義簡單明暸。例如:

  • num_view 影片的觀看次數
  • stock_value 現有股票的市值
  • calc_letter_count(letter, text) 計算字母letter在此字串text中的出現次數

我們不希望看到很複雜的定義。例如:

  • half_income_or_zero 當本月收入為正時,是本月收入的一半,本月收入為負時,是0
  • calc_what(integers) 當integers中有0的時候,回傳0,都為正時,回傳當中的最小值,都為負時,回傳最大值,有正有負時,回傳總和

如果真的定義出這樣的東西,除非為了效率或是其它考量,否則一定要想想是否有更好的表達方式。以上面的calc_what為例,它其實是在求和或是找出和0最接近的數,那麼程式流程中能不能改用2個動作calc_sum和get_mindist_to_zero來表達呢?

再次觀察定義的結構,「令x為樹的數量」,可以看到它分成2個部份,「x」與「樹的數量」,我們之所以這樣定義,是因為我們思考某個問題時發現需要「樹的數量」這個概念,它是思考的主體,通常我們會用自己慣用的語言來表達,而「x」只是代表這個概念的符號,這個例子中,兩者都是簡單的。但在程式碼中,前者也可能變成很複雜,使得它不只是一個名字。因此,程式碼中複雜的定義大致可分成2種,一種發生在符號的部份,另一就是定義本身。

符號複雜的例子

一個影片播放器的影片畫面大小有3種模式:

a. 原始視窗大小

b. 填滿整個螢幕的大小,長和寬不維持等比例

c. 填滿整個螢幕的大小,長和寬維持等比例,無法填滿的部份留黑

以下是在程式中用2個bool變數來定義的方式:

令m1為false且m2為false時為模式a

令m1為true且m2為false時為模式b

令m1為false且m2為true時為模式c

這樣的定義方式很難說明m1、m2分別是什麼意思,兩個必須要一起看才能有完整意義。m1、m2的組合有4種,難道有4種模式?不了解影片畫面有3種模式的人,閱讀程式碼時要花上許多時間才能知道。另外,兩者皆為true時未定義,這很可能是潛在的bug來源。

若真的要討論m2的定義,我們只能這麼說「當m1為false時,false表示模式a,true表示模式c,當m1為true時,false表示模式b,true則未定義」,這完全是把真值表口述一遍。

也許會認為怎麼可能有人這麼寫,但這是我在實際應用的專案中看過的程式碼!只是命名稍有不同(用的是isFullScreen、isFullScreen2)。在該專案中,原本模式只有a和b,當時只用了一個布林變數即可,它剛好對應2種模式,然而隨著專案的變化,加了模式c後,開發者為了時程趕工,覺得多加一個布林值來改就好,程式碼即變成如此,m2的加入,破壞了m1的定義,使得m1、m2要一起看才具意義,隨著程式的發展,m1、m2開始變成許多函數的參數。

注意這裡並不是m1、m2的命名問題,分別改2個名字不管怎麼改都不可能成功,這是因為符號使用上出現了問題,在這個例子中並不適合用2個變數來定義3個模式。我們可以用許多語言都有的enum來表達這3種模式,例如enum VideoSizeMode {WINDOW_MODE, FULL_SCREEN, RATIO_FULL_SCREEN},用video_size_mode這樣的「符號」來代表3種模式。

定義本身複雜的例子

當我們在向別人解釋一段程式碼的時候,符號的部份我們可以用自己的語言解釋,以上面影片播放器的例子為例,我們很可能只要講模式abc即可,它只是發生在轉換成程式時,用了糟糕的符號來表達定義,定義本身是很好解釋的。但如果定義複雜,很可能是寫程式的人當時就以非常迂迴的邏輯在思考,又或者是這個要解決的問題本身就真的這麼複雜。

除了本篇文最開頭的例子以外,下方再舉個實際專案看過的例子,看不懂也沒關系,因為它就是這麼讓人看不懂!

「有一個Searcher物件內有一個2D地圖,地圖上的每個格子只會有valid和invalid兩種狀態,設計者提供2個函數介面。一、get_valid_loc:讓使用者傳進一個矩形區域和一個中心點,然後回傳矩形內離中心點最近的valid格子。二、get_alt_valid_loc:其用法是在使用get_valid_loc前先呼叫Searcher的find_alt_loc,接著再呼叫get_valid_loc,最後就能使用get_alt_valid_loc,get_alt_valid_loc並沒有參數,最後的效果是當get_valid_loc有找到的話,get_alt_valid_loc會回傳一樣的位置,如果沒有找到,它會回傳一個矩形外的valid格子。」

當初設計這2個介面的人或是為了加快速度,或是趕時程,所以設計出這麼奇怪的get_alt_valid_loc定義,你可能看了許多次都看不懂上面那段文字再說什麼,更不用說只能從程式碼來理解get_alt_valid_loc目的的人有多麼疑惑了!

我們不可能避免複雜的定義,但是定義出複雜的東西時一定要想想,這樣的複雜性是必要的嗎?還能再簡化嗎?這是絕不可免的思考過程。

定義之上──規則

從數學的角度而言,定義就是規則。但在此我們就以日常生活用語來看待規則,規則是將事物運作的法則經過整理與歸納進而去蕪存菁的結果,它是從定義發展而來的更上層的結構。規則是必要的複雜定義,它也與程式語言無關,每個人的想法不同,觀察與制定出的規則也會不同。

有玩過桌遊的應該知道某些會有擴充版,其新道具通常都會和基本版的道具有所關聯,因此說明書一定要詳細說明新舊道具之間的組合效果,擴充版越多,就需要越多的規則。規則的設計是極具巧思的,以「Bang!」這款知名的桌遊為例,為什麼遊戲流程分為「第一階段『摸2張牌』,第二階段『使用手牌』,第三階段『丟棄手牌』」?而不是簡單地說「摸2張牌,使用手牌,多的丟掉」?這是因為遊戲中的其它元素,使得各個玩家可以在別人使用手牌時觸發一些事件,可能摸牌或丟牌,如果沒有嚴格定義出第一、二、三階段,規則的描述會非常混亂,甚至每個玩家對規則的認知不同,使得遊戲發生某個事件時無法繼續進行。

並不是每款遊戲都能把規則定得清清楚楚,許多手機遊戲為了留住玩家,每一至二個月就會更新遊戲新增角色,常常玩家組合了不同的角色技能就產生bug,而且從遊戲內的技能描述也無法肯定效果到底是什麼,以致於玩家是用「試」的來了解遊戲中的新元素,幫遊戲設計公司debug。

遊戲規則的訂定到底是由企劃部來執行,還是企劃與工程師共同製作,依各個團隊而有所不同。然而身為軟體工程師,其實我們每天都在製作規則,每個函式、物件的使用方法都是一種規則。規則訂得不好,使用者研究了老半天還是不知道怎麼使用,隨便用就crash。清楚的規則並非一蹴可幾的,即使是一些知名的函式庫,在每次的大更新中,也會有更加優化的方法取代舊的,但至少我們應該在每次的軟體變動之時,以制定規則的思考方式來撰寫程式碼。

定義的一致性

程式中往往有許多變數是在計算完才符合其定義,例如x為100年10月1日當天全班參加羽球社的人數,依定義它是一個固定不動的值,但為了計算x,我們可能掃過當天全班學生的狀態,並累加到x中,在計算完畢之前,x的值並不符合定義,這段時期它可能造成別人的錯誤使用與誤會。我們不可能完全避免這種事情發生,但有些方法可以儘量彌補,可以定義一個生命週期較短的東西來代表這個會變化的過程。例如將計算這件事放在一個函數中,將x的值設定為此函數的結果,函數中雖然也有一個累加的計數器,但它的生命週期在離開函數之後就消失了,這樣的做法可以確保x一旦被初始化即符合定義。

另外有一種定義的變化是完全不必要的,例如「x在執行到這裡之前是降雨量,到了這一行變成是溫度計的攝氏溫度,再然後被指定成了空氣品質指數」,想必許多人都看過數百行甚至破千行的函數存在類似的變數,如果程式碼寫成這樣,那完全是個災難。

命名

定義是我們理解事物與互相溝通的基礎,清楚的定義是最重要的一步。腦中有了清楚的定義,再去想合適的命名,若定義本身就有問題,是不可能會有一個好名字的。就如同前述的m1、m2、GetAltValidLoc,怎麼樣的命名能夠表達出m2的意思:「當m1為false時,false表示模式a,true表示模式c,當m1為true時,false表示模式b,true則未定義」?沒有,不可能有。

定義若想好了,那就要給予一個好的命名,命名在程式碼中極度重要,閱讀程式碼的人是從名字、前後文、注解或文件去了解該名子的定義。沒有人想要花上數個小時,最後發現原來x、y、z的定義原來只是簡單一句話就能講完的東西。名字取得好,可以讓人立刻想到其意義,絕對可以大幅增加程式碼的可讀性,並為後續的維護者節省大量的時間。

有個判斷命名是否適當的基本方式,就是假設自己在對別人解釋,如果一個變數解釋很久,別人還是搞不懂,那就是定義複雜,如果聽得懂所講的,但一看程式碼中的名稱想不到是指這個東西,那就是命名的問題。

而名字可長可短,到底要取到多清楚呢?這與前後文有關。例如「壞掉的玩具數量」,那麼取名就應該是broken_toy_count。是不是一定要講得這麼完整?若只要講「壞掉的」別人就聽得懂,從可讀性而言取名為broken就可以了,因為當講「壞掉的」就可以讓人聽懂,表示前後文沒有讓人混淆的其它名詞。如果前後文有壞掉的文具,或是壞掉的家具數量,那別人會不懂「壞掉的」到底是指什麼東西,甚至不知道是指東西還是數量。但這裡要注意的是,如果使用一個較短的命名,未來擴充的時候也很可能要跟著一起改,因為後來加入的code,很可能使得原本的短命名變混淆。

生活中我們常常可以發現有人很習慣使用代名詞講話,用詞充滿了「它」、「這個」、「那個」,或是愛用很籠統的詞彙,這種習慣若帶到程式中,很容易寫出模糊的程式碼。

命名有許多小細節。在數學的語言中,通常不會把變數名稱寫得很完整,而是用一個簡單的符號做代表,原因之一是簡單的符號容易表達出數學中美妙的對稱性(另一原因是數學建模完成後,更在意其性質,而不需管代數的實際意義,再者程式中所用到的變數名稱多太多了)。但程式中若像數學符號那樣命名,很容易就會出錯,若出現相對稱的事物,有一種程式風格是以較短的名稱並搭配上清楚的註解,然後將相關的符號與邏輯並排在一起,例如要表達「現在的XXX」和「之前的XXX」,很可能會使用curXXX和preXXX,讓其字母數量相同而方便對稱排列,而不會寫成currentXXX,previousXXX。另外也要考量到命名相似的問題,如data與date、rectangle_center_x與rectangle_center_y,如果一個scope中有2個以上長的很像的變數,那麼看錯的機率會大幅提升,撰碼時要注意視覺上容易區分出不同的變數。

命名也有些通則,例如一般變數必須使用名詞,函數要使用動詞……等等,有的軟體公司會有自己的命名準則,規定一些常用的縮寫、prefix、suffix等等,使得開發團隊相互之間能夠更快地理解程式碼。

範例

許多人在定義變數或函式時,心中的想法是簡單的,聽他解釋時沒問題,但如果看寫出來的程式碼,總是與想法有差異,以下都是我在實際應用中看過的,只是稍微簡化與改名。

例子1


int get_min(MyIntArray int_array) {

    int ret = INT_MAX;

    for (int v : int_array) {

        if (v <= 1) return 1;

        ret = min(ret, v);

    }

    return ret;

}

這個函式的目的是什麼呢?從名字來看是要取最小值,但遇到不超過1的值時就立刻回傳,它真正的完整意義是:「若int_array是空的,回傳INT_MAX。若元素都大於1,回傳所有元素的最小值,否則回傳1。」這麼複雜的函式定義是很難取一個相符的名字的,設計者當初為什麼要這樣寫呢?可能是用到的地方其元素大小至少會是1,為了不浪費時間看過所有元素,所以看到小於等於1的就回傳了,這種專為caller的特殊用途而寫的函式,很容易造成未來的維護問題。

例子2

想要表達做某件事的步驟依序是做A,做B,做C。


void do_A() {

    do_B();

}

void do_B() {

    do_C();

}

void do_C() {

    ...

}

使用時呼叫do_A即可,確實是A做完做B,B做完做C,結果完全正確。但這整個設計是很有問題的,首先3個函式名應該為do_ABC、do_BC、do_C才符合定義,再者,當我們思考某件事有ABC三個步驟時,是因為這3個步驟應該同等重要,它們應該像是寫文章時的三個段落,所以,這幾個函式應該要這麼寫才對:


void do_ABC() {

    do_A();

    do_B();

    do_C();

}

void do_A() {

    ...

}

void do_B() {

    ...

}

void do_C() {

    ...

}

如果ABC是某做某些事(something)的三個步驟,那麼應將do_ABC改成do_something。

例子3


void do_something() {

    if (is_some_condition()) {

        ...

    }

}

函式名稱意指要做某件事,但函式內容表達的是符合某個情況才真的做這件事。這是非常常見的形式,通常這發生在軟體需求改變的時候,原本函式是一定會做這件事,後來變成要條件發生才做,設計者認為改在caller的地方不如函數內加一行條件式,於是就變成這樣了。有時候我們會命名為do_something_if_needed,名字很長,視覺上會讓人認為這函數很重要,是不是真的重要並不一定,但這命名真的符合函數的意思,命名是否要如此就自己權衡了。

結論

定義與命名是軟體設計的基石,同時也表達出設計者的思考方式,設計者會為了描述一件事情,而定義了一些東西,不同的設計者因為理解方式不同,定義出不同的東西與不同的命名。「影片大小模式」這樣的詞彙是我對於那3種模式的理解,到底是不是要稱這3種為「模式」?重點是不是「影片」與「大小」?其它人可能有不同見解,也許有些人會覺得是「畫面比例模式」,有的人覺得是「顯示方式」,而使用了不同的名稱。每個人的理解方式都有些差異,但最重要的是定義與命名簡單明暸,能夠讓人看出所要表達的概念,怎樣的定義和命名是好,這是必要的思考過程,是軟體設計基本的第一步。