Nov 4,2019 ~ Nov 10,2019
Algorithm
本周主要的算法是如何求兩個數的最大公因數。傳統的想法便是對這兩個數分解質因數，而後找到其公共因數，再相乘，這樣就會得到最大公因數了。話不多說，直接看代碼吧。
# 求解一個數字x的質因數。注意循環的範圍，若在範圍内沒有找到因數，則說明它是一個素數
import math
def factors(x):
y = int(math.sqrt(x))
R = []
for i in range(2, y+1):
if x % i == 0:
R.append(i)
R = R + factors(x//i)
break
else:
R = [x]
return R
def product(L):
y = 1
for i in L:
y = y * i
return y
def GCD_factors(x, y):
Lx = factors(x)
Ly = factors(y)
def search_and_delete(a, L):
for i in range(len(L)):
if L[i] == a:
return True, L[:i] + L[i+1:]
return False, L
R = []
for e in Lx:
found, Ly = search_and_delete(e, Ly)
if found:
R.append(e)
return product(R)
但是，顯然可以看出，先求解因數，再求解公共因數集合，最後相乘得到結果。這種算法求解最大公因數的時間開銷是較大的，雖然便于了解。那還有一種更快的求解方法，那就是輾轉相除法（又稱歐幾裡德算法），算法主要用到了一個等式，具體如下：
- GCD：求解x，y的最大公因數
- mod：求餘數。例如 a m o d b a \bmod b amodb表示求解a除以b的餘數
- 注，下面的描述中假設$ a > b $
G C D ( a , b ) = G C D ( b , a m o d b ) GCD(a,b) = GCD(b, a \bmod b) GCD(a,b)=GCD(b,amodb)
下面用實際計算過程作為一個例子：
$ GCD(12, 8) = GCD(8, 12 \bmod 8) = GCD(8, 4) = GCD(4, 8 \bmod 4) = GCD(4, 0) = 4 $
有了上面的描述，那麼代碼就很好寫了，代碼如下：
def GCD_Euclid(x, y):
if x < y:
x, y = y, x
if x % y == 0:
return y
return GCD_Euclid(y, x % y)
Review
本周繼續上周的沒有完成的文章，Linux Kernel coding style，開始吧
-
Kconfig檔案
Kcinfig檔案的縮進有所不同，而其中的help隻需要兩格縮進，如果有危險的地方，需要用大寫提醒。縮進格式如下。
config AUDIT
bool "Auditing support"
depends on NET
help
Enable auditing infrastructure that can be used with another
kernel subsystem, such as SELinux (which requires this for
logging of avc messages output). Does not do system-call
auditing without CONFIG_AUDITSYSCALL.
config ADFS_FS_RW
bool "ADFS write support (DANGEROUS)"
depends on ADFS_FS
- 資料結構：資料結構需要注意的要進行引用計數，以防止産生垃圾和遭遇鎖定。
-
宏定義，枚舉
宏定義和枚舉類型的變量必須使用大寫。
宏定義的函數可以像普通函數一樣，函數名采用小寫。但要盡量避免寫宏定義函數，可以用内聯函數去替代。使用宏定義函數有如下幾個需要注意的地方，下面的例子均為反例
- 不要影響控制流
#define FOO(x) \
do { \
if (blah(x) < 0) \
return -EBUGGERED; \
} while (0)
- 避免依賴于局部變量
- 不要用作左值
- 注意優先級，宏定義函數中宏定義變量要用括号擴起來
#define CONSTANT 0x4000
#define CONSTEXP (CONSTANT | 3)
- 在其中定義局部變量時，注意和已有的變量名沖突
#define FOO(x) \
({ \
typeof(x) ret; \
ret = calc_ret(x); \
(ret); \
})
- 列印核心消息，盡量使用簡短正式的語言，準确的描述資訊。
-
配置設定記憶體
為結構體配置設定記憶體盡量使用如下代碼：
配置設定數組盡量使用如下代碼：
配置設定歸零數組盡量使用如下代碼：
-
内聯函數。
大量的使用
inline
會導緻CPU中的icache占用量更大，進而帶來無法命中，反而降低了效率。
内聯要盡可能簡單，文章中給出的建議代碼行數不要多于三行。例外情況是，參數是編譯時常量。
-
函數傳回值和類型
bool類型和整數類型的濫用可能會帶來風險，雖然有時編譯器能幫我們發現這些。
當函數表示動作或指令時，傳回值類型應為整數
當函數表示謂詞（比如是否）時，傳回值類型應為bool
-
不要重新發明核心宏
如果核心中已有某功能的宏函數，那麼不要自己編寫函數。比如計算數組的長度。請利用如下宏函數。
- 不要把個人的對編輯器的設定存放到代碼中
-
内聯彙編
大量的彙編代碼要放到
.s
檔案中。
也許會需要把彙編代碼标記為
volatile
，以防止GCC在将它去除
若有多行彙編，每行彙編要新起一行，不要放在一行代碼裡。
asm ("magic %reg1, #42\n\t"
"more_magic %reg2, %reg3"
: /* outputs */ : /* inputs */ : /* clobbers */);
-
條件編譯
不要将條件編譯語句放到
.c
檔案中
條件編譯最小範圍應為函數，而不是表達式等其他
Tip
在Python中，清單的分片會帶來複制産生新清單。而使用索引就不會帶來這個問題。在一些函數中，參數使用索引來控制通路清單可以提高效率，尤其是在一些遞歸函數中，因為自始自終清單都沒有發生變化。
Share
看完Linux核心代碼風格，雖然有一些東西我在編寫C語言時基本沒有使用過（有可能是我沒有涉及到），但仍有一些東西還是讓我有了一些新的知識。就比如内聯函數，我之前的了解是那隻是對編譯器的一種建議，并不一定會内聯。從來不知道内聯函數過多會帶來性能較低的問題。當然文章裡面也有一些東西我認為是很正常的要求，比如内聯彙編有多行需要換行，但文中仍提及到了，那說明還是有些人并不如此認為
![ARTS Week 25ARTS Week 25[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)