一、codetest1
4.3約筆試，兩道題，一道考察算法，一道考察深度學(xué)習(xí)框架，兩小時(shí)，線下做。
二、codetest2
手寫代碼，檢測(cè)鏈表中是否有環(huán)，這個(gè)比較簡(jiǎn)單，和leetcode的一個(gè)題目是一樣的，因?yàn)槲覍懙锰炝耍捅患恿它c(diǎn)難度，如果一個(gè)鏈表中有環(huán)，那么判斷哪個(gè)節(jié)點(diǎn)是環(huán)的進(jìn)入節(jié)點(diǎn)。
方法一：哈希表
思路及算法
最容易想到的方法是遍歷所有節(jié)點(diǎn)，每次遍歷到一個(gè)節(jié)點(diǎn)時(shí)，判斷該節(jié)點(diǎn)此前是否被訪問(wèn)過(guò)。
具體地，我們可以使用哈希表來(lái)存儲(chǔ)所有已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。每次我們到達(dá)一個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)已經(jīng)存在于哈希表中，則說(shuō)明該鏈表是環(huán)形鏈表，否則就將該節(jié)點(diǎn)加入哈希表中。重復(fù)這一過(guò)程，直到我們遍歷完整個(gè)鏈表即可。
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> seen;
while (head != nullptr) {
if (seen.count(head)) {
return true;
}
seen.insert(head);
head = head->next;
}
return false;
}
};
class Solution:
def hasCycle(self, head: ListNode) -> bool:
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
復(fù)雜度分析
時(shí)間復(fù)雜度：O(N)O(N)，其中 NN 是鏈表中的節(jié)點(diǎn)數(shù)。最壞情況下我們需要遍歷每個(gè)節(jié)點(diǎn)一次。
空間復(fù)雜度：O(N)O(N)，其中 NN 是鏈表中的節(jié)點(diǎn)數(shù)。主要為哈希表的開銷，最壞情況下我們需要將每個(gè)節(jié)點(diǎn)插入到哈希表中一次。
方法二：快慢指針
思路及算法
本方法需要讀者對(duì)「Floyd 判圈算法」（又稱龜兔賽跑算法）有所了解。
假想「烏龜」和「兔子」在鏈表上移動(dòng)，「兔子」跑得快，「烏龜」跑得慢。當(dāng)「烏龜」和「兔子」從鏈表上的同一個(gè)節(jié)點(diǎn)開始移動(dòng)時(shí)，如果該鏈表中沒(méi)有環(huán)，那么「兔子」將一直處于「烏龜」的前方；如果該鏈表中有環(huán)，那么「兔子」會(huì)先于「烏龜」進(jìn)入環(huán)，并且一直在環(huán)內(nèi)移動(dòng)。等到「烏龜」進(jìn)入環(huán)時(shí)，由于「兔子」的速度快，它一定會(huì)在某個(gè)時(shí)刻與烏龜相遇，即套了「烏龜」若干圈。
我們可以根據(jù)上述思路來(lái)解決本題。具體地，我們定義兩個(gè)指針，一快一滿。慢指針每次只移動(dòng)一步，而快指針每次移動(dòng)兩步。初始時(shí)，慢指針在位置 head，而快指針在位置 head.next。這樣一來(lái)，如果在移動(dòng)的過(guò)程中，快指針?lè)催^(guò)來(lái)追上慢指針，就說(shuō)明該鏈表為環(huán)形鏈表。否則快指針將到達(dá)鏈表尾部，該鏈表不為環(huán)形鏈表。
細(xì)節(jié)
為什么我們要規(guī)定初始時(shí)慢指針在位置 head，快指針在位置 head.next，而不是兩個(gè)指針都在位置 head（即與「烏龜」和「兔子」中的敘述相同）？
觀察下面的代碼，我們使用的是 while 循環(huán)，循環(huán)條件先于循環(huán)體。由于循環(huán)條件一定是判斷快慢指針是否重合，如果我們將兩個(gè)指針初始都置于 head，那么 while 循環(huán)就不會(huì)執(zhí)行。因此，我們可以假想一個(gè)在 head 之前的虛擬節(jié)點(diǎn)，慢指針從虛擬節(jié)點(diǎn)移動(dòng)一步到達(dá) head，快指針從虛擬節(jié)點(diǎn)移動(dòng)兩步到達(dá) head.next，這樣我們就可以使用 while 循環(huán)了。當(dāng)然，我們也可以使用 do-while 循環(huán)。此時(shí)，我們就可以把快慢指針的初始值都置為 head。
class Solution {
public:
bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(N)O(N)，其中 NN 是鏈表中的節(jié)點(diǎn)數(shù)。
當(dāng)鏈表中不存在環(huán)時(shí)，快指針將先于慢指針到達(dá)鏈表尾部，鏈表中每個(gè)節(jié)點(diǎn)至多被訪問(wèn)兩次。
當(dāng)鏈表中存在環(huán)時(shí)，每一輪移動(dòng)后，快慢指針的距離將減小一。而初始距離為環(huán)的長(zhǎng)度，因此至多移動(dòng) NN 輪。 - 空間復(fù)雜度：O(1)O(1)。我們只使用了兩個(gè)指針的額外空間。
手寫代碼，判斷一個(gè)無(wú)序數(shù)組中，最長(zhǎng)的連續(xù)相同的元素個(gè)數(shù)，這個(gè)也挺簡(jiǎn)單的，就是注意一下跳出的時(shí)候最后一次有沒(méi)有進(jìn)行比較就行了，面試官說(shuō)看你思路清晰，經(jīng)常刷題吧，勉強(qiáng)算你過(guò)了吧。
三、codetest3
題目1：
A為一個(gè)十進(jìn)制數(shù)（以整數(shù)為例），k位，k<100。求B使得B為大于A的最小整數(shù)，且A各位的和等于B各位的和。
題目2：
給一定數(shù)量的信封，帶有整數(shù)對(duì) (w, h) 分別代表信封寬度和高度。一個(gè)信封的寬高均大于另一個(gè)信封時(shí)可以放下另一個(gè)信封。求最大的信封嵌套層數(shù)。
樣例
給一些信封 [[5,4],[6,4],[6,7],[2,3]] ，最大的信封嵌套層數(shù)是 3([2,3] => [5,4] => [6,7])。
給你一個(gè)二維整數(shù)數(shù)組 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 個(gè)信封的寬度和高度。當(dāng)另一個(gè)信封的寬度和高度都比這個(gè)信封大的時(shí)候，這個(gè)信封就可以放進(jìn)另一個(gè)信封里，如同俄羅斯套娃一樣。請(qǐng)計(jì)算 最多能有多少個(gè) 信封能組成一組“俄羅斯套娃”信封（即可以把一個(gè)信封放到另一個(gè)信封里面）。
注意：不允許旋轉(zhuǎn)信封。
示例 1：
輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出：3
解釋：最多信封的個(gè)數(shù)為 3, 組合為: [2,3] => [5,4] => [6,7]。
示例 2：
輸入：envelopes = [[1,1],[1,1],[1,1]]
輸出：1
前言
動(dòng)態(tài)規(guī)劃
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.empty()) {
return 0;
}
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
});
vector<int> f(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (envelopes[j][1] < envelopes[i][1]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
return *max_element(f.begin(), f.end());
}
};
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
n = len(envelopes)
envelopes.sort(key=lambda x: (x[0], -x[1]))
f = [1] * n
for i in range(n):
for j in range(i):
if envelopes[j][1] < envelopes[i][1]:
f[i] = max(f[i], f[j] + 1)
return max(f)
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n^2)，其中 nn 是數(shù)組 \textit{envelopes}envelopes 的長(zhǎng)度，排序需要的時(shí)間復(fù)雜度為O(nlogn)，動(dòng)態(tài)規(guī)劃需要的時(shí)間復(fù)雜度為 O(n^2)O，前者在漸近意義下小于后者，可以忽略。
- 空間復(fù)雜度：O(n)O(n)，即為數(shù)組 ff 需要的空間。
基于二分查找的動(dòng)態(tài)規(guī)劃
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.empty()) {
return 0;
}
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
});
vector<int> f = {envelopes[0][1]};
for (int i = 1; i < n; ++i) {
if (int num = envelopes[i][1]; num > f.back()) {
f.push_back(num);
}
else {
auto it = lower_bound(f.begin(), f.end(), num);
*it = num;
}
}
return f.size();
}
};
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
n = len(envelopes)
envelopes.sort(key=lambda x: (x[0], -x[1]))
f = [envelopes[0][1]]
for i in range(1, n):
if (num := envelopes[i][1]) > f[-1]:
f.append(num)
else:
index = bisect.bisect_left(f, num)
f[index] = num
return len(f)
復(fù)雜度分析
時(shí)間復(fù)雜度：O(nlogn)，其中 nn 是數(shù)組 \textit{envelopes}envelopes 的長(zhǎng)度，排序需要的時(shí)間復(fù)雜度為O(nlogn)，動(dòng)態(tài)規(guī)劃需要的時(shí)間復(fù)雜度同樣為 O(nlogn)。
空間復(fù)雜度：O(n)，即為數(shù)組 ff 需要的空間。
from typing import List
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
size = len(envelopes)
#print(envelopes)
if size < 2: # if the size of envelopes is smaller than 2, return
return size
envelopes.sort(key=lambda x: x[0]) # sort the envelopes according the width
dp = [1 for _ in range(size)] #record the number of envelope layers
#print(dp)
for i in range(1, size):
for j in range(i):
# compare the width and length of envelopes
if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
if __name__ == '__main__':
envelopes = [[5,4],[6,4],[6,7],[2,3],[99,100]] #input the matrix of envelopes
solution = Solution()
res = solution.maxEnvelopes(envelopes)
print("The maximum envelope nesting layer is %d" %(res))
四、codetest4
反向部分鏈表元素（LeetCode中等難度；僅可通過(guò)常規(guī)的鏈表指針操作實(shí)現(xiàn)、僅可遍歷一次、不可通過(guò)交換鏈表指向的值來(lái)完成）。
給你單鏈表的頭指針 head 和兩個(gè)整數(shù) left 和 right ，其中 left <= right 。請(qǐng)你反轉(zhuǎn)從位置 left 到位置 right 的鏈表節(jié)點(diǎn)，返回 反轉(zhuǎn)后的鏈表 。
前言
鏈表的操作問(wèn)題，一般而言面試（機(jī)試）的時(shí)候不允許我們修改節(jié)點(diǎn)的值，而只能修改節(jié)點(diǎn)的指向操作。思路通常都不難，寫對(duì)鏈表問(wèn)題的技巧是：一定要先想清楚思路，并且必要的時(shí)候在草稿紙上畫圖，理清「穿針引線」的先后步驟，然后再編碼。
方法一：穿針引線
我們以下圖中黃色區(qū)域的鏈表反轉(zhuǎn)為例。
使用「206. 反轉(zhuǎn)鏈表」的解法，反轉(zhuǎn) left 到 right 部分以后，再拼接起來(lái)。我們還需要記錄 left 的前一個(gè)節(jié)點(diǎn)，和 right 的后一個(gè)節(jié)點(diǎn)。如圖所示：
算法步驟：
- 先將待反轉(zhuǎn)的區(qū)域反轉(zhuǎn)；
-
把 pre 的 next 指針指向反轉(zhuǎn)以后的鏈表頭節(jié)點(diǎn)，把反轉(zhuǎn)以后的鏈表的尾節(jié)點(diǎn)的 next 指針指向 succ。
image.png
說(shuō)明：編碼細(xì)節(jié)我們不在題解中介紹了，請(qǐng)見(jiàn)下方代碼。思路想明白以后，編碼不是一件很難的事情。這里要提醒大家的是，鏈接什么時(shí)候切斷，什么時(shí)候補(bǔ)上去，先后順序一定要想清楚，如果想不清楚，可以在紙上模擬，讓思路清晰。
class Solution {
private:
void reverseLinkedList(ListNode *head) {
// 也可以使用遞歸反轉(zhuǎn)一個(gè)鏈表
ListNode *pre = nullptr;
ListNode *cur = head;
while (cur != nullptr) {
ListNode *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
}
public:
ListNode *reverseBetween(ListNode *head, int left, int right) {
// 因?yàn)轭^節(jié)點(diǎn)有可能發(fā)生變化，使用虛擬頭節(jié)點(diǎn)可以避免復(fù)雜的分類討論
ListNode *dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode *pre = dummyNode;
// 第 1 步：從虛擬頭節(jié)點(diǎn)走 left - 1 步，來(lái)到 left 節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
// 建議寫在 for 循環(huán)里，語(yǔ)義清晰
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
// 第 2 步：從 pre 再走 right - left + 1 步，來(lái)到 right 節(jié)點(diǎn)
ListNode *rightNode = pre;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode->next;
}
// 第 3 步：切斷出一個(gè)子鏈表（截取鏈表）
ListNode *leftNode = pre->next;
ListNode *curr = rightNode->next;
// 注意：切斷鏈接
pre->next = nullptr;
rightNode->next = nullptr;
// 第 4 步：同第 206 題，反轉(zhuǎn)鏈表的子區(qū)間
reverseLinkedList(leftNode);
// 第 5 步：接回到原來(lái)的鏈表中
pre->next = rightNode;
leftNode->next = curr;
return dummyNode->next;
}
};
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
def reverse_linked_list(head: ListNode):
# 也可以使用遞歸反轉(zhuǎn)一個(gè)鏈表
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
# 因?yàn)轭^節(jié)點(diǎn)有可能發(fā)生變化，使用虛擬頭節(jié)點(diǎn)可以避免復(fù)雜的分類討論
dummy_node = ListNode(-1)
dummy_node.next = head
pre = dummy_node
# 第 1 步：從虛擬頭節(jié)點(diǎn)走 left - 1 步，來(lái)到 left 節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
# 建議寫在 for 循環(huán)里，語(yǔ)義清晰
for _ in range(left - 1):
pre = pre.next
# 第 2 步：從 pre 再走 right - left + 1 步，來(lái)到 right 節(jié)點(diǎn)
right_node = pre
for _ in range(right - left + 1):
right_node = right_node.next
# 第 3 步：切斷出一個(gè)子鏈表（截取鏈表）
left_node = pre.next
curr = right_node.next
# 注意：切斷鏈接
pre.next = None
right_node.next = None
# 第 4 步：同第 206 題，反轉(zhuǎn)鏈表的子區(qū)間
reverse_linked_list(left_node)
# 第 5 步：接回到原來(lái)的鏈表中
pre.next = right_node
left_node.next = curr
return dummy_node.next
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(N)O(N)，其中 NN 是鏈表總節(jié)點(diǎn)數(shù)。最壞情況下，需要遍歷整個(gè)鏈表。
- 空間復(fù)雜度：O(1)O(1)。只使用到常數(shù)個(gè)變量。
方法二：一次遍歷「穿針引線」反轉(zhuǎn)鏈表（頭插法）
方法一的缺點(diǎn)是：如果 left 和 right 的區(qū)域很大，恰好是鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)時(shí)，找到 left 和 right 需要遍歷一次，反轉(zhuǎn)它們之間的鏈表還需要遍歷一次，雖然總的時(shí)間復(fù)雜度為 O(N)O(N)，但遍歷了鏈表 22 次，可不可以只遍歷一次呢？答案是可以的。我們依然畫圖進(jìn)行說(shuō)明。
我們依然以方法一的示例為例進(jìn)行說(shuō)明。
整體思想是：在需要反轉(zhuǎn)的區(qū)間里，每遍歷到一個(gè)節(jié)點(diǎn)，讓這個(gè)新節(jié)點(diǎn)來(lái)到反轉(zhuǎn)部分的起始位置。下面的圖展示了整個(gè)流程。
下面我們具體解釋如何實(shí)現(xiàn)。使用三個(gè)指針變量 pre、curr、next 來(lái)記錄反轉(zhuǎn)的過(guò)程中需要的變量，它們的意義如下：
- curr：指向待反轉(zhuǎn)區(qū)域的第一個(gè)節(jié)點(diǎn) left；
- next：永遠(yuǎn)指向 curr 的下一個(gè)節(jié)點(diǎn)，循環(huán)過(guò)程中，curr 變化以后 next 會(huì)變化；
- pre：永遠(yuǎn)指向待反轉(zhuǎn)區(qū)域的第一個(gè)節(jié)點(diǎn) left 的前一個(gè)節(jié)點(diǎn)，在循環(huán)過(guò)程中不變。
第 1 步，我們使用 ①、②、③ 標(biāo)注「穿針引線」的步驟。
操作步驟：
- 先將 curr 的下一個(gè)節(jié)點(diǎn)記錄為 next；
- 執(zhí)行操作 ①：把 curr 的下一個(gè)節(jié)點(diǎn)指向 next 的下一個(gè)節(jié)點(diǎn)；
- 執(zhí)行操作 ②：把 next 的下一個(gè)節(jié)點(diǎn)指向 pre 的下一個(gè)節(jié)點(diǎn)；
- 執(zhí)行操作 ③：把 pre 的下一個(gè)節(jié)點(diǎn)指向 next。
第 1 步完成以后「拉直」的效果如下：
image.png
第 2 步，同理。同樣需要注意 「穿針引線」操作的先后順序。
image.png
第 2 步完成以后「拉直」的效果如下：
image.png
第 3 步，同理。
image.png
第 3 步完成以后「拉直」的效果如下：
image.png
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int left, int right) {
// 設(shè)置 dummyNode 是這一類問(wèn)題的一般做法
ListNode *dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode *pre = dummyNode;
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
ListNode *cur = pre->next;
ListNode *next;
for (int i = 0; i < right - left; i++) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
return dummyNode->next;
}
};
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
# 設(shè)置 dummyNode 是這一類問(wèn)題的一般做法
dummy_node = ListNode(-1)
dummy_node.next = head
pre = dummy_node
for _ in range(left - 1):
pre = pre.next
cur = pre.next
for _ in range(right - left):
next = cur.next
cur.next = next.next
next.next = pre.next
pre.next = next
return dummy_node.next
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：O(N)O(N)，其中 NN 是鏈表總節(jié)點(diǎn)數(shù)。最多只遍歷了鏈表一次，就完成了反轉(zhuǎn)。
- 空間復(fù)雜度：O(1)O(1)。只使用到常數(shù)個(gè)變量。
五、codetest5
卷積加速
1、常規(guī)for循環(huán)
這樣會(huì)引入串行for循環(huán)逐一像素進(jìn)行操作，然后在每一個(gè)窗口大小的矩陣上進(jìn)行卷積運(yùn)算，效率太低。下面擴(kuò)展到3通道卷積操作，利用numpy切片同時(shí)計(jì)算3個(gè)通道。
def convolve2d(arr, kernel, stride=1, padding='same'):
'''
Using convolution kernel to smooth image
Parameters
===========
arr: 3D array or 3-channel image
kernel: Filter matrix
stride: Stride of scanning
padding: padding mode
'''
h, w, channel = arr.shape
k = kernel.shape[0]
r = int(k/2)
kernel_r = np.rot90(kernel,k=2,axes=(0,1))
# padding outer area with 0
padding_arr = np.zeros([h+k-1,w+k-1,channel])
padding_arr[r:h+r,r:w+r] = arr
new_arr = np.zeros(arr.shape)
for i in range(r,h+r,stride):
for j in range(r,w+r,stride):
roi = padding_arr[i-r:i+r+1,j-r:j+r+1]
new_arr[i-r,j-r] = np.sum(np.sum(roi*kernel_r,axis=0),axis=0)
return new_arr[::stride,::stride]
if __name__=='__main__':
A = np.arange(1,10001).reshape((100,100,1))
print(A.shape)
kernel = np.arange(1,10).reshape((3,3,1))/45
# convert to 3-channels
A3 = np.concatenate((A, 2*A, 3*A), axis=-1)
k3 = np.concatenate((kernel, kernel, kernel), axis=-1)
t1 = time.time()
for i in range(100):
A1 = convolve2d(A3,kernel,stride=2).astype(np.int)
t2 = time.time()
print(t2-t1)
###output
(100, 100, 1)
3.2025175
雖然不用循環(huán)計(jì)算多個(gè)通道，單通道與多通道耗時(shí)相同，但是依然需要for循環(huán)來(lái)滑動(dòng)窗口kernel，對(duì)于大圖片速度很慢，需要進(jìn)一步將外層循環(huán)替代。
向量化索引運(yùn)算
def convolve2d_vector(arr, kernel, stride=1, padding='same'):
h, w, channel = arr.shape[0],arr.shape[1],arr.shape[2]
k = kernel.shape[0]
r = int(k/2)
kernel_r = np.rot90(kernel,k=2,axes=(0,1))
# padding outer area with 0
padding_arr = np.zeros([h+k-1,w+k-1,channel])
padding_arr[r:h+r,r:w+r] = arr
new_arr = np.zeros(arr.shape)
vector = np.array(list(itertools.product(np.arange(r,h+r,stride),np.arange(r,w+r,stride))))
vi = vector[:,0]
vj = vector[:,1]
def _convolution(vi,vj):
roi = padding_arr[vi-r:vi+r+1,vj-r:vj+r+1]
new_arr[vi-r,vj-r] = np.sum(np.sum(roi*kernel_r,axis=0),axis=0)
vfunc = np.vectorize(_convolution)
vfunc(vi,vj)
return new_arr[::stride,::stride]
看來(lái)簡(jiǎn)單地使用 np.vectorize(）并沒(méi)有實(shí)現(xiàn)向量化展開，必須對(duì)原圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行重新排列和擴(kuò)展才能真正地利用向量化機(jī)制，即將窗口滑動(dòng)轉(zhuǎn)換為真正的矩陣運(yùn)算。
矩陣乘法運(yùn)算
正常的三通道卷積
轉(zhuǎn)換為矩陣相乘，對(duì)kernel和原圖進(jìn)行重新排列：
將卷積運(yùn)算轉(zhuǎn)化為矩陣乘法，從乘法和加法的運(yùn)算次數(shù)上看沒(méi)什么差別，但是轉(zhuǎn)化成矩陣后，可以在連續(xù)內(nèi)存和緩存上操作，而且有很多庫(kù)提供了高效的實(shí)現(xiàn)方法（BLAS、MKL），numpy內(nèi)部基于MKL實(shí)現(xiàn)運(yùn)算的加速。圖像展開消耗了更多的內(nèi)存，以空間換時(shí)間，另一方面，展開成矩陣形式可以轉(zhuǎn)換成CUDA代碼使用GPU加速。
上圖展示了3通道卷積的展開過(guò)程，RGB通道首位拼接，矩陣乘法運(yùn)算后的結(jié)果是三個(gè)通道卷積結(jié)果的累加，這里有所不同，我們需要單獨(dú)輸出每個(gè)通道的卷積結(jié)果而不累加，與原圖像大小相同，見(jiàn)下圖。
二維矩陣乘法采用np.dot()函數(shù)，而高維數(shù)組乘法運(yùn)算采用np.matmul()函數(shù)。高維數(shù)組（n>2）相乘須滿足以下兩個(gè)條件：
兩個(gè)n維數(shù)組的前n-2維必須完全相同。例如（3,2,4,2）（3,2,2,3）前兩維必須完全一致；
最后兩維必須滿足二階矩陣乘法要求。例如（3,2,4,2）（3,2,2,3）的后兩維可視為（4,2）x（2,3）滿足矩陣乘法。
先利用reshape將kernel展開為(1,k*k,c)，再用轉(zhuǎn)置函數(shù)transpose將channel前置，照此方法循環(huán)展開image矩陣。numpy的廣播規(guī)則會(huì)將kernel的第一個(gè)維度補(bǔ)齊，所以輸入kernel可以是1通道的（三通道共用一個(gè)卷積核）。
def convolve2d_vector(arr, kernel, stride=1, padding='same'):
h, w, channel = arr.shape[0],arr.shape[1],arr.shape[2]
k, n = kernel.shape[0], kernel.shape[2]
r = int(k/2)
#重新排列kernel為左乘矩陣，通道channel前置以便利用高維數(shù)組的矩陣乘法
matrix_l = kernel.reshape((1,k*k,n)).transpose((2,0,1))
padding_arr = np.zeros([h+k-1,w+k-1,channel])
padding_arr[r:h+r,r:w+r] = arr
#重新排列image為右乘矩陣，通道channel前置
matrix_r = np.zeros((channel,k*k,h*w))
for i in range(r,h+r,stride):
for j in range(r,w+r,stride):
roi = padding_arr[i-r:i+r+1,j-r:j+r+1].reshape((k*k,1,channel)).transpose((2,0,1))
matrix_r[:,:,(i-r)*w+j-r:(i-r)*w+j-r+1] = roi[:,::-1,:]
result = np.matmul(matrix_l, matrix_r)
out = result.reshape((channel,h,w)).transpose((1,2,0))
return out[::stride,::stride]
if __name__=='__main__':
N=1000
A = np.arange(1,N**2+1).reshape((N,N,1))
print(A.shape)
kernel = np.arange(3**2).reshape((3,3,1))/45
# convert to 3-channels
A3 = np.concatenate((A, 2*A, 3*A), axis=-1)
k3 = np.concatenate((kernel, kernel, kernel), axis=-1)
t1 = time.time()
for i in range(1):
B1 = convolve2d(A,kernel,stride=2).astype(np.int)
t2 = time.time()
print(t2-t1)
t1 = time.time()
for i in range(1):
B2 = convolve2d_vector(A,kernel,stride=2).astype(np.int)
t2 = time.time()
print(t2-t1)
print(B1.all()==B2.all())
###output
(1000, 1000, 1)
4.517540216445923
0.8763346672058105
True
可以看到運(yùn)算結(jié)果與convolve2d滑動(dòng)卷積的結(jié)果一致，且速度提升了5倍左右。速度主要瓶頸還是來(lái)自image的展開操作，這里還是滑動(dòng)窗口掃描實(shí)現(xiàn)的，for循環(huán)內(nèi)部進(jìn)行了局部拷貝操作，是串行的，數(shù)組切片和矩陣運(yùn)算部分是并行的。
總結(jié)
在CPU程序上優(yōu)化卷積運(yùn)算，numpy庫(kù)是個(gè)不錯(cuò)的選擇，初始算法將三通道計(jì)算和求和過(guò)程并行化，獲得了接近3倍的加速。轉(zhuǎn)換為矩陣/多維數(shù)組乘法后，速度進(jìn)一步提升了5倍。在python中用多線程和多進(jìn)程的方式加速for循環(huán)效果并不理想，CPU程序上創(chuàng)建和啟動(dòng)多線程開銷很大，進(jìn)程和線程通信、傳遞數(shù)據(jù)消耗了大部分時(shí)間，總體速度不升反降。
六、codetest6 sigmoid 反向傳播
class Network(object):
...
def backprop(self, x, y):
"""Return a tuple "(nabla_b, nabla_w)" representing the
gradient for the cost function C_x. "nabla_b" and
"nabla_w" are layer-by-layer lists of numpy arrays, similar
to "self.biases" and "self.weights"."""
nabla_b = [np.zeros(b.shape) for b in self.biases]
nabla_w = [np.zeros(w.shape) for w in self.weights]
# feedforward
activation = x
activations = [x] # list to store all the activations, layer by layer
zs = [] # list to store all the z vectors, layer by layer
for b, w in zip(self.biases, self.weights):
z = np.dot(w, activation)+b
zs.append(z)
activation = sigmoid(z)
activations.append(activation)
# backward pass
delta = self.cost_derivative(activations[-1], y) * \
sigmoid_prime(zs[-1])
nabla_b[-1] = delta
nabla_w[-1] = np.dot(delta, activations[-2].transpose())
# Note that the variable l in the loop below is used a little
# differently to the notation in Chapter 2 of the book. Here,
# l = 1 means the last layer of neurons, l = 2 is the
# second-last layer, and so on. It's a renumbering of the
# scheme in the book, used here to take advantage of the fact
# that Python can use negative indices in lists.
for l in xrange(2, self.num_layers):
z = zs[-l]
sp = sigmoid_prime(z)
delta = np.dot(self.weights[-l+1].transpose(), delta) * sp
nabla_b[-l] = delta
nabla_w[-l] = np.dot(delta, activations[-l-1].transpose())
return (nabla_b, nabla_w)
...
def cost_derivative(self, output_activations, y):
"""Return the vector of partial derivatives \partial C_x /
\partial a for the output activations."""
return (output_activations-y)
def sigmoid(z):
"""The sigmoid function."""
return 1.0/(1.0+np.exp(-z))
def sigmoid_prime(z):
"""Derivative of the sigmoid function."""
return sigmoid(z)*(1-sigmoid(z))
https://zhuanlan.zhihu.com/p/78713744
https://zhuanlan.zhihu.com/p/260109670
