Lec04 資料結構 第三週課程

NYCU OCW
75粉絲
2 次觀看·2023年12月3日
Arrays (2/4)
授課教師:資訊工程學系 彭文志老師
課程資訊:http://ocw.nctu.edu.tw/course_detail.php?bgid=9&gid=0&nid=412
授權條款:Creative Commons BY-NC-SA
更多課程歡迎瀏覽交大開放式課程網站:http://ocw.nctu.edu.tw/ 本課程同時收錄至國立交通大學機構典藏,詳情請見:
http://ir.nctu.edu.tw/handle/11536/108205
其實我們開始上課了
禮拜五的時候我們有講到
Array 的話
原則上可以稍微複習一下
Array 就是 a set of records
這個 records 的話
它是一個 index 還有 data
所構成的這個 pair
其實大家在
就是大家看一下
Array 的話就是 a set of pairs
它構成是 index 還有 value
value 或是 data
它可以是 one-dimensional array
也可以是 two-dimensional array
我相信大家在記慨的時候
都知道 Array 是什麼了
所以就在後面
你會看到我們用了一些
例子來跟大家講說
Array 到底怎麼用
其實它的變化方式還蠻多的
所以上禮拜五的時候
我們大概就講了一個
用多項式來代表一個 Array
比方說我們想要去做
多項式的表示方法
比方說 ax 等於 xxx
這是一個多項式
那你要怎麼去用 Array 來表示它呢
在上禮拜五的時候
我們有講過兩個表示方法
第一個表示方法的話
就是長成這樣
每一個多項式都會有一個 Array
你可以看
它的這個 Array
它的名字叫 coefficient
這名字不要亂訂
其實是有道理的
coefficient Array
那這告訴你什麼呢
就是在 Array 裡面
它所存放的都是 coefficient
就是係數
那它的指數部分在哪裡呢
它的指數部分就是在
它的 index 就是它的指數
所以就是每一個 polynomial
都會有一個 Array
那這個 Array 就是係數
你可以把它寫成 coefficient Array
那裡面的 value 就是係數
指數部分是在它的 index
那這樣表示方法也有什麼不好
上禮拜我們大概有講
假設你是一個很 sparse 的 Array
比方說 2 的 x 1000 加 1
那這樣子的 Array 的話
你想想看
你會用一個很大的 Array
去存放 coefficient
而這個 coefficient 只有兩個地方
是有值的
一個是 x 1000 的那個地方
它是存放 2
那另外一個是 x 的 index
0 的地方存放 1
那其他地方就是空的
這樣的話就蠻浪費空間的
第二種表示方法的話
請同學回去看一下書
這個我們不講
但有可能期中還會考
所以請同學回去看一下書
那稍微講一下第三種表示方法
第三種表示方法的話是
所有的 polynomial
都用一個 Array
一個 global 的 Array 去存放它
那第三種表示方法呢
這個是很重要的
就是它用一個 global 的 Array
存放所有的多項值
那要達到這個目的的話
它這個 Array 呢
它會長成這個樣子
那最下面那一行
0、1、2、3、4、5、6
它代表的是 index
是 Array 的 index
可是這個 index 呢
它會告訴你是什麼呢
就是告訴你說
哪一個 polynomial
它佔用哪一些 Array 的空間
在這例子裡面大家可以看一下
就是說 A star 和 A finish
那這兩個 column
它存放的就是 polynomial A 這個 Array
那 B star 到 B finish
大家看一下 B star 到 B finish
它所存放的就是 B 的 polynomial
所以大家大概會知道就是說
那這個 global Array 存了
以這個例子來看
它存了兩個 polynomial
那 index 的部分
是用來記錄每一個 polynomial
它的 start 和 end
就是這個 polynomial
在這整個 Array 裡面
它是在哪個位置
那接下來我們再仔細看一下
就是說每一個 index
比方說 A 點 start
A 點 start 那個地方
它有存放這個 Array
它存放了兩個資訊
一個資訊是什麼
就是係數的部分
就是 2
那 ESP 就指數部分呢
它就除了 1000
那它是告訴你說
那 A 這個 polynomial
它的第一個項
第一個 element
是 2 的 x 的 1000 次方
那 A finish 這個地方
接下來大家再看一下
A finish 這個地方
coefficient 是 1
its potential 地方是 0
加 x 的 0 次方
就一直類推
它是用一個 global Array 去表示它
那這個概念
這個概念其實也還好啦
也不會太難
但是要注意一下
假設你有一個 global Array
那接下來你要 implement 它
implement 它在 class 的宣告的時候
要怎麼 implement
大家都用一個 global Array
你要去 implement 它的時候
要怎麼 implement
所以上禮拜
上禮拜我們就有跟同學講說
你看這個 class 的宣告
你可能要特別注意一下
對應於上面這個表
上面這個表裡面的每一個 column
每一個 column
比方說每一個 element
每一個 element
它都會用一個 class 的 turn 來表示它
那你看一下
有一個 class 的 turn
那它的朋友 friend 的 class 是誰
是 polynomial
就是有一個多項式
那是它的 friend class
那這個 turn 呢
它有兩個重要的
這個 data
第一個是它的 coefficient 的部分
第二個是它的 its potential 的部分
就是每個 turn
那看完這個宣告以後
大家再看一下 polynomial 這個地方
class polynomial 這個地方
就是 private 的部分
有三個變數的宣告
那大家要注意一下
就是多項式
每一個多項式
我們都會用一個 star
一個 n
star 和 n
來代表說
這一個多項式
它在這整個 global array 裡面
它所在的位置在哪裡
所以大家先不要看前面那兩個
static 那個部分
你 polynomial 你會想到的是說
它會告訴你說
這個多項式的 star 和 finish 是在哪裡
n 在哪裡
所以這有一個 int star 和 finish
那前面這個地方
前面這個地方在幹嘛
前面這個地方
前面這個地方就是用來去做
global array
很多的 polynomial
去分享一個 global array 的空間
這個 global array 的空間是在哪裡呢
這是很神奇的
不是應該說很神奇
很自然的
它用一個叫 static turn
turn array
就是你會有一個 turn array
turn 所構成的 array
data type 是 turn
那注意一下
前面要有一個 static
就是不同的 polynomial
只要你宣告它是 static
那它會佔用到
相同的 turn array 的空間
所以這個地方要用 static
不要把它去掉
static 是有它的意義
那同樣的
在這個 turn array 裡面
它會用一個指標
來代表說
哪些 array 的空間
哪些 index 是沒有用的
那這個指標
就是在 int free
那它也是同樣的宣告成 static
那這個呢
就是在指到哪裡呢
它是一個 index 的位置
它指到是
假設這個 turn array 裡面
最後那個 column
這個就叫 free
這是 free
那 free 的用處是幹嘛
今天假設我們有一個 array
叫 cx
cx 等於可能 x 的 100 加 1
那這個時候呢
這個時候你要怎麼宣告這個 polynomial
cx 等於 x 的 100 加 1
那這個時候就是要
用到的空間就是
從 free 6 開始以後
6 那個位置以後
所以你可以知道說
c 那個 polynomial
它的 start
它的位置的 start
會是在第六個位置
那 x 100 加 1
所以它的 end
可能是第七個位置
那像剛才所說的
cx 等於 x 的 100 加 1
那這件事情怎麼讓它發生
那就一樣
因為 turn 它是一個 class
那所以呢
在剛剛的例子裡面
cx 等於 x 的 100 加 1
所以當你宣告一個 polynomial 是 c
當你宣告一個 polynomial 是 c
那這個時候你就要 new 一個 turn
你要產生這個 cx 的 x 100 加 1
那你就要 new 一個 turn 出來
那 new 那個 turn 出來以後呢
它所要做的事情
就會去檢查
第一件事情就是檢查說
它的 free
它最後那個指標的 index
有沒有超過 maximum turn
其實那 turn array
它還是有它的限制
可是那 turn array
最多隻能夠放 100 個 turn
100 個 turn 這樣
那如果 free 超過那 maximum 限制的話
它就告訴你這個錯誤訊息
就是沒辦法放下去
那假設呢
free 是小於 maximum 的 turn 的話
它就會做下面這件事情
那下面這個事情是要怎麼做呢
就是 turn array free
點 coefficient 等於 c
那剛剛我們說的那個例子
x 的 100 加 1
那 x 的 100 加 1
我們的第一個 element 是
c 是多少
x 的 100 加 1
c 是 1
1 是多少
1 是 100 這樣
所以接下來要做的事情
就是把那個 turn array
那第六個位置的空間
它的 coefficient
係數部分是 1
its potential 部分是 100
那接下來要注意一下
它要去做一件事情
free 加加
就是把那個 free 的指標
往前一個
往後面移一個
那做完這件事情以後呢
剛剛我們看到
x 的 100 加 1
還有另外一個 turn
那另外一個 turn
你要再 new 一個 turn 出來
就是這時候 c 是
也是 1
1 的話是 0
那這樣就會完成
這個 cx 把它塞到
這個 turn array 裡面
那所以呢
這個就是一個很簡單的
不是很簡單
是很不錯的設計技巧
所以請大家看一下
data structure 的時候
有時候要知道說
它的設計理念是什麼
那接下來呢
看它怎麼 implement
就是你都知道
用一個 global array
那既然你怎麼 implement
你要怎麼去 implement 它
是請大家要特別注意
這些 class 這些宣告
都是有它的意義的
那下面這個東西呢
在做 polynomial 多項式的加法
多項式的加法
那這個地方我們就不仔細講
因為它的概念就跟
上禮拜五的時候
我們講的是很像的
兩個 polynomial 相加的話
就看比指數的大小
最大項
就從最大的相似
開始去做比較
那如果它的指數部分相同的話
係數就相加
那如果指數比較
比方說 a 比較大
b 比較小的話
那就把 a 那個指數
比較大的部分
copy 一份
存在新的 polynomial 上面
那接下來要做的事情
記得
只要你對多項式的加法
做完以後
那個指標要 shift
那這個地方
大概就是類似這樣
那他們做的做法上
大家可以稍微看一下
有一個叫 y
a 小於等於 finish
b 小於等於 finish
這就是告訴你什麼
告訴你說
假設我還沒有
我看到了 a 這個 polynomial
我看到了 b 這個 polynomial
如果他們的 index 的指標
還沒有到 finish 的時候
那我就可以去做
做那個 polynomial 的比大小
然後呢
就是看要做
這個三個 case 的哪一個 case
看它是屬於三個 case 哪一個 case
那如果有 finish 的
看到 finish 的時候
就代表
假設 a 等於 finish
就代表說
a 這個多項式
我已經都檢查完了
那可能 b 還沒有到 finish
那這時候要做的動作是什麼
這時候的動作
你就可以看下面
就把下面的 turn
假設說 a 已經完了
b 沒有完
那就把 b 剩餘的項次
element 把它 copy 一份
到新的 array 裡面
所以下面這個 for 迴圈
這兩個 for 迴圈
它其實要做的事情就是
當你發現
就是有沒有完
就是還沒有到 finish
是別的 polynomial finish 的
那這個時候
就是再做一個
做一個 copy 的動作
這個程式不難
但是同學要花時間去看
因為我覺得 data structure
和計算機概論
不一樣的地方就是
你要去了解這些程式在幹嘛
瞭解這些程式在幹嘛
像我們剛才那個概念就是
首先我告訴你是
polynomial 怎麼表示它
然後第二個呢
我就會告訴你說
這個程式大概是怎麼 run 的
怎麼 run 的
那基於這樣子一個 concept
你有這個 concept 以後
接下來你要做的事情
你真的要去 trace 那些程式
trace 一行一行去看它程式
到底在幹嘛
那如果你覺得
就是用
通常我都在開玩笑
就是如果你覺得用那個
如果你是用人去 trace
一行一行去 trace 的話
這個我們都叫做工人智慧
有沒有聽過人工智慧
人工智慧有沒有聽過
AI 嘛
就假設你用 iPhone 4s
它不是一個 Siri 這樣
但你跟它對答
它會跟你聊天
那一樣呢
這個都技術怎麼達到
就是透過 machine learning
就是人工智慧
還有一些 data mining 的技巧
這樣去達成的
那這個叫做人工智慧
那這也是題外話
就是大家想想看
就是當你的講話
問的問題越多了
假設大家都在問說
假設大家問說
你這次最好的電話是什麼
大家問的這個問題很多了
然後接下來根據
他所問的問題的解答
他會看 user
他會問下面哪個問題
他就可以去修正那個答案
所以其實 computer science 是蠻有趣的
不是隻有硬邦邦在寫程式
寫程式只是幫助我們
把我們所想像的這個東西
實作出來
後面其實還有很多
很有趣的東西
所以所謂的人工智慧是這樣子
那工人智慧呢
工人智慧就是各位
發揮我們人腦的極限
不是極限
就一步一步去 trace 那個 code
那怎麼去 trace 那個 code
把這個程式 key 到 C 裡面
然後再做一些宣告
然後一行一行去 debug
debug 會吧
debug
就是出錯
這個請同學自己要去實作看看
這個要花時間
久了以後你就會知道
這個程式寫得還不錯
那接下來大家就要看一下
這 capacity 分析
因為在這個例子裡面
你可以看到
假設有兩個 array
一個是 a array
一個是 a 的 polynomial
一個是 b 的 polynomial
那 a 的 polynomial
他總共有 n 個 element
總共有 n 個 element 相似的
那 b 假設有 m 個的話
你看他這整個程式
他實際上是要把 n 和 m
都要 scan
scan 過一次
當然你可以想像說
界線有 a 和 b 這個 polynomial
然後有兩個 pointer
那接下來他是
每一個 element
都要去做比較
那所以
事實上他的 capacity
就是要把 n 還有 m
這兩個 element
都要 scan 過一次
比較過一次
所以他的 capacity 是 order n 加 m
那注意一下就是說
n 和 m
他分別代表是
這個 a polynomial 和 b polynomial
那個非 0 的 non-zero
non-zero 的相似
0 的相似不用管他
0 的相似就是比方說
那個 coefficient 是 0 的
那其實不用管
為什麼不用管
因為他也不會出現在
這個 tender array 裡面
在他這個表示方法裡面
你看看這個地方
非 0 的相似
ax 1000 加 1
其他的那個 element
x 的 999
他是 0
係數是 0
他根本不會出現在這個地方
前面那個就會出現了
這個非 0 的就會出現
那這個寫法
就是回到上禮拜講的
這個是另外一種
第一種表示方法
他的 polynomial 的相加
他的概念很像
那你會發現說
老師這個程式
detail 細節不像
那是當然的
因為不同的表示方法
你很自然的
裡面程式的某些宣告
就會不一樣
那接下來我們來看一下
就有一些問題
這問題是什麼呢
假設我要產生一個新的 array
這個 free
這個空間已經超過了
max 碼的 turn 的時候怎麼辦
我們不是有一個 global array 嗎
這個 global array 呢
最大 假設我們最多隻能允許
100個 turn
100個 element
就是可以存100個
100個 element 的資訊
就是係數和指數
存到100個這樣
那假設呢
我們這個多項式
又來一個多項式這樣
那100個多項式都滿了
都滿了這樣
global array 已經滿了
那怎麼辦
最笨的方法
就是說老師那沒有怎麼辦
就送他一個訊息
說這已經滿了
請下次盡早用
這個是另外一種方法
這個一定會被
user 就會覺得被惹了鬧
寫這個程式這麼爛
就會告訴你說
可以滿了
然後也不做什麼事
那比較好的方法是什麼
對 比較好的方法
大家可以想想看
比較好的方法是說
那有沒有可能
有些 array 有些 polynomial
已經用過了
前面它的位置是可以回收的
比方說這個 a x
b x
a 和 a 加了 b 以後變成 c
那從此以後呢
a 和 b 都不用了
那接下來就是
這同學可以想想看
就是 a 和 b
就是加完這件事情
做完加法以後
我們就不用了
那接下來是什麼
回收
就把那個 a 的位置
a 和 b 所佔用的這些
turned array 的位置
回收回來
那回收回來是什麼呢
就是今天假設
有新的 array 要進來
然後他發現後面都沒有空間了
那他就去用
人家已經用過的位置
就是用過人家的位置
因為 a 和 b 都不用了
所以這個時候
你可以去佔用它的
這是一種解決方法
那解決方法有什麼缺點
這個解決方法
對 我再洩題好了
期中考可能會考
我就問你
假設我要用 turned array 裡面
我要回收使用
怎麼回收使用
光靠一個 free 的指標
可以回收嗎
如果你要回收使用
這 a 用完
這 b 又用完
那大家想想看
這個
他要回收使用
那回收使用的話
是怎麼回收使用
那有沒有可能
他不見得會是在
turned array 的前面
那可能中間那些 array
也被用完了
那這個時候
你就要回收使用
那注意一下
那回收使用這件事情
如果真的要去寫的話
會寫在哪裡
constructor 大家都知道嗎
destructor 大家知道嗎
destructor 就不用了
要把它 destruct 掉
所以你要寫一個
寫一個 member function
就 destructor
destructor 就是
要把自己的這個
要告訴系統說
我現在這個 polynomial
未來不會用了
那所以呢
就把我所使用的空間
交還吧
就交還給 turned array
就交還給系統
但在 destructor
所以其實你看
我又幾乎都快把答案跟你講了
在 destructor 那個地方
要做一些事
destructor 那個地方
要做一些事
那很好玩的是什麼呢
假設那個 polynomial
就是有人 destruct 掉了
destruct 那個 polynomial
那有些空間就會空出來
所以你可以想想看
假設是總共有100個 array
100個相似
它有些地方是空的
有些地方是沒有空的
有些地方是空的
有些地方是沒有空的
有些地方可以用
有些地方是被佔用
正好有 polynomial
正在佔用它
所以在這種 case 的情況之下
你的 new turn 這個 function
要怎麼改寫
今天假設我有一個 array 的空間
這個我要產生一個新的 array
這個 new turn 要怎麼改寫
它就不見得每次都會去
去找到最後那個 free 那個地方
因為前面可能會有些空間
是可以被使用的
因為別人不用了嘛
這也是把它 release 出來
那可以被使用
所以這個題
這個題目這樣
我們沒有講明答案
但可能會考
機率到底多少我不知道
就是可能會考
那這個就是觸發大家去想
那這個題目呢
為什麼會想到這個題目
你們學過作業系統了沒
OS
到作業系統的時候
它就會告訴你
這種問題就很像了
很像什麼
大家有沒有聽過 memory
執行程式總是要 memory
基幹應該有上吧
稍微講一下
memory 的空間是有限的
你用完以後
這個程式結束以後
memory 的空間就要 release 出來
release 出來
給別的程式來使用
那所以呢
就有一個叫 memory 的 management
在 OS 裡面
在作業系統裡面
有 manager 的 management
那如果基幹
你沒有好好
基幹你在上課的時候
基幹在睡著了
那從前有沒有聽過
磁碟觀念
你在 Windows 裡面
Windows 7 Windows XP
跑太慢了
就來個磁碟重整
磁碟重整也很像這個概念
為什麼
就是重整
為什麼要重整
這個地方
這個檔案已經被刪除了
所以它就不用了
那所以呢
這磁碟裡面
你可以看到說
這個有些是空的
有些是佔滿的
那磁碟重整的目的在幹嘛
就是把它調一調
就是去做 shift 的動作
把它集中在某一個區塊
讓它
這個區塊裡面
所有的程式都是被
這個 disk 都是有用的
那其他區塊就不用了
所以這個可以給大家一個 hint
就是說
假設你要去做到這件事情的話
我們會
要寫 destructor
destructor 就是那個
要刪除這個 polynomial
要去做一些事
要 destruct 它
那 destruct 它完了以後
destruct 完了以後
就是這個 array 裡面
會剩多很多的空間
那你要做什麼事
使得你的 new turn
這件事情會比較方便
請同學回去想想看
所以這一頁
其實還蠻重要的
那還有一個事情
因為 polynomial representation
這個 tool
我沒有講
這目的是幹嘛
就是請同學去
看書
這題外話
昨天我遇到
華通的老闆
你知道華通的老闆
叫什麼名字嗎
華通書店知道吧
華通書店的老闆
叫什麼名字
不知道
你們都不知道
因為以前我當學藝
我大一的時候
就不小心被選出當學藝
就遇到這個老闆
這老闆叫什麼名字
叫李鵬
我那時候大一的時候
剛好發生
就是六四天安門事件
就附近
我是1991年讀書的
就讀大一
就是發生了這個
之前大概1986年
還是什麼
發生天安門事件
就覺得
怎麼會叫李鵬呢
然後我昨天遇到他
他就說
黃老師好久不見
因為他真的是看著我長大
這些有很多西班牙小姐
都是看著我長大的
讀完大學研究所
就回來當老師
那我昨天看到他
然後他就跟我說
老師
這個學生
都不買教科書
我說蛤
總共比例大概有多少
他說
比方說這個
Database
上學期我上的課
大概有兩三百個人修
買教科書的比例大概兩成
很低
非常低
其他的都不用買教科書
不知道為什麼
可是發現
有另外一個現象是什麼
大家不買原文教科書
另外一個現象是
大家去買綜藝本
我在一開始上課的時候
就跟同學講
就不要買綜藝本
因為那些譯者都是騙人的
我以前也是譯者
我都沒有用過Photoshop
但是我能夠翻出Photoshop
你問我怎麼用
其實我也不知道
我只是照著翻而已
可能有些人
笨笨的就買了一本書
怎麼會弄不出來
寫信問我們
我們也丟給那些後面的出版商
請他自己解決
這就是譯者
當然也有好的譯者
我自己比較差
接下來我要跟同學講說
買原文書的目的是要訓練同學
幹嘛
去閱讀這些英文
老師上課
老師上課講譯可不可以
當然是可以
但是上課
總是我們是用講出來的
大概是這樣
這麼做
但接下來
你如果知道這個concept以後
就知道
Pronominal的加法或減法
是怎麼run的以後
再麻煩你去看一下書本
它所對應到的段落
那做這件事情的目的是幹嘛
目的是訓練大家閱讀
訓練大家去讀英文
然後去吸收那英文所寫的東西
訓練同學去閱讀
那為什麼要做這件事
為什麼要做這件事
兩個目的
第一個
大家不要說
以後等我上研究所以後
我來再讀論文好了
然後這個時候呢
我再來訓練一下
再讀一下公眾英語教室
來不及了
在讀論文的時候
都是英文寫的
你說這時候再來補強一下
從小就要慢慢
大一大二大三大四
就開始要讀原文書
訓練自己閱讀能力
不是每個字都差
就是要訓練自己閱讀能力
所以這是第一個目的
從小就要訓練
那第二個目的是幹嘛
上研究所的時候
你有沒有看到
基本上原則上
老師實驗室畢業的學生
都是用英文寫的
論文都是用英文寫的
很少用中文寫的
那我們要講的是說
如果你的論文是用中文寫的
而且又是繁體中文的話
那你的論文的影響力
僅限於臺灣這個地區
這是太少了
所以我們會希望
同學的論文都是用英文寫的
來啦
假設你以前都在讀中譯本
臨時要叫你寫英文出來
那個不是像大學聯考的作文
是寫一個段落
英文的論文
假設有看過Two Colour的話
十頁到十二頁
如果你說
老師我以前都讀中譯版
在論文的時候
能夠自然的寫出英文來
很難
然後千萬不要做一件事情
老師這個不用
就用Google Translate
那你就完了
就是完蛋
我看同學
之前我看到有些
就是說書班的學生
去口試很多學生
奇怪這怎麼翻得怪怪的
真的都不知道
有沒有文法
所以就問
被拷打之後
我們沒有尋求啦
只是一直問而已
被拷打之後
他就跟他的指導教授說
他用Google Translate
那這是不好的
所以鼓勵同學
在大二或大三的時候
就必須要去
買一些原文書
開始閱讀
那閱讀
有些讀熟了
那些句子其實還蠻不錯的
很自然的你就會
很自然就會吸收
當你要寫的時候
就很容易就
就跑出來了
以前我在臺大讀博士班的時候
很好玩
有一門課
叫論文寫作
論文寫作
我那時候以為是混課
跑去修
結果發現
真的蠻累的
為什麼蠻累的
每一週
他叫我背
背一篇文章的
某一個段落
然後老師上課的時候
就會點
這個同學
來吧你背一下
叫我們把他背出來
那個老師
那個老師現在你知道在哪裡嗎
在華碩
CTO
已經戒掉了
去華碩電腦了
CTO就是那個
執行長
科技的CTO
就是執行長
那門課是蠻有趣的
那你看
那時候就背很多
這個文章
就回來正題
就是請大家多讀原文
多讀原文
不要看綜藝版這樣
大家在機蓋的時候
有沒有學過spending tree
有沒有
機蓋
有沒有聽過spending tree
spending tree知道是什麼吧
對
這以前我們在
就是碩士班口試的時候很好玩
有些私立學校
私立學校
我們就問他說spending tree是什麼
spending tree是什麼
對
私立學校的學生
那時候他們都用綜藝版
我說老師spending tree
是不是叫做生成數
最少生成數
我說這什麼
對
所以他們都是透過綜藝版
就比較不好
好
那接下來我們回歸正題
就是
matrix講過了
就是polynomial的表示方法
也講過了
那接下來我們再看第二個問題
第二個問題是說
這個
大家都知道
這是matrix
矩陣
好
那矩陣通常在做運算
就是你就會想說
那矩陣做運算
對
那首先要
矩陣運算就包含了
加法減法
加減乘
然後或者是
去做一個轉換
對
這個
有沒有學工程數學
對
有沒有
聽過
Fourier transform嗎
FFT
Fourier
都沒有
或
對
好
那這個作業意義
我們就不要考了
這個作業意義就不出了
我們還想說
請他的作業去做一個
那個Fourier轉換
對
用matrix做一個Fourier轉換
然後再拿解釋衝出來
那如果這樣的話
我們就先
跳過這樣
待會我們還有更好的題目給大家
對
那現在
這個問題就是說
矩陣這個運算
在
矩陣這個運算是
大家在高中都知道
就是矩陣加減乘
對
好
那現在
如果我們要讓
程式要能夠做到矩陣的運算
首先
對
首先在做這些運算
要實作之前
先去想一下
矩陣要怎麼表示它
矩陣到底要怎麼表示它
好
那
對
矩陣要怎麼表示它
有沒有人要講
矩陣要怎麼表示它
對
嗯
就假設一個matrix
n by m
好了這樣
就看
老師這個很簡單啊
就是
我們就宣告一個
n by m
那two-dimensional array
two-dimensional array
二維的陣列
來存放它
好
那這是一種表示方式
這樣
這是一種表示方式
那現在我們要問的問題就是說
就因為我們上面的標題
叫sparse matrix
對
sparse matrix的意思是什麼
對
顧名思義sparse嘛
對
其實sparse就是說
就是有很多矩陣呢
那裡面的
value
這個element
它是零的
比方說像這個b的部分
它是一個660的矩陣
就是660
總共有36個element
在這個矩陣表示方法裡面
那同樣的
在這樣的表示方法裡面呢
這個
你看大部分的區塊都是零的
大部分的區塊都是零的
所以
你就會覺得說
好
那用這個
二維矩陣
two-dimensional array
去存放這個矩陣
有點浪費空間
為什麼呢
因為大部分是零的這樣
好
所以接下來我們要
想要做的事情是
那如果對於sparse matrix
你可不可以想出
比二維陣列更好的方式
去存放它
對
就是對於sparse的matrix
可不可以想出
比較節省空間的方式
去存放這個sparse matrix
好
對
那
在
給同學想想看
這
這有它的典故之在
就是
你可不可以想出
更好的data structure
好
那在講這個data structure之前
就是在講
講它之前
就是來看一下
就是一個叫class
sparse matrix
好
對
就是一個class
你可以把它想像成
一個ADT
對
其實呢
它可以包含了
row
column
和value
那sparse matrix裡面呢
就是
上面有
第一個就是sparse matrix
它是constructor
就是你會告訴我
就是這個矩陣
它的row和column是什麼這樣
然後第二個呢
就是大家看一下
第二個就是
maxima的turn
就是在這個矩陣裡面
對
有哪一些
像
element
它是非0的
然後大家再看一下
sparse matrix transpose
transpose等一下我們要去做
就是做什麼
轉換
比方說
就是一個矩陣給你這樣
它的t
t就是transpose
就是row變column
column變row這樣
就叫transpose這樣
那要去做轉換這樣
那同樣的
在sparse matrix裡面
還可以去做什麼add
就是
做矩陣相加
那還有矩陣相乘這樣
就是
這是sparse matrix的
這是相乘
那等一下我們會講的是什麼
就是
sparse matrix怎麼表示它
然後第二個呢
重點是
sparse matrix怎麼做到transpose這樣
就是
t這樣
好那
所以這就告訴同學答案了
這樣
就是
它不用二維的陣列去存放
它採取的策略是這樣
這個講出來很簡單
那我們就去
在sparse matrix裡面
我們去記載
記載那一些
element
假設它不是0的話
它的位置在哪裡
在這個sparse matrix裡面
它的位置怎麼表示
比方說15
它的位置怎麼表示
對
就是看它的row和column
因為這剛好是二維的這樣
就是去看它的row和column
那所以15這個位置呢
它的位置
在那個二元
two-dimensional array裡面
它的位置是什麼
0
在第0個row
在第0個column
它的value是多少
第15這樣
那大家看一下22
對
22它是在
它的位置是什麼
第0個row
第3個column
22最上面那個
22是
第0個row
第3個column這樣
所以sparse matrix要怎麼樣
去用比較節省空間的方式
去存放它
那它的概念很簡單
我們只要記載
我們只要去記錄
那一些非0的element
它的所在位置
還有它的值
非0的位置
所在位置和值
所以
就會導出這個
那我們就用row
column和value
去存放它
row和column
你可以在下面畫個底線
代表它的位置
存放它的話
我們存放
以這個例子來看
總共有8個
8個非0的value
總共有8個
依照剛才那個row和column
還有value
這樣子的架構去存放它
接下來呢
這8個要怎麼存
在array裡面要怎麼存
它是依照
它的row的順序
去做排序
那如果row相同的話
它就依照它的color
這是一個準則
依照row、column和value
去做排序
然後呢
對應於其他的element
依照它的row
先去做排序
就是最上面的
最先出現
那如果
你是在相同的row的話
那就依照它的color
由左到右
去放它
那所以依照
注意像這樣
就是A的部分
對
A的部分呢
就是
剛才那個B
那個matrix
file matrix的例子
就會存放成像A這樣
那A這樣的
看
它是一個array
像A這樣
A0到A7
因為總共有8個element
總共有8個element
那第一個
是一個A0的地方
它放的是什麼
是0.15
對
相當好
第0就是
第0個row
第0個column
那第二個呢
它就是放
0、3、2、2
第0個row
第3個column
那
對
相應的意思
那同學有沒有發現一個現象
就是說
第0個row
比方說A2這個地方
第0個row
第5個column
它放50
完了以後呢
就放第1個row
第1個column
所以這整個
這個
存放方式
會是以0
那個row
去排序
越小的
會排在越前面
那如果相同的row的話
相同的row
就相同的
比方說0的
都是第0行那個row
就會以它的column
去做排序
以它的column
去做排序
e-state
所以這就是
Spot Matrix的表示方法
對
這裡沒問題
對
這裡沒問題
沒問題
確定
好
那現在我們要去做轉化
轉制
transpose
對
transpose
那transpose的話
對
第一個就是
Spot Matrix的表示方法
沒有問題的
沒問題
對
就總共
它也只不過
用了一個one-dimensional array
one-dimensional array
不是用two-dimensional array
one-dimensional array
就是去存放它
那每一個
array裡面的element
存它的row
column
還有value
row column value
就這樣
這沒問題
好
那存放的準則
就是像剛剛所說的
就是先根據row排序
row完以後
就column
好
那transpose
好
那現在問你說
基於這樣子一個架構
要去做transpose
要怎麼做
對
那大家看一下
transpose的目的是
比方說
0 3 2 2
我們看這個
0 3 2 2
對
第0個row
第3個column
它的值是22
轉換
就是transpose
過後呢
這個array的位置
是在哪裡
第3個row
第0個column
value是22
就是
這是它transpose後的位置
第3個row
第0 22
這沒問題
好
那同樣的
要注意一下
就是說
這個
當我們去做transpose
過後
是從a要轉換成b
這叫transpose
transpose過後
那它的這個
這個matrix
還是要符合
符合我們所定的規則
那規則是什麼
第0個row
完了以後就是第1個row
第1個row
完了以後就是第2個row
就是
它還是依照row
先去做排序
排完序以後
假設相同的row
它還是依照那個column
去做排序這樣
好
對
就是還是要依照那個準則這樣
好
對
這裡有沒有問題
對
沒有問題
那接下來就問同學
那現在我們怎麼做
對
就是假設有一個a這個matrix
要去做transpose
你會怎麼做
對
就是這個
我們先講最naive的方法
講完就下課
好
那所以呢
就是
基於剛才那個表示方法的話
就是同學看一下
這個matrix
對
它有一個matrix的turn
就有一個matrix的turn
好
那這matrix的turn
這名字都不是亂取
這matrix裡面的turn
裡面的turn
那它的friend class
friend class是誰
friend class是sparse matrix
好
那這個turn裡面
它包含了
三個重要的
這個
data
row column和value這樣
row column和value
好
那接下來看
sparse matrix
class sparse matrix裡面
它有定一個叫matrix的turn
sm sparse matrix的array
這個也不是亂定的
這是叫sparse matrix的array
那max turn
max turn就是
這個array
這個array最大
它可以容許多少turn在裡面
好
那接下來我們看一下
就是說
怎麼去做transpose呢
對
我們先講最笨的方法
最笨的方法是什麼呢
對
那老師那還不簡單
就一行一行來
對
從原來的matrix裡面
比方說0 0 15
它去做transpose
就把它的row變column
column變row
那在這個地方
剛好是0 0 15這樣
那0 3 22
0 3 22
第0個row
第3個column 22
在transpose過後呢
它就是放在第3個row
第0個column 22這樣
那0 5 負15
對
去做transpose以後
就是它放在第5個row
第0個column
然後負15這樣
1 1 11
對
那
同學有沒有看到
一個現象
對
這是我們照著這個
照著這個A0
A0它transpose過後
就是0 0 15這樣
0 3 22
它transpose過後
就是3 0
對 3 0 22
那第3個
第3個叫0 5 負15
它transpose過後就是5 0 負15
那問題來囉
第4個
1 1 11這樣
它transpose過後
過去也是1 1 11
它transpose過後也是1 1 11
但是我們要跟同學講說
1 1 11有沒有符合
這個標準
其實這個
那個matrix的表示方法
對 它是第1個row
第1個column
在第11
它的位置是放在第4個位置嗎
它位置不會放在這個位置
它位置應該是放在
0和3
就第1個row和第2個row
的中間
就是
1和11的話
它不應該放在最後那個地方
它的位置應該是要放在
對
transpose後
過去的matrix
在這個例子裡面的第2個位置
所以是應該
合理的方法就是要把
1 1 11往上
往上移動
會變成說
0 0 15
存放完了以後
接下來就放
1 1 11
然後接下來纔是3 0 22
然後接下來纔是5 0-15
同學自己再想想看
這是在
在依照
這個1 2 3
1 2 3
transpose後過去是什麼
這是2 1 3
2 1 3
那2 1 3要放在哪裡
對
2 1 3
不可能放在最後一個位置
它必須要移到什麼
移到3的
前面一格
前面一格這樣
所以這告訴你是什麼呢
就是說
transpose後
transpose
很簡單
就是
弱變color
color變弱
工人智慧就會了
這太簡單了
其實呢
電腦其實很笨
為什麼
你要告訴它說
transpose後
那個位置要對
位置要對
要存放它該放的這個
array的位置
那接下來呢
如果依照剛才這樣子的概念的話
你每一次transpose後
每一次
每一次把它轉過去以後
你要去做調整位置的動作
那這樣調整非常的頻繁
調整非常的頻繁
那這個準則是依照每一個rule
去做調整
那甚至同學可以設想得到
它還要依照那個color去做調整
它要依照color去做調整
好
那所以呢
這個地方
這個層次
其實就是要做到調整
這禮拜五的時候會講
那請同學回去想想看
有沒有更好
更聰明的調整方式
其實當然有更聰明的調整方式
我用一句話就可以講完
那禮拜五的時候
我們再
那我們今天上到這邊
