Lt的學習日誌

C++11中最重要的改變除了lambda表達式外大概就屬右值參考與搬移語意了(move semantics) lambda表達式其實並沒有讓C++做到什麼原本做不到的事，嚴格來說他只算一個語法糖(syntax sugar)，只是這個糖果還滿大顆的 而右值參考與搬移語意，若使用得當是能讓牽扯到記憶體配置的物件，例如容器，使用效率有革命性的提升 先從最簡單的開始，左值與右值的名稱由來就是因為一個出現在assignment operator的左邊，一個則是在右邊 例如以下程式碼： a=1+3 a是左值，而1+2就是右值了 不過，用位置是在左在右來區分兩者也並不精確，例如，加上const修飾詞的左值不能出現在左邊 他們真正的分別是，左值為運算式結束後還會持續存在的非暫時物件，右值則為運算式結束後就不再存在之暫時物件 更深入地講，左值右值的概念並不只是侷限在指某個＂值＂，或＂物件＂，而是更廣義的 ＂運算式＂(expression) 那左值參考(以下簡寫為T&)與右值參考(以下簡寫為T&&)是怎麼來的呢？ 在舊的C++標準裡參考只有左值參考：T&，它是一種特殊的型態，每個參考都會綁定一個物件 可以透過參考所作的任何改變也會同步反應到其所綁定之物件，以T&作為函式的參數型態意味著傳進函式的引數不會被複製，而是直接將函式中的參考綁定到該引數上 我們都知道，C++函式接收引數的方式預設是以傳值參考(pass by value)，函式裡的變數實際上只是原來引數的副本而不是引數本身 使用參考可以省去複製龐大物件的成本，但需注意若在函式內改變了物件的狀態，那麼原本的物件也會受影響，因此若確定引數不該在函式裡改變的話我們通常會使用const T&作為參數型態 上面這些事其實使用指標也辦得到(除了暫時物件外，你不能對暫時物件解參考)，以傳遞物件的指標取代傳遞物件本身也可以避免物件的複製，但是會多很多*、&、->等運算子的使用，看起來就囉嗦了些 而真正只有參考做得到事情是自訂拷貝建構子 拷貝運算子指的是接收相同型態的另一個物件作為引數的建構子，即使在程式裡沒有明確地用到它，它也可能依然存在，例如從函式以值語意回傳一個物件時就會呼叫拷貝建構子 這時若你沒有實作自己的版本，編譯器會提供一個 而關

這系列是記錄我自己從MIT的開放式課程：Introdution to Algorithms中之所學 相信很多跟我一樣自學程式語言的人很常聽到人講：演算法跟資料結構很重要 但這兩個東西到底要怎麼學？隨便拿一本原文書都是厚厚一本，看完不知道要到民國幾年，而且也不知道重點在哪 看影音課程我認為是個比較好的方法，一來一堂課不到一個小時不會看到恍神，二來有真人講解比較容易理解與抓到重點 這個課程算是非常的淺顯易懂，講師由兩位教授輪流授課，兩位講解得都算很清楚，速度也不會太快 非常適合跟我一樣完全無基礎的人自學 雖然課程中有說他在這堂課使用的語言是Python，但其實只是偶爾會寫幾行這個演算法的Python實作出來，不懂Python也沒什麼影響 我的文章主要是把他每堂課中我認為的重點抓出來，以及補充一些我自己的心得 一些課堂上太細節的東西我就不會寫了以免模糊了焦點 那麼底下就開始進入第一堂課 課程連結： https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-1-algorithmic-thinking-peak-finding / 第一堂課沒有講到太多技術性的東西，所以我會花比較多篇幅介紹所謂的複雜度(Complexity) 首先講師提到了什麼是演算法 演算法就是處理一大群輸入資料來得到我們想要的結果的過程 一個演算法我們主要在意的有以下兩點： Efficient ：這應該很好理解，就是演算法的速度，另外也包含記憶體的使用效率 Scalability︰ 這個詞我想不到比較好的中文翻譯(Google翻譯為可擴展性)，意思就是當輸入資料的數量變得越來越多時，這個演算法的運作情況是否能一樣好，而不會不成比例的變慢 例如資料從一萬個變成兩萬個時，演算法的速度是不是只是從10ms變成20ms 另外我們評斷一個演算法的好壞時，常常用$T(n)$代表一個演算法的效率 $n$是輸入資料的數量，$T(n)$代表這個演算法的複雜度，複雜度又分時間複雜度(計算速度)及空間複雜度(所需記憶體空間) 那這個$T(n)$的單位究竟是什麼呢

在Python中，並沒有所謂的primitive type(原始資料型態)，所有資料型態都是物件 包括數值型態、字元、字串以及容器(list、dict等) 而所有的變數都是指向某物件的參考 值得一提的是Python中的函式實際上是call by value of reference，而不是call by reference 意思是說呼叫一個函式並傳遞參考進去時，函式裡的變數實際上是那份參考的副本而不是參考本身 所以你可以透過該副本改變參考所指物件的內容，但是在函式內將參考重新綁定到新的物件是對原本的參考沒有影響的 這點與Java的機制是一樣的 物件又分成可變(mutable)與不可變(immutable)，顧名思義不可變物件一旦創建後其內容就不能再改變 以容器為例，list、dict與set是可變物件，tuple與frozenset是不可變物件 若嘗試對不可變物件做+=或-=等運算，實際上是將參考綁定到一新的物件 與我們一般的認知：+=是改變原本物件是不一樣的，我們可以使用is運算子來測試 is與==運算子的差別在於前者是比較兩個參考是否綁定到同一物件，後者則是比較兩物件的內容是否相等 所以==回傳True並不代表兩者就是同一個物件 如以下範例： a=1 b=a #將b與a綁定到同一個整數物件 a is b True a+=10 a is b False 不可變物件為容器時，雖然其所包含的參考不能改變 但參考所指向的物件卻可以改變，聽起來好像很奇怪？ 看看以下範例： a=([1],[2],[3])#創建一個tuple，包含三個指向不同list的參考 a[2].append(5)#將第三個參考所指向的list增加一個元素 以上程式碼不會有任何問題！因為tuple裡面的參考並沒有被指向不同的物件 另外，在Fluent Python中提到了一個有趣的問題，請先看以下程式碼 a=([1],[2]) a[0]+=[3,4,5] 這段程式碼是否能正常運作呢？ 答案是：能！但也不能 解譯器會告訴你tuple物件不支援assign操作 但a[0]這個list會被成功地改變！ 關鍵在於第二行的執行次序是先對a[0]這個List執行+=操作 然後在將執行結果assign給a[0]，到這個動作的時候解譯器才會報錯！ 有興趣的人可以用d