首页 > 安全资讯 >

【编程珠玑】第一章:开篇

12-05-14

一,题目: 如何在1MB的空间里面对一千万个整数进行排序?并且每个数都小于1千万。实际上这个需要1.25MB的内存空间。 1MB总共有838,8608。所以估计也可以在1MB左右的空间里面进行排序了。二,分析: 1)基于...

一,题目:
       如何在1MB的空间里面对一千万个整数进行排序?并且每个数都小于1千万。实际上这个需要1.25MB的内存空间。
       1MB总共有838,8608。所以估计也可以在1MB左右的空间里面进行排序了。
二,分析:
        1)基于磁盘的归并排序(耗时间)
        2)每个号码采用32位整数存储的话,1MB大约可以存储250 000 个号码,需要读取文件40趟才能把全部整数排序。(耗时间)
        3)位图法,采用一个1千万位的字符串表示每个数,比如{0,2,3}表示为   1  0 1 1 0 0 0 0 。遍历每一个整数,有则标记为1,否则标记为0。然后按顺序输出每个整数。这种方法实际需要1.25MB内存,如果可以方便弄到内存的话可以采用此种方法。
        4)假如严格限制为1MB,可以采用的策略:两次遍历或者除去第一位为0的整数。
三,源码:
[html]
#include <stdio.h> 
#include <stdlib.h> 
 
#define SHIFT 5 
#define MASK 0x1F 
#define N 10000000 
int a[1 + N/32]; 
void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); } 
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); } 
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); } 
int main() 
{       int i = 0; 
        //int  top = 1 + N/BITSPERWORD; 
        //memset(a, 0, sizeof(a)*sizeof(int)); 
        while (scanf("%d", &i))  
            set(i); 
        for (i = 0; i < N; i++) 
                if (test(i))  
           printf("%d\n", i); 
        return 0; 


四,课后的题目:
1、使用库函数来进行排序
[cpp]
#include <stdio.h> 
#include <stdlib.h> 
#define ms 1025 
int a[ms]; 
int cmp(const void *a, const void *b) 

    return (*(int*)a) - (*(int*)b); 

int main(void) 

    int n, i; 
    while (scanf("%d", &n) != EOF) 
    { 
        for (i = 0; i < n; ++i) scanf("%d", &a[i]);                       
        qsort(a, n, sizeof(int), cmp); 
        for (i = 0; i < n - 1; ++i) printf("%d ", a[i]); 
        printf("%d\n", a[i]); 
    } 
    return 0; 

使用set容器
[html]
#include <iostream> 
#include <set> 
using namespace std; 
int main() 

    set<int> S;  //STL容器内部采用红黑树作为排序数据结构 
    int i; 
    set<int>::iterator j; 
    while(cin>>i) 
        S.insert(i); 
    for(j=S.begin();j!=S.end();++j) 
        cout<<*j<<endl; 
    return 0; 


2、使用位运算
[cpp]
void set(int i) {  a[i>>SHIFT] |=  (1<<(i & MASK)); } 
void clr(int i)  {  a[i>>SHIFT] &= ~(1<<(i & MASK)); } 
int  test(int i) {   return a[i>>SHIFT] &   (1<<(i & MASK)); } 
3、比较位图排序与系统排序
       位图排序是最快的,针对这个问题而言,qsort比stl sort速度快。
4、随机生成[0, n)之间不重复的随机数(关键思想为:先把所有可能数顺序放到数组,然后打乱顺序,则保证不重复)
[cpp]
for (i = 0; i < n; ++i)  
    a[i] = i; 
for (i = 0; i < n; ++i) 

    pos = rand()%(n - i) + i; 
    t = a[i]; a[i] = a[pos]; a[pos] = t; 

5、如果1MB是严格控制的空间,如果数据有1.25MB的bit数目。那么应该是需要读取2次。
        k = 需要跑几趟直接用需要排序的数据量/内存空间bit数,往上取整则可。
        时间开销 = kn
        空间开销 n/k
        注意的是,每次在扫描的时候,取数据的范围是不一样的。
6、如果每个数据出现最多10次,那么需要4个bit位来刻录一个数。这时存储空间减小至原来的1/4。
       那么如果一定要按照bitmap的方式来进行处理,则需要利用5题中的结论。
7、问题:[R. Weil]本书1.4 节中描述的程序存在一些缺陷。首先是假定在输入中没有出现两次的整数。如果某个数出现超过一次的话,会发生什么?在这种情况下,如何         修改程序来调用错误处理函数?当输入整数小于零或大于等于n时,又会发生什么?如果某个输入不是数值又如何?在这些情况下,程序该如何处理?程序还应该包含 哪些明智的检查?描述一些用以测试程序的小型数据集合,并说明如何正确处理上述以及其他的不良情况。
      如果某个数出现超过一次的话,会发生什么?
      会被忽略掉, 因为原来的程序本身就是用来处理只出现一次的情况的。
        在这种情况下,如何修改程序来调用错误处理函数?
[html]
while (scanf("%d", &i) != EOF) 
    if(test(i)) call_error_fun(); 
    else set(i); 
  当输入整数小于零或大于等于n时,又会发生什么?
      会出现访问越界的情况。-1访问时,会访问a[-1]的31个bit位。
如果某个输入不是数值又如何?在这些情况下,程序该如何处理?
    输入可能是浮点数,或是字符什么的~~
   可以先读入字符串,再用atoi转换成为整形数,如果失败,则进行出错处理。
    程序还应该包含哪些明智的检查?
8、免费电话号码至少有800,878,888等,那么如何查看一个号码是否是免费号码。?
第一种方案:如果是一千万个电话号码都有可能成为免费号码,那么至需要1.25MB * (免费号码前缀个数)。
第二种方案:省空间,多次扫描文件:
                  1、首先扫描整个文件,看有哪个免费号码前缀。以及每个免费号码前缀下的号码个数。
                  2、设置区间映射表:比如800前缀有125个免费号码,找到最大的数,与最小的数,差值做为bit长度。
第三种方案:建立索引的方式来进行处理。以最后7位为索引,后面800,878什么的,为值。如果不是免费号码,应该是不用加入到这个hash表中。

9、避免初始化问题 www.2cto.com
做法是:使用两个等长的辅助数组,比如要把a[n]初始化,那么在第一次访问时:
     b[i] = top;
    c[b[i]] = i;
    ++top;

给出示例代码
[html]
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
 
#define ms 100 
int a[ms]; 
int b[ms]; 
int c[ms]; 
int top; 
 
//判断是否被初始化过。 
bool is_init(int i) 

    return (b[i] < top && c[b[i]] == i); 

int main(void) 

    top = 0; 
//这里生成一些随机数值。 
        for (int i = 0; i < ms; ++i) 
        a[i] = b[i] = c[i] = i; 
    for (int i = 0; i < ms; ++i) 
    { 
        if (is_init(i)) 
        { 
            printf("error"); 
        } 
        int v = i + rand()%(ms - i + 1); 
        int t = a[i]; a[i] = a[v]; a[v] = t; 
 
        v = i + rand()%(ms - i + 1); 
        t = b[i]; b[i] = b[v]; b[v] = t; 
 
        v = i + rand()%(ms - i + 1); 
        t = c[i]; c[i] = c[v] ; c[v] = t; 
    } 
 
    for (int i = 0; i < ms; ++i) 
    { 
        if (is_init(i) == false) 
        { 
            a[i] = i; 
            b[i] = top; 
            c[top++] = i; 
        } 
    } 
 
    for (int i = 0; i < ms; ++i) 
    { 
        if (!is_init(i)) 
        { 
            printf("error: %d\n", i); 
        } 
    } 
    return 0; 

 


摘自 小田的专栏

相关文章
最新文章
热点推荐