Feb 23, 2016 課程紀錄

[2016q1 Week #1] [編輯共筆內容]

2016 年春季課程說明

你我為何在此?

建立對資訊的「品味」

Integer Overflow

為什麼程式開發者要學習歷史?

出處: Xiqiao

  1. 最早的中文字: 倚天中文
  2. 文字編碼規範: 

前進和成長

from 鄭伊廷 (@xdite)

「要一路前進,並不是一直去學新的東西。而是一直去改善以前自己做不好的地方,找「新方法」去修正。這樣就一直可以前進與成長。以及看到新的世界。不是一直開戰線「玩自己不懂的東西」,然後在同樣的地方一直死。」

《Revolution OS》的時代意義

The Evolution of Operating Systems

Tag: CTSS, Multics, Unix, BSD, Linux, Android, mbed

Abstract Data Type (ADT): the module’s state is manipulated only through its API (Application Programming Interface).

p.26 作業系統演進

早期: serial processing 軍事用途 (彈道模擬)

二戰期間,賓州大學和阿伯丁彈道研究實驗室共同負責為陸軍每日提供 6 張火力表,每張表都要計算幾百條彈道,一個熟練的計算員計算一條飛行時間 60 秒的彈道要花 20 小時。儘管改進了微分分析儀,聘用 200 多名計算員, 一張火力表仍要算兩三個月。這是電子計算機發展的迫切需求

p.27 分時多工系統

期望的硬體特徵

p.32 作業系統任務: 分配資源

「電腦科學」之所以不算是「科學」的緣故:先有明確工程需求和實作, 才有整理過的理論發表

p.34 CTSS: 多人多工

process 可定義為

p.42 process isolation, dynamic linking(模組化)

p.50 microkernel: 只在核心保留最基本的功能,其他搬去 userspace

負面案例: Microsoft Windows patch: font driver

p.62 hypervisor 實例:  big.LITTLE 中大核(CA15)/小核(CA7)之間互相切換(依功能需求切換另一個核心時會通知另一個核心開機並將當前核心關機), 但是切換過程中的interrupt (中間切換過程約需 200 us), 由誰來收 -> [sol] 在核心上增加一個 interrupt 處理單元

關鍵字: Linux: KVM, virtio

p.70 LInux system component

重點: system call, scheduler, memory management

面試題目分析

給定一個 singly-linked list 結構:

要求:初始化 10000 個 element,使其內含值為介於 1 到 10000 之間的亂數,彼此不重複

執行結果(以1~100示意)

效能分析

分析工具: Linux 效能分析工具: Perf

   

分析 : 由於每次random都必須在從頭在跑一遍看是否重複,若重複的話就在重新random,那在list越長的情況下重複的機率就越大,就必須不斷的重新random,因此執行時間將會變得無法預期

       

分析 : card shuffle algorithm複雜度為O(n*n) , 因此效率比方法一要好很多

延伸討論

(以下由 YouTube 工程師 YC 提供)

延伸提問:

 1. 除了linked list本身的佔用的空間外,若允許額外使用O(N)的空間,怎麼做較好呢?

可在O(N)內完成,典型的空間換時間。

 2.若允許額外使用O(log(N))的空間,怎麼做較好呢?(call stack的空間也算) 

先初始化linked list並填入1~N的整數。

再使用merge sort的變形,但不依靠比較大小,而以亂數決定順序。Pseudo Code連結

這個程式結構跟merge sort一模一樣,只是以機率取代比大小而已

worst case time complexity是O(N*log(N)),space complexity是O(log(N))用在call stack上。

機率部份的計算比較奇怪一些,這是為了讓N!種組合出現的機率都相同。

比方說left剩3個right剩2個時,應該要有60%的機率從left拿取元素。

 3.若僅能允許額外使用O(1)的空間,怎麼做較好呢?

我會使用方法二O(N^2)的方法。有任何其他想法嗎?

 4.方法一雖然不如方法二,其平均時間複雜度是多少呢?

這個方法的worst case time complexity是沒有理論上限的

就算是完美的RNG,理論上還是有可能連續連續出現同一個數字幾百萬次。

但是average case time complexity呢?

假設使用的PRNG夠亂(當作RNG討論),如果需要的平均時間能用一個算式model

應該就可以分析其時間隨資料量的成長趨勢。

* 先討論一個簡單的機率問題

重複做一件成功機率為p的事(每次機率皆為p,每次為獨立事件),一成功就停手

「做幾次會成功」的期望值是多少呢?

有p的機率會一次成功

有1-p的機率會在第一次失敗,然後再需要E次嘗試才會成功

設此期望值為E,可列等式E = p + (1-p) * (1+E)

化簡後可得E = 1/p,次數的期望值為成功率的倒數

具體的例子:連續丟銅板丟到正面才停,需要的平均次數是2次。連續丟六面骰子丟到1才停,平均需要的次數是6次。

* 接下來,考慮取一個元素的cost:

分析已經取了x個元素,要取第x+1個元素的狀況

從1~N中任取一個元素,有x/N的機率會取到重複的元素

試問:「取第幾次元素會取到不重複元素」的期望值是多少呢?

以p = 1 - x/N代入前式,需嘗試的次數期望值為N / (N - x)

那麼,共要做多少次整數比較呢?顯然,若選到已重複的元素,需比較次數的期望值為x/2

兩式相乘為N * x / (N - x) / 2

* 最後,考慮取得所有元素的cost總和

累加選擇每個元素,所需的比較次數則為:

最後一個term其實是harmonic數列的前N項。以積分的面積思考,其值不會超過1+ln(N-1) (見下式,可參考此圖,但此圖是求下限,考量每個區塊的右邊界則可求上限)

故整體cost為O(N^2*log(N))。

測驗題目

給定一個 singly-linked list 結構:

Q1: swap 函式的作用是交換存在 list 中兩個節點的函式,指出以下程式碼的不足或錯誤之處: