算法部分

這周的算法完成的是largest container，開始用的是暴力枚舉比較出最大值，后來改成了兩個首尾兩個cursor依次收縮。大致上復雜度就變成了線性。不過我在收縮首尾時設了一個循環，這樣只有新值比原值更大時才投入計算容積，不然就一直收縮。不過我看比我更快的算法時，它不做比較直接收縮。直觀上看似乎計算量不小，但是性能上其實更好，畢竟內部套一個循環實際要多很多測試和跳轉，對于程序是不必要的開銷。

int maxArea(int* height, int heightSize) {int cur_l=0,cur_r=heightSize-1;int ht_l = height[cur_l], ht_r = height[cur_r];int vol=0;int maxVol = 0;int move;int h;while(cur_l < cur_r){move = ht_l < ht_r? LEFT: RIGHT;h = MIN(ht_l,ht_r);vol = (cur_r-cur_l)* h ;maxVol = vol > maxVol? vol:maxVol;if(move == LEFT){do{cur_l++;if ((ht_l=height[cur_l])>h){break;}}while(cur_l < cur_r);} else {do{cur_r--;if ((ht_r=height[cur_r])>h){break;}}while(cur_l < cur_r);}}return maxVol; } 復制代碼

Review部分

這周倒是沒有看新的部分，而是繼續把CSAPP的第三章習題做完了。涉及反匯編時反推編譯器是如何優化代碼，以及我們怎樣寫程序能夠使編譯器編譯時少用一個寄存器這個還是蠻有意思的。比如3.66和3.67反推結構體聲明和原始C程序。下面附上3.67的答案（我自己在x86上測試正確）。

// CSAPP2ed 3.67 void proc(union ele *up) {up->e2.next->e1.x = *(up->e2.next->e1.p) - up->e2.y; } 復制代碼

Tip部分

在完成CSAPP課后練習時因為需要生成超過BUFSIZE的字符串文本而且不能換行，又復習了一下shell的用法：

echo -n {0001..2048} >> test_file 復制代碼

使用-n 是為了不換行，不然結果就會是

0001 0002 0003 ... 2048 復制代碼

使用 >> 是為了追加到原文本中，而不是全部重寫。不過用來生成測試文本用>重寫一遍也沒問題的。

Summary部分（計算機體系結構）

Feature size的定義為x軸或y軸上晶體管的最小尺寸。

晶體管在芯片上的尺寸線性下降，因此晶體管的密度平方階上升。

晶體管性能的提升就稍微復雜了一點。feature size的下降意味著水平和垂直方向尺寸均在下降。垂直方向的下降意味著電壓也需要下降至適配的情況。近似來看，性能的變化與feature size呈線性關系。

晶體管性能的線性提升和數目的平方階提升既是機遇又是挑戰。這一變化促進了多核處理器的轉變。以及SIMD（單一指令多數據）的推廣。

不過盡管晶體管密度變大了，單位長度的電阻和電容也變差了。

23頁提到了微處理器的電量消耗與時鐘頻率，電壓，電容等的關系。時鐘頻率越慢的處理器，單位時間耗電量更小（但不代表完成固定任務消耗的能量少）。因此25頁談到了現代處理器有幾個省電的方式，其中之一就是關閉時鐘（如無需浮點計算時關閉浮點單元的時鐘）；動態調節時鐘（比如移動設備的睡眠模式，由于此時無任務需要處理，使用低頻時鐘，耗電量變低）；主存和磁盤也據此情況設計得更為省電；為了省電，可以關閉某些核，同時使另一些核具有超過硬件規定的時鐘頻率做短時間的運算處理。

考慮到晶體管數目的變多會自然帶來能耗的增加，而且也會增加leakage(漏電)。考察性能的度量方式不再是每平方毫米上的性能表現，而是基于每瓦或每焦耳完成的任務量（會在第4和5章繼續討論）。

======

CSAPP要繼續看第四章了，也是會要說到指令集結構等關乎硬件方面的東西，感覺稍稍有些硬。計算機體系結構一書也是蠻硬的。希望能繼續啃下去。

總結

以上是生活随笔為你收集整理的ARTS训练第三周的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。