Perlがくしゅう帳(Rubyも)

プログラミングの勉強会の参加記録や学んだことなど。 twitter ID : @tomcha_で活動しています。 最近は主にPerl関連の勉強会やコミュニティに参加しています。移転前のブログはこちら->http://ruby.doorblog.jp/

Perlで色々なアルゴリズムを実装してみた その2

アルゴリズムの実装力を養成するため、Perlで書いてみましたの続編です。

こちらの本の第8章から

図解入門よくわかるアルゴリズムの基本と仕組み (How‐nual Visual Guide Book)

図解入門よくわかるアルゴリズムの基本と仕組み (How‐nual Visual Guide Book)

再帰(第8章)

再帰アルゴリズムとは、その関数が目的を達成するまで、自分自身を何度も呼び出す構造となっている面白い構造です。
自分自身を深く深く掘り下げて、到達点に達した途端にすべてが解決するという、ピタゴラスイッチ的な面白い仕組みでとても好きなアルゴリズムです。
が、この「どう自分自身を掘り下げる(関数を呼び出す)か」「解決の到達点は何なのか」の勘所がなかなか難しいアルゴリズムでもあります。

最大公約数を求めるコード

2つの数の最大公約数を求める方法にユークリッドの互除法という方法があるそうです。2つの数を互いに割り算していくと答えが出る方法です。
その方法の理解はまだ出来ていませんが、とりあえずその仕組みを再帰で実装してみました。
「何度も割り算をしていく」が自分自身を掘り下げる関数に、「余りが0になった時」が解決の到達点っぽいですね。

最大公約数をユークリッドの互除法を使って再帰で実装する

階乗を求める

1からある数まで、1ずつ増やした数を掛け算した答えをだす(1 * 2 * 3 * ... * n)問題です。
掛けていく数を1ずつ増やすより、逆にnから1ずつ減らしていって最後に1になった時を解決の到達点と考えるのがポイントです。

階乗を求める

クイックソート

クイックソートは並べ替えのアルゴリズムの1つです。並べ替える元データから任意の1つの値を取り出し、その値より大きいグループと小さいグループの2つのグループに分け、出来たグループでまた同じ動作をしていきます。各グループの要素数はだんだん少なくなっていき、グループ分けが出来なくなるまで少なくなればそこが到達点 と考えます。
まずは自分なりに考えてたコードです。問題点は、グループ分けした要素(配列)を量産しているので、実行時のメモリを沢山使っているところです。

クイックソート1

クイックソートその2

本の実装例では、その1の問題点を見事に解決(新しい配列を量産するのではなく、元の配列内の数値をうまいこと入れ替えることで実装)していたので、その考え方で実装してみました。
配列の値をコピーするのではなく、元の配列の値の場所を入れ替える・・・そう、リファレンスの出番ですね。

クイックソートその2

ニュートン法

微分を使って平方根の値(近似値)を求める方法です。
ニュートン法自体の理解は数学的素養が必要なので、最近通っている高校数学勉強会での知識で、なんとなく分かった様な気がしている状態ですが、理屈の実装自体は難しくありません。

ニュートン法

台形法

ある関数(数学の)で書かれたグラフの面積を、定積分を使って求める方法です。
ニュートン法と同様、数学的素養が必要ですが、理屈の実装自体は難しくありません。

台形法

ダイクストラ

経路探索のアルゴリズム駅すぱあとみたいなやつですね。
自力ではさっぱり分からなかったので解説を読んで実装しました。すべての点の最短経路を求めるていき、その点がゴールなら解決するというアルゴリズムです。

ダイクストラ法

色々な基本アルゴリズムを実装してみましたが、このあたり全てがヒントなしでスラスラ書けるようになれたらなぁと思います。
まだ難しいアルゴリズムはすぐに忘れてしまいそうになるので、精進あるのみです。

Perlで色々なアルゴリズムを実装してみた

ちょいちょい参加している AtCoder で、二分探索のアルゴリズムを時間内に実装する自身がなかったので、基本的なアルゴリズムを手を動かした実装してみました。
まぁ、ソートやサーチなんかは、大体の言語でメソッドや組み込み関数が定義されているので実務で使うことは無いと思いますが、実際にどういう動きをするかを頭で考えてコードで表現する訓練は大事だなぁと思って色々書いてみました。

アルゴリズムについては色々書籍が販売されていますが、手頃な感じの本を入手して最初の問題からコードを書いてみました。普遍的な知識ですね。

図解入門よくわかるアルゴリズムの基本と仕組み (How‐nual Visual Guide Book)

図解入門よくわかるアルゴリズムの基本と仕組み (How‐nual Visual Guide Book)

それぞれのコードは、どんな動きをするのかの趣旨だけ読んで自分なりにコーディングしてみたので、コードにツッコミやアドバイス等々あればお手柔らかにお願いします(笑)。
まずは第7章までの基本編。

値の集合から、条件にあった値を取り出すコード(第4章)

合計

sum

数を数える

count

平均

average

最大値

max

最小値

min

まぁ、この辺りは基本編ですね。プログラミングの初心者の方は、このあたりからコードを書いてちゃんと動くか試してみると良いと思います。Perl入学式の復習にもどうぞ。

順番をソートするアルゴリズムの実装(第6章)

選択ソート

selection_sort

バブルソート

bubble_sort

挿入ソート

insert_sort

シェルソート

shell_sort

ちょっとアルゴリズムっぽくなってきました。シェルソートはグループ分けをどう実装するか、頭の中だけで考えるだけでは混乱したので、実際に動きをノートに書き出して実装しました。
頭で考えて書いたコードは思うような結果になりませんでしたが、ノートに書いて整理するとあっさりと書けました。いきなり書かずにまず整理。
どんな言語でも通用する基本って大事。

値の集合から特定の値を探索するアルゴリズムの実装(第7章)

線形探索

linear_search

二分探索(当たり入り)

binary_search

二分探索(当たりなし)

binary_search2

文字列の照合

strings_search

アルゴリズムの実装、頭の体操的にも面白いですね。引き続き第8章以降もやっていきたいと思います。

吉祥寺.pm 17に参加しました

行ってきました、吉祥寺.pm 17。今回、2回目の参加です。

f:id:tomcha0079:20190302114734j:plain:w250

そして「YAPCに行けば人生は変わる」というタイトルでLTをしました。

関西在住なのでなかなか東京近郊の勉強会に行くことはできませんが、今回は参加できそうな機会あったので行けたらいいなと思い家族に相談。
二つ返事で行ってきたら?とOKをもらい、妻に感謝。しかし申し込もうとした時は既に参加枠はキャンセル待ちの状態。
なんとか確実に行ける方法はよく見ると、YAPC-LT枠が一つまだ空いているではありませんか!

妻に赤ちゃんの面倒をかける事になるし、LTするからには有益なLTをしたいけれど、果たして自分に話すネタはあるのか?直前に体調を崩したりしないだろうかetc...
行きたいという気持ちもありつつ、その気持ちの足を引っ張る考えが色々と頭をよぎりました。

しかし、少しでも行きたい気持ちがあるのなら、行動しよう!今までも行動して良かったことが山ほどあるやん!と思って、勢いでLT参加ボタンを押しました。
(まさか、こんなに沢山の参加者がいる前で喋ることになるとは!)

何かを変えるには、行動するしかない。"待ってるだけの昨日にアディオス!"。そんな気持ちを若い人達に伝えられたら、、、とLTのテーマを決めました。スライドはこちら。

speakerdeck.com

終わってからの懇親会やTwitterで、LT良かったですよと声もかけてもらい、ああ勇気を出して参加してよかったなぁとホッとしております。

しかも、嬉しいことに近藤佑子🐱技術書典6 か66(@kondoyuko)さん | Twitterさんに、なんと自分のLTをグラレコしてもらいました!これはめっちゃ嬉しかった!

f:id:tomcha0079:20190302164627j:plain:w500

今回のトーク4本を聞いて色々と感じたことは、、、

  • 1ob1の話

    • 自分の仕事の業界は、完全ウォーターフォール型組織なので、育てていく意識をちゃんと持っていて凄いなと思いました。若手を育てない組織の将来性は真っ暗だよなぁと。
  • Bitcoinの話

    • 自分も暗号通貨の技術面を知りたいと思って、書籍を買って読んだり、実装されたコードを写経してみたりして、なんとなく分かった感じだった事が、あらためて整理された話を聞けてとても面白かったです。もっと時間をかけてたっぷり聞きたかった!
    • そういえば、今年のkof2018に楠さんの話も聞きに行きました。k-of.jp
  • 非公開APIを探る話

    • 自分で既存のサービスから情報が欲しい時、APIが公開されていないとスクレイピングしたり諦めるしかないのかなと思っていたので、chromeのツールを使って探るお話はとても勉強になりました。懇親会でも自分の疑問点に色々丁寧に教えてもらえました。へっくす? (@codehex) | Twitterさん、ありがとうございました。
  • そして、Perl入学式を卒業する話

    • 私がここまで深くプログラミング界隈にかかわる事となったきっかけは、間違いなく 超大陸パンゲア (@__papix__) | Twitter さんのおかげで、今回自分がLTをするにあたり昔のPerl入学式やYAPCの出来事を色々調べて思い出したりしていた事も重なって、非常に感慨深い話でした。papix校長はPerl入学式運営から卒業し、ANAの修行に入られるとの事ですが、7年間続けてきたPerl入学式というコミュニティは、いつでもふらっと遊びに帰って来られるよう、サポーターメンバー皆が守り続けていきますので、安心して修行に行ってください!

そしてLTも多様な話が聞けて楽しかったです。vimや26進数や愛の深いお話、Riot.jsは手軽そうで試してみたい。Perlにインターフェースを実装するPerlハッカー凄い!ラリーとは私も写真とってもらいました!書籍出版たいへん!

その他、久しぶりにお会いする方々との懇親会でのお話も楽しかった!

今回驚いたこと、感じたことメモ

  • 自分が参加者最高齢だと思っていたけど違った。多分3番目?
  • 69歳現役プログラマー凄い!あと20年以上戦える!
  • よしたくさん、想像と違ってめっちゃ若かった
  • グラフィックレコーディングはめっちゃ嬉しかった!
  • 自分の様な非エンジニアのエンジョイ勢の受け入れてもらえる、多様性のある勉強会。
  • 懇親会で初めてお話した方々、新しいつながりができて嬉しい!
  • Papixさん、Perl入学式のめっちゃ良い話だった!感極まって泣いて胴上げの展開になったらどうしようかと心配したけど、それはならなくてよかった
  • そーだいさんのLT、めっちゃ男前な方だなぁ

吉祥寺.pm、本編も懇親会も本当に楽しかったです。 magnoliak (@magnolia_k_) | Twitter さん、ありがとうございました。

そして憧れのおにやんまの讃岐うどんを食べて帰りました。美味しかった!

f:id:tomcha0079:20190302123003j:plainf:id:tomcha0079:20190302123246j:plain

関西のPerlmongerの皆さんにも、東京まで行く価値が十二分にある素晴らしい.pmです!

そしてKansai.pmもよろしくお願い致します!

kansaipm.connpass.com

キッカソン#3を開催しました

YAPC::Tokyo 2019の余韻がまだ続いている最中、2019.2.9~2019.2.10の1泊2日で京都の太秦(うずまさ)にある菊香荘で開発合宿を開催しました。

菊香荘+ハッカソン=キッカソン、今回はで3回目です。毎年1回のペースで開催を続けています。 キッカソンは別名Perl修学旅行、Perl入学式の修学旅行的な初心者向け開発合宿のイベントでしたが、Perl入学式が全国に広まり、サポーター同士がオンライン上だけでのコミュニケーションに成りがちなので、入学式のスタッフが集まって今後の活動体制等を話し合うPerl入学式職員旅行のような一面も出てきました。

f:id:tomcha0079:20190209181743j:plain:w300

初日のスケジュールは13時に宿に到着し、大広間の1室に集まって各々持ってきた課題をすすめました。

今回自分は、データベースを使ったアプリケーションをPerlで作成するというチャレンジをしていて、そのアプリ作成の続きをする事にしました。とはいっても、DB操作の基本的なSQLの知識はあるものの、実際にPerlでどうコードを書けば良いのか分からないので、Perlゼミのデータベース操作のページを見ながら実装をすすめました。 tutorial.perlzemi.com そして今回、もくもくしている自分の左隣には、Perlゼミの作成者の木本さんが!なんと贅沢な開発環境なんでしょう!

また、モダンなDB操作ならORマッパを使ったらいいよと色々アドバイスもいただき、なんと私のすぐ右の方には、 Perl製のシンプルさが特徴のORマッパ、Anikiの作成者かるぱねるらさんが!なんと頼もしい開発環境なんでしょう! metacpan.org

18時お楽しみの夕食タイム、今回は菊香荘の夕食を堪能しました。夕食後は参加者の皆さんとお酒を交えてワイワイと懇親会を。修学旅行の雰囲気で、夜中の1時頃まで楽しく話ました。

f:id:tomcha0079:20190217150935j:plain:w300

翌朝の朝食も豪華な旅館のお食事です。

f:id:tomcha0079:20190210082546j:plain:w300

朝食後は昼過ぎくらいまで各自もくもくと作業を進めました。1日目よりも2日目の方が作業効率が上がるようでした。次回キッカソンは2泊3日プランもありかという話も。 自分も普段家でプログラミングするよりも随分と作業が進みました。 集中してガッとやる環境、大切ですね。

続ける事で全国にたくさんの仲間ができるコミュニティ、Perl入学式。 今後のスケジュールはこんな感じです。

perl-entrance-osaka.connpass.com

perl-entrance-tokyo.connpass.com

perl-entrance-sapporo.connpass.com

perl-entrance-fukuoka.connpass.com

各地域まだまだ空き枠があるので、プログラミングを学びたい!と興味を持たれた方は参加してみて下さい。

また、受講生を卒業して、運営スタッフにも興味があるという方がおられましたら、気軽にスタッフに声をかけてみて下さい。

続・Acme大全への道

このエントリーは下記の記事へのアンサーです。 tomcha.hatenablog.jp

体調不良で残念な結果に終わったYAPC::Tokyo 2019でしたが、よかった事もありました。
makamakaさんに事前にお願いをして、Acme大全2018を遂に入手しました!

ページをめくって確認すると・・・

f:id:tomcha0079:20190203122808j:plain:w400

あった!!!

紙の書籍に自分のプログラムが載るってなかなか感動モノです! makamakaさん、ありがとうございました!

AcmeモジュールはCPANにモジュールを上げる良い入り口なので、何かモジュールのネタを持っている人はチャレンジしてみると良いと思います。 Acme大全掲載を目指しましょう!




<おまけ>

makamakaさんの会社、毎度おなじみのネコトーストラボさんのYAPCノベルティ、0歳6ヶ月の娘が大変気に入っておりました。 こちらもありがとうございました。

f:id:tomcha0079:20190203231126j:plain:w300f:id:tomcha0079:20190203231911j:plain:w300

ピザ会のお題のコードを書いてみた

帰りの新幹線で一人Perl会。 お題のコード書いてみた。

sironekotoro.hateblo.jp

card_simulator

よく読むとリファレンスを使わない縛りもあったので、その回答はこちら。

card_simulator_without_ref

YAPC::2019の感想ブログ

初めて参加したYAPC::2012から、ほぼ毎年参加してきましたが、今回は行きの新幹線で体調を崩してしまい、トークも一部しか見ることができず、前夜祭や懇親会も参加できず、次回リベンジしたい!!!となったYAPC体験でした。

 

体調不良で見たかったトーク全部を見ることができませんでしたが、見たトークで印象に残ったのが @songmu さんの

「多くのCPAN Authorに育てられ、息をするようにCPANモジュールを書けるようになり、そして分かったこと」。

続ける事、とにかく愚直に続ける事の大切さをしみじみと実感。とても感銘を受けました。

 

また、note103 さんのLTでは、同じ非エンジニアとしてとても刺激を受け、まだまだやらねばと思いました。YAPC::Fukuokaでトークをさせてもらって、自分の中ではやり切った感があったのですが、まだまだ頑張り続けなければと。引退宣言を撤回するスポーツ選手のようだなぁとセルフ突っ込み。

 

今回、懇親会や飲み会で久しぶりに会える方々とお話できるのを楽しみにしていただけに残念。

 

 

最後に、スタッフの皆さんありがとうございました。全てのスタッフさんに感謝は当然のことながら、ベテランながらも運営コミットをされている@nekokakさんmagnoliakさんは本当に尊敬します。YAPC::Japan、本当に良いイベントです!

 

f:id:tomcha0079:20190126125615j:plain

YAPC::Tokyo 2019

次回絶対リベンジだ!(要 : 有給と旅費の捻出と家族の説得)

 

あと、宣伝ですが次回Perl入学式in大阪は、2019/2/23開催です。

絶賛参加者募集中です!

perl-entrance-osaka.connpass.com