【读薄《编程珠玑》】壹 开篇

这篇文章是《读薄<编程珠玑>》系列博客的第一篇，在这篇文章中，我总结了在书中出现的一些问题以及一些解决方案。

问题集合

• 0x01：一个最多包含n个正整数的文件，每个数都小于n，其中n=10⁷，并且没有重复。最多有1MB内存可用。要求用最快方式将它们排序并按升序输出

• 0x02：使用位逻辑运算来实现位向量

• 0x03：尽可能快的生成位于 0~n-1 之间的 k 个随机不同顺序的整数

• 0x04：如果在问题0x01中需要1.25MB 的内存空间来进行排序，而我们只有1MB 空间该如何处理？

• 0x05：如果在问题0x01中，每个数字出现的次数不是1次，而是不多于10次，该如何处理？

• 0x06：如果说我们的位向量非常的稀疏，可能10000位里只有100位得到了使用，这样的话大量的时间都会浪费在初始化空间上，该如何解决这个问题？

• 0x07：如何组织电话号码的存储，来能够支持高效的插入和检索操作？

方案集合

• 0x01：把文件一次读入，出现的数字在位向量对应索引处中标注为1，读取完文件之后，将位向量从低位向高位依次将为1的索引输出即可。(具体实现详见：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
 

(详细分析请见：位向量的实现与应用)

• 0x03：

首先，生成一个大小为 N 的数组，每个值都等于它的索引值。

然后，遍历该数组 0~K-1 的位置，将遍历的第 i 个位置的值与随机的 第 K~N-1 的数字进行交换。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#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趟排序，第一次排序前一半，然后把前一半的位图结果存到硬盘，然后再处理后一半。这种方法需要读两遍文件。

• 0x05：我们可以在位图中使用4位来表示该数字出现的次数，例：0000表示没有出现，1010表示出现10次。

• 0x06：我们可以对位向量已经使用的位进行标注，只有将要使用的位才进行初始化。

我们借助两个 n 元向量和一个变量 top（初始为0） 来标识初始化向量，下面的代码实现了对数组元素 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 位被标注

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

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

 

  
1
 

单凭第一个条件并不能确定第 i 位已被初始化因为 from 中的第 i 位有可能没被初始化，是一个随机的值。如果 to 中的第 from[i] 位等于 i 就能够说明 data[i] 已经被初始化。

• 0x07：使用电话号码的后两位来组织一个散列表，因为电话号码的后两位随机性比较强适合作为散列函数。

本文的版权归作者 罗远航 所有，采用 Attribution-NonCommercial 3.0 License。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！

文章来源: blog.csdn.net，作者：冰水比水冰，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/luoyhang003/article/details/51456499