算法心得：高效算法的奧秘（原書第2版） ( 簡體 字) |
| 作者：（美）Henry S. Warren, Jr. 著 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：機械工業出版社 |  3dWoo書號： 37855
詢問書籍請說出此書號！【缺書】
NT售價： 445 元 |
| 出版日：3/1/2014 |
| 頁數：417 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787111453567 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：造力第一定律：軟件維護成本與程序員創造力的平方成正比。
——Robert D杄Bliss，1992年
本書收集了筆者多年來總結的一些編程小技巧，其中大部分都必須運行在以二進制補碼來表示整數的電腦上。盡管本書假設寄存器長度是32位，但在寄存器長度不是32位的電腦中，這些技巧基本上仍能適用。
本書不打算講高深的排序算法或是編譯器的優化技術等大話題，而是著重來談涉及單個計算機字組或指令的小技巧，比如怎樣統計字組中值為1的位元數。此類技巧通常需要混用算術與邏輯指令。
我們還需假定整數溢出中斷已經屏蔽，這樣的話，就算整數運算溢出了，也不會出問題。C、Fortran、Java等程序都是如此，但使用Pascal與Ada語言的程序員一定要注意這一點！
在本書語境中，電腦、計算機(computer)、機器(machine)、處理器(processor)等詞常常都指代中央處理器(CPU)，故譯文在不致混淆的情況下，將其視為互相通用的概念。——譯者注
integer overflow，指算術運算時由于結果過大或過小而超出存儲范圍的情形。詳情參見：https：//en杄wikipedia杄org/wiki/Integer_overflow。——譯者注
書中以通俗的語言來講述各技巧，只有算法含義不明顯時才會給出證明，有時甚至略去證明。算法中將會出現計算機算術指令、“地板”函數、算術與邏輯操作混搭等內容，它們要證明起來通常比較困難，而且也不易表述。
floor function，又叫向下取整函數或最低值函數，返回不大于自變量的最大整數，也常稱為“高斯函數”。詳情參見：https：//zh杄wikipedia杄org/wiki/地板函數。——譯者注
筆者把很多算法都寫成了程序代碼，在電腦上執行并驗證，以減少筆誤及疏忽。用實際存在的編程語言來描述算法，就有這個好處；然而即便如此，每一種計算機語言也還是各有其缺陷。我使用很多人能看懂的C代碼來描述高級語言部分，因為它可以直接把整數與位串操作寫在一起，而且很多C語言編譯器都能產生高質量的目標代碼。
object code，又叫“目的碼”，是編譯器處理源代碼后的產物，一般由機器碼或近于機器語言的代碼組成。存放此類代碼的文件叫目標文件(object code)，也叫二進制文件。詳情參見：https：//zh杄wikipedia杄org/wiki/目標代碼。——譯者注
書中偶爾也會用到機器語言，它們都以“三地址格式”出現，這樣讀起來更方便。其中的匯編語言是筆者參照當下的RISC指令集虛構出來的。
three拟address format，即three address code，縮寫為TAC或3AC，又叫“三位址碼”、“三地址碼”。它把通常的算式“運算結果=操作數1 操作符 操作數2”寫成“操作符 操作數1，操作數2，運算結果”的形式，因其中牽涉3個變量(即操作數1、操作數2、運算結果)而得名。例如z=x+y用TAC格式來寫就是add x，y，z。詳情參見：https：//en杄wikipedia杄org/wiki/Three_address_code。——譯者注
RISC，Reduced Instruction Set Computing的縮寫，是一種設計CPU的模式，該設計思路精簡了指令數目及定址方式，使CPU的制作更為容易，也有助于提升其并行能力與執行效率。使用此種指令集的CPU目前主要應用于智能手機和平板電腦等移動設備上，與之相對的是x86等處理器所用的“復雜指令集”(CISC，C表示Complex)。詳情參見：https：//zh杄wikipedia杄org/wiki/精簡指令集。——譯者注
大家應該盡量編寫沒有分支的代碼(branch拟free code)，因為分支代碼會拖慢很多電腦的指令獲取速度，并阻止CPU并發執行。此外，它還會妨礙一些編譯器優化措施𡸷𡸷，如指令調度崐崐、重復子表達式消除崘崘、寄存器分配嵆嵆等。也就是說，編譯器優化大段的簡單代碼要比優化很多小代碼塊的效果更好。
常見的編譯器優化技法請參考：https：//en杄wikipedia杄org/wiki/Category：Compiler_optimizations。——譯者注
instruction scheduling，是通過指令流水線(instruction pipeline)技術提升指令并發執行效果的優化手法。詳情參見：https：//en杄wikipedia杄org/wiki/Instruction_scheduling。——譯者注
commoning，即common subexpression elimination(CSE)，是通過消減重復的表達式來提升執行速度的優化技術。詳情參見：https：//en杄wikipedia杄org/wiki/Common_subexpression_elimination。——譯者注
register allocation，該技術讓眾多變量共用一個CPU寄存器，以優化執行速度。詳情參見：https：//en杄wikipedia杄org/wiki/Register_allocation。——譯者注
此外，編碼時還應該多用數值較小的常量𡺤𡺤，多與0比較(少與非0值比較)，盡量寫出易于并發執行的指令序列岺岺。如果改寫書里很多代碼，讓它們從內存中查表，其結果會更精確，然而筆者通常不提這種做法。因為與算術指令相比，從內存中加載數據反而更耗時。雖說查表法的確很實用，但是一般來說都比較乏味。當然還有些特例不屬于上述情況。
immediate value，也叫“立即值”。——譯者注
instruction拟level parallism，縮寫為ILP，意為指令級并行度，用于度量指令序列的并發執行程度。例如某段指令在非并發方式下需要3個時間單位來執行，而并發執行只需2個時間單位，那么其ILP就是3/2。詳情參見：https：//en杄wikipedia杄org/wiki/Instruction拟level_parallelism。書中還用該詞表示CPU并發執行指令的能力。——譯者注
最后要說的是，本書書名本書英文書名為Hacker𠖥s Delight。——譯者注中的“hacker”用的是本意，也就是指癡迷于計算機的人。這種人喜歡拿電腦開發點新玩意兒，或是用新潮而有創意的辦法來實現原有的功能。他們都挺會用電腦，但卻很可能不是一名專職電腦程序員或設計師，這些電腦極客峯峯開發出來的東西，有些有用，有些只是玩玩而已。說到此類純屬玩樂的戲作，讓我想起很多資深編程票友都寫過一段小程序，它可以把自己照原樣打印出來嶋嶋比方說，下面這段用C語言寫的程序代碼：
本書語境中的“hacker”可理解成“電腦極客”、“程序玩家”、“編程票友”、“編程達人”、“技術發燒友”等意思，以便與容易引發歧義的“駭客”、“黑客”等通俗叫法區分開。本來hacker指計算機技術狂熱愛好者，而cracker指破壞計算機安全的人，但后者的詞義逐漸侵蝕了前者，導致cracker、hacker及“駭客、黑客、怪客、劊客”等譯名全都成了“計算機安全破壞者”，令hacker一詞喪失了原意。詳情參見：https：//zh杄wikipedia杄org/wiki/駭客。——譯者注
main(){char*p="main(){char*p=%c%s%c；(void)printf(p，34，p，34，10)；}%c"；(void)printf(p，34，p，34，10)；}。這才是我使用“hacker”一詞的初衷，在書里可別想找到教你怎樣入侵他人電腦的把戲哦。
致謝
首先要感謝Bruce Shriver與Dennis Allison兩位先生鼓勵我寫作本書，然后還要對IBM諸位同仁致意，參考文獻中也提到了其中一些同事的名字。尤其感謝Martin E.Hopkins先生，他可謂IBM的“活編譯器”(Mr杄Compiler)。Hopkins先生在編碼工作中一絲不茍，認真優化每一個循環——這種敬業精神深深感染了我。仰賴Addison拟Wesley各位評審，本書內容有了極大改觀。他們的姓名筆者大多不了解，我唯一記住的是大名鼎鼎的Guy L杄Steele，Jr杄。在50頁書評中，Guy補充了一些我當時沒有談到的新問題，如位元的打亂與復原，“綿羊與山羊分離操作”(分羊法，sheep and goats operation)，等等，而且他提出的一些算法也比我原來用的更高明。Guy是個非常仔細的人，比方說，我曾把十六進制數AAAAAAAA的質因子分解式錯寫為2×3×17×257×65 537，而他發現其中的3應該是5。此外，他還提了一些旨在改善寫作風格的建議，并且從不回避書里的細節問題。讀者若發現文中有疑似他人捉刀之處𡷹𡷹，那恐怕得歸功于Guy了。
原文為parallel prefix，意為“并行前置式算法”、“平行前綴算法”，是一套分組歸并形式的速算流程。詳情參見：https：//www杄wikipedia杄org/wiki/Prefix_sum。作者在此處以之比喻他與Guy四手聯彈的佳話。——譯者注
H.S.Warren，Jr杄
2012年6月于紐約州約克鎮
本書英文版相關資料請查閱
www.HackersDelight.org |
內容簡介：是第一本宣稱能講解計算機算法隱晦細節的書，而且講得還真不錯。我知道的每一條技巧書里都提到了，而且還講了好多好多我不知道的。不論是在開發程序庫或編譯器，還是在極力搜求優雅算法，此書都可謂天賜良冊，應放在高德納所著《計算機程序設計藝術》那套書旁邊。本書第一版刊印后的10年間，它對我在Sun和Google的工作大有裨益，而第二版所添加新內容亦令我驚羨不已。”
—— Joshua Bloch
“初看本書書名時，我想，這是教人怎么入侵計算機系統的書嗎？不太可能吧。嗯，那就肯定是一本編程小技巧的集錦。看了之后發現，沒錯，這就是一本編程秘籍，然而卻是一本包羅萬象的秘籍。第二版新增了兩個大主題，并用數十個小技巧豐富了本書內容，其中有個小絕招是如何在不溢出的情況下求兩數均值，我寫二分查找算法時直接就把這條拿來用了。這真是本令算法愛好者開懷暢讀的書啊！”
—— Guy Steele
在本書中，作者給我們帶來了一大批極為誘人的知識，其中包括各種節省程序運行時間的技巧、算法與竅門。學習了這些技術，程序員就可寫出優雅高效的軟件，同時還能洞悉其中原理。這些技術極為實用，而且其問題本身又非常有趣，有時甚至像猜謎解謎一般，需要奇思妙想才行。簡而言之，軟件開發者看到這些改進程序效率的妙計之后，定然大喜。
本書較第1版增補了大量內容
新增了循環冗余校驗（CRC）一章，其中講解了常用的CRC-32校驗碼
新增了糾錯碼（ECC）一章，其中講解了漢明碼
詳解了除數為常數的整數除法，增補了僅含移位操作和加法操作的算法
不計算商而直接求余數
擴充了與種群計數和前導0計數有關的知識
數組種群計數
執行壓縮與擴展操作的新算法
LRU算法
浮點數與整數互化
估算浮點數的平方根倒數
一系列離散函數圖像
各章均配有習題與參考答案 |
目錄：譯者序
序（第1版序）
前言
第1章概述
1.1記法
1.2指令集與執行時間模型
1.3習題
第2章基礎知識
2.1操作最右邊的位元
2.1.1德摩根定律的推論
2.1.2從右至左的可計算性測試
2.1.3位操作的新式用法
2.2結合邏輯操作的加減運算
2.3邏輯與算術表達式中的不等式
2.4絕對值函數
2.5兩數平均值
2.6符號擴展
2.7用無符號右移模擬帶符號右移操作
2.8符號函數
2.9三值比較函數
2.10符號傳遞函數
2.11將值為0的位段解碼為2的n次方
2.12比較謂詞
2.12.1利用進位標志求比較謂詞
2.12.2計算機如何設置比較謂詞
2.13溢出檢測
2.13.1帶符號的加減法
2.13.2計算機執行帶符號數的加減法時如何設置溢出標志
2.13.3無符號數的加減法
2.13.4乘法
2.13.5除法
2.14加法、減法與乘法的特征碼
2.15循環移位
2.16雙字長加減法
2.17雙字長移位
2.18多字節加減法與求絕對值
2.19doz、max、min函數
2.20互換寄存器中的值
2.20.1交換寄存器中相應的位段
2.20.2交換同一寄存器內的兩個位段
2.20.3有條件的交換
2.21在兩個或兩個以上的值之間切換
2.22布爾函數分解公式
2.23實現16種二元布爾操作
2.24習題
第3章2的冪邊界
3.1將數值上調/下調為2的已知次冪的倍數
3.2調整到上一個/下一個2的冪
3.2.1向下舍入
3.2.2向上舍入
3.3判斷取值范圍是否跨越了2的冪邊界
3.4習題
第4章算術邊界
4.1檢測整數邊界
4.2通過加減法傳播邊界
4.3通過邏輯操作傳播邊界
4.4習題
第5章位計數
5.1統計值為“1”的位元數
5.1.1兩個字組種群計數的和與差
5.1.2比較兩個字組的種群計數
5.1.3統計數組中值為“1”的位元數
5.1.4應用
5.2奇偶性
5.2.1計算字組的奇偶性
5.2.2將表示奇偶性的位元添加到7位量中
5.2.3應用
5.3前導0計數
5.3.1浮點數算法
5.3.2比較兩個字組前導0的個數
5.3.3與對數函數的關系
5.3.4應用
5.4后綴0計數
5.5習題
第6章在字組中搜索位串
6.1尋找首個值為0的字節
6.1.10值字節位置函數的
一些簡單推廣
6.1.2搜索給定范圍內的值
6.2尋找首個給定長度的全1位串
6.3尋找最長全1位串
6.4尋找最短全1位串
6.5習題
第7章重排位元與字節
7.1反轉位元與字節
7.1.1位元反轉算法的推廣
7.1.2奇特的位元反轉算法
7.1.3遞增反轉后的整數
7.2亂序排列位元
7.3轉置位矩陣
7.4壓縮算法(廣義提取算法)
7.4.1用“插入”、“提取”指令實現壓縮操作
7.4.2向左壓縮
7.5展開算法(廣義插入算法)
7.6壓縮與展開操作的硬件算法
7.6.1壓縮
7.6.2展開
7.7通用置換算法及分羊操作
7.8重排與下標變換
7.9LRU算法
7.10習題
第8章乘法
8.1多字乘法
8.264位積的高權重部分
8.3無符號與帶符號的高權重積互化
8.4與常數相乘
8.5習題
第9章整數除法
9.1預備知識
9.2多字除法
9.3用帶符號除法計算無符號短除法
9.3.1用帶符號長除法計算無符號短除法
9.3.2用帶符號短除法計算無符號短除法
9.4無符號長除法
9.4.1用硬件實現移位并相減算法
9.4.2用短除法實現無符號長除法
9.5用長除法實現雙字除法
9.5.1無符號雙字除法
9.5.2帶符號雙字除法
9.6習題
第10章除數為常量的整數除法
10.1除數為2的已知次冪的帶符號除法
10.2求與2的已知次冪相除的帶符號余數
10.3在除數不是2的冪時求帶符號除法及余數
10.3.1除以3
10.3.2除以5
10.3.3除以7
10.4除數大于等于2的帶符號除法
10.4.1算法
10.4.2算法可行性證明
10.4.3證明乘積正確
10.5除數小于等于-2的帶符號除法
10.6將除法算法集成至編譯器中
10.7其他主題
10.7.1唯一性
10.7.2可生成最佳程序代碼的除數
10.8無符號除法
10.8.1除數為3的無符號除法
10.8.2除數為7的無符號除法
10.9除數大于等于1的無符號除法
10.9.1無符號版算法
10.9.2算法可行性證明
10.9.3證明無符號版算法的乘積正確
10.10將無符號除法算法集成至編譯器中
10.11與無符號除法相關的其他話題
10.11.1可生成最佳無符號除法代碼的除數
10.11.2帶符號乘法與無符號乘法互化
10.11.3更簡單的無符號除法生成算法
10.12余數非負式除法與向下取整式除法的適用性
10.13類似算法
10.14神奇數字示例
10.15用Python語言編寫的簡單代碼
10.16除數為常量的精確除法
10.16.1用歐幾里得算法計算乘法逆元素
10.16.2用牛頓法計算乘法逆元素
10.16.3乘法逆元素示例
10.17檢測除以常數后是否余0
10.17.1無符號除法
10.17.2除數大于等于2的帶符號除法
10.18不使用Multiply High指令的除法算法
10.18.1無符號除法
10.18.2帶符號除法
10.19合計各數位求余數
10.19.1求無符號除法的余數
10.19.2求帶符號除法的余數
10.20用乘法及右移位求余數
10.20.1求無符號除法的余數
10.20.2求帶符號除法的余數
10.21將普通除法化為精確除法
10.22計時測試
10.23用電路計算除數為3的除法
10.24習題
第11章初等函數
11.1整數平方根
11.1.1用牛頓法開平方
11.1.2二分查找
11.1.3硬件算法
11.2整數立方根
11.3求整數冪
11.3.1用n的二進制分解式計算xn
11.3.2用Fortran語言計算2n
11.4整數對數
11.4.1以2為底的整數對數
11.4.2以10為底的整數對數
11.5習題
第12章以特殊值為底的數制
12.1以-2為底的數制
12.2以-1+i為底的數制
12.3以其他數為底的數制
12.4最高效的底是什么
12.5習題
第13章格雷碼
13.1簡介
13.2遞增格雷碼整數
13.3負二進制格雷碼
13.4格雷碼簡史及應用
13.5習題
第14章循環冗余校驗
14.1簡介
14.2理論
14.3實現
14.3.1硬件實現
14.3.2軟件實現
14.4習題
第15章糾錯碼
15.1簡介
15.2漢明碼
15.2.1SEC拟DED碼
15.2.2校驗位個數的最小值
15.2.3小結
15.3適用于32位信息的軟件SEC拟DED算法
15.4廣義錯誤修正
15.4.1漢明距離
15.4.2編碼論的主要問題
15.4.3n維球面
15.5習題
第16章希爾伯特曲線
16.1生成希爾伯特曲線的遞歸算法
16.2根據希爾伯特曲線上從起點到某點的途經距離求其坐標
16.3根據希爾伯特曲線上的坐標求從起點到某點的途經距離
16.4遞增希爾伯特曲線上點的坐標
16.5非遞歸的曲線生成算法
16.6其他空間填充曲線
16.7應用
16.8習題
第17章浮點數
17.1IEEE格式
17.2整數與浮點數互化
17.3使用整數操作比較浮點數大小
17.4估算平方根倒數
17.5前導數位的分布
17.6雜項數值表
17.7習題
第18章素數公式
18.1簡介
18.2Willans公式
18.2.1Willans第二公式
18.2.2Willans第三公式
18.2.3Willans第四公式
18.3Wormell公式
18.4用公式來描述其他難解的函數
18.5習題
參考答案
附錄A4位計算機算術運算表
附錄B牛頓法
附錄C各種離散函數圖像
參考文獻 |
| 序： |
