(learn&think)

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

Programming Pearls: Column11-12

| Comments

Book notes

QuickSort

void swap(int *array, int m, int n) {
  int temp;
  temp = array[m];
  array[m] = array[n];
  array[n] = temp;
}

int randint(int m, int n) {
  return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

void isort(int *array, int n) {
  int i, j, t;
  for (i = 1; i < n; ++i) {
    t = array[i];
    for (j = i; j >= 0  && array[j - 1] < t; --j) {
      array[j] = array[j - 1];
    }
    array[j - 1] = t;
  }
}

void qsort1(int *array, int l, int u) {
  /*use array[l] for the mid element */
  if (l >= u) {
    return;
  }
  int m;
  m = l;
  for (int i = l + 1; i <= u; ++i) {
    if (array[i] < array[l]) {
      swap(array, ++m, i);
    }
  }
  swap(array, l, m);
  qsort1(array, l, m - 1);
  qsort1(array, m + 1, u);
}

void qsort2(int *array, int l, int u) {
  /*use array[l] for the mid element, from back to start,
    always swap the first element */
  if (l >= u) {
    return;
  }
  int i, m;
  i = m = u + 1;
  do {
    do {
      --i;
    } while (array[i] < array[l]);
    swap(array, --m, i);
  } while (i > l);
  qsort2(array, l, m - 1);
  qsort2(array, m + 1, u);
}

void qsort3(int *array, int l, int u) {
  /* two-way partition, use array[l] for the mid element */
  if (l >= u) {
    return;
  }
  int t, i , j;
  t = array[l];
  i = l;
  j = u + 1;
  for (;;) {
    do {
      ++i;
    } while (i <= u && array[i] < t);
    do {
      --j;
    } while (array[j] > t);
    if (i > j) {
      break;
    }
    swap(array, i, j);
  }
  swap(array, l, j);
  qsort3(array, l, j - 1);
  qsort3(array, j + 1, u);
}

const int kCutOff = 50;
void qsort4(int *array, int l, int u) {
  /* qsort3 + randomization + isort small subarrays + swap inline */
  if (u - l < kCutOff) {
    return;
  }
  int t, i , j;
  swap(array, l, randint(l, u));
  t = array[l];
  i = l;
  j = u + 1;
  for (;;) {
    do {
      ++i;
    } while (i <= u && array[i] < t);
    do {
      --j;
    } while (array[j] > t);
    if (i > j) {
      break;
    }
    swap(array, i, j);
  }
  swap(array, l, j);
  qsort3(array, l, j - 1);
  qsort3(array, j + 1, u);
}

生成随机数

从 n 中生成不重复的 m 个随机数。

1

void GenerateSortedRand(int m, int n) {
  int select = m;
  int remaining = n;
  for (int i = 0; i < n && select > 0; ++i) {
    if (rand() % remaining < select) {
      cout << i << " ";
      --select;
    }
    --remaining;
  }
  cout << endl;
}

2

void GenKnuth(int m, int n) {
  for (int i = 0; i < n && m > 0; ++i) {
    if (rand() % (n - i) < m) {
      cout << i << " ";
      --m;
    }
  }
  cout << endl;
}

3

void GenSets(int m, int n) {
  set<int> num_set;
  while (num_set.size() < m) {
    num_set.insert(rand() % n);
  }
  for (set<int>::iterator it = num_set.begin(); it != num_set.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

4

int randint(int m, int n) {
  return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

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

void GenShuf(int m, int n) {
  int *x = new int[n];
  int i = 0;
  for (i = 0; i < n; ++i) {
    x[i] = i;
  }
  for (i = 0; i < m; ++i) {
    int j = randint(i, n - 1);
    int t = x[j];
    x[j] = x[i];
    x[i] = t;
  }
  qsort(x, m, sizeof(int), compare);
  for (i = 0; i < m; ++i) {
    cout << x[i] << " ";
  }
  cout << endl;
  delete x;
}

原则

  • 理解问题。与用户讨论提出问题的有关场景。问题的陈述中往往包含问题的想法，和所有早期的想法一样，它们应该被考虑而不是与其他排斥。
  • 指出一个抽象问题。一个清晰，整洁的问题陈述不旦帮助我们解决这个问题，并且能体现如何把这个解答应用到其他的问题上。
  • 探索设计空间。不要急于立刻去解决问题，思考一分钟，花一天时间编程。应该思考一小时，编程一小时。使用通俗的上层语言帮助我们描述设计：伪代码描述控制六，抽象化表示关键数据结构的数据类型。
  • 实现一种解答。我们应该追求以直接清晰的代码来实现选择的设计，使用最强大的能用的操作。
  • 回顾。Polya 的How to Solve It能帮助任何程序员成为更好的问题解决者。在 15 页他说：”基本存在一些东西去做，随着足够的学习和突破，我们能改善每个解答，并且在任何情况下，我们都能经常改善我们对解答的理解。“

Problems

Column11-9

在数组 n 中以算法复杂度 O(n)找出第 k 个小的元素。 

void swap(int *array, int m, int n) {
  int temp;
  temp = array[m];
  array[m] = array[n];
  array[n] = temp;
}

int randint(int m, int n) {
  return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

void SelectK(int *array, int l, int u, int k) {
  if (l >= u) {
    return;
  }
  int t, i, j;
  swap(array, l, randint(l, u));
  t = array[l];
  i = l;
  j = u + 1;
  for (;;) {
    do {
      ++i;
    } while (i <= u && array[i] < t);
    do {
      --j;
    } while (array[j] > t);
    if (i > j) {
      break;
    }
    swap(array, i, j);
  }
  swap(array, l, j);
  if (j < k) {
    SelectK(array, j + 1, u, k);
  }
  else if (j > k) {
    SelectK(array, l, j - 1, k);
  }
}

1

int randint(int m, int n) {
  return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

int bigrand() {
  return RAND_MAX * rand() + rand();
}

2

int randint(int m, int n) {
  return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

void GenerateM(int m, int n) {
  int i, t;
  i = randint(0, n - 1);
  for(int j = 0; j < m; ++j) {
    t = i + j;
    if (t >= n) {
      t -= n;
    }
    cout << t << " " << endl;
  }
  cout << endl;
}

8

0..n-1 中生成 m 个随机数。 

int randint(int m, int n) {
  return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

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

void GenShuf(int m, int n) {
  int *x = new int[n];
  int i = 0;
  for (i = 0; i < n; ++i) {
    x[i] = i;
  }
  for (i = 0; i < m; ++i) {
    int j = randint(i, n - 1);
    int t = x[j];
    x[j] = x[i];
    x[i] = t;
  }

  for (i = 0; i < m; ++i) {
    cout << x[i] << " ";
  }
  cout << endl;
  delete x;
}

如果允许有重复的数，如何生成排序的 m 个随机数。 

void GenSets(int m, int n) {
  multiset<int> num_set;
  while (num_set.size() < m) {
    num_set.insert(rand() % n);
  }
  for (multiset<int>::iterator it = num_set.begin(); it != num_set.end();
       ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

如果可以重复并顺序随机。 

void GenM(int m, int n) {
  for (int i = 0; i < m; ++i) {
    cout << randint(0, n - 1) << " ";
  }
  cout << endl;
}

9

int randint(int m, int n) {
  return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

void GenSets(int m, int n) {
  set<int> num_set;
  int t;
  for (int i = n - m ; i < n; ++i) {
    t = randint(0, i);
    if (num_set.find(t) == num_set.end()) {
      num_set.insert(t);
    } else {
      num_set.insert(i);
    }
  }
  for (set<int>::iterator it = num_set.begin(); it != num_set.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

10

int randint(int m, int n) {
  return m + (rand() / (RAND_MAX / (n - m + 1) + 1));
}

int Select() {
  int res;
  int i = 0;
  res = object[i];
  ++i;
  while (IsEnd(object[i])) {
      int j = randint(0, i);
      if (j < 1) {
        res = object[i];
      }
      ++i;
  }
  return res;
}

More: 选 k 个

12

生成 N>1e6 组的 m 个随机数，计算生成每个随机数出现的概率，是不是符合预期，还是偏差很大而不是随机的。

Comments