Coursera – Algorithmic Toolbox 第一週學習筆記

Welcome

  1. 演算法的運用隨處可見。
  2. 演算法是使電腦執行一系列的步驟以解決問題。
  3. 演算法除了必須正確解決問題,也必須考量時間、記憶體空間的使用效率。
  4. 學習演算法有助於實現有效率的各領域應用程式。
  5. 本堂課除了講解演算法背後的理論,也會指定作業讓學員根據自己選擇的程式語言實作演算法。

Solving a Simple Code Problem

  1. 本堂課必須實作一些演算法,使學員對演算法的理解更加深刻。
  2. 提交的程式碼會被執行一些自動化測試項目,學員可以得知測試結果。
  3. 線上系統會根據提交的檔案副檔名,判斷該檔案所採用的程式語言。
  4. 自動化測試項目支援多種程式語言,因此學員可以用被支援的任一種語言進行實作,而課程本身會提供C++、Java、Python3的基本程式範例,採用該語言的學員可以此為基礎進行修改以完成作業目標。
  5. 為了使學員在本地端的執行測試結果和遠端系統的測試結果相同,各語言在本機端編譯、執行程式所下的命令列指令,需要包含課程所指定的參數。
  6. 藉由實作、提交一個簡單的程式碼(回傳兩個input數值相加後的結果),以熟悉建置的開發環境、Debug程式、上傳作業到線上系統的流程。

Solving a More Challenging Code Problem

  1. 完成作業Maximum Pairwise Product:在輸入的一系列數值序列中,序列中任兩者相乘可取得的乘積,找出最大的乘積數值為何。將發現:
  2. input的數值序列項目過多時,基本程式因為採用了兩層的For迴圈,一一比較序列中任兩種數值的相乘結果,導致時間效能過低,需要修改演算法(改變解決問題的執行步驟),才可以有效提升時間效能。解決方式為:不採用兩層For迴圈,找出數值序列中的最大值、次大值,兩者的乘積即為結果。
  3. 兩個相乘的input數值過大時,將導致相乘的結果過大,使得原本用來放置相乘結果的int型態的變數產生integer overflow,使得相乘結果失真。解決方式為:將用來放置相乘結果的變數提升為long型態,可容許的數值範圍較大,可放置兩個input皆為最大值時的乘積。
  4. 在提交程式碼之前應進行一些手動測試、邊際條件測試(例如:輸入為最大值、最小值、相等值),確認程式的結果是否符合預期。此外,也可以進行壓力測試,步驟如下:
  5. 具有解決相同問題的兩個演算法,一個效率較低但確保答案正確,另一個不確保答案正確。
  6. 規範input條件後隨機產生input數值,並同時提供相同的input給兩個演算法進行運算,並比較兩者的運算結果。
  7. 使用While(true)持續在提供input給兩個演算法並比較運算結果,顯示input和output數據,當兩者的運算結果不相同時即藉由break語法中斷迴圈。
  8. 找到input數值較小但會產生bug的測試案例。
  9. 藉由較簡單的測試案例調整並測試演算法。
  10. 執行一段時間的壓力測試,皆沒有產生問題。
  11. 提交程式碼到線上系統。
  12. 這種壓力測試無法測出程式的時間和記憶體效能是否符合目標(time limit和memory limit)。
  13. 必須確保程式在"全部"的input狀況下,都能產生正確的output。
  14. “測試"程式是寫程式的基礎。
  15. 個人見解
  16. 這種壓力測試要運作良好必須有一個基本前提:必須先擁有一個可以根據input進行運算,總是產生正確output的演算法,以此作為另一個演算法的對照組。
  17. 因為input是根據某個規範條件下產生的隨機值,當input的可能數值範圍愈大時,想藉由隨機性壓力測試正確測出程式Bug的機率將愈低,所需的時間將愈久(而且不知道該執行壓力測試多久才算洽當)。因此教材中指出,可將input範圍更聚焦於特定條件(例如數值較大、數值較小)。
Advertisements

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s