【讀薄《編程珠璣》】壹 開篇

這篇文章是《讀薄<編程珠璣>》系列博客的第一篇，在這篇文章中，我總結(jié)了在書中出現(xiàn)的一些問題以及一些解決方案。

問題集合

0x01：一個最多包含n個正整數(shù)的文件，每個數(shù)都小于n，其中n=107，并且沒有重復(fù)。最多有1MB內(nèi)存可用。要求用最快方式將它們排序并按升序輸出

0x02：使用位邏輯運算來實現(xiàn)位向量

0x03：盡可能快的生成位于 0~n-1 之間的 k 個隨機不同順序的整數(shù)

0x04：如果在問題0x01中需要1.25MB 的內(nèi)存空間來進行排序，而我們只有1MB 空間該如何處理？

0x05：如果在問題0x01中，每個數(shù)字出現(xiàn)的次數(shù)不是1次，而是不多于10次，該如何處理？

0x06：如果說我們的位向量非常的稀疏，可能10000位里只有100位得到了使用，這樣的話大量的時間都會浪費在初始化空間上，該如何解決這個問題？

0x07：如何組織電話號碼的存儲，來能夠支持高效的插入和檢索操作？

方案集合

0x01：把文件一次讀入，出現(xiàn)的數(shù)字在位向量對應(yīng)索引處中標(biāo)注為1，讀取完文件之后，將位向量從低位向高位依次將為1的索引輸出即可。(具體實現(xiàn)詳見：http://blog.luoyuanhang.com/2016/05/15/I-%E4%BD%8D%E5%90%91%E9%87%8F%E7%9A%84%E5%AE%9E%E7%8E%B0%E4%B8%8E%E5%BA%94%E7%94%A8/)

0x02：

#define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/BITSPERWORD]; void set(int i){ a[i>>SHIFT] |= (1<<(i & MASK)); } void clr(int i){ a[i>>SHIFT] &= ~(1<<(i & MASK)); } void set(int i){ a[i>>SHIFT] &= (1<<(i & MASK)); }

1

2

3

4

5

6

7

8

9

10

11

(詳細(xì)分析請見：位向量的實現(xiàn)與應(yīng)用)

0x03：

首先，生成一個大小為 N 的數(shù)組，每個值都等于它的索引值。

然后，遍歷該數(shù)組 0~K-1 的位置，將遍歷的第 i 個位置的值與隨機的 第 K~N-1 的數(shù)字進行交換。

代碼如下：

#include #include #include #define N 100 #define K 80 void swap(int *i, int *j); int randint(int m, int n); int main(void) { srand((unsigned)time(NULL)); int x[N]; int i; for(i = 0; i < N; i++) { x[i] = i; } for(i = 0; i < K; i++) { swap(&x[i], &x[randint(i+1,N-1)]); } for(i = 0; i < K; i++) { printf("%d ", x[i]); } } int randint(int m, int n) { return (rand()%(n-m+1) + m); } void swap(int *i, int *j) { *j = *j ^ *i; *i = *i ^ *j; *j = *j ^ *i; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

0x04：我們可以使用2趟排序，第一次排序前一半，然后把前一半的位圖結(jié)果存到硬盤，然后再處理后一半。這種方法需要讀兩遍文件。

0x05：我們可以在位圖中使用4位來表示該數(shù)字出現(xiàn)的次數(shù)，例：0000表示沒有出現(xiàn)，1010表示出現(xiàn)10次。

0x06：我們可以對位向量已經(jīng)使用的位進行標(biāo)注，只有將要使用的位才進行初始化。

我們借助兩個 n 元向量和一個變量 top（初始為0） 來標(biāo)識初始化向量，下面的代碼實現(xiàn)了對數(shù)組元素 i 的首次訪問：

from[i] = top; to[top] = i; data[i] = 1; top++;

1

2

3

4

from[i] = top;表示將 i 在 to 中的索引值存放到 from 的第 i 位中

to[top] = i;表示 to 的第 top 位存放的是 i 的值，即 data 中的第 i 位被標(biāo)注

判斷第 i 位是否被初始化的方法：

(from[i] < top) && (to[from[i]] == i)

1

單憑第一個條件并不能確定第 i 位已被初始化因為 from 中的第 i 位有可能沒被初始化，是一個隨機的值。如果 to 中的第 from[i] 位等于 i 就能夠說明 data[i] 已經(jīng)被初始化。

0x07：使用電話號碼的后兩位來組織一個散列表，因為電話號碼的后兩位隨機性比較強適合作為散列函數(shù)。

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

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。