Perlで色々なアルゴリズムを実装してみた その2
アルゴリズムの実装力を養成するため、Perlで書いてみましたの続編です。
こちらの本の第8章から
図解入門よくわかるアルゴリズムの基本と仕組み (How‐nual Visual Guide Book)
- 作者: 杉浦賢
- 出版社/メーカー: 秀和システム
- 発売日: 2002/02/26
- メディア: 単行本
- 購入: 1人 クリック: 36回
- この商品を含むブログ (6件) を見る
再帰(第8章)
再帰アルゴリズムとは、その関数が目的を達成するまで、自分自身を何度も呼び出す構造となっている面白い構造です。
自分自身を深く深く掘り下げて、到達点に達した途端にすべてが解決するという、ピタゴラスイッチ的な面白い仕組みでとても好きなアルゴリズムです。
が、この「どう自分自身を掘り下げる（関数を呼び出す）か」「解決の到達点は何なのか」の勘所がなかなか難しいアルゴリズムでもあります。
最大公約数を求めるコード
2つの数の最大公約数を求める方法にユークリッドの互除法という方法があるそうです。2つの数を互いに割り算していくと答えが出る方法です。
その方法の理解はまだ出来ていませんが、とりあえずその仕組みを再帰で実装してみました。
「何度も割り算をしていく」が自分自身を掘り下げる関数に、「余りが0になった時」が解決の到達点っぽいですね。
階乗を求める
1からある数まで、1ずつ増やした数を掛け算した答えをだす（1 * 2 * 3 * ... * n）問題です。
掛けていく数を１ずつ増やすより、逆にnから1ずつ減らしていって最後に1になった時を解決の到達点と考えるのがポイントです。
クイックソート
クイックソートは並べ替えのアルゴリズムの1つです。並べ替える元データから任意の1つの値を取り出し、その値より大きいグループと小さいグループの2つのグループに分け、出来たグループでまた同じ動作をしていきます。各グループの要素数はだんだん少なくなっていき、グループ分けが出来なくなるまで少なくなればそこが到達点
と考えます。
まずは自分なりに考えてたコードです。問題点は、グループ分けした要素（配列）を量産しているので、実行時のメモリを沢山使っているところです。
クイックソートその2
本の実装例では、その1の問題点を見事に解決（新しい配列を量産するのではなく、元の配列内の数値をうまいこと入れ替えることで実装）していたので、その考え方で実装してみました。
配列の値をコピーするのではなく、元の配列の値の場所を入れ替える・・・そう、リファレンスの出番ですね。
ニュートン法
微分を使って平方根の値（近似値）を求める方法です。
ニュートン法自体の理解は数学的素養が必要なので、最近通っている高校数学勉強会での知識で、なんとなく分かった様な気がしている状態ですが、理屈の実装自体は難しくありません。
台形法
ある関数（数学の）で書かれたグラフの面積を、定積分を使って求める方法です。
ニュートン法と同様、数学的素養が必要ですが、理屈の実装自体は難しくありません。
ダイクストラ法
経路探索のアルゴリズム、駅すぱあとみたいなやつですね。
自力ではさっぱり分からなかったので解説を読んで実装しました。すべての点の最短経路を求めるていき、その点がゴールなら解決するというアルゴリズムです。
色々な基本アルゴリズムを実装してみましたが、このあたり全てがヒントなしでスラスラ書けるようになれたらなぁと思います。
まだ難しいアルゴリズムはすぐに忘れてしまいそうになるので、精進あるのみです。
Perlで色々なアルゴリズムを実装してみた
ちょいちょい参加している AtCoder で、二分探索のアルゴリズムを時間内に実装する自身がなかったので、基本的なアルゴリズムを手を動かした実装してみました。
まぁ、ソートやサーチなんかは、大体の言語でメソッドや組み込み関数が定義されているので実務で使うことは無いと思いますが、実際にどういう動きをするかを頭で考えてコードで表現する訓練は大事だなぁと思って色々書いてみました。
アルゴリズムについては色々書籍が販売されていますが、手頃な感じの本を入手して最初の問題からコードを書いてみました。普遍的な知識ですね。
図解入門よくわかるアルゴリズムの基本と仕組み (How‐nual Visual Guide Book)
- 作者: 杉浦賢
- 出版社/メーカー: 秀和システム
- 発売日: 2002/02/26
- メディア: 単行本
- 購入: 1人 クリック: 36回
- この商品を含むブログ (6件) を見る
それぞれのコードは、どんな動きをするのかの趣旨だけ読んで自分なりにコーディングしてみたので、コードにツッコミやアドバイス等々あればお手柔らかにお願いします(笑)。
まずは第7章までの基本編。
値の集合から、条件にあった値を取り出すコード(第4章)
合計
数を数える
平均
最大値
最小値
まぁ、この辺りは基本編ですね。プログラミングの初心者の方は、このあたりからコードを書いてちゃんと動くか試してみると良いと思います。Perl入学式の復習にもどうぞ。
順番をソートするアルゴリズムの実装(第6章)
選択ソート
挿入ソート
ちょっとアルゴリズムっぽくなってきました。シェルソートはグループ分けをどう実装するか、頭の中だけで考えるだけでは混乱したので、実際に動きをノートに書き出して実装しました。
頭で考えて書いたコードは思うような結果になりませんでしたが、ノートに書いて整理するとあっさりと書けました。いきなり書かずにまず整理。
どんな言語でも通用する基本って大事。
値の集合から特定の値を探索するアルゴリズムの実装(第7章)
線形探索
二分探索（当たり入り）
二分探索（当たりなし）
文字列の照合
アルゴリズムの実装、頭の体操的にも面白いですね。引き続き第8章以降もやっていきたいと思います。
吉祥寺.pm 17に参加しました
行ってきました、吉祥寺.pm 17。今回、２回目の参加です。
そして「YAPCに行けば人生は変わる」というタイトルでLTをしました。
関西在住なのでなかなか東京近郊の勉強会に行くことはできませんが、今回は参加できそうな機会あったので行けたらいいなと思い家族に相談。
二つ返事で行ってきたら？とOKをもらい、妻に感謝。しかし申し込もうとした時は既に参加枠はキャンセル待ちの状態。
なんとか確実に行ける方法はよく見ると、YAPC-LT枠が一つまだ空いているではありませんか！
妻に赤ちゃんの面倒をかける事になるし、LTするからには有益なLTをしたいけれど、果たして自分に話すネタはあるのか？直前に体調を崩したりしないだろうかetc...
行きたいという気持ちもありつつ、その気持ちの足を引っ張る考えが色々と頭をよぎりました。
しかし、少しでも行きたい気持ちがあるのなら、行動しよう！今までも行動して良かったことが山ほどあるやん！と思って、勢いでLT参加ボタンを押しました。
（まさか、こんなに沢山の参加者がいる前で喋ることになるとは！）
何かを変えるには、行動するしかない。"待ってるだけの昨日にアディオス！"。そんな気持ちを若い人達に伝えられたら、、、とLTのテーマを決めました。スライドはこちら。
終わってからの懇親会やTwitterで、LT良かったですよと声もかけてもらい、ああ勇気を出して参加してよかったなぁとホッとしております。
しかも、嬉しいことに近藤佑子🐱技術書典6 か66(@kondoyuko)さん | Twitterさんに、なんと自分のLTをグラレコしてもらいました！これはめっちゃ嬉しかった！
今回のトーク4本を聞いて色々と感じたことは、、、
1ob1の話
- 自分の仕事の業界は、完全ウォーターフォール型組織なので、育てていく意識をちゃんと持っていて凄いなと思いました。若手を育てない組織の将来性は真っ暗だよなぁと。
Bitcoinの話
- 自分も暗号通貨の技術面を知りたいと思って、書籍を買って読んだり、実装されたコードを写経してみたりして、なんとなく分かった感じだった事が、あらためて整理された話を聞けてとても面白かったです。もっと時間をかけてたっぷり聞きたかった！
- そういえば、今年のkof2018に楠さんの話も聞きに行きました。k-of.jp
非公開APIを探る話
- 自分で既存のサービスから情報が欲しい時、APIが公開されていないとスクレイピングしたり諦めるしかないのかなと思っていたので、chromeのツールを使って探るお話はとても勉強になりました。懇親会でも自分の疑問点に色々丁寧に教えてもらえました。へっくす？ (@codehex) | Twitterさん、ありがとうございました。
そして、Perl入学式を卒業する話
そしてLTも多様な話が聞けて楽しかったです。vimや26進数や愛の深いお話、Riot.jsは手軽そうで試してみたい。Perlにインターフェースを実装するPerlハッカー凄い！ラリーとは私も写真とってもらいました！書籍出版たいへん！
その他、久しぶりにお会いする方々との懇親会でのお話も楽しかった！
今回驚いたこと、感じたことメモ
- 自分が参加者最高齢だと思っていたけど違った。多分３番目？
- 69歳現役プログラマー凄い！あと20年以上戦える！
- よしたくさん、想像と違ってめっちゃ若かった
- グラフィックレコーディングはめっちゃ嬉しかった！
- 自分の様な非エンジニアのエンジョイ勢の受け入れてもらえる、多様性のある勉強会。
- 懇親会で初めてお話した方々、新しいつながりができて嬉しい！
- Papixさん、Perl入学式のめっちゃ良い話だった！感極まって泣いて胴上げの展開になったらどうしようかと心配したけど、それはならなくてよかった
- そーだいさんのLT、めっちゃ男前な方だなぁ
吉祥寺.pm、本編も懇親会も本当に楽しかったです。 magnoliak (@magnolia_k_) | Twitter さん、ありがとうございました。
そして憧れのおにやんまの讃岐うどんを食べて帰りました。美味しかった！
関西のPerlmongerの皆さんにも、東京まで行く価値が十二分にある素晴らしい.pmです！
そしてKansai.pmもよろしくお願い致します！
続・Acme大全への道
このエントリーは下記の記事へのアンサーです。 tomcha.hatenablog.jp
体調不良で残念な結果に終わったYAPC::Tokyo 2019でしたが、よかった事もありました。
makamakaさんに事前にお願いをして、Acme大全2018を遂に入手しました!
ページをめくって確認すると・・・
あった！！！
紙の書籍に自分のプログラムが載るってなかなか感動モノです！ makamakaさん、ありがとうございました！
AcmeモジュールはCPANにモジュールを上げる良い入り口なので、何かモジュールのネタを持っている人はチャレンジしてみると良いと思います。
Acme大全掲載を目指しましょう！
<おまけ>
makamakaさんの会社、毎度おなじみのネコトーストラボさんのYAPCのノベルティ、0歳6ヶ月の娘が大変気に入っておりました。 こちらもありがとうございました。
ピザ会のお題のコードを書いてみた
帰りの新幹線で一人Perl会。 お題のコード書いてみた。
よく読むとリファレンスを使わない縛りもあったので、その回答はこちら。
YAPC::2019の感想ブログ
初めて参加したYAPC::2012から、ほぼ毎年参加してきましたが、今回は行きの新幹線で体調を崩してしまい、トークも一部しか見ることができず、前夜祭や懇親会も参加できず、次回リベンジしたい！！！となったYAPC体験でした。
体調不良で見たかったトーク全部を見ることができませんでしたが、見たトークで印象に残ったのが @songmu さんの
「多くのCPAN Authorに育てられ、息をするようにCPANモジュールを書けるようになり、そして分かったこと」。
続ける事、とにかく愚直に続ける事の大切さをしみじみと実感。とても感銘を受けました。
また、note103 さんのLTでは、同じ非エンジニアとしてとても刺激を受け、まだまだやらねばと思いました。YAPC::Fukuokaでトークをさせてもらって、自分の中ではやり切った感があったのですが、まだまだ頑張り続けなければと。引退宣言を撤回するスポーツ選手のようだなぁとセルフ突っ込み。
今回、懇親会や飲み会で久しぶりに会える方々とお話できるのを楽しみにしていただけに残念。
YAPC::Tokyo 2019 個人スポンサーチケット購入done.
— tomcha (@tomcha_) 2018年11月14日
YAPC::Tokyo 2019のチケットも買ったし、宿と新幹線も申し込み完了したので、後は家族の説得と仕事の有給申請通すだけだ！（難易度高いタスクばっかり残ってる）
— tomcha (@tomcha_) 2018年11月14日
今回は体調不良で残念だったので、是非とも次回YAPCでリベンジしたい！ https://t.co/FHq9sM1xBh
— tomcha (@tomcha_) 2019年1月27日
最後に、スタッフの皆さんありがとうございました。全てのスタッフさんに感謝は当然のことながら、ベテランながらも運営コミットをされている@nekokakさんmagnoliakさんは本当に尊敬します。YAPC::Japan、本当に良いイベントです！
次回絶対リベンジだ！（要 : 有給と旅費の捻出と家族の説得）
あと、宣伝ですが次回Perl入学式in大阪は、2019/2/23開催です。
絶賛参加者募集中です！
