(learn&think)

不浮躁，不自傲，学习，思考，总结

Programming Pearls: Column1

| Comments

1 Book notes

1.1 The Bitmap Data Structure

这个数据结构用来表明在有限域中的一个密集集合，当集合中每个元素最多出现一次且没有其他数据与这些元素相关。即使这些情况得不到满足（比如，当有多个相同元素或其他附加数据），一个来自有限域的键能被在一个复杂数据表中用来做索引。 

#include <cstdio>
#define BITSPERINTEGER 32
#define SHIFT 5
#define MASK 0x1F
#define MAX_BITS 10000000

int array[1 + MAX_BITS / BITSPERINTEGER];

void set_bit(int i) {
  array[i >> SHIFT] |= (1 << (i & MASK));
}

void clr_bit(int i) {
  array[i >> SHIFT] &= ~(1 << (i & MASK));
}

int test_bit(int i) {
  return array[i >> SHIFT] & (1 << (i & MASK));
}

int main(int argc, char *argv[]) {
  int i;
  for (i = 0; i < MAX_BITS; ++i) {
    clr_bit(i);
  }
  while (scanf("%d", &i) != EOF) {
    set_bit(i);
  }
  for (i = 0; i < MAX_BITS; ++i) {
    if (test_bit(i)) {
      printf("%d\n", i);
    }
  }
  return 0;
}

2 Problems

2.1 1

如果内存足够大，如何用库实现排序算法。 

#include <cstdlib>
#include <cstdio>

int comp(const void *a, const void *b) {
  return (*reinterpret_cast<const int *>(a) -
          *reinterpret_cast<const int *>(b));
}

int main(int argc, char *argv[]) {
  int n = 0;
  int array[10000];
  while (scanf("%d", &array[n]) != EOF) {
    ++n;
  }
  qsort(array, n, sizeof(int), comp);
  for (int i = 0; i < n; ++i) {
      printf("%d\n", array[i]);
  }
  return 0;
}

2.2 2

如何使用 bit 操作来实现 bit 数组？ 

#define BITSPERINTEGER 32
#define SHIFT 5
#define MASK 0x1F
#define MAX_BITS 10000000

int array[1 + MAX_BITS / BITSPERINTEGER];

void set_bit(int i) {
  array[i >> SHIFT] |= (1 << (i & MASK));
}

void clr_bit(int i) {
  array[i >> SHIFT] &= ~(1 << (i & MASK));
}

int test_bit(int i) {
  return array[i >> SHIFT] & (1 << (i & MASK));
}

2.3 4

如何在 0 到 n-1 间随机生成 k 个唯一的随机整数？ 

#include <cstdlib>
#include <utility>
#include <ctime>

unsigned int seed = time(NULL);
int randint(int m, int n) {
  return m + rand_r(&seed) / (RAND_MAX / (n + 1 - m) + 1);
}

void generate_unique_random(const int n, const int k, int *out) {
  int num[n];
  int i;
  for(i = 0; i < n; ++i) {
    num[i] = i;
  }
  for(i = 0; i < k; ++i) {
    int p = randint(i, n - 1);
    std::swap(num[i], num[p]);
    out[i] = num[i];
  }
}

类似于洗牌问题或不知道 n 时，选取随机数： Fisher–Yates shuffle

2.4 5

使用两次传递算法，第一次排序 0-4,999,999，第二次排序 5,000,000-9,999,999.

2.5 6

每个整数最多出现 10 次，用 4bit 就可以表示，多需要空间 n×4bit 就来存储每个数的个数就可以。

2.6 9

One problem with trading more space to use less time is that initializing the space can itself take a great deal of time. Show how to circumvent this problem by designing a technique to initialize an entry of a vector to zero the first time it is accessed. Your scheme should use constant time for initialization and for each vector access, and use extra space proportional to the size of the vector.

data[0…n-1]是这个未初始化的数组，每个元素都是个随机数，额外添加两个数组 from[0..n-1]和 to[0…n]，和一个 top 变量。如果元素 data[i] 已经被访问过，那么 from[i] < top 且 to[from[i]] = i 。访问过的如下图：

代码如下： 

if (from[i] < top && to[from[i]] = i) {
  //has been accessed
} else {
  from[i] = top;
  to[top] = i;
  data[i] = 0;
  top++;
}

2.7 10

open hashing with collision resolution by sequential search.

2.8 11

扫描图纸，通过信鸽载送 35nm 的影片到测试站，在那里图纸得到重新放大和打印。

2.9 12

用铅笔。

Comments