Lt的學習日誌

剛接觸Python的時候著實為iterator、iterable、generator所困擾 且一開始從官網下載安裝的就是Python3，但在摸索的過程中又看到了許多Python2的文章 剛開始哪搞得清楚Python2與Python3的差別，試了許多Python2的範例常常都行不通 從C++轉過來的我又對Python的duck typing非常地不能理解與適應 讓我不禁納悶想問：是誰說Python簡單的呀？ 以下先總結我對這些名詞的認知(本篇文章內容都是針對Python3)： iterable ：中文翻作可迭代物，通常是一個容器、iterable實作__iter__方法回傳一個參考到此容器內部的iterator iterator ：中文翻作迭代器、iterator pattern在Python中的實作，為序列或容器型態提供一相同的介面讓客戶端可遍歷(iterate over)容器內的元素，iterator實作了__next__與__iter__方法，方別供next與iter函式呼叫，每個iterator同時也 是 一個iterable generator ：中文翻作產生器，是由包含yield敘述的函式或產生器表達式(簡稱genexp)所產生，支援所有iterator的操作以及額外的send方法，客戶端可透過send方法與generator溝通、影響其內部狀態 先舉個簡單的例子，請看以下的程式碼： >>>a=[1,2] >>>b=iter(a) >>>c=iter(b) >>>c is b True >>>next(b) 1 >>>next(b) 2 >>>next(b) Traceback (most recent call last): File " ", line 1, in next(b) StopIteration 從上面的例子我們就可以弄懂iterable與iterator的分別了 iterable指的就是容器 本身 ，將iterable傳進iter函式可以得到一個iterator iterator的操作非常簡單，透過next函式可以不斷取出下一個元素，抵達尾端時會

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)$的單位究竟是什麼呢