コラム１真珠貝を開いて【珠玉のプログラミング】

珠玉のプログラミング本質を見抜いたアルゴリズムとデータ構造

作者:ジョン・ベントリー
発売日: 2014/02/28
メディア: 単行本（ソフトカバー）

問題1.6を解いてみた。自分の解答を載せる。

1

全ての番号を配列に格納してライブラリのソート関数でソートする。

2

理解力が及ばず問題の意味がわからなかった。

3

手元の環境だと、ビット列ソートの方が30倍くらい速かった。記事の最後にソース載せた。（question3.cpp）

4

乱数を使うんだろうな、ということは思いついたけど、具体的な実装は考えつかなかった。

ヒントにしたがってコラム12を読んで実装。記事の最後にソース載せた。（question4.cpp）

ほぼコピペ。実装して動作は理解できたけど、このアルゴリズムがどうして等確率で整数を選びとれるのかを理解できてない。

5

入力データを小さくする？ビット列以外のアプローチを考える？

ヒントを見たけど、実装が思いつかなかった。

答えを見たら、これ思いついたやつじゃんってなった。悔しい。

6

回数をカウンタで数える。

セットの各要素ごとに4bitのカウンタを用意して、データが重複するごとにカウンタをインクリメントする。

この場合メモリ量は4倍になる。

7

もし間違いで重複した整数が入力されたら？

→重複分はカウントされない

エラー関数を呼ぶには？

→毎回データが入っているかどうか確認する

0未満の整数やn以上の整数が入力された場合は？

→配列の範囲外アクセスが起きる

数値以外のデータが入力されたらどうなる？

→意図しないインデックスにアクセスする、又は範囲外アクセスが起きる

このような自体に備えるためにどうしたらいいか？

→入力は文字列として読み込み、atoiで数値にしたのち、範囲チェックを行う。配列に書き込む前に、そのインデックスに既にデータがあるか確認し、データがあればエラー関数を呼ぶ。

8

問5の2パスのアルゴリズムを使い、余ったメモリを地域コードを識別するために使う。地域コードの識別は12bitあればいいかな。

ある番号がすでに無料電話として登録されているかどうかを～という部分は問題の意図がわからなかった。

9

未解答

10

地域コード別に分けて新しい注文を末尾に追加していく。

11

インターネットが普及し始めたのは1990年前後のことなので、電子的に送るのは無理。

「別のデータの移送方法」なので、別の試験場を使う、とかは無理か。

陸路か空路か海路か。

陸路なら公共交通機関を使う？（あるのか？）

試験場側からも近づいてきてもらい、中間地点で受け渡すとか？（意味ない気がする）

答えを見た。思いつきはしたけど、それアリなのか〜となった。

12

「一方ソ連は鉛筆を使った」これは知ってた。

"真相を知りたい読者はwww.spacepen.comを見てください"とのこと。

コラム１の感想

具体的な課題に対するアルゴリズム検討を追体験できて楽しい。

問題については、文意をうまく汲み取れない部分がちらほらあった。読解力を高めたい。あと、全問真面目に解こうとすると思った以上に時間がかかるので、時間制限つきで考えるようにしよう。最初はRustも同時に勉強しながら使ってみようと思ってたんだけど、同時に２つのものをインプットするのは挫折しそうだったのでやめた。

コラム1ではないけど、ヒントのために読んだコラム12で印象に残った文章。このようなプログラマ然とした振る舞いを心がけようと思った。

プログラマの1つの仕事は目の前にある問題を解決することです。しかし、おそらくもっと重要な仕事は、次の仕事に備えることです。それはときに講習会に参加したり、Knuthの本(Seminumerical Algorithm等)などを読むことです。しかし、より頻繁に、プログラマは自分が解決した問題を別の方法で解決できなかったか自問してみるとよいでしょう。この精神的な訓練が、次の問題に備えることになるのです。

ソースコード

実行環境やコンパイラは以下のとおり。

$ system_profiler SPHardwareDataType
Hardware:

    Hardware Overview:

      Model Name: MacBook Pro
      Model Identifier: MacBookPro15,1
      Processor Name: 6-Core Intel Core i7
      Processor Speed: 2.2 GHz
      Number of Processors: 1
      Total Number of Cores: 6
      L2 Cache (per Core): 256 KB
      L3 Cache: 9 MB
      Hyper-Threading Technology: Enabled
      Memory: 16 GB

$ g++ --version
g++ (Homebrew GCC 9.2.0_1) 9.2.0

ソースコードは以下。エラー処理などはほぼなし。

// question3.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

constexpr int dataSize = 10000000;

std::vector<int> genData(const int num)
{
  std::vector<int> data(num);
  std::iota(data.begin(), data.end(), 0);
  std::random_device rng;
  std::mt19937 engine(rng());
  std::shuffle(data.begin(), data.end(), engine);

  return data;
}

int main()
{
  auto data = genData(dataSize);

  //普通のソート
  auto d1(data);
  std::sort(d1.begin(), d1.end());

  //ビット列ソート
  auto d2(data);
  std::vector<bool> binData(dataSize);
  for(auto d : d2)
  {
    binData[d] = 1;
  }
}

// question4.cpp

#include <iostream>
#include <random>

void genknuth(int m, int n) {
  std::mt19937_64 mt;
  std::random_device rnd;
  mt.seed(rnd());

  for (int i = 0; i < n; i++) {
    if ((mt() % (n - i)) < m) {
      std::cout << i << std::endl;
      m--;
    }
  }
}

int main(int argc, char** argv) {

  if(argc != 3) {
    std::cout << "wrong number of arguments" << std::endl;
    return 0;
  }

  int m = std::atoi(argv[1]);
  int n = std::atoi(argv[2]);

  if(m > n) {
    std::swap(m, n);
  }

  genknuth(m, n);

  return 0;
}

ささきのブログ

日記、技術メモ、勉強記録など。

コラム１真珠貝を開いて【珠玉のプログラミング】

1

2

3

4

5

6

7

8

9

10

11

12

コラム１の感想

ソースコード