---
hackpadID: 3K44Ldi1lyW
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# DS 讀書會 - 第 4 週

12/09/2014

[« 回首頁](/JwdmDZwMwE3BacBGApgDngFkwYx/NAVjQxlgCZgkdo0AjNIA)

## 討論範圍

* Analysis
* Objectives - An Anagram Detection Example

## 預定進度

* Big-O 兩題練習題
* Analysis
* Performance of Python Data Structures - Programming Exercises

## 認領狀態

* Lists
* Wen00072
* Dictionaries
* StarNight

## 心得筆記

**What is Algorithm Analysis?**

* 如何分辨演算法好壞、優劣？
* 要先定義好壞的條件。如果我們說點好的演算法會節省電腦資源的話，需要再定義
* 什麼是電腦資源？
* 省CPU資源，表示最短的時間把工作做完。換句話說，速度快。（時間複雜度 ）
* 省電
* 省空間（空間複雜度）
* 記憶體空間
* 儲存空間
* ...
* 定義了感興趣的資源，還要定義及量化精確客觀的資訊「品質」
* 以省CPU的資源為例，也就就是速度快的話。第一個想法就是，量測程式碼執行時間。我們可以想一下，這個精確可靠嘛？同樣的演算法，有沒有可能每次結果會不同？是會的，隨便列就可以列出幾個因素
* 軟體執行環境
* 電腦內同時跑其他Process的數量，以及他們消耗的資源。
* 同時播放多個HD影片時跑和沒有播放時去執行演算法。
* 不同Compiler的影響。Compiler A有使用執行CPU加速而Compiler B則無。
* 作業系統差別，不同的作業系統可能針對process有不同的排程策略。
* Cache影響。
* 是否被swap out?
* IO影響？
* ...
* 硬體執行環境
* CPU
* 不同電腦CPU時脈不同
* CPU指令集不同
* Cache影響
* IO效能
* ...
* 顯然以上的方式來看，計算執行時間並不是個精確客觀的方式。
* 除了要定義客觀精確的品質因素以外，這個品質因素最好還要能夠顯示出演算法複雜度和處理資料數量的關聯性。

**Vim plugin: Python Mode**

請參照 [Python 開發環境設定](/GYdhCYFNwNhhaADAYwCwFZ6ssAnPAI1WWHhAA5dIBGXAQzvV1CA=)一文。

**Big-O**

* [Notes for Big-O](http://nbviewer.ipython.org/github/dboyliao/TOSSUG/blob/master/DS/Big_O/Tossug_Big_O.ipynb) by [DboyLiao](/ep/profile/t8QgcYLgWLS)
* [dockerhack2014 (Teaching Platform)](http://dockerhack2014.opennote.info/)

* dockerhack2014 現已改為 [](http://agilearning.io/)http://agilearning.io/，但我無法登入，有人可以登嗎？

[Implementing Breadth First Search](http://interactivepython.org/runestone/static/pythonds/Graphs/ImplementingBreadthFirstSearch.html)

[The Merge Sort](http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html)

* Big-O 提供一種更為客觀的評估方式，不受硬體和執行環境影響。
* Big-O 一般來說都是估最緊的上限，否則就是低估演算法的效能。
* 有 best case, average case 和 worst case，並且受到資料量影響。
* 在解決一個問題時，可先試暴力法，驗證後找出瓶頸，調整做法。
* numpy 可以跑 regression，猜測該演算法的複雜度，並且畫出來。

IPython Notebook 有兩種方式支援簡報模式：

* [安裝 slidemode extension](http://nbviewer.ipython.org/github/fperez/nb-slideshow-template/blob/master/install-support.ipynb)
* 透過 NBConvert 轉換
* ipython nbconvert --to slides --post serve notebook.ipynb

練習題：

* BFS 演算法用了 while 迴圈，試評估其 Big-O。
* Helper 產生的是有序 graph，設法與 BFS 對上。

**An Anagram Detection Example**

[演算法分析：解讀易位構詞偵測](http://slides.com/tedwu/ananagramdetectionexample)

[Ted Wu](/ep/profile/xo5A62wXl3B) 的暴力解，至少 O(2^n)：

[AnagramDetectionBruteForce.py](https://slack-files.com/T02V6GR30-F034C8PF5-f22c3f)

Quick fail 減輕比對失敗的挫敗感。

[Carl Su](/ep/profile/n5euV0AaWLn) 的排序解：

* def anagramSolution2(s1, s2):
* return (len(s1) == len(s2)) and (sorted(s1) == sorted(s2))

* 這是還沒看到教材前想的解法，其中 `sorted()` 函式會直接回傳新的值，不會去改到原來的值。
* 因為python中str有實作iterable所以不用先轉成list也可以直接丟進去sorted()。
* 真的耶，沒注意到可以不必轉成 list，已更新。

## 活動簽到

[Carl Su](/ep/profile/n5euV0AaWLn)

[DboyLiao](https://tossug.hackpad.com/ep/profile/t8QgcYLgWLS)

[FourDollars](/ep/profile/tgNQRpN8EgG)

[Jonathan Hsieh](/ep/profile/v2IkzygwDuI)

[Kevin Chen](https://tossug.hackpad.com/ep/profile/t1WzUr1rPTe)

[Manuel Stallman](https://tossug.hackpad.com/ep/profile/GgkcGJEol5r)

[Scott Yu](/ep/profile/FXMAg851dkz)

[StarNight](/ep/profile/sDJQZaRfOhF)

[Ted Wu](https://tossug.hackpad.com/ep/profile/xo5A62wXl3B)

[Wen00072](/ep/profile/H12yKD7rYmT)

高顯忠