Raspberry Pi板子(以下簡稱rpi)上有26個GPIO 針腳(2x13),可用來連接其他電子元件。本篇將以其中兩個針腳連接LED,並寫Python程式讓它閃爍。我知道這很簡單、很無聊,但總是個開始。
注意,本篇將直接使用GPIO針腳,這是很危險的,搞不好的話會弄壞板子、弄壞板子上的晶片,安全的用法則該使用緩衝板(譬如Mike Cook的Buffer Board)。若你把rpi板子搞壞了,可別說我沒警告你喔。
下圖是rpi的功能區塊圖,左上角就是GPIO的排針。
雖然針腳有26個,但其中6個保留不用,另外有3個是5v、3.3v、0v(GND),所以還有17個針腳可用。
首先是硬體的部份,需製作一條排線,將rpi的針腳接出來。至少需要買一條排線與一個牛角母座。
26線的排線。我買彩色的,比較容易分辨。
牛角母座(2x13),用來壓排線。
將排線平平放進牛角母座的中間,不要突出來。
然後,應該用虎鉗壓緊,但我沒有,於是用鐵鎚敲一敲,嗯,還不錯嘛。
這一端就可以插進rpi的GPIO針腳了。
至於排線的另一端,在這篇裡只需要腳位1(3.3V)與腳位11(GPIO 0),所以我把這兩條線剝皮,腳位1接到紅線,腳位11接到藍紫線。
然後將這兩條線接到麵包板。
紅線(腳位1、3.3V)接LED的正極長腳,
LED負極短腳接1k ohm電阻,
電阻另一腳接藍紫線(腳位11、GPIO 0)。
硬體的部份完成囉。
然後是軟體的部份,將使用RPi.GPIO這套Python程式庫控制GPIO,請到這裡http://pypi.python.org/pypi/RPi.GPIO找到下載網址,我下載的是RPi.GPIO 0.3.1a(RPi.GPIO-0.3.1a.tar.gz)。
下載後解壓縮,
$ tar zxvf RPi.GPIO-0.3.1a.tar.gz
然後切換進入解壓縮後的目錄,以下列指令進行安裝,
$ sudo python setup.py install
但是卻安裝失敗,錯誤訊息說少了Python.h檔,到網路上搜尋後發現需要安裝python-dev這個套件,
$ sudo apt-get install python-dev
然後就能成功安裝RPi.GPIO了。
(目前需要自己手動安裝RPi.GPIO,將來此程式庫應該會被打包成套件。)
(2012.09.27更新:新的映像檔2012-09-18-wheezy-raspbian.img已經內建RPi.GPIO套件。)
接下來要開始寫程式了,請以root身分執行python,
$ sudo python
匯入程式庫,
>>> import RPi.GPIO as GPIO
使用rpi板子的腳位編號,
>>> GPIO.setmode(GPIO.BOARD)
將腳位11(GPIO 0)設為輸出模式,此時LED應該會亮起來,
>>> GPIO.setup(11, GPIO.OUT)
設定為HIGH,LED會熄滅,
>>> GPIO.output(11, GPIO.HIGH)
設定為LOW,LED又會亮起來,
>>> GPIO.output(11, GPIO.LOW)
然後寫個迴圈,讓LED不停閃爍,
>>> while True :
... GPIO.output(11, GPIO.HIGH)
... time.sleep(1)
... GPIO.output(11, GPIO.LOW)
... time.sleep(1)
哇,成功啦,想停止的話請按下Ctrl-C。
後記:
最好還是用虎鉗或老虎鉗壓排線,若用鐵鎚敲可能會敲壞喔,如下所示。
嗚嗚,壞掉啦,壓不緊了。
既然壞了,就拆開看看裡面的樣子吧。
參考資料:
Dr. Monk's DIY Electronics Blog的GPIO LED blink from Python using Slice of Pi。 我用排線接出GPIO針腳,而Dr. Monk使用Slice of Pi這塊擴充板將GPIO腳位接出來。
Raspberry Pi Spy的Simple Guide to the RPi GPIO Header and Pins與Control LED Using GPIO Output Pin,也是以Python程式庫RPi.GPIO以GPIO腳位讓LD閃爍。
RPi.GPIO程式庫的網站。
Hardware lesson with Gert: make your own ribbon cable connector,自己製作排線,比較省錢。
各種牛角母座與牛角公座。我在這篇將排線剝皮直接使用,一般來說會以母座與公座相連接。
Raspberry Pi的GPIO腳位配置。
RPi Low-level peripherals,rpi維基百科裡關於低階周邊的資料。
Tutorial: How to use your Raspberry Pi like an Arduino,以python、bash、c寫程式控制GPIO腳位。
Benchmarking Raspberry Pi GPIO Speed,以shell script、python、c、perl寫程式測試rpi的rpi的速度。
Jeremy's Blog的Raspberry Pi 7 segment displays,驅動七段顯示器。
Raise your cup, say cheers to the moon, look down on the ground, the shadow is also drinking with me. I'm not a lonely drinker.
2012/07/31
在Raspberry Pi上開發Arduino
要把Raspberry Pi當做開發主機,在上面撰寫Arduino的程式,實在非常簡單,因為Raspberry Pi就是一台Linux機器,而Arduino軟體開發環境原本就支援Linux了。
我在Raspberry Pi在命令列模式下,讓Arduino的LED燈閃爍,步驟記錄如下。
我的環境是Raspbian wheezy,2012-07-15-wheezy-raspbian.img,後來也試過2014-06-20-wheezy-raspbian.img。板子是Arduino Uno Rev 3。
Arduino的軟體開發環境都已經打包好了,直接以apt-get安裝即可。
$ sudo apt-get install arduino arduino-mk
其中arduino-mk是要在命令列模式下以make進行編譯與燒錄動作所需要的套件。
安裝後,執行檔(arduino、avr-g++、avr-gcc、avrdude、等等)位於/usr/bin裡,avrdude的設定檔位於/etc/avrdude.conf,範例程式碼與API參考文件分別位於/usr/share/doc/arduino-core的子目錄examples與reference裡,Arduino核心程式碼位於/usr/share/arduino/hardware/arduino/cores/arduino裡,內建程式庫位於/usr/share/arduino/libraries裡,重要的就這些,請自行瀏覽其他相關目錄。
然後,在家目錄下新增子目錄sketchbook,在裡面新增BlinkByPi專案目錄,我們將需要兩支檔案,BlinkByPi.cpp與Makefile,內容如下。
BlinkByPi.cpp的內容:
#include <Arduino.h>
void setup(){
pinMode(13, OUTPUT);
}
void loop(){
digitalWrite(13, HIGH);
delay(500);
digitalWrite(13, LOW);
delay(500);
}
Makefile的內容:
TARGET = BlinkByPi
ARDUINO_DIR = /usr/share/arduino
BOARD_TAG = uno
ARDUINO_PORT =/dev/ttyACM0
include /usr/share/arduino/Arduino.mk
以ARDUINO_DIR指定Arduino軟體開發環境的路徑。若你從Arduino官方網站自行下載、自行解壓縮的話,請修改此路徑。
以TARGET指定最後產生出來的檔案的主檔名,最好跟此專案名相同。(註:有時若出問題,拿掉此項或可解決,那麼TARGET就會預設為當前目錄名。)
以BOARD_TAG指定你使用的板子。
以ARDUINO_PORT指定與板子連接的通訊埠,在Raspberry Pi上為/dev/ttyACM0。
然後使用include匯入內涵基本設定與規則的Arduino.mk。
如果使用內建函式庫的話,須再加入類似於底下的這一行:
ARDUINO_LIBS = Ethernet Ethernet/utility SPI
接下來,在此專案目錄裡以
$ make
即可編譯、連結,將會產生出build-cli子目錄,存放建置過程的中間檔,最後產生出來的.elf與.hex也會放在裡面。
然後以
$ make upload
即可燒錄。
哇,成功囉。
另外可用make clean清除,以make depends更新檔案相依性。
更詳細的用法可參考/usr/share/arduino/Arduino.mk裡的說明,以及底下的參考資料。
參考資料:
我在Raspberry Pi在命令列模式下,讓Arduino的LED燈閃爍,步驟記錄如下。
我的環境是Raspbian wheezy,2012-07-15-wheezy-raspbian.img,後來也試過2014-06-20-wheezy-raspbian.img。板子是Arduino Uno Rev 3。
Arduino的軟體開發環境都已經打包好了,直接以apt-get安裝即可。
$ sudo apt-get install arduino arduino-mk
其中arduino-mk是要在命令列模式下以make進行編譯與燒錄動作所需要的套件。
安裝後,執行檔(arduino、avr-g++、avr-gcc、avrdude、等等)位於/usr/bin裡,avrdude的設定檔位於/etc/avrdude.conf,範例程式碼與API參考文件分別位於/usr/share/doc/arduino-core的子目錄examples與reference裡,Arduino核心程式碼位於/usr/share/arduino/hardware/arduino/cores/arduino裡,內建程式庫位於/usr/share/arduino/libraries裡,重要的就這些,請自行瀏覽其他相關目錄。
然後,在家目錄下新增子目錄sketchbook,在裡面新增BlinkByPi專案目錄,我們將需要兩支檔案,BlinkByPi.cpp與Makefile,內容如下。
BlinkByPi.cpp的內容:
#include <Arduino.h>
void setup(){
pinMode(13, OUTPUT);
}
void loop(){
digitalWrite(13, HIGH);
delay(500);
digitalWrite(13, LOW);
delay(500);
}
Makefile的內容:
TARGET = BlinkByPi
ARDUINO_DIR = /usr/share/arduino
BOARD_TAG = uno
ARDUINO_PORT =/dev/ttyACM0
include /usr/share/arduino/Arduino.mk
以ARDUINO_DIR指定Arduino軟體開發環境的路徑。若你從Arduino官方網站自行下載、自行解壓縮的話,請修改此路徑。
以TARGET指定最後產生出來的檔案的主檔名,最好跟此專案名相同。(註:有時若出問題,拿掉此項或可解決,那麼TARGET就會預設為當前目錄名。)
以BOARD_TAG指定你使用的板子。
以ARDUINO_PORT指定與板子連接的通訊埠,在Raspberry Pi上為/dev/ttyACM0。
然後使用include匯入內涵基本設定與規則的Arduino.mk。
如果使用內建函式庫的話,須再加入類似於底下的這一行:
ARDUINO_LIBS = Ethernet Ethernet/utility SPI
接下來,在此專案目錄裡以
$ make
即可編譯、連結,將會產生出build-cli子目錄,存放建置過程的中間檔,最後產生出來的.elf與.hex也會放在裡面。
然後以
$ make upload
即可燒錄。
哇,成功囉。
另外可用make clean清除,以make depends更新檔案相依性。
更詳細的用法可參考/usr/share/arduino/Arduino.mk裡的說明,以及底下的參考資料。
參考資料:
- Arduino Playground的Install on Debian。
- Arduino Playground的Installing Arduino on Linux。
- RaspberryPi @Homelabs的RaspberryPi the Arduino Development Tool。
- netduinoplusfun的Arduino IDE on Raspberry Pi with Arduino Uno。
- Dr. Monk's DIY Electronics Blog的Raspberry Pi and Arduino。
- Martin's Atelier: Arduino from the command line。
- Arduino 1.0 development with a makefile on Linux。
2012/07/30
一些很棒的Raspberry Pi專案
Raspberry Pi自從2012.02.29 06:00 GMT(台灣時間下午兩點)開始販賣,到現在已經五個月了,量產也追上了需求量,不再限定一筆訂單只能買一塊板子了;受到世界各地熱烈的討論,不少人運用Raspberry Pi打造出有趣的專案。
Code Club - Mini Band Project
吉他、鼓、沙球,讓我們來組個迷你樂團吧!
哇賽,不僅有Raspberry Pi,還用了Arduino耶。
PIE1 – Raspberry Pi Sends Live Images from Near Space
國外興起一股叫做High Altitude Ballooning的風潮,利用天氣觀測氣球將一些東西(相機、GPS、各種感測器、儀器)送上高度大約30公里的近空進行各種偵測與實驗。很自然地,當然會有人利用Raspberry Pi完成此壯舉囉。上升到近空傳回即時拍攝的照片,真不錯啊。
好,要升空了喔。
哇,居然可以在這麼高的地方拍照啊。
飛的範圍還真廣。
Camera Pi
將Raspberry Pi塞入Canon 5D Mark II,藉由傳輸線連接後,可直接讀取拍攝的照片,並透過無線方式傳送到另外一台電腦或平板,也能使用自動備份功能,這僅是剛開始而已,將來還會繼續擴增其他功能,。
Raspberry driven TB-2? Or better RPI-TB-2
當然啦,少不了將Raspberry Pi與機器人結合在一起。
FishPi | An autonomos drop in the Ocean
FishPi這項專案要打造一條自動在海上航行的船隻,能夠自動導航不需人類插手,預備橫渡大西洋,並且進行各種科學量測與實驗。
目前尚在建構中。
SNESDev-RPi: A SNES-Adapter for the Raspberry Pi
這位仁兄把Raspberry Pi改造成通用型電視遊樂器,製作轉接板將超級任天堂的手把與Raspberry Pi連接後,啟動模擬器,開始回味8位元、16位元的骨灰級遊戲吧。
轉接部分的硬體,將超任手把與Raspberry Pi連接。(當然,還有軟體的部份。)
連接後的樣子。
開始玩囉。
Project Glass: Real Time Translation … inspired
這是個"眼鏡"的專案,它可以即時翻譯,讓一個只會講英文、一個只會講西班牙文的兩人交談。
講話時,語音會被傳送到網路伺服器那進行翻譯,然後將翻譯後的文字顯示在眼鏡上。
哇,看起來好困難啊。
這裡有YouTube詳細影片可觀賞。
Portable Raspberry Pi
Raspberry Pi加上螢幕、鍵盤、行動電源,哈,變成筆電了嗎?
The Magic Wand
想要魔杖嗎?自己做一根吧。拿著魔杖快速的來回揮動,就能顯示文字喔。
看到桌上那根木棒了嗎,那就是魔杖喔。
來回快速揮動,哇,漂浮在空中的文字耶。
參考資料:
Code Club - Mini Band Project
吉他、鼓、沙球,讓我們來組個迷你樂團吧!
哇賽,不僅有Raspberry Pi,還用了Arduino耶。
PIE1 – Raspberry Pi Sends Live Images from Near Space
國外興起一股叫做High Altitude Ballooning的風潮,利用天氣觀測氣球將一些東西(相機、GPS、各種感測器、儀器)送上高度大約30公里的近空進行各種偵測與實驗。很自然地,當然會有人利用Raspberry Pi完成此壯舉囉。上升到近空傳回即時拍攝的照片,真不錯啊。
好,要升空了喔。
哇,居然可以在這麼高的地方拍照啊。
飛的範圍還真廣。
Camera Pi
將Raspberry Pi塞入Canon 5D Mark II,藉由傳輸線連接後,可直接讀取拍攝的照片,並透過無線方式傳送到另外一台電腦或平板,也能使用自動備份功能,這僅是剛開始而已,將來還會繼續擴增其他功能,。
Raspberry driven TB-2? Or better RPI-TB-2
當然啦,少不了將Raspberry Pi與機器人結合在一起。
FishPi | An autonomos drop in the Ocean
FishPi這項專案要打造一條自動在海上航行的船隻,能夠自動導航不需人類插手,預備橫渡大西洋,並且進行各種科學量測與實驗。
目前尚在建構中。
SNESDev-RPi: A SNES-Adapter for the Raspberry Pi
這位仁兄把Raspberry Pi改造成通用型電視遊樂器,製作轉接板將超級任天堂的手把與Raspberry Pi連接後,啟動模擬器,開始回味8位元、16位元的骨灰級遊戲吧。
轉接部分的硬體,將超任手把與Raspberry Pi連接。(當然,還有軟體的部份。)
連接後的樣子。
開始玩囉。
Project Glass: Real Time Translation … inspired
這是個"眼鏡"的專案,它可以即時翻譯,讓一個只會講英文、一個只會講西班牙文的兩人交談。
講話時,語音會被傳送到網路伺服器那進行翻譯,然後將翻譯後的文字顯示在眼鏡上。
哇,看起來好困難啊。
這裡有YouTube詳細影片可觀賞。
Portable Raspberry Pi
Raspberry Pi加上螢幕、鍵盤、行動電源,哈,變成筆電了嗎?
The Magic Wand
想要魔杖嗎?自己做一根吧。拿著魔杖快速的來回揮動,就能顯示文字喔。
看到桌上那根木棒了嗎,那就是魔杖喔。
來回快速揮動,哇,漂浮在空中的文字耶。
參考資料:
Raspberry Pi可以跑Clozure CL囉
2012年7月21日發佈的消息,Clozure CL從版本r14525開始支援ARMv6的Linux了,也就是說,可以在Raspberry Pi(以下簡稱rpi)板子上跑囉。
底下是我安裝Clozure CL的過程,我用的發行套件是Raspbian wheezy(2012-07-15-wheezy-raspbian.img)。
啟動rpi,連上網路。
安裝subversion(若尚未安裝的話)。
$ sudo apt-get install subversion
以subversion抓取Clozure CL,以底下指令抓取linux + arm的最新版本。
$ svn co http://svn.clozure.com/publicsvn/openmcl/trunk/linuxarm/ccl
其中trunk代表要抓最新的,linuxarm代表要抓ARM的Linux。Clozure CL支援很多種CPU架構與作業系統,其他還有darwinx86、linuxx86、freebsdx86、solarisx86、windows、linuxppc。
我抓完後畫面上顯示著"Checked out revision 15426.",請注意這個數字應該要大於14525。
抓下來的Clozure CL被存放在ccl子目錄裡。請切換到ccl子目錄。然後就能以裡面的映像檔啟動Clozure CL環境了。
$ ./armcl
哇,可以計算1+2耶,有了lisp環境,你想做什麼就做什麼吧。
上圖歡迎訊息裡可以看到r15424的字眼,這跟我們抓到的15426不一樣,所以接下來我要嘗試重新編譯Clozure CL。
執行原有的ccl映像檔:
$ ./armcl --no-init
看到Clozure CL的歡迎訊息後,下達重新編譯建置的指令:
? (rebuild-ccl :full t)
但我遭遇一些障礙,記錄如下:
我編譯時發現少了m4這支工具,所以請以$ sudo apt-get install m4安裝。
ccl開發人員似乎是在Debian squeeze上測試的,而我用的是wheezy(2012-07-15-wheezy-raspbian.img),因為如此(我也不確定),所以編譯時會出現類似
/usr/bin/ld: error: ../../armcl uses VFP register arguments, pmcl-kernel.o does not
/usr/bin/ld: failed to merge target specific data of file pmcl-kernel.o
的錯誤訊息,解法方法是修改ccl/lisp-kernel/linuxarm/float_abi.mk這支檔案,將FLOAT_ABI = softfp改成FLOAT_ABI = hard,然後就能成功編譯了。
下圖是成功編譯一開始的畫面。
下圖是成功編譯的結束畫面。
重新編譯成功後,以$ ./armcl重新啟動,耶,出現15426字樣囉,最新版本。
編譯所需時間還滿久的(我忘記記錄了,大概要一小時吧)。
如果你編譯時發生其他錯誤,因為重新編譯會砍掉原有Clozure CL映像檔,可下指令$ svn update重新抓回來。
參考文件可到Clozure CL官方網站找找重新編譯的步驟與解說。
然後找本lisp好書學習這支程式語言*_*。
底下是我安裝Clozure CL的過程,我用的發行套件是Raspbian wheezy(2012-07-15-wheezy-raspbian.img)。
啟動rpi,連上網路。
安裝subversion(若尚未安裝的話)。
$ sudo apt-get install subversion
以subversion抓取Clozure CL,以底下指令抓取linux + arm的最新版本。
$ svn co http://svn.clozure.com/publicsvn/openmcl/trunk/linuxarm/ccl
其中trunk代表要抓最新的,linuxarm代表要抓ARM的Linux。Clozure CL支援很多種CPU架構與作業系統,其他還有darwinx86、linuxx86、freebsdx86、solarisx86、windows、linuxppc。
我抓完後畫面上顯示著"Checked out revision 15426.",請注意這個數字應該要大於14525。
抓下來的Clozure CL被存放在ccl子目錄裡。請切換到ccl子目錄。然後就能以裡面的映像檔啟動Clozure CL環境了。
$ ./armcl
哇,可以計算1+2耶,有了lisp環境,你想做什麼就做什麼吧。
上圖歡迎訊息裡可以看到r15424的字眼,這跟我們抓到的15426不一樣,所以接下來我要嘗試重新編譯Clozure CL。
執行原有的ccl映像檔:
$ ./armcl --no-init
看到Clozure CL的歡迎訊息後,下達重新編譯建置的指令:
? (rebuild-ccl :full t)
但我遭遇一些障礙,記錄如下:
我編譯時發現少了m4這支工具,所以請以$ sudo apt-get install m4安裝。
ccl開發人員似乎是在Debian squeeze上測試的,而我用的是wheezy(2012-07-15-wheezy-raspbian.img),因為如此(我也不確定),所以編譯時會出現類似
/usr/bin/ld: error: ../../armcl uses VFP register arguments, pmcl-kernel.o does not
/usr/bin/ld: failed to merge target specific data of file pmcl-kernel.o
的錯誤訊息,解法方法是修改ccl/lisp-kernel/linuxarm/float_abi.mk這支檔案,將FLOAT_ABI = softfp改成FLOAT_ABI = hard,然後就能成功編譯了。
下圖是成功編譯一開始的畫面。
下圖是成功編譯的結束畫面。
重新編譯成功後,以$ ./armcl重新啟動,耶,出現15426字樣囉,最新版本。
編譯所需時間還滿久的(我忘記記錄了,大概要一小時吧)。
如果你編譯時發生其他錯誤,因為重新編譯會砍掉原有Clozure CL映像檔,可下指令$ svn update重新抓回來。
參考文件可到Clozure CL官方網站找找重新編譯的步驟與解說。
然後找本lisp好書學習這支程式語言*_*。
2012/07/26
[廣告] 來自程式的試鍊:專為程式開發人員所寫的技術面試完全攻略 (Cracking the Coding Interview, 5/e : 150 Programming Questions and Solutions)
嗨,我翻譯了一本書,在這裡打打廣告。
書名:來自程式的試鍊:專為程式開發人員所寫的技術面試完全攻略
原書名:Cracking the Coding Interview, 5/e : 150 Programming Questions and Solutions
作者:Gayle Laakmann McDowell
譯者:我
出版社:悅知
頁數:560
很高興能夠接下這本書的翻譯工作,原書在Amazon獲得了五顆星的評價,希望我翻出來的譯文能讓大家滿意。
顧名思義,這本書的主題就是"面試",而且是關於軟體設計、寫程式、、演算法資料結構、電腦網路、資料庫這方面工作的技術面試,前面約75頁介紹了面試前與面試後、面試流程與幕後、等等注意事項(不過這部份不是我翻譯的),接下來的篇幅就都是考題與解題技巧了,詳細列出常出會考的、重要的、該注意的考題,並且有詳細的解答、題目分析、以及該如何在面試中回答出讓面試官滿意的回答。
好書一本,希望我翻譯的成果也能讓你說好。
底下是這本書的目錄:
PART 1 面試流程
PART 2 幕後真相
PART 3 特殊情況
PART 4 面試之前
PART 5 行為式問題
PART 6 技術問題
PART 7 收到工作邀請之後
PART 8 面試考題
資料結構:面試考題與建議
01 陣列與字串
02 鏈結串列
03 堆疊與佇列
04 樹與圖形
概念與演算法:面試考題與建議
05 位元操作
06 腦力激盪考題
07 數學與機率
08 物件導向設計
09 遞迴與動態規劃法
10 規模擴展性與記憶體限制
11 排序與搜尋
12 測試 知識型:面試考題與建議
13 C與C++
14 Java
15 資料庫
16 執行緒與鎖
其他複習題:面試考題與建議
17 一般程度考題
18 進階程度考題
PART 9 解題技巧
資料結構:解題技巧
01 陣列與字串
02 鏈結串列
03 堆疊與佇列
04 樹與圖形
概念與演算法:解題技巧
05 位元操作
06 腦力激盪考題
07 數學與機率
08 物件導向設計
09 遞迴與動態規劃法
10 規模擴展性與記憶體限制
11 排序與搜尋
12 測試
知識型:解題技巧
13 C與C++
14 Java
15 資料庫
16 執行緒與鎖
其他複習題:解題技巧
17 一般程度考題
18 進階程度考題
勘誤表:
(感謝「路人22/9/12 11:38」的指正)
頁數:87、213
考題2.6的「連結串列」,應該是「鏈結串列」才對。
頁數:92
traversal跟traverse,我翻譯成「追蹤」,有讀者指出翻為「遍歷」或「走訪」較佳,我不否認,但追蹤一詞已經用了滿久了,有其歷史包袱。
頁數:132
合併排序法的英文應為「Merge Sort」,而非「Selection Sort」。
頁數:258、520
suffix tree,我翻成「後置樹」,應該翻成「後綴樹」才對。
頁數:266
原文:2. 搬移(shift)M,讓它對齊從 j到 i的位元。
shift在此翻譯成「移位」或「位移」 應該較佳。
書名:來自程式的試鍊:專為程式開發人員所寫的技術面試完全攻略
原書名:Cracking the Coding Interview, 5/e : 150 Programming Questions and Solutions
作者:Gayle Laakmann McDowell
譯者:我
出版社:悅知
頁數:560
很高興能夠接下這本書的翻譯工作,原書在Amazon獲得了五顆星的評價,希望我翻出來的譯文能讓大家滿意。
顧名思義,這本書的主題就是"面試",而且是關於軟體設計、寫程式、、演算法資料結構、電腦網路、資料庫這方面工作的技術面試,前面約75頁介紹了面試前與面試後、面試流程與幕後、等等注意事項(不過這部份不是我翻譯的),接下來的篇幅就都是考題與解題技巧了,詳細列出常出會考的、重要的、該注意的考題,並且有詳細的解答、題目分析、以及該如何在面試中回答出讓面試官滿意的回答。
好書一本,希望我翻譯的成果也能讓你說好。
底下是這本書的目錄:
PART 1 面試流程
PART 2 幕後真相
PART 3 特殊情況
PART 4 面試之前
PART 5 行為式問題
PART 6 技術問題
PART 7 收到工作邀請之後
PART 8 面試考題
資料結構:面試考題與建議
01 陣列與字串
02 鏈結串列
03 堆疊與佇列
04 樹與圖形
概念與演算法:面試考題與建議
05 位元操作
06 腦力激盪考題
07 數學與機率
08 物件導向設計
09 遞迴與動態規劃法
10 規模擴展性與記憶體限制
11 排序與搜尋
12 測試 知識型:面試考題與建議
13 C與C++
14 Java
15 資料庫
16 執行緒與鎖
其他複習題:面試考題與建議
17 一般程度考題
18 進階程度考題
PART 9 解題技巧
資料結構:解題技巧
01 陣列與字串
02 鏈結串列
03 堆疊與佇列
04 樹與圖形
概念與演算法:解題技巧
05 位元操作
06 腦力激盪考題
07 數學與機率
08 物件導向設計
09 遞迴與動態規劃法
10 規模擴展性與記憶體限制
11 排序與搜尋
12 測試
知識型:解題技巧
13 C與C++
14 Java
15 資料庫
16 執行緒與鎖
其他複習題:解題技巧
17 一般程度考題
18 進階程度考題
勘誤表:
(感謝「路人22/9/12 11:38」的指正)
頁數:87、213
考題2.6的「連結串列」,應該是「鏈結串列」才對。
頁數:92
traversal跟traverse,我翻譯成「追蹤」,有讀者指出翻為「遍歷」或「走訪」較佳,我不否認,但追蹤一詞已經用了滿久了,有其歷史包袱。
頁數:132
合併排序法的英文應為「Merge Sort」,而非「Selection Sort」。
頁數:258、520
suffix tree,我翻成「後置樹」,應該翻成「後綴樹」才對。
頁數:266
原文:2. 搬移(shift)M,讓它對齊從 j到 i的位元。
shift在此翻譯成「移位」或「位移」 應該較佳。
2012/07/22
Raspbian:Raspberry Pi新的Debian發行套件
Raspberry Pi基金會於7月18日釋出了新的發行套件:Raspbian,顧名思義就是Raspberry Pi加上Debian,與之前的Debian squeeze(debian6-19-04-2012.img)相比,這個版本以Debain wheezy為基礎,善加運用了rpi的浮點運算硬體(也就是hard float),不論是韌體、作業系統核心、應用軟體,都做了不少最佳化,執行效能大大提昇,X Window更快了、媒體播放更快了、上網瀏覽網站更快了、等等。
大家趕快到Raspberry Pi官方網站下載Raspbian "wheezy"吧。
有個叫做raspi-config的新東西,第一次開機後會自動執行這支設定組態的工具:
expand_rootfs:調整根檔案系統所在分割區的大小,
overscan:修正電視不正常的顯示畫面,
configure_keyboard:修改鍵盤配置,
change_pass:修改預設帳號pi的密碼(原為raspberry),
change_locale:修改地區設定,
change_timezone:修改時區設定,
memory_split:設定分配給CPU與顯示卡的記憶體容量,
ssh:開機時即啟動或關閉ssh,
boot_behaviour:要不要開機後就啟動X Window,
update:更新raspi-config這支工具,
Finish:結束。
設定細節可看看我之前寫的Raspberry Pi基本設定、編譯核心、上網,或是參考任何一本的Linux的書籍。
其中,若你選了expand_rootfs擴大根檔案系統分割區的大小,我建議你馬上重新開機,比較不會發生奇奇怪怪的問題,下圖是重開機時,進行大小修改時的畫面,要花上一段時間。
下圖是CPU與顯示卡晶片(VideoCore)記憶體分配的設定。若你想執行的是X Window、播放影片音樂、等等多媒體應用,那麼就給VideoCore多一點記憶體。
趕快到X Window四處玩玩吧,享受一下速度提昇後的快感。
看看這張效能比較表,大概可知道效能提昇了多少,詳情請見Raspbian Benchmarking – armel vs armhf。
PS 量產已經追上需求量,現在已經可以一次購買多塊Raspberry Pi板子囉。
大家趕快到Raspberry Pi官方網站下載Raspbian "wheezy"吧。
有個叫做raspi-config的新東西,第一次開機後會自動執行這支設定組態的工具:
expand_rootfs:調整根檔案系統所在分割區的大小,
overscan:修正電視不正常的顯示畫面,
configure_keyboard:修改鍵盤配置,
change_pass:修改預設帳號pi的密碼(原為raspberry),
change_locale:修改地區設定,
change_timezone:修改時區設定,
memory_split:設定分配給CPU與顯示卡的記憶體容量,
ssh:開機時即啟動或關閉ssh,
boot_behaviour:要不要開機後就啟動X Window,
update:更新raspi-config這支工具,
設定細節可看看我之前寫的Raspberry Pi基本設定、編譯核心、上網,或是參考任何一本的Linux的書籍。
其中,若你選了expand_rootfs擴大根檔案系統分割區的大小,我建議你馬上重新開機,比較不會發生奇奇怪怪的問題,下圖是重開機時,進行大小修改時的畫面,要花上一段時間。
下圖是CPU與顯示卡晶片(VideoCore)記憶體分配的設定。若你想執行的是X Window、播放影片音樂、等等多媒體應用,那麼就給VideoCore多一點記憶體。
趕快到X Window四處玩玩吧,享受一下速度提昇後的快感。
看看這張效能比較表,大概可知道效能提昇了多少,詳情請見Raspbian Benchmarking – armel vs armhf。
PS 量產已經追上需求量,現在已經可以一次購買多塊Raspberry Pi板子囉。
2012/07/21
RasPiThon:為Raspberry Pi籌募資金的48小時程式馬拉松
由4個年齡12~16歲的學生,Ryan、Ben、Edward、Luke,從7月20日下午6點(GMT+1 英國夏季時間)開始,在48小時的時限內,以Python程式語言撰寫遊戲。
這場程式馬拉松是個獨立的活動,跟Raspberry Pi基金會或任何公司組織皆無關。但主要目的是為了Raspberry Pi基金會籌募資金,那麼,這4位成員能得到什麼好處呢?基本上並不會獲得實質利益,得到的是名聲。
4個成員中,3個在英國,1個在澳洲,將以網路為溝通媒介,並非全部在同一間房間裡進行開發。
此活動的官方網址為http://www.RasPiThon.org.uk,可看到撰寫程式開發遊戲的即時過程(當然啦,是指在那48小時內),4個成員的基本資料,捐款途徑,新聞稿,常見問題等等資訊。
此活動已經結束了,可以到官方網站線上觀看寫程式的過程喔,最終寫出一個叫做Rasperroids的遊戲,可到GitHub下載原始碼,並為Raspberry Pi基金會募集超過£500的資金。
這場程式馬拉松是個獨立的活動,跟Raspberry Pi基金會或任何公司組織皆無關。但主要目的是為了Raspberry Pi基金會籌募資金,那麼,這4位成員能得到什麼好處呢?基本上並不會獲得實質利益,得到的是名聲。
4個成員中,3個在英國,1個在澳洲,將以網路為溝通媒介,並非全部在同一間房間裡進行開發。
此活動的官方網址為http://www.RasPiThon.org.uk,可看到撰寫程式開發遊戲的即時過程(當然啦,是指在那48小時內),4個成員的基本資料,捐款途徑,新聞稿,常見問題等等資訊。
此活動已經結束了,可以到官方網站線上觀看寫程式的過程喔,最終寫出一個叫做Rasperroids的遊戲,可到GitHub下載原始碼,並為Raspberry Pi基金會募集超過£500的資金。
2012/07/08
Objective-C在Xcode 4.4版裡的新增功能
2012年Apple年度大會WWDC(Apple Worldwide Developers Conference)的影片可以下載囉。
底下記錄一些未來的Objective-C將會擁有的新功能與新特色,在Xcode版本4.4以後的編譯器才有這些新功能,編譯出來的程式可以相容於先前版本的系統。
參考影片:
Session 405 - Modern Objective-C
Session 413 - Migrating to Modern Objective-C
首先,跟類別裡方法的宣告順序有關。譬如說,在類別裡有個私有的方法,該怎麼辦?
// SongPlayer.h
@interface SongPlayer : NSObject
{
}
- (void)playSong:(Song *)song;
@end
// SongPlayer.m
@implementation SongPlayer
- (void)playSong:(Song *)song
{
NSError *error;
[self startAudio:&error];
//...
}
- (void)startAudio:(NSError **)error
{
//...
}
@end
其中playSong是公開的介面,而startAudio是內部私用的方法。上面這段程式碼會有編譯錯誤,因為playSong在startAudio宣告之前就呼叫了。
如果能將startAudio搬到前面去就可解決,但有時候做不到或不想這麼做,一般的解法是運用class extension,修改如下:
// SongPlayer.h
@interface SongPlayer : NSObject
{
}
- (void)playSong:(Song *)song;
@end
// SongPlayer.m
@implementation SongPlayer
- (void)playSong:(Song *)song
{
NSError *error;
[self startAudio:&error];
//...
}
- (void)startAudio:(NSError **)error
{
//...
}
@end
我們可以把私用方法宣告在class extension(@interface SongPlayer () ... @end)裡,就可解決此問題。
但新的Objective-C更強,它直接幫我們處理好了,編譯器會先解析各方法的宣告(方法名、回傳型別、參數型別),然後再解析方法的內容,這麼一來,一開始的程式碼就不會有錯誤了。
新的Objective-C的enum有了不錯的進步,新型的enum可如下定義:
enum FruitEnum : NSUInteger
{
FruitEnumApple,
FruitEnumBanana,
FruitEnumCherry,
FruitEnumBlueberry,
//...
} FruitEnum;
其名為fixed underlying type enum。
有了這種enum後,Xcode在補足程式碼(code completion)時就更聰明了,而且,編譯器也能作檢查型別,譬如說把某enum值指定給另一個enum型別的變數,就會出現錯誤訊息(編譯器參數為-Wcovnersion),還有,以switch根據某enum型別作判斷的話,若少寫某enum值時編譯器也會提醒你(編譯器參數為-Wswitch)。
對於property也有很多新東西。
原本會這麼寫:
//Person.h
@interface Person : NSObject
{
NSString *_name;
}
//Person.m
@implementation Person
@end
可以把instance variable的宣告改放在@implementation裡:
//Person.h
@interface Person : NSObject
{
NSString *_name;
}
//Person.m
@implementation Person
{
NSString *_name;
}
@end
而且,既然用了@synthesize,根本就不需要自己宣告instance variable了:
//Person.h
@interface Person : NSObject
{
NSString *_name;
}
//Person.m
@implementation Person
{
NSString *_name;
}
@end
以上是本來就有的,現在,在Xcode 4.4(與之後的版本),連@synthesize都可以省略了:
//Person.h
@interface Person : NSObject
{
NSString *_name;
}
//Person.m
@implementation Person
{
NSString *_name;
}
@synthesize name = _name;
@end
也就是說,synthesize是"預設"的行為了,原本property要寫好幾行程式,現在只需一行即可,編譯器會自動加入:
@synthesize name = _name;
預設會在property名字前面加上底線「_」作為instance variable的名字。
注意,為了相容於舊版,若你寫了
@synthesize name;
則等同於
@synthesize name = name;
object literal(這是我覺得早就應該加入的功能)。
首先是NSNumber,原本要這麼寫:
NSNumber *n1 = [NSNumber numberWithInt:1234];
NSNumber *n2 = [NSNumber numberWithFloat:1234.56f];
NSNumber *n3 = [NSNumber numberWithBool:YES];
等等...
新版的只需寫:
NSNumber *n1 = @1234;
NSNumber *n2 = @1234.56f;
NSNumber *n3 = @(YES); // iOS 5寫@YES不行
等等...
不僅如此,以下的運算式都會變成NSNumber:
@( M_PI / 6 )
@( "0123456789ABCDEF"[x % 16] )
@( NSWriteDirectionLeftToRight )
@( getenv("PATH") ),這個會變成NSString
同樣的,NSArray,原本要寫很多程式碼,要擔心有沒有在末端加上nil,現在可改成:
NSArray *array1 = @[]; // 空的陣列
NSArray *array2 = @[a]; // 只含有a物件的陣列
NSArray *array3 = @[@"a", @"b", @"c"]; // 含有三個字串的陣列
既然NSArray出現了,沒道理NSDictionary會缺席啊,同理,NSDictionary也有了類似的新語法:
NSDictionary *dict1 = @{};
NSDictionary *dict2 = @{k1:o1};
NSDictionary *dict3 = @{k1:o1, k2:o2, k3:o3};
id value = aDictionary[@"key"]; // 讀取
aMutableDictionary[@"key"] = newValue; // 寫入
subscripting
NSArray的物件也可以用[]來存取其內的東西了,
NSArray *songs = @[@"song1", @"song2", @"song3"];
NSString *s1 = songs[0]; //讀取
songs[0] = @"newSong"; //寫入
不只NSArray可以利用[]語法,你自己寫的類別也可以喔,只需實作底下的方法即可:
-(元素型別)objectAtIndexedSubscript:(索引型別)idx;
-(void)setObject:(元素型別)object atIndexedSubscript:(索引型別)idx;
嗯,還不錯,程式碼可以大幅簡化囉。
底下記錄一些未來的Objective-C將會擁有的新功能與新特色,在Xcode版本4.4以後的編譯器才有這些新功能,編譯出來的程式可以相容於先前版本的系統。
參考影片:
Session 405 - Modern Objective-C
Session 413 - Migrating to Modern Objective-C
首先,跟類別裡方法的宣告順序有關。譬如說,在類別裡有個私有的方法,該怎麼辦?
// SongPlayer.h
@interface SongPlayer : NSObject
{
}
- (void)playSong:(Song *)song;
@end
// SongPlayer.m
@implementation SongPlayer
- (void)playSong:(Song *)song
{
NSError *error;
[self startAudio:&error];
//...
}
- (void)startAudio:(NSError **)error
{
//...
}
@end
其中playSong是公開的介面,而startAudio是內部私用的方法。上面這段程式碼會有編譯錯誤,因為playSong在startAudio宣告之前就呼叫了。
如果能將startAudio搬到前面去就可解決,但有時候做不到或不想這麼做,一般的解法是運用class extension,修改如下:
// SongPlayer.h
@interface SongPlayer : NSObject
{
}
- (void)playSong:(Song *)song;
@end
// SongPlayer.m
@interface SongPlayer ()
- (void)startAudio:(NSError **)error;
@end @implementation SongPlayer
- (void)playSong:(Song *)song
{
NSError *error;
[self startAudio:&error];
//...
}
- (void)startAudio:(NSError **)error
{
//...
}
@end
我們可以把私用方法宣告在class extension(@interface SongPlayer () ... @end)裡,就可解決此問題。
但新的Objective-C更強,它直接幫我們處理好了,編譯器會先解析各方法的宣告(方法名、回傳型別、參數型別),然後再解析方法的內容,這麼一來,一開始的程式碼就不會有錯誤了。
新的Objective-C的enum有了不錯的進步,新型的enum可如下定義:
enum FruitEnum : NSUInteger
{
FruitEnumApple,
FruitEnumBanana,
FruitEnumCherry,
FruitEnumBlueberry,
//...
} FruitEnum;
其名為fixed underlying type enum。
有了這種enum後,Xcode在補足程式碼(code completion)時就更聰明了,而且,編譯器也能作檢查型別,譬如說把某enum值指定給另一個enum型別的變數,就會出現錯誤訊息(編譯器參數為-Wcovnersion),還有,以switch根據某enum型別作判斷的話,若少寫某enum值時編譯器也會提醒你(編譯器參數為-Wswitch)。
對於property也有很多新東西。
原本會這麼寫:
//Person.h
@interface Person : NSObject
{
NSString *_name;
}
@property (strong) NSString *name;
@end//Person.m
@implementation Person
@synthesize name = _name;
@end
可以把instance variable的宣告改放在@implementation裡:
//Person.h
@interface Person : NSObject
{
}
@property (strong) NSString *name;
@end//Person.m
@implementation Person
{
NSString *_name;
}
@synthesize name = _name;
@end
而且,既然用了@synthesize,根本就不需要自己宣告instance variable了:
//Person.h
@interface Person : NSObject
{
}
@property (strong) NSString *name;
@end//Person.m
@implementation Person
{
}
@synthesize name = _name;
@end
以上是本來就有的,現在,在Xcode 4.4(與之後的版本),連@synthesize都可以省略了:
//Person.h
@interface Person : NSObject
{
}
@property (strong) NSString *name;
@end//Person.m
@implementation Person
{
}
@end
也就是說,synthesize是"預設"的行為了,原本property要寫好幾行程式,現在只需一行即可,編譯器會自動加入:
@synthesize name = _name;
預設會在property名字前面加上底線「_」作為instance variable的名字。
注意,為了相容於舊版,若你寫了
@synthesize name;
則等同於
@synthesize name = name;
object literal(這是我覺得早就應該加入的功能)。
首先是NSNumber,原本要這麼寫:
NSNumber *n1 = [NSNumber numberWithInt:1234];
NSNumber *n2 = [NSNumber numberWithFloat:1234.56f];
NSNumber *n3 = [NSNumber numberWithBool:YES];
等等...
新版的只需寫:
NSNumber *n1 = @1234;
NSNumber *n2 = @1234.56f;
NSNumber *n3 = @(YES); // iOS 5寫@YES不行
等等...
不僅如此,以下的運算式都會變成NSNumber:
@( M_PI / 6 )
@( "0123456789ABCDEF"[x % 16] )
@( NSWriteDirectionLeftToRight )
@( getenv("PATH") ),這個會變成NSString
同樣的,NSArray,原本要寫很多程式碼,要擔心有沒有在末端加上nil,現在可改成:
NSArray *array1 = @[]; // 空的陣列
NSArray *array2 = @[a]; // 只含有a物件的陣列
NSArray *array3 = @[@"a", @"b", @"c"]; // 含有三個字串的陣列
既然NSArray出現了,沒道理NSDictionary會缺席啊,同理,NSDictionary也有了類似的新語法:
NSDictionary *dict1 = @{};
NSDictionary *dict2 = @{k1:o1};
NSDictionary *dict3 = @{k1:o1, k2:o2, k3:o3};
id value = aDictionary[@"key"]; // 讀取
aMutableDictionary[@"key"] = newValue; // 寫入
subscripting
NSArray的物件也可以用[]來存取其內的東西了,
NSArray *songs = @[@"song1", @"song2", @"song3"];
NSString *s1 = songs[0]; //讀取
songs[0] = @"newSong"; //寫入
不只NSArray可以利用[]語法,你自己寫的類別也可以喔,只需實作底下的方法即可:
-(元素型別)objectAtIndexedSubscript:(索引型別)idx;
-(void)setObject:(元素型別)object atIndexedSubscript:(索引型別)idx;
嗯,還不錯,程式碼可以大幅簡化囉。
在Raspberry Pi之外值得注意的產品
有人將Raspberry Pi定義為單板電腦,有人歸類為低價替代品,官方的主要初衷則希望作為教育用途,不論如何,這世界不是只有Raspberry Pi而已,還有很多其他有趣的產品值得我們關注。
PS 我只是把知道的、網路上找得到的、從新聞看來的各種玩意兒整理整理,沒列出詳細的產品規格,底下有些產品尚未問世,而且,以下產品我都沒有*_*。
BeagleBoard:
此開發平台使用TI的OMAP系統單晶片,其內部核心也是ARM,適用於開發各種嵌入式系統。價格依規格不同而不同,有$89的、也有$149的。
PandaBoard:
使用OMAP系統單晶片,可運行Android與Linux系統,有各種擴充板。價格低於$200。
Intel NUC(Next Unit of Computing) :
使用Intel的Core i系列處理器,可跑Windows,有人把它拿來跟Mac Mini相比。目前看到的價格是$400。
VIA APC:
VIA推出可運行Android 2.3的迷你主機,比香蕉還要小,從圖中你可以看到各種插座一應俱全。目前看到的價格是$49。
Mele A1000:
以ARM為硬體核心,可跑Android或Ubuntu,定位為家庭媒體娛樂系統。目前看到的價格是$70。
Android Mini PC MK802:
大陸的廠商所開發,搭配Android 4.0.3系統,非常迷你。依規格不同價格不同,$79~$99。
FXI Cotton Candy:
挪威公司製作的超級迷你系統,就跟USB隨身碟差不多,使用ARM核心,可運行Android與Ubuntu作業系統,除了可當做獨立的電腦主機使用外,也可以插入一般電腦的USB埠,會在原本電腦裡開一個視窗供這台迷你系統使用,相當有趣。看到的價格是$199。
CuBox:
也是非常迷你的系統,使用Marvell Armada 510系統單晶片。價格為$135。
Ninja Blocks:
價格為澳幣155。
Gooseberry:
一批匿名人士自製的Android電腦,售價為英鎊40。
其他:
PS 我只是把知道的、網路上找得到的、從新聞看來的各種玩意兒整理整理,沒列出詳細的產品規格,底下有些產品尚未問世,而且,以下產品我都沒有*_*。
BeagleBoard:
此開發平台使用TI的OMAP系統單晶片,其內部核心也是ARM,適用於開發各種嵌入式系統。價格依規格不同而不同,有$89的、也有$149的。
PandaBoard:
使用OMAP系統單晶片,可運行Android與Linux系統,有各種擴充板。價格低於$200。
Intel NUC(Next Unit of Computing) :
使用Intel的Core i系列處理器,可跑Windows,有人把它拿來跟Mac Mini相比。目前看到的價格是$400。
VIA APC:
VIA推出可運行Android 2.3的迷你主機,比香蕉還要小,從圖中你可以看到各種插座一應俱全。目前看到的價格是$49。
Mele A1000:
以ARM為硬體核心,可跑Android或Ubuntu,定位為家庭媒體娛樂系統。目前看到的價格是$70。
Android Mini PC MK802:
大陸的廠商所開發,搭配Android 4.0.3系統,非常迷你。依規格不同價格不同,$79~$99。
FXI Cotton Candy:
挪威公司製作的超級迷你系統,就跟USB隨身碟差不多,使用ARM核心,可運行Android與Ubuntu作業系統,除了可當做獨立的電腦主機使用外,也可以插入一般電腦的USB埠,會在原本電腦裡開一個視窗供這台迷你系統使用,相當有趣。看到的價格是$199。
CuBox:
也是非常迷你的系統,使用Marvell Armada 510系統單晶片。價格為$135。
Ninja Blocks:
價格為澳幣155。
Gooseberry:
一批匿名人士自製的Android電腦,售價為英鎊40。
其他: