小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

分享

把《編程珠璣》讀薄

 PorcelainCat 2016-04-06


作者Hawstein

鏈接:http:///posts/make-thiner-programming-pearls.html


開篇


具體化你的解決的問題。下面是A和B的對話。


A:我該如何對磁盤文件進行排序?

B:需要排序的內(nèi)容是什么?文件中有多少條記錄?每個記錄的格式是什么?

A:該文件包含至多10,000,000個記錄,每條記錄都是一個7位整數(shù)。

B:如果文件那么小,為什么要使用磁盤排序呢?為什么不在主存中對它排序?

A:該功能是某大型系統(tǒng)中的一部分,大概只能提供1MB主存給它。

B:你能將記錄方面的內(nèi)容說得更詳細一些嗎?

A:每個記錄是一個7位正整數(shù),沒有其它的關(guān)聯(lián)數(shù)據(jù),每個整數(shù)至多只能出現(xiàn)一次。

... ...

經(jīng)過一系統(tǒng)的問題,我們可以將一個定義模糊不清的問題變得具體而清晰:


輸入:

所輸入的是一個文件,至多包含n個正整數(shù),每個正整數(shù)都要小于n,這里n=10^7。

如果輸入時某一個整數(shù)出現(xiàn)了兩次,就會產(chǎn)生一個致命的錯誤。

這些整數(shù)與其它任何數(shù)據(jù)都不關(guān)聯(lián)。

輸出:

以增序形式輸出經(jīng)過排序的整數(shù)列表。

約束:

大概有1MB的可用主存,但可用磁盤空間充足。運行時間至多允許幾分鐘,

10秒鐘是最適宜的運行時間。


如果主存容量不是嚴苛地限制在1MB,比如說可以是1MB多,或是1~2MB之間, 那么我們就可以一次性將所有數(shù)據(jù)都加載到主存中,用Bitmap來做。 10,000,000個數(shù)就需要10,000,000位,也就是10,000,000b = 1.25MB。


程序可分為三個部分:第一,初始化所有的位為0;第二,讀取文件中每個整數(shù), 如果該整數(shù)對應(yīng)的位已經(jīng)為1,說明前面已經(jīng)出現(xiàn)過這個整數(shù),拋出異常,退出程序 (輸入要求每個整數(shù)都只能出現(xiàn)一次)。否則,將相應(yīng)的位置1;第三, 檢查每個位,如果某個位是1,就寫出相應(yīng)的整數(shù),從而創(chuàng)建已排序的輸出文件。


如果主存容量嚴苛地限制在1MB,而使用Bitmap需要1.25MB, 因此無法一次載入完成排序。那么,我們可以將該文件分割成兩個文件, 再分別用Bitmap處理。分割策略可以簡單地把前一半的數(shù)據(jù)放到一個文件, 后一半的數(shù)據(jù)放到另一個文件,分別排序后再做歸并。 也可以把文件中小于某個數(shù)(比如5,000,000)的整數(shù)放到一個文件,叫l(wèi)ess.txt, 把其余的整數(shù)放到另一個文件,叫g(shù)reater.txt。分別排序后, 把greater.txt的排序結(jié)果追加到less.txt的排序結(jié)果即可。


啊哈!算法


第2章圍繞3個問題展開。


  • 給定一個包含32位整數(shù)的順序文件,它至多只能包含40億個這樣的整數(shù), 并且整數(shù)的次序是隨機的。請查找一個此文件中不存在的32位整數(shù)。 在有足夠主存的情況下,你會如何解決這個問題? 如果你可以使用若干外部臨時文件,但可用主存卻只有上百字節(jié), 你會如何解決這個問題?


這是CTCI中的一道題目,詳細解答請戳以下鏈接:


請猛戳我


請將一個具有n個元素的一維向量向左旋轉(zhuǎn)i個位置。例如,假設(shè)n=8,i=3, 那么向量abcdefgh旋轉(zhuǎn)之后得到向量defghabc。


這個問題很常見了,做3次翻轉(zhuǎn)即可,無需額外空間:


reverse(0, i-1); // cbadefgh

reverse(i, n-1); // cbahgfed

reverse(0, n-1); // defghabc


給定一本英語單詞詞典,請找出所有的變位詞集。例如,因為“pots”, “stop”,“tops”相互之間都是由另一個詞的各個字母改變序列而構(gòu)成的, 因此這些詞相互之間就是變位詞。


這個問題可以分3步來解決。第一步將每個單詞按字典序排序, 做為原單詞的簽名,這樣一來,變位詞就會具有相同的簽名。 第二步對所有的單詞按照其簽名進行排序,這樣一來,變位詞就會聚集到一起。 第三步將變位詞分組,形成變位詞集。示意圖如下:




數(shù)據(jù)決定程序結(jié)構(gòu)


恰當?shù)臄?shù)據(jù)視圖實際上決定了程序的結(jié)構(gòu)。 我們常常可以通過重新組織內(nèi)部數(shù)據(jù)來使程序變得小而美。


發(fā)明家悖論:更一般性的問題也許更容易解決。(有時候吧)


程序員在節(jié)省空間方面無計可施時,將自己從代碼中解脫出來, 退回起點并集中心力研究數(shù)據(jù),常常能有奇效。數(shù)據(jù)的表示形式是程序設(shè)計的根本。


下面是退回起點進行思考時的幾條原則:


使用數(shù)組重新編寫重復代碼。冗長的相似代碼常??梢允褂米詈唵蔚臄?shù)據(jù)結(jié)構(gòu)—— 數(shù)組來更好地表述。


封裝復雜結(jié)構(gòu)。當需要非常復雜的數(shù)據(jù)結(jié)構(gòu)時,使用抽象術(shù)語進行定義, 并將操作表示為類。


盡可能使用高級工具。超文本,名字-值對,電子表格,數(shù)據(jù)庫, 編程語言等都是特定問題領(lǐng)域中的強大的工具。


從數(shù)據(jù)得出程序的結(jié)構(gòu)。在動手編寫代碼之前,優(yōu)秀的程序員會徹底理解輸入, 輸出和中間數(shù)據(jù)結(jié)構(gòu),并圍繞這些結(jié)構(gòu)創(chuàng)建程序。


提到的書籍:Polya的《How to Solve it》,中文書《怎樣解題》; Kernighan和Plauger的《Elements of Programming Style》;Fred Brooks的《人月神話》 Steve McConnell的《代碼大全》;《Rapid Development》; 《Software Project Survival Guide》


編寫正確的程序


本章以二分搜索為例子,講述了如何對程序進行驗證及正確性分析。


深入閱讀:David Gries的《Science of Programming》 是程序驗證領(lǐng)域里極佳的一本入門書籍。


編程中的次要問題


到目前為止,你已經(jīng)做了一切該做的事:通過深入挖掘定義了正確的問題, 通過仔細選擇算法和數(shù)據(jù)結(jié)構(gòu)平衡了真正的需求,通過程序驗證技術(shù)寫出了優(yōu)雅的代碼, 并且對其正確性相當有把握。萬事俱備,只欠編程。


  • 使用斷言assert

  • 自動化測試程序


進階閱讀:《Practice of Programming》第5章(調(diào)試),第6章(測試) 《Code Complete》第25章(單元測試),第26章(調(diào)試)


程序性能分析


下圖展示了一個程序的性能提升過程, 該程序的作用是對三維空間中n個物體的運動進行仿真。從圖中可以看出, 一個程序可以從多方面進行性能提升,而其中算法和數(shù)據(jù)結(jié)構(gòu)的選擇又顯得尤為重要。




從設(shè)計層面提升程序性能:


1、問題定義。良好的問題定義可以有效減少程序運行時間和程序長度。

2、系統(tǒng)結(jié)構(gòu)。將大型系統(tǒng)分解成模塊,也許是決定其性能的最重要的單個因素。

3、算法和數(shù)據(jù)結(jié)構(gòu)。這個不用說了。

4、代碼調(diào)優(yōu)。針對代碼本身的改進。

5、系統(tǒng)軟件。有時候改變系統(tǒng)所基于的軟件比改變系統(tǒng)本身更容易。

6、硬件。更快的硬件可以提高系統(tǒng)的性能。


深入閱讀:Butler Lampson的“Hints for Computer System Design”, 該論文特別適合于集成硬件和軟件的計算機系統(tǒng)設(shè)計。


粗略估算


這一章講述了估算技術(shù),我認為是相當有用的一章。


文中先拋出一個問題:密西西比河一天流出多少水?如果讓你來回答, 你會怎么答,注意不能去Google哦。


作者是這么回答這個問題:假設(shè)河的出口大約有1英里寬和20英尺深(1/250英里), 而河水的流速是每小時5英里,也就是每天120英里。則可以計算出一天的流量:


1英里 * 1/250英里 * 120英里/天  約等于  1/2 英里^3/天


上述算式非常簡單,可是在看到這些文字之前,如果有人真的問你, 密西西比河一天流出多少水?你真的能答上來嗎?還是愣了一下后,擺擺手,說: 這我哪知道!


對于上面的問題,我們至少可以注意到以下兩點:


你需要把問題轉(zhuǎn)換成一個可計算的具體模型。這一點往往不需要太擔心, 因為我們做的是估算,所以可以忽視很多無關(guān)緊要的因素,可以去簡化你的模型, 記住我們要的只是一個粗略計算的結(jié)果。比如對于上面的問題, 計算密西西比河一天流出多少水其實就是計算其一天的流量,利用中學所學知識, 流量 = 截面積 x 流速,那我們就只需計算密西西比河的出水口的截面積和流速即可。 我們可以將出水口簡化成一個矩形,因此就只需要知道出水口的寬和深即可。


你需要知道常識性的東西。上面我們已經(jīng)把問題轉(zhuǎn)換成了一個可計算的具體模型: 流量 = 出水口寬 x 出水口深 x 流速。接下來呢?你需要代入具體的數(shù)值去求得答案。 而這就需要你具備一些常識性的知識了。比如作者就估計了密西西比河的出口有1英里寬, 20英尺深(如果你估計只有幾十米寬,那就相差得太離譜了)。 這些常識性的知識比第1點更值得關(guān)注,因為你無法給出一個靠譜的估算值往往是因為這點。


當我們懂得如何把一個問題具體化定義出來并為其選用適當?shù)哪P停?并且我們也積累了必要的常識性的知識后,回答那些初看起來無從下手的問題也就不難了。 這就是估算的力量。


以下是估算時的一些有用提示:


兩個答案比一個答案好。即鼓勵你從多個角度去對一個問題進行估算, 如果從不同角度得到的答案差別都不大,說明這個估算值是比較靠譜的。


快速檢驗。即量綱檢驗。即等式兩邊最終的量綱要一致。 這一點在等式簡單的時候相當顯而易見。比如位移的單位是米,時間單位是秒, 速度單位是米/秒,那顯然我們應(yīng)該要用位移去除以時間來得到速度, 這樣才能保證它們單位的一致。你可能會說,我了個去,這種小學生都懂的事, 你好意思拿出來講。其實不然,當你面對的是一個具有多個變量的復雜物理公式, 或者你提出某種物理假設(shè),正在考慮將其公式化,該方法可以切切實實地幫你做出檢驗。


經(jīng)驗法則。“72法則”:1.假設(shè)以年利率r%投資一筆錢y年,如果r*y = 72, 那么你的投資差不多會翻倍。2.如果一個盤子里的菌群以每小時3%的速率增長, 那么其數(shù)量每天(24小時)都會翻倍。在誤差不超過千分之五的情況下, \pi秒就是一個納世紀。也就是說:


3.14秒 = 10^(-9) * 100年 = 10^(-7) 年


也就是說,1年大概是3.14x10^7 秒。所以如果有人告訴你,一個程序運行10^7 秒, 你應(yīng)該能很快反應(yīng)出,他說的其實是4個月。


實踐。與許多其他活動一樣,估算技巧只能通過實踐來提高。


如果問題的規(guī)模太大,我們還可以通過求解它的小規(guī)模同質(zhì)問題來做估算。比如, 我們想測試某個程序運行10億次需要多長時間,如果你真去跑10億次, 說不定運行幾個小時都沒結(jié)束,那不是很悲劇?我們可以運行這個程序1萬次或是10萬次, 得出結(jié)果然后倍增它即可。當然,這個結(jié)果未必是準確的, 因為你沒法保證運行時間是隨著運行次數(shù)線性增加的。謹慎起見,我們可以運行不同的次數(shù), 來觀察它的變化趨勢。比如運行10次,100次,1000次,10000次等, 觀察它的運行時間是否是線性增加的,或是一條二次曲線。


有時候,我們需要為估算的結(jié)果乘上一個安全系數(shù)。比如, 我們預(yù)估完成某項功能需要時間t,那根據(jù)以往經(jīng)驗,也許我們需要為這個值乘上2或4, 這樣也許才是一個靠譜的預(yù)估值。


Little定律:系統(tǒng)中物體的平均數(shù)量等于物體離開系統(tǒng)的平均速率和每個物體在系統(tǒng)中停留 的平均時間的乘積。(如果物體離開和進入系統(tǒng)的總體出入流是平衡的, 那么離開速率也就是進入速率)


舉個例子,比如你正在排除等待進入一個火爆的夜總會, 你可以通過估計人們進入的速率來了解自己還要等待多長時間。根據(jù)Little定律, 你可以推論:這個地方可以容納約60人,每個人在里面逗留時間大約是3小時, 因此我們進入夜總會的速率大概是每小時20人。現(xiàn)在隊伍中我們前面還有20人, 也就意味著我們還要等待大約一個小時。


深入閱讀:Darrell Huff的《How To Lie With Statistics》;關(guān)鍵詞: 費米近似(Fermi estimate, Fermi problem)


算法設(shè)計技術(shù)


這一章就一個小問題研究了4種不同的算法,重點強調(diào)這些算法的設(shè)計技術(shù)。 研究的這個小問題是一個非常常見的面試題:子數(shù)組之和的最大值。 如果之前沒有聽過,建議Google之。


深入閱讀:Aho,Hopcroft和Ullman的《Data Structures and Algorithms》 Cormen,Leiserson,Rivest和Stein的《Introduction to Algorithms》


代碼調(diào)優(yōu)


前面各章討論了提高程序效率的高層次方法:問題定義,系統(tǒng)結(jié)構(gòu), 算法設(shè)計及數(shù)據(jù)結(jié)構(gòu)選擇。本章討論的則是低層次的方法:代碼調(diào)優(yōu)。


代碼調(diào)優(yōu)的最重要原理就是盡量少用它。不成熟的優(yōu)化是大量編程災(zāi)害的根源。 它會危及程序的正確性,功能性以及可維護性。當效率很重要時, 第一步就是對系統(tǒng)進行性能監(jiān)視,以確定其運行時間的分布狀況。 效率問題可以由多種方法來解決,只有在確信沒有更好的解決方案時才考慮進行代碼調(diào)優(yōu)。


事實上,如果不是十分十分必要,不要去做代碼調(diào)優(yōu), 因為它會犧牲掉軟件的其他許多性質(zhì)。


so,just skip this chapter。


節(jié)省空間


本章講述了節(jié)省空間的一些重要方法。


減少程序所需數(shù)據(jù)的存儲空間,一般有以下方法:


  • 不存儲,重新計算。

  • 稀疏數(shù)據(jù)結(jié)構(gòu)。下面著重講一下這點。

  • 數(shù)據(jù)壓縮??梢酝ㄟ^壓縮的方式對對象進行編碼,以減少存儲空間。

  • 分配策略。只有在需要的時候才進行分配。

  • 垃圾回收。對廢棄的存儲空間進行回收再利用。


以下是節(jié)省代碼空間的幾種通用技術(shù):


  • 函數(shù)定義。用函數(shù)替換代碼中的常見模式可以簡化程序,同時減少代碼的空間需求。

  • 解釋程序。用解釋程序命令替換長的程序文本。

  • 翻譯成機器語言??梢詫⒋笮拖到y(tǒng)中的關(guān)鍵部分用匯編語言進行手工編碼。


稀疏數(shù)據(jù)結(jié)構(gòu)


假設(shè)我們有一個200 x 200的矩陣(共40000個元素),里面只有2000個元素有值, 其它的都為0,示意圖如下:




顯然這是一個稀疏矩陣,直接用一個200 x 200 的二維數(shù)組來存儲這些數(shù)據(jù)會造成大量的空間浪費,共需要200x200x4B=160KB。 所以,我們應(yīng)該想辦法用另一種形式來存儲這些數(shù)據(jù)。


方法一


使用數(shù)組表示所有的列,同時使用鏈表來表示給定列中的活躍元素。 如下圖所示:




該結(jié)構(gòu)中,有200個指針(colhead)和2000條記錄(每條記錄是兩個整數(shù)和一個指針), 占用空間是200x4B + 2000x12B = 24800B = 24.8KB, 比直接用二維數(shù)組存儲(160KB)要小很多。


方法二


我們可以開三個數(shù)組來保存這些數(shù),如下圖所示:




firstincol是一個長度為201的數(shù)組,對于第i列,在數(shù)組row中, 下標為firstincol[i]到firstincol[i+1]-1對應(yīng)的行元素非0, 其值存儲在相應(yīng)的pointnum數(shù)組中。


比如對于上圖,在第0列中,元素值非0的行有3行,分別是row[0],row[1],row[2], 元素值是pointnum[0],pointnum[1],pointnum[2];在第1列中,元素值非0的行有2行, 分別是row[3],row[4],元素值是pointnum[3],pointnum[4]。依次類推。


該結(jié)構(gòu)所需要的存儲空間為2x2000x4B + 201x4B = 16804B = 16.8KB。 由于row數(shù)組中的元素全部都小于200,所以每個元素可以用一個unsigned char來保存, firstincol數(shù)組中元素最大也就2000,所以可以用一個short(或unsigned short)來保存, pointnum中的元素是一個4B的int, 最終所需空間變?yōu)椋?000x4B + 2000x1B + 201x2B = 10402B = 10.4KB。


深入閱讀:Fred Brooks的《人月神話》


排序


本章先簡單介紹了插入排序,然后著重講述快速排序。


插入排序




快速排序


我們在這里規(guī)定:小于等于pivot的元素移到左邊,大于pivot的元素移到右邊。


實現(xiàn)1:單向移動版本


這個版本的關(guān)鍵是設(shè)置一快一慢兩個指針,慢指針左側(cè)都是小于等于pivot(包含慢指針所在位置), 慢指針到快指針之間的值是大于pivot,快指針右側(cè)的值是還未比較過的。示意圖如下:


小于等于pivot    |    大于pivot    |    ?

             slow                fast


快指針一次一步向前走,遇到大于pivot什么也不做繼續(xù)向前走。遇到小于等于pivot的元素, 則慢指針slow向前走一步,然后交換快慢指針指向的元素。一次劃分結(jié)束后, 再遞歸對左右兩側(cè)的元素進行快排。代碼如下:




排序數(shù)組a只需要調(diào)用QSort(a, 0, n)即可。該思路同樣可以很容易地在鏈表上實現(xiàn):



排序頭指針為head的單鏈表只需調(diào)用qsort(head, NULL)即可。


實現(xiàn)2:雙向移動版本


版本1能能夠快速完成對隨機整數(shù)數(shù)組的排序,但如果數(shù)組有序, 或是數(shù)組中元素相同,快排的時間復雜度會退化成O(n^2 ),性能變得非常差。


一種緩解方案是使用雙向移動版本的快排,它每次劃分也是使用兩個指針, 不過一個是從左向右移動,一個是從右向左移動,示意圖如下:


小于等于pivot    |    ?    |    大于pivot

               i            j


指針j不斷向左移動,直到遇到小于等于pivot,就交換指針i和j所指元素 (指針i一開始指向pivot);指針i不斷向右移動,直到遇到大于pivot的, 就交換指針i和j所指元素。pivot在這個過程中,不斷地換來換去, 最終會停在分界線上,分界線左邊都是小于等于它的元素,右邊都是大于它的元素。 這樣就避免了最后還要交換一次pivot的操作,代碼也變得美觀許多。



當然,如果對于partition函數(shù),你如果覺得大循環(huán)內(nèi)的兩個swap還是做了些無用功的話, 也可以把pivot的賦值放到最后一步,而不是在這個過程中swap來swap去的。代碼如下:



如果數(shù)組基本有序,那隨機選擇pivot(而不像上面那樣選擇第一個做為pivot) 會得到更好的性能。在partition函數(shù)里,我們只需要在數(shù)組中隨機選一個元素, 然后將它和數(shù)組中第一個元素交換,后面的劃分代碼無需改變, 就可以達到隨機選擇pivot的效果。


進一步優(yōu)化


對于小數(shù)組,用插入排序之類的簡單方法來排序反而會更快,因此在快排中, 當數(shù)組長度小于某個值時,我們就什么也不做。對應(yīng)到代碼中, 就是修改quicksort中的if條件:


if(first < last)=""  改為=""  if(last-first=""> cutoff)


其中cutoff是一個小整數(shù)。程序結(jié)束時,數(shù)組并不是有序的, 而是被組合成一塊一塊隨機排列的值,并且滿足這樣的條件: 某一塊中的元素小于它右邊任何塊中的元素。我們必須通過另一種排序算法對塊內(nèi)進行排序。 由于數(shù)組是幾乎有序的,因此插入排序比較適用。


這種方法結(jié)合了快排和插入排序,讓它們?nèi)プ龈髯陨瞄L的事情,往往比單純用快排要快。


深入閱讀:Don Knuth的《The Art of Computer Programming, Volume 3: Sorting and Searching》;Robert Sedgewick的《Algorithms》; 《Algorithms in C》,《Algorithms in C++》,《Algorithms in Java》。


取樣問題


本章講述了一個小的隨機抽樣問題,并用不同的方法來解決它。


問題:對于整數(shù)m和n,其中m


比如m=3, n=5,那么一種可能輸出是0,2,3(要求有序)。實現(xiàn)1來自Knuth的TAOCP, 時間復雜度O(n):


void GenKnuth(int m, int n) {

for(int i=0; i

if((bigrand()%(n-i)) < m)="">

cout<><>

--m;

}

}

}


其中,bigrand()的作用是返回一個很大的隨機整數(shù)。


實現(xiàn)2:在一個初始為空的集合里面插入隨機整數(shù),直到個數(shù)足夠。代碼如下:


void GenSets(int m, int n) {

set s;

while(s.size() <>

s.insert(bigrand() % n);

set::iterator i;

for(i=s.begin(); i!=s.end(); ++i)

cout<><>

}


實現(xiàn)3:把包含整數(shù)0~n-1的數(shù)組順序打亂,然后把前m個元素排序輸出。 該方法的性能通常不如Knuth的算法。代碼如下:


void GenShuf(int m, int n) {

int x[n];

for(int i=0; i

x[i] = i;

for(int i=0; i

int j = randint(i, n-1);

swap(x[i], x[j]);

}

sort(x, x+m);

for(int i=0; i

cout<><>

}


深入閱讀:Don Knuth的《The Art of Computer Programming, Volume 2: Seminumerical Algorithms》


搜索


本章詳細研究這樣一個搜索問題:在沒有其他相關(guān)數(shù)據(jù)的情況下,如何存儲一組整數(shù)? 為些介紹了5種數(shù)據(jù)結(jié)構(gòu):有序數(shù)組,有序鏈表,二叉搜索樹,箱,位向量。


其中,二叉搜索樹應(yīng)該熟練掌握,以下是一種實現(xiàn):










本章主要介紹堆,下面是關(guān)于堆的一些主要操作:


// 最大堆實現(xiàn), 數(shù)組下標從1開始,a[0]不使用。


// 交換兩數(shù)

void swap(int &a, int &b) {

    int t = a;

    a = b;

    b = t;

}


// 把第i個元素向上移動

void ShiftUp(int a[], int i) {

    while(i>1 && a[i]>a[i/2]) {

        swap(a[i], a[i/2]);

        i >>= 1;

    }

}


// 把第i個元素向下移動

void ShiftDown(int a[], int n, int i) {

    while((i=2*i) <= n)="">

        if(i+1<=n &&="" a[i+1]="">a[i]) ++i;

        if(a[i] > a[i/2]) swap(a[i], a[i/2]);

        else break;

    }

}


// 把數(shù)組a變成具備最大堆性質(zhì)的數(shù)組

void MakeHeap(int a[], int n) {

    for(int i=n/2; i>0; --i)

        ShiftDown(a, n, i);

}


// 向堆中插入元素x

void Insert(int a[], int &n, int x) {

    a[++n] = x;

    ShiftUp(a, n);

}


// 刪除堆中第i個元素

void Del(int a[], int &n, int i) {

    a[i] = a[n--];

    if(i>1 && a[i]>a[i/2]) ShiftUp(a, i);

    else ShiftDown(a, n, i);

}


// 堆排序,時間復雜度O(nlogn)

void HeapSort(int a[], int n) {

    MakeHeap(a, n);

    for(int i=n; i>1; --i) {

        swap(a[i], a[1]);

        ShiftDown(a, i-1, 1);

    }

}


字符串


程序1:循環(huán)輸入并將每個單詞插入集合S(忽略重復單詞),然后排序輸出。


int main(void) {

set s;

set::iterator j;

string t;

while(cin >> t)

s.insert(t);

for(j=s.begin(); j!=s.end(); ++j)

cout<><>

return 0;

}


程序2:單詞計數(shù)


int main(void) {

map m;

map::iterator j;

string t;

while(cin >> t)

m[t]++;

for(j=m.begin(); j!=m.end(); ++j)

coutfirst<'>second<>

return 0;

}


程序3:建立自己的哈希表(散列表),以下是一種實現(xiàn):


class Hash {

public:

    Hash(): seed_(131), size_(0) {

        memset(head_, 0, sizeof(head_));

    }

    

    void Insert(const char* str) {

        unsigned int id = hash(str);

        char *dst = (char*)node_[size_].word;

        while(*dst++ = *str++);

        node_[size_].next = head_[id];

        head_[id] = &node_[size_];

        ++size_;

    }


    bool Find(const char* str) {

        unsigned int id = hash(str);

        for(Node* p=head_[id]; p; p=p->next) {

            char* dst = (char*)p->word;

            int i = 0;

            for(; *(str+i) && *(str+i)==*(dst+i); ++i);

            if(!*(str+i) && !*(dst+i)) return true;

        }

        return false;

    }

    

private:

    unsigned int hash(const char* str) {// BKDR Hash Function

        unsigned int hash = 0;

        while(*str) {

            hash = hash * seed_ + (*str++);

        }

        return (hash & 0x7FFFFFFF) % kHashSize;

    }

    

private:

    unsigned int seed_;

    unsigned int size_;

    static const int kWordSize = 26 + 1;

    static const int kNodeSize = 20000;

    static const int kHashSize = 10001;

    struct Node {

        char word[kWordSize];

        Node *next;

    };

    Node node_[kNodeSize];

    Node* head_[kHashSize];

};


后綴數(shù)組


假設(shè)我們有以下字符串及一個char*數(shù)組:


 char c[20] = 'hawstein';

 char* pc[20];


我們讓指針pc[i]指向字符串的第i個字符,即:


for(int i=0; i<8;>

pc[i] = &c[i];


這時候我們輸出pc[i],會得到字符串”hawstein”的所有后綴:


hawstein

awstein

wstein

stein

tein

ein

in

n


然后,我們對數(shù)組pc進行排序,將所有后綴按字典序排序:


sort(pc, pc+8, cmp);


其中,比較函數(shù)cmp如下:


inline bool cmp(char* p, char*q) {

    return strcmp(p, q) <>

}


這時,我們再輸出pc[i],會得到排序后的結(jié)果:


awstein

ein

hawstein

in

n

stein

tein

wstein


我們把數(shù)組pc稱為“后綴數(shù)組”。這里需要注意,數(shù)組pc 中存儲的是指向每個后綴首字符的地址。我們也可以存儲每個后綴首字符在原數(shù)組中的下標, 效果是一樣的。


本章中用后綴數(shù)組解決了一個小問題:可重疊最長重復子串。比如對于字符串”banana”, 其后綴數(shù)組為:


a

ana

anana

banana

na

nana


掃描一次數(shù)組,比較相鄰子串,找到相鄰子串的最長公共前綴即可。本例為”ana”, 其中一個a是重疊的。


    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間,所有內(nèi)容均由用戶發(fā)布,不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式、誘導購買等信息,謹防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請點擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻花(0

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多