四則演算の計算結果を返すプログラムを書きながら学習とは何かについて考える

LT資料

Transcript

1. 四則演算の計算結果を返すプログラムを書きながら 学習とは何かについて考える Yuhei Nakasaka 1
2. 四則演算の式を受け取って その計算結果を返すプログラム書けますか？ 例: 1+2*3 => 7 2
3. 楽勝〜〜 eval('1+2*3') 3
4. 条件 文字列 s は、非負整数・空白・演算子 + - * / だけからなる有効な式である s を評価して結果を返せ * / は通常通り優先し、整数除算は 0 方向に切り捨てる 1 <= s.length <= 3 * 10^5 eval などの式評価関数は禁止 https://leetcode.com/problems/basic-calculator-ii/ 4
5. 再帰下降構文解析のパーサーを書けば良いのでは どうやって書くんだっけ？ ぼんやりとしか記憶していない → 調べる 5
6. 再帰下降構文解析とは 文法規則ごとに関数を用意する トップダウン構文解析 各関数が、対応する非終端記号を処理する 書いたプログラムの構造が文法の構造に近くなる 実装的には優先順位が低いものから順に再帰的に降って下から順に計算する感じ https://en.wikipedia.org/wiki/Recursive_descent_parser 6
7. 四則演算のBNF書くか〜 どうやって書くんだっけ？ ぼんやりとしか記憶していない → 調べる 7
8. BNF（バッカスナウア）記法とは Backus–Naur Form の略 記号の書き換え規則を用いて文字列の構造を定義する仕組み プログラミング言語やプロトコルの構文定義で使われる <expr> ::= <term> [ ('+'|'-') <term> ]* <term> ::= <number> [ ('*'|'/') <number> ]* <number> ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9' https://en.wikipedia.org/wiki/Backus–Naur_form 8
9. 再帰下降構文解析で書いてみた結果 https://gist.github.com/YuheiNakasaka/e6574b98653bb1d0548fb4583ed1f205 9
10. というかこんなことしなくても もっと雑に解ける方法あるのでは... 10
11. 四則演算のプログラムといえば 逆ポーランド記法！！ 逆ポーランド記法に変換すれば良いのでは 11
12. 逆ポーランド記法とは 演算子を、対応するオペランドの 後ろ に置く記法 1 + 2 * 3 は 1 2 3 * + 左から読み、数値はスタックに積み、演算子が来たら計算する 1 2 3 * + push 1 push 2 push 3 * => 2 * 3 = 6 + => 1 + 6 = 7 https://en.wikipedia.org/wiki/Reverse_Polish_notation 12
13. と言っても 中置記法を逆ポーランド記法に変換するの面倒そう 13
14. 操車場アルゴリズムというのがある ダイクストラ先生 が考案した、式を構文解析するためのアルゴリズム 中置記法から、逆ポーランド記法や AST を生成できる（らしい） 演算子スタックを使い、優先順位が高いものから出力に送る input: 1 + 2 * 3 output: 1 2 3 * + https://en.wikipedia.org/wiki/Shunting_yard_algorithm 14
15. 実際のコード https://gist.github.com/YuheiNakasaka/62e96c088fa12c30ad6b46b1837d8d7a これで提出 15
16. 通った 16
17. では模範解答をチェック！ 17
18. 模範解答 https://gist.github.com/YuheiNakasaka/0bcfb8c124ad852dccf79a5e41ddfc73 18
19. 全然違う解法... スタックを一つ使うだけ...だと 19
20. 模範解答の考え方 * / だけ、その場で計算する + n は n をスタックに積む / - n は -n をスタックに積む * n は直前の値を取り出して掛ける / / n は直前の値を取り出して割る 最後にスタックを合計する 3 + 2 * 2 stack: [3] stack: [3, 2] stack: [3, 4] sum : 7 20
21. 気づき 21
22. 人間は知ってる道具で課題解決しようとする ハンマーしか持っていなければ、すべてのものが釘に見える(ハンマーを持ってる と釘を探したくなる) 技術選定や設計などあらゆる意思決定でも言えること(学んだばかりのデザインパ ターンで実装したくなる、など) 様々な選択肢を持っていないと最適な選択ができない 22
23. 最適な答えが全てではない 最適な答えを得ることは大事だが、そこに辿り着くまでの過程は無駄だったか 再起下降構文/BNF/逆ポーランド記法/操車場アルゴリズムなど。寄り道によって 様々なアプローチを再学習できた。 23
24. AIと学習機会 AIを使うと最適な答えがすぐに手に入る 最適な答えが手に入るのは便利だが、その過程で本来得られたかもしれない新た な学びの機会を失っているのではないか 本当にそれでいいのか 24
25. もっと間違って寄り道しよう 自分のプログラマ人生を振り返ってみると、いつも何か学びを多く得られたのは 答えを得た時ではなく、答えを得るまでの道中だった気がする ゴールに辿り着くまでの試行錯誤こそが学習の肝なのではないか 成長のために必要な、大切な寄り道の機会をAIに奪われるのは勿体無い 25
26. ただし、あくまで学習という観点の話 業務ではAIが簡単にやってしまえることはAIにやらせて人間はより複雑な判断や創 造的な仕事に時間を使うべき AIを使うなというわけではなく、学習という観点で大切なのは寄り道の中にある のではないか、という話です。 AIで仕事が出来るからといって、自分が賢くなっているわけではない もちろんAIを使って学習を加速させることもできる(が、これはまた別の機会で) 26
27. 終わり 27
28. 参考資料 LeetCode 227. Basic Calculator II: https://leetcode.com/problems/basic-calculator-ii/description/ Recursive descent parser: https://en.wikipedia.org/wiki/Recursive_descent_parser BNF notation for syntax, W3C: https://www.w3.org/Notation.html バッカス・ナウア記法: https://ja.wikipedia.org/wiki/バッカス・ナウア記法 Reverse Polish notation: https://en.wikipedia.org/wiki/Reverse_Polish_notation Shunting yard algorithm: https://en.wikipedia.org/wiki/Shunting_yard_algorithm Law of the instrument: https://en.wikipedia.org/wiki/Law_of_the_instrument 28