コラム２ 「ああ（そうか）！」アルゴリズム 【珠玉のプログラミング】

問題への回答。

1

単語と辞書だけが与えられた場合：

与えられた単語を正規化。

辞書をシーケンシャルに読み、読みだした単語の正規化結果と 与えられた単語の正規化結果を比較、 一致していたら、読みだした単語を記録。

辞書の最後に到達すれば、全てのアナグラムが見つかったことになる。

辞書を操作する時間とメモリがある場合：

辞書の各単語を正規化。

正規化結果をキー、正規化前の単語をバリューとした連想配列を作っておく。

単語が与えられたらそれを正規化したものを使い要素を検索をする。

2

問題Aの解法と同様に2分探索する。

ただし、要素が欠けている方ではなく、多い方を探索していく。

3

外側のループの終了条件がわからず答えをみた。

question3.cppで実装。

4

とばした

5

a bcにわけて配列の回転を行う。

bcaになる。

bc aに分け、bcの部分に対して配列の回転を行う。

cbaになる。

6

「誤った一致」をどのように整理しておくとよいか：

分からん

同じ数字になる可能なすべての名前のセットを返す関数をどう書くか：

予め数字をキー、名前を値にした連想配列を作っておき、 ある名前の数字が与えられたらそれを引数にとって 連想配列から要素を検索した結果を返す。

7

わからん

8

わからん

9

これはソートの種類によって変わらない？問題の解釈の仕方が違う？

10

電球いっぱいに水を入れて、その水の体積を秤で測る。

感想

あんまり"AHA!"という感覚は得られなかったが、問題の解法にすぐとびつくのではなく、一呼吸おいて考えてみることは大事だと思う。

ソースコード

// question3.cpp

#include <iostream>
#include <numeric>
#include <vector>

void rotate(std::vector<int>& v, const int i) {
  const int n = v.size();

  for(int cnt = 0; cnt < std::gcd(i, n); cnt++) {
    int t = v[cnt];
    int dst = cnt;

    while(1) {
      int src = dst + i; 
      if (src >= n) src = src % n;
      if (src == cnt) break;
      v[dst] = v[src];
      dst = src;
    }

    v[dst] = t;
  }
}

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

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

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

  if(n < i) {
    std::cout << "error: n < i" << std::endl;
    return 0;
  }

  std::vector<int> v(n);

  std::iota(v.begin(), v.end(), 0);

  rotate(v, i);

  return 0;
}

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

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

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

問題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;
}

近況

久しぶりにブログ更新する。近況についていくつかのトピックにわけて書く。

ポッドキャスト

ぼくは通勤時間によくポッドキャストを聴いてる。 この頃フォローしてる番組の更新が軒並み停滞気味で、聞くエピソードがなくなって困っていた。 そんな折に、はてブでちょうどこんな記事を見つけたので、いくつかの番組をフォローしてみた。

よく聴いてるポッドキャスト

ここ数日は、記事中で紹介されていた番組のひとつ、『ゆるふわポッドキャスト』を聴いてる。 北海道の高専卒、現在ソフトウェアエンジニアとして働く若い３人組が雑談をする番組。

ゆるふわPodcast 〜北海道出身の若手エンジニアによるPodcast〜

年齢の近い人たちがわいわい話してるのを聴くのは心地いい。 3人ともお互いをリスペクトしてるのが会話から伝わってきてとてもよき。 自分も誰か誘ってポッドキャスト始めてみたくなった。

C++講座

昨日今日と、通勤電車でuchan氏のC++講座を視聴した。 ソフトウェアエンジニアのuchan氏による、ライブ動画で若者にC++を教えるという取り組み。 ツイッターで知って、すぐにDiscordに参加した。（え？もう若者じゃないって？）

わりと大きな反響をいただけたので，さっそく6/29（月）21:00から始めてみようと思います。初回は環境構築の話からかな？興味ある方はこちらのDiscord招待リンクからどうぞ https://t.co/juPjhbWCm9 https://t.co/mMTryKm854

— uchan (@uchan_nos) 2020年6月28日

youtu.be

ライブプログラミング見てるの楽しいし、どんなことを考えながら手を動かしてるのかが垣間見えて参考になる。 この方、めちゃくちゃ強い人のはずなんだけど、不慣れなライブラリに四苦八苦していたりして、なんかちょっと安心する。 でもドキュメントから必要な情報を拾ってくるのめちゃくちゃ速くて、やっぱり強いなと思う。

あと、問題にぶつかったときのトライアンドエラーの手数が自分と比べてすごく多い。 元々持ってる知識や経験値の違いはあるだろうけど、「完全に理解しきる前に手を動かせるかどうか」という違いがあると感じた。次なにか問題にぶつかったら真似てみようかな。

珠玉のプログラミング

昨日から「珠玉のプログラミング」を読み始めた。

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

これは、僕が密かに尊敬しているエンジニアのhigepon氏がおすすめしていた本なんだけど、ずっと昔に買ったまま積んじゃってた。

「これを読まねばプログラマーではない」Twitterエンジニア蓑輪氏おすすめの名著2冊と、技術書の読み方 - ログミーTech

読者にしっかり考えさせる本のようなので、通勤電車で読むのではなく、自宅で腰を据えて取り組もうと思う。

TODOアプリ

会社のTODO管理に使うツールについて。 職場のセキュリティが厳しくて、使えるTODOアプリの選択肢があまりない。結局これまで普通のテキストファイルにマークダウンで書き込んでいたんだけど、Microsoft TODOを使えることに気がついたので、ちょっと使ってみようと思う。

その他

東京のコロナ感染者、また100人超えたらしいね。気をつけないとね(小並感)

Jetson nanoいじり

しばらくJetson nanoを使ってWebからカメラとモーターを制御する仕組みを作っていきたいと思う。

外部ディスプレイが届いたのでJetson nanoとHDMIで接続した。

最初、起動しても映像が出力されなかった。→ Jetcardじゃなくて普通の(?)イメージに書き換えたらいけた。

ここを参考にしながらMIPIカメラを接続。 しかし認識されない。→リブートしたら認識された。

以下のコマンドでカメラの映像を表示できるらしい。また、jキーで静止画を保存できるようだ。

$ nvgstcapture

実行。160度の広角レンズなので魚眼レンズのような歪みがある。画がかなりノイズっぽいのはどうしてだろう。

とりあえずこれでカメラ接続は一旦おっけー。

次はモーターを制御したい。

使用するモーターはSG90。 このモーターを制御するには、5Vの電源電圧、GDD、5Vの制御信号(PWM)が必要。 Jetson nanoのピンアサインを確認する。Jetson nanoのデータシートはこれ。

5Vピンが2つ、3.3Vピンが2つ、GNDピンが8つ。デフォルトでは、3ピンと5ピン、27ピンと28ピンはそれぞれI2CのSDAとSCL、8ピンと10ピンはUARTのTXとRX、それ以外はGPIOピン。ピン番号は基板に書いてある。
GPIOが3.3Vレベルだった。GPIO使ってソフトウェアPWMで動かせばいいやってなんとなく考えていたけどだめっぽい。モータードライバ買わないとかー。

サイクリングとチャーシューの日曜日

ただの日記。

昼間は近所の大きな公園までサイクリングをしてきた。

緊急事態宣言後、初めての日曜日。意外と人は多かった。密集するほどではないけど。
とくに子供連れが多かった印象。部屋に籠りきりじゃあ子供もストレスたまっちゃうもんなあ。
屋外だし、広いから他の人と充分に距離を保てるし、気晴らしをするにはすごくいい場所だと思った。

夜は自宅でチャーシューを作った。最近の週末はもっぱら自宅で料理にいそしんでる。

参考にしたレシピはこれ。 www.mamatenna.jp

チャーシューを自作したのは初めてだったけど、とんでもなく美味しく出来上がってびびった。
しっとりしつつホロホロっと崩れるような柔らかさで脂がしつこくない。その辺のラーメン屋で出てくるやつより美味かった。自炊のポテンシャルやばい。

200gのブロック肉があっという間になくなってしまったので、今度は1kgぐらい作りたい。

ROS勉強日記：通信方式とrvizとrqt

• ROSの用語集に目を通したけどさっぱり頭に入らなかった
  →必要になったときに照らし合わせながら覚えよう

• ノード間の通信方式をざっくり学んだ

  • トピック通信：非同期的、永続的、単方向 ... センサデータ向き
  • サービス通信：同期的、一回限り、双方向 ... ロボットの状態確認など、すぐに返事が欲しいとき向き
  • アクション通信：非同期、中断するか最終結果が返るまで（複数回）、双方向 ... 応答に遅延がある場合や処理の中間結果が欲しいとき向き

→具体的な部分はあとで実際に使って覚えよう

• ROSコマンド集に目を通した
  →頭に入らなかったので具体的な部分はry

• ３次元可視化ツールのrvizを軽く触った
  →これROS使ってるロボットの動画でよく見るやつや
  

• GUIツールのrqtも軽く触った
  

• どちらのツールも多機能で使いこなせたらめっちゃ強力そうだった

Dockerでめっちゃ簡単にGUI付きROS環境を作れるやつ

こちらの方法を試した。

https://qiita.com/karaage0703/items/957bdc7b4dabfc6639da

ROSノード立てるたびにいちいちdocker execしなくていい分、こっちの方が楽なので、ROS学習はこれでやっていこう。

あとは本でROSの概念的な部分を学習中。ちょっと時間かかりそう。