神刀安全网

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

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

问题集合

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

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

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

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

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

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

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

方案集合

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

  • 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;
}

  • 0x04:我们可以使用2趟排序,第一次排序前一半,然后把前一半的位图结果存到硬盘,然后再处理后一半。这种方法需要读两遍文件。

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

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

我们借助两个 n 元向量和一个变量 top(初始为0) 来标识初始化向量,下面的代码实现了对数组元素 i 的首次访问:

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

from[i] = top; 表示将 i 在 to 中的索引值存放到 from 的第 i 位中
to[top] = i; 表示 to 的第 top 位存放的是 i 的值,即 data 中的第 i 位被标注

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

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

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

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

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

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 【读薄《编程珠玑》】壹 开篇

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址