2018年4月29日 星期日

TCP學習筆記


ARQ

在傳輸層以下的底層通道可能會造成封包位元錯誤(由於封包傳輸,傳播,暫存在網路中的實體元件)的時候,我們可以和接電話一樣想像如何確保資訊正確:

使用肯定/否定確認(Positive Acknowledge),以此建立具重送機制的自動重複請求(Automatic Repeat Request, ARQ)協定。
因為這種機制的關係,ARQ協定需要三種額外的功能:

1.錯誤偵測:檢查位元錯誤(ex:UDP checksum欄位)。
2.接收端回饋:ACK, NAK,通常僅需要一個位元(ex: 0 for NAK, 1 for ACK)。
3.重送:經過以上的偵測後如果有問題,就要有重送的功能。

可靠連線

序號(sequence number)欄位可以用來編號封包,除了可以解決ACK/NAK封包可能損毀的問題,也讓協定的接收端可以確定封包是否為重送。

接收端送出重複的ACK(duplicate ACK)可以用來代替送出NAK,讓傳送端知道該ACK標註的封包序號之後的封包並未被接收到(P3-26, rdt2.2)。

計時器可以處理封包的逾時並重送。主要觸發條件可能是封包遺失,也可能是傳輸延遲過長。

TCP連線

連線狀態存在於終端系統上,而不會在中介網路元件(路由器, L2 switch..)上。
這種連線是一種點到點(point-to-point)的全雙工服務(full-duplex service)。

TCP連線管理

假設用戶端應用程式行程想跟伺服端上的某筆行程建立連線,以下為步驟:
  1. 用戶端TCP會先傳送一筆不含應用層資料的TCP區段,其SYN bit會被設為1,因此這種特殊區段又被稱作SYN區段。同時用戶端會隨機選擇一個初始序號(client_isn)並放入SYN區段的序號欄位。
  2. 當包含此區段的IP資料報抵達伺服端主機,伺服端就會取出SYN區段,配置TCP緩衝區與變數給這筆連線,然後送出一筆也不包含應用層資料的SYNACK區段,其標頭有3項重要資訊:

    • SYN bit被設為1
    • 確認欄位被設為client_isn+1
    • 序號欄位會設為伺服端自己的初始序號(server_isn)
    • 其意義為:「我已經收到要求開啟連線的SYN封包,其序號為client_isn。我同意建立此連線,並且決定我的初始序號為server_isn。
  3.  當用戶端收到SYNACK封包,也會配置TCP緩衝區與變數,並送出具以下標頭的確認區段:
  • SYN bit被設為0(因為連線已經建立)
  • 確認欄位被設為server_isn+1
  • 在此區段中可能就會有給伺服端的資料
在以上三步驟完成之後,未來所有的區段的SYN bit都會設為0。由於會互相傳送三份封包來建立連線,此程序又被稱為三向交握(three-way handshake)。





Python筆記:物件與類別

類別

__init__(self)是在Python中的類別建構子(class constructor,就像C++中和類別同名的成員函式),其中self參數代表正在被建構的物件本身。此方法並非必要

繼承

在Python中,父類別又稱為parent, superclass, base class,子類別又稱為child, subclass, derived class。以下範例可以看到Yugo繼承Car,及複寫Car的成員方法。

當我們想要在子類別中呼叫父類別的函式時,我們可以在函式名稱前加上super()。如果子類別需要定義新的作法,但是又需要父類別的作法時,使用super()可以確保子類別沒有重複的程式碼,且當父類別定義被更動時,我們不需要更改子類別就能反應其改變。

特性(property)

特性可以作為用來裝飾物件屬性(attibute)的介面,有兩種方式可以使用它:
1. 先定義getter, setter之後,把property(getter, [setter])指派給該屬性。
2. 用裝飾器,@property放在getter之前,@attibute.setter放在setter之前。
如果沒有藉由特性的以上兩個方法來指定setter給某屬性的話,就無法直接改變該屬性,這對於唯讀的屬性來說很方便。注意到getter是必要的,如果沒有getter的話會無法編譯程式。

用__attibuteName來隱藏屬性

在屬性前面加上雙底線可以建立"表面上"只有類別定義域內可以存取的屬性(因為如果我們用該屬性名稱或是加了雙底限的屬性名稱去存取會找不到該屬性),但如果真的要從外部存取的話,可以用_ClassName__attibuteName。

方法類型

除了實例方法(在方法的第一個參數使用self的方法)之外,還有類別方法(在方法的第一個參數使用cls),並且在方法宣告前一行要加上@classmethod。類別方法會共通於所有的實例。通常會用來紀錄關於類型的資訊(類型各物件的數量、類型的狀態等等)。另外還有靜態方法,以@staticmethod開頭,這種方法是唯一不需要帶入任何參數的方法,通常用來處理屬於該類別相當一般化的工作。由於其靜態的特性,呼叫它甚至不需要建立物件。

重載運算子(Operator overloading)

Python中,如果我們的自定義類別需要重載運算子,可以定義以下函數(僅列出部份):
__eq__(self, other)    self == other
__ne__(self, other)    self != other
__lt__(self, other)      self < other
__gt__(self, other)     self > other
__le__(self, other)     self <= other
__ge__(self, other)    self >= other
__add__(self, other) self + other
__str__(self)   print(str())
__repr__(self)   object


Python筆記:模組、套件與程式

匯入模組(module)

整個檔案匯入可以用import filename或是局部匯入可以用from filename import function_name

我們也可以為匯入的模組取個別名(alias),例如把上圖的第二行加上 as ex,這樣就可以使用叫簡短的ex來使用該模組。第七行的匯入也可以依樣畫葫蘆。

模組搜尋路徑

Python會在sys標準模組的path此一變數中定義要去哪裡找尋匯入的檔案,其中第一行的字串代表當前目錄。我們可以印出該變數內容來看(上方3行是用來印出變數的程式):
同時我們也要注意因為自定義模組和標準模組名字衝突而造成標準模組函式無法正常使用。

套件(package)

透過在程式的目錄下新增一個名為__init__.py的檔案(無論有無內容),此目錄就會被視為一個套件。例如我們可以在主程式的目錄下新增一個src目錄,並在裡頭放一些模組檔案,還有__init__.py,這樣一來src目錄就會被Python視為一個套件(多個模組檔案的集合)。

通用模組介紹

1. setdefault(ele, default)的用途是在指定字典中某鍵"ele"的值時,如果該鍵值不存在則設定為"default"。
2. defaultdict(func)則是建立一個預設值為某種類型或內容的字典。func可能是int(), dict()等等,也可能是自定義的任何內容。例如,defaultdict(int)用來建立計數器相當方便,因為該字典內的元素的預設值為0。
3. collections套件中的Counter(list)則是內建的計數器,呼叫它會回傳一個Counter物件。該物件有一些方法如most_common()可以降冪回傳結果,或是用"&", "+","-"來對多個物件計算。
4. collections套件中還有OrderedDict()可以協助我們建立記得項目順序的字典。
5 collections套件還有deque(一種雙頭的序列資料結構,同時具有stack和sequence的功能)可以使用。

2018年4月28日 星期六

Python筆記:程式結構

迴圈

在Python中有個While/For迴圈搭配else的奇特用法(至少我沒有印象在Java, C/C++有看過),主要是在迴圈正常結束(沒有因為break而提早結束)時,進入到else的區塊中執行程式碼:

>>>pos = 1
>>>while pos < 5:
            if pos == 7:
                   break
            pos++
       else:
               #do nothing

以上展示了一個一定會進入else區塊的範例,因為pos永遠不會等於7,所以一定不會提早結束迴圈。else內可以放入只有迴圈正常結束才會執行的code。在for迴圈的使用方式也是一樣。

 迭代

1. zip()函式可以協助我們並行地迭代多個序列:

>>> animals = ['Dog', 'Cat', 'Elephant']
>>> colors = ['Blue', 'Yellow', 'Black']
>>> for animal, color in zip(animals, colors):
                 print( 'animal: ', animal, 'is in', color )
zip()回傳的是一個可迭代(iterable)的合併值,我們可以直接把此值轉換為list, dict...
2. range(start, stop, step)可以用來產生[start, stop)範圍的整數,並且每次數值會變動step的量。

生成式

1. list生成式:[ 運算式 for 項目 in 可迭代項目 ]

>>> mlist = [ num-1 for num in range(4,8) if num not 5 ]
>>> mlist
[3, 4, 6]

>>> a = range(2, 5)
>>> b = range(5,8)
>>> c = [(d,e) for d in a for e in b]
>>> c
(2, 5)
(2, 6)
(2, 7)
(3, 5)
(3, 6)
(3, 7)
(4, 5)
(4, 6)
(4, 7)

2. dict生成式:{鍵運算式 :值運算式 for 運算式 in 可迭代項目}

>>> word = 'letters'
>>> letter_counts = {letter: word.count(letter) for letter in set(word)}
>>> letter_counts
{'l': 1, 'e': 2, 't': 2, 'r': 1, 's': 1}

3. set生成式:{運算式 for 運算式 in 可迭代項目}

幾乎和list生成式一樣,只是換成了大括號。

4. 產生器生成式:(運算式 for 項目 in 可迭代項目)

注意到並沒有tuple生成式,上面的公式會回傳一種類型為generator的物件。這種產生器物件很特別,一旦被執行(例如用list()對它進行迭代)就無法再次使用。

函式(function)

1. 函式可以有任意數量及類型的參數(parameter),也可以回傳任意數量及類型的值,如果函式沒有使用return,呼叫函式之後會得到None:

>>> print(no_return())
None

None在Python中是一個特殊的值,它與False不一樣,雖然在布林運算中它屬於false。我們可以用is運算子來分辨遺漏值(missing value)與空值(empty value, 例如 ''、[]、(,)、{}、set())。

2. 函式的參數定義中可以有預設值,但是我們如果指定可變的值(串列、字典等)當作預設參數,該參數會被保留在函數的域(scope)當中,下一次呼叫該函式時,該預設參數的值會是上一次呼叫結束時的值。

3. 在函式呼叫時也有位置參數(照位置順序)及關鍵字參數(照參數定義)兩種方式。且位置參數及關鍵字參數可以混合使用。但是要注意混合使用時位置參數必須都在前面。

4. 用" * "來收集位置參數,例如foo(arg1, arg2, *args),args在此是tuple類型;用" ** "來收集關鍵字參數,例如bar(**kwargs),kwargs在此是dict類型。args和kwargs都是可隨意定義的參數名稱。

5. 文件字串是用來在函式定義的開頭加入一些說明用的,可以用'docstring'或'''docstring'''的方式加入,並使用help()來印出格式化的文件字串,echo.__doc__則是印出原始的文件字串。

閉包(Closure)

這其實就是一種內部函式,只要理解到所有函式本身所包含的區塊都是一個scope,在那個區塊當中的任何物件都認識彼此,因此當我們把這個內部函式用某種方式(例如當作回傳值)帶到更外部的scope時,我們就能把該scope的相關變數也帶過去。

>>> def foo(high):
             def inner():
                   return high
             return inner
>>> a = foo('Good')
>>> a()
'Good'
>>>type(a)
<class 'function'>

產生器(Generator)

產生器是一種序列(sequence)建立物件,可以用來迭代很大的序列,而不需在記憶體中儲存整個序列。通常產生器會是迭代器的資料來源。特別的是,每次迭代產生器時,它都會記得之前的呼叫(但其實類型還是一般的函式,除了把return改為yield之外並沒有什麼特殊的)中回傳的值到了哪裡。我們可以自己寫產生器函式:

>>> def giveMagicNumber(end):
               val = 1
               while val < end:
                       yield val * 9487
                       val++
>>> type(giveMagicNumber)
<class 'function'>
>>> a = giveMagicNumber(484)
>>> type(a)
<class 'generator'>

裝飾器(Decorator)

裝飾器可以拿來修飾原有的函式,例如加入除錯的log或是稍微在函式原有的執行流程上加入一些處理。我們可以直接呼叫裝飾器:


在以上的例子中,deco是裝飾器,add是原函式,可以看到在第10行我直接呼叫該裝飾器且加上參數,當然我們也可以先myNewFunc = deco(add)建立一個被裝飾過的函式後再呼叫也可以。Python中也可以直接把裝飾器加在函式定義上一行,告訴直譯器我們要直接裝飾原函式:

如果有多個裝飾器,會先執行最靠近函式的那個,再依序往上執行。







2018年4月23日 星期一

Python筆記:串列(list)、Tuple、字典(dictionary)、集合(set)

List&Tuple

1. 與字串不同,tuple與list的元素可以是不同的類型,且可以是任何Python物件
2. list可以用[Object A, ObjectB, ...]的方式建立。
3. list()可以用來建立empty list。也可以用來轉換其他資料結構為list:


>>>list('meow')
['m', 'e', 'o', 'w']

或是把tuple轉換為list:

>>> tup = ('a', 'b', 'c')
>>>list(tup)
['a', 'b', 'c']

4. 我們可以用[ : : -1]來把list內的元素倒置。

串列操作

假設mlist = [ 'a', 'b', 'c'] ; mlist2 = [ 'd', 'e', 'f']。
1. mlist.extend(mlist2)可以把串列無縫合併為 [ 'a', 'b', 'c', 'd', 'e', 'f']。
2. mlist += mlist2也是一樣的效果。
3. mlist.append(mlist2)則是把mlist2當成一個新元素加入mlist。
4. 用insert( pos, el ) 可以把el加到pos,超出pos的話會和append()一樣,加入結尾。
5. 用del mlist[pos]可以把位在pos的元素移除,注意到del是一種Python陳述式而非函式。
   這種特殊的陳述式是賦值( = )的反向操作。
6. 用mlist.remove(el)可以把el給移除。
7. mlist.pop(pos)會把位在pos的元素移出,預設是取出結尾的元素,相當於pos = -1。

從以上的操作之中,我們可以實作出LIFO(Last In First Out)或FIFO(First In First Out)資料結構。LIFO相當於堆疊(stack),可以用pop()和append()完成 ; FIFO相當於佇列(queue),可以用pop(0)和append()完成。

8. 用mlist.index(el)來找出某個元素的index,夠直白吧。
9. 用in來檢查list是否存在某值:

>>> mlist3 = [ 'bird', 'min', 'ham' ]
>>> 'min' in mlist3
True
>>> 'B' in mlist3
False

10. 如果要排序元素,可以使用sort()來就地(sort in place)排序,回傳list本身。如果要回傳副本的話可以使用sorted()。數字的排序預設是升冪,但我們可以用sort(reverse=true)來改為降冪排列。

Tuple

1. 因為其不可變的性質,我們可以說Tuple是constant list。
2. 我們可以用()來建立空tuple,也可以直接用mtuple = 'a', 'b', 'c'的方式建立tuple。
3. tuple unpacking指的是把一個tuple指派給多個變數,像是a, b, c = mtuple。
4. tuple可以用來交換變數的值,像是a, b = b, a這樣,就可以把a,b 各自所含的值給交換。

Dictionary

1. 字典又稱為associative array, hash, hashmap,其中的元素為鍵值對(key-value pair),鍵可以是任何不可變的Python類型:Boolean, Integer, Floating point, tuple, string....但是字典通常是可變的,這代表字典的元素可以被新增、刪除、改變。
2. 用{}來建立空字典。
3. 用dict(Object)來建立字典,其中Object可以是任何含有鍵值對的序列,包含類似'ab', ['a', 'b'], ('a', 'b')這樣的雙項目,都會被視為一組鍵值對 'a' : 'b'。
4. 用dict1.update(dict2)的方式來合併字典。
5. 用del dict1[key]的方式來刪除某個元素。
6. 用dict1.clear()來清除字典。
7. 用in來找字典是否有某個鍵。
8. 用dict2.keys()來取得包含所有鍵的一個可迭代(iterable)的dict_keys物件,這種物件因為不會像Python2回傳的list一樣佔用那麼多記憶體及消耗時間。
9. 用dict2.values()來取得所有的值,用dict2.items()取得所有的鍵值對。

Set

1. 集合就像是從鍵值對去掉值的字典。
2. 用set()來建立空集合,用大括號建立一般的集合。
3. 因為{}會被解譯器優先解譯為空字典,所以不能用{}建立空集合。
4. 用set(Object)來轉換其他類型的物件為集合。
5. 經常會用in來檢查集合內容或是設定迴圈變數值:

>>> alphabet = { 'a' : {'x', 'y', 'z'}, 'b' : {'y', 'z'}, 'c' : {x} }
for key, value in alphabet.items():
      if  'y' in value:
             print(key)

6. 用'&'或是intersection()來取得交集,或是用'|'或union()來取得聯集,或是用'-'或difference()來取得差集
7. 用'<='或issubset()來檢查子集合。用'<'來檢查真子集合(proper subset, 代表兩集合不一樣)。也可以用'>='或ussuperset()來檢查超集合(superset),用'>'來檢查真超集合(proper superset)。

2018年4月22日 星期日

Python筆記:數字、字串與變數

變數、名稱與物件

1.在Python中,所有的東西都是物件,物件會有一個類型(type),類型決定物件的特性。類別(class)則是物件的定義。在Python中兩者幾乎是同樣的意義。
2.Python是一種強類型(strong typing)的語言,意味著物件的類型無法變更
3.我們可以使用type(Object)來取得物件的類型:
>>>type(67)
<class 'int'>

數字

"/ "是浮點數除法運算子,"//"是整數的除法運算子:
>>>9 / 5 
1.8
>>>9 // 5
1
divmod(a, b)可以用來同時取得商和餘數:
>>>divmod(9, 5)
(1, 4)

基數

整數預設都是十進位,但是可以用0b/0B(二進位),0o/0O(八進位),0x/0X(十六進位)來表達其他基數的整數。

類型轉換

int(literal)可以把合法的literal轉換為整數。

字串

1. Python 3支援Unicode標準,這種處理標準的能力是Python2所不具備的。
2. 在Python中,我們可以用雙引號或單引號來包字串。也可以使用三個單/雙引號來建立多行字串
>>poem = '''This is a purposely created
multi-lined string.''''
這樣的方式產生的字串會包含所有內含的跳脫字元以及空格。
3. print()會自動把多個參數合在一起並在其間加上空格,並在結尾加上換行符號。
4. str()可以用來把其他資料類型轉為字串。
5. "*"可以用來複製字串。ex: 'A' *4。
注意:Python中的字串是不可變的。

Slice: [開啟:結束:間隔]

Slice可以用來擷取子字串:
  • [:]會擷取整個字串
  • [start:]會從start擷取到結束
  • [:end]會從開始擷取到end-1
  • [start:end:step]會從start以step個間隔擷取到end
其他函式:
1. string.split('delimiter')可以用來以特定字元分割字串。
2. 'delimiter'.join(sequence)可以用來結合序列。