西灣筆記

擷英採華,以備不需!

【譯】後綴樹快速字串搜尋

• Suffix Tree, Trie, Algorithm

這篇筆記、翻譯自博文:Fast String Searching With Suffix Trees,作者Mark Nelson。尊重他人勞動果實,轉載請註明!

I think that I shall never see
A poem lovely as a tree.
Poems are made by fools like me,
But only God can make a tree.

–Joyce Kilmer

A tree’s a tree. How many more do you need to look at?

–Ronald Reagan-

字串序列匹配是電腦程式設計師經常需要面對的問題。一些編程任務,例如數據壓縮或DNA測序,可以從字串匹配演算法的改進中獲益匪淺。本文探討了一種相對未知的數據結構,即後綴樹,並展示如何使用它的特性着手解决字串匹配的難題。

【譯】C語言「右左規則」

• C

這篇筆記、翻譯自博文:C Right-Left Rule,作者Rick Ord。尊重他人勞動果實,轉載請註明!

「右左」規則是解讀C宣告十分實用的規則。創建宣告時它也同樣有用。

Android原始碼下載

• Android, AOSP, kernel, repo

Android原始碼包含兩個部分:Android開源專案(Android Open Source Project,AOSP)原始碼與Android內核原始碼。

下載前、首先確認以下事項:

前三項都是下載所需的組件,不必多說;說說最後一項:一開始打算在Windows下使用MinGW32進行下載的,但是遇到這樣的錯誤:

ImportError: No module named fcntl

於是、果斷投奔Mac OS X的懷抱。但也有人改換Cygwin,感興趣的可以一試。

鑑於龐大的程式碼規模、請務必使用高速且穩定的網路:Android開源專案原始碼藉由專用工具repo、可以實現斷點續傳;而Android內核原始碼、一旦中斷就得重新開始。

Android開源專案原始碼的下載教程請參考這裡,Android內核原始碼的下載教程請參考這裡。以下簡單的做下筆記:

閏年的最佳效率演算法

• Leap Year, Algorithm

所謂閏年,維基百科做了如是介紹

閏年是比普通年分多出一段時間的年分,在各種曆法中都有出現,目的是為了彌補人為規定的紀年與地球公轉產生的差異。

目前使用的格里曆閏年規則如下:

  1. 西元年分除以400可整除,為閏年。
  2. 西元年分除以4可整除但除以100不可整除,為閏年。
  3. 西元年分除以4不可整除,為平年。
  4. 西元年分除以100可整除但除以400不可整除,為平年。

在C,C++,C#,Java,以及許多類C編程語言的入門書籍裏,舉凡講到運算子一節,一般都會提及閏年的演算法;且不出意外、一般皆為:

if (((year % 4) == 0 && (year % 100) != 0) || (year % 400) == 0)
{
    /* leap year */
}

這演算法簡單明瞭、但在效率上卻顯得差強人意;因而、在stackoverflow上有討論,認為若以效率考量、則最佳演算法為:

if ((year & 3) == 0 && ((year % 25) != 0 || (year & 15) == 0))
{
    /* leap year */
}

那麼、這「最佳效率」演算法如何得來呢?以下便是推演過程。

Mac OS X下Git遇到編輯器vi錯誤

• Mac OS X, Git, vi

Mac OS X下Git進行提交時,會遇到這樣的錯誤:

error: There was a problem with the editor ‘vi’.
Please supply the message using either -m or -F option.

大致搜尋了下,stackoverflow上的這個解答剛好對症。