コードレビューを試す会
始まってますね。
実は趣旨を説明しようかなと 思いますけど、
みんなでコードレビューを試す会 というタイトルにして、
自分が他の人と喋っている時に、 コードレビューをする機会が
あんまりないみたいな話を聞いて、 コードレビューって結構僕は
僕はプログラマーにおいては、 ものすごいデカい機能というか、
すごいものができたなって思ってて、 コードレビューができる前とできた後で、
コードに対する安定性とかって、 段違いになったんじゃないかなと
思ってたんで、ぜひもっといろんな人が コードレビューみたいなことを
体験できる機会があればいいなと思って、 これを企画しました。
ただ、コードレビューをするには 当然なんですけど、コードが必要で、
なかなかこのスタイルでコードを 持ってきてくださいっていうのは
ちょっとレベルが高いなと思ってたんで、 どういう形でやれば
勉強会の提案を出せるかなって思った時に、 アルゴリズムを解くっていうのは
結構いいかもしれないって思いました。
アルゴリズムを解くっていうのは 一問に特化できるし、
その中でどれコードを解くかみたいなことを 考えるだけでも面白いと思うので、
今日結構計算業の話とか、 どうやって解くかみたいな話も含めて
いろいろ説明していこうかなって 思っているので、
コードレビューをしつつ、 アルゴリズム問題を解きつつ、
そこから派生式ACシャープのいろんな話を する可能性もあるんですけど、
それらが一番僕が重要かなと思っているのは 楽しめるかなって思っていることなので、
そんな難しそうな回って思ってもらうよりは、
すごいコードをかけて楽しかったですって 言ってもらえるのが一番嬉しいと思うし、
こんな質問とかしてもいいのかな みたいなことは全然考えずに、
全然いつでも止めてもらって、 何でも聞いてもらえばいいかなと思っているので、
そんな形でワイワイガヤガヤ進めれるのが 理想だと思っています。
一応今回資料を作っていくので、 その資料からやろうと思うんですけど、
さっき雑談でちょっとしゃべってましたけど、
今回はマークダウンで資料が作れるっていう、
スライデブっていうサービスがあったので、 それで資料を作ってみました。
実際こういう感じでマークダウンで わーって書いて、
NPMでビルドするとそれが資料になって、 こんな感じで資料ができますと。
コードとかも書けるので、
実際パワポでコードとか貼り付けるのって、 意外と思った通りにできなかったりするので、
そういうところにデータを書けるのって 意外とアホらしいなと思うんですけど、
マークダウンだとフォーマットがしっかりしてるので、
それの通りに書いてそれをそのまま資料にしてくれて、
これGitHubで管理しておけば、
GitHubページにそのまま上げることもできるので、
Ippei Usami
これもう今そのまま実は上がってるんですけど、
これかな?
これ僕のGitHubのアカウントなんですけど、
さっきのこの資料はGitHubって 一応アカウント作ってるやつでやってるので、
Ippei Usami
全く同じものが世界で見える形になってる状態です。
一応資料の感じで進めていくと、
一応ローカルのほうでやってるやつで、
自己紹介は別にみんな知ってるのでいいかなと思います。
今回はリートコードっていうのを使って 進めていこうかなと思うんですけど、
リートコード知ってる方はいらっしゃいます?
初めて知りました。
一応コンパスのほうには書いてあったと思うんですけど、
今回もうできればアカウントまで作ってもらおう。
この場でアカウント作ってもらって そこで解くのがいいかなって思ってるんですけど、
まず最初に謝罪があって、
ごめんなさい、一問目を解くっていう趣旨にしたんですけど、
資料作ってて説明するのに若干ちょっと やりづらいところがあったんで、
ほとんど一緒なんですけど、
Ippei Usami
問題を変えたいと思います。
今リートコードに行ってもらって、
160ならば同じ2,3っていう問題があるので、
リートコードアカウント今作れます?
今ちょっとロゴンしようとしてる。
アカウント作らないといいのですか?
Ippei Usami
アカウント作らなくても問題を見ることはできます。
で、できないのは解くことができない。
Ippei Usami
そうなんですかね。
サブミットできない。
そうですね。
ラントサブミットができないので、
この後ローカルでやる方法も 説明しようかなと思ってるんですけど、
最終的にはここでテストが見えるんですけど、
3個こうやってテストが見えるんですよね。
これで走らせることもできるんですけど、
実はこのテストリザルトやると、
もっと何百枚もチェックが走る状態になって、
アルゴリズム問題と解法の説明
全部クリアできるかどうかっていうのが分かるので、
ここ上でコード書くことももちろんできるので、
何も使わなくても問題を解いていくことはできるんですけど、
Ippei Usami
実はこれインテリセンスも効かないんですよね。
効かないわけじゃなくて、有料です。
お金払うとできたりするんですけど、
ここにオートってあって、
ログインしても使えなかったので、
ローカルで使った方がやりやすいかなと思ってるので、
今回はこの167番を解いていくっていう感じで、
進めていこうかなって思ってます。
Ippei Usami
今私の状態は、
リードコードのページまでたどり着こうとしてて、
くるくる回ってる状態。
あ、ネットワークが重い。
ここのゲストのネットワーク?
一応ネットワークはLTEで持ってたので、
Ippei Usami
大丈夫ですか?
ここの使ってもらっても?
Wi-Fiはちょっとどうかなと思ってたので。
もしあれだったら、
ここのWi-Fi使います?
Ippei Usami
使わせてもらっていいですか?
ネットワークになったら大丈夫かな?
どうするかな?
あと、GitHubにリポジトリまで作っちゃってもいいかなって、
個人的には思ってます。
ミスではないんですか?
後ろに入ってます。
Ippei Usami
これはSSH?
SSHです。
アジアカスタードがちょっと長いんですけど。
すいません、すいませんですね。
そっちもカウント用意してみると。
これは事前にやっといてもよかった。
そんなに慌てなくても、
Ippei Usami
来てもらってからやるでもいいかなって思ってたので。
これいいかな?
3、2、1。
打ち間違えられるのかな?
今日、白石さんとも話してたんですけど、
アルゴリズム問題って、正直答えを探せば、
わりと世の中に転がってるし、
このリート構造上でも、実はディスカッションみたいなのをしてて、
そこを見ると答えはだいたいわかるんですよね。
このソリューションズというところで
みんなが回答について喋っていたりするので
答えが知りたい人は
いくらでも探る術はあります
ただアルゴリズム問題は
できれば自分で1回解いてから
他の人の答えを見る方がいいと思うので
そこは正前説みたいな話にしかならないですけど
いきなり答え見て解くだとやっぱり
あんまり学習効果が薄いかなと思うので
ぜひ悩んだせいで解けなかったというのは
全然アリだと思うんですけど
考えた状態で答えを見るのと
全く何もせずにいきなり答えを見るのでは
全く学習効果が違うかなと思うので
ぜひ事前に解いてくるにしても
時間をかけて考えた上で
答えを見るようにした方がいいかなと思っています
全く同じ理由で
GitHubコパイロットとか入ってらっしゃる人も
結構いるかなって思うんですけど
割とアルゴリズム問題は
的確に答えをすぐ提案してくるケースが多い
っていう印象を僕は強く持っています
やっぱりGenerative AI全般的に
答えが明確な問題っていうのは
強いかなってすごく思っているので
実際よくあるケースとして
普段だったらメソッド作っただけで
もう大体の答えの提案してくるときもあるんですけど
それをしないにしても
ifって書いたら割と次々と提案してくれて
自分としては学習の効果もあると思うので
考えたいと思っているのに
いきなり答えのコードをバッて出されたりすると
いやいやまだ考えてるんだけどって
思ったりすることがあるので
もしかしたらアルゴリズム問題を解くときは
これはいいと思ってますけど
コパイロットは切っといたほうが
あまり答えをいきなりやらずにする
っていう面あると思うので
そこは各自にお任せしますけど
答えはあまりないとか
コパイロットは使わないほうが
いいかなって思ってます
サイトに関して言うと
ヒントがある問題とかも結構あったりするので
リートコードの利用とGitHubにリポジトリの作成
どうしても悩んで分かんないときとかは
それを見たりするでもいいかなって思ってます
この辺は本当に任意の話にしかならないと思うので
推奨としては先に答えを知っておくのは
あまり良くないんじゃないかなっていうぐらいで
Ippei Usami
考えてください
アカウント作ってました
では一問目を解くところからやろうかなと
思ってるんですけど
167に入るためにどこに
プロフレームリストっていうのがあって
あるいは検索してもいい
Ippei Usami
ビートボード167で検索すれば
それが一番早いかもしれない
Ippei Usami
Googleで検索したら
Googleで検索したら
それがたぶん
167のビートボードね
Ippei Usami
これも日本語翻訳したらいいかなと思ってるので
先にちょっとコードどうやって書くか
説明からしようかなと思うんですけど
さっきも言った通りここでいきなり書いてもいいです
ここで言語を選べるので
日本語にしてるとすごい可能性がある
ここでCシャープにしておいたら
こんな感じで回答が出ますと
でもこれだけだと
さっきも言った通りインテリセンスとか
効かないので
ローカルに
いきなり作っちゃってもいいですし
GitHubでリポジトリ作って
新規で作成するっていう形でも
どっちでもいいかなとは思ってるけど
僕も今回作っていく形にしようかなと思うので
テストプロジェクトをまず作るところから
Ippei Usami
これ自体はまだ作ってるな
もう一個新規で
新しいプロジェクトの作成から
これ出た
Ippei Usami
いきなり落ちる
Visual Studioが不安定なんですよ
Ippei Usami
って話をさっきしてたんですけど
ちょっと落ちますね
新しいプロジェクトで
MSテストを使って
Ippei Usami
1個
CSプロジェクトを作ってもらいたいなと思ってて
テストは多分
世の中的には3種類
今メジャーなのがあって
MSテストとXユニットとLユニットがあります
どれを使うかは正直僕はどれでもいいかなと思ってて
若干の癖はありますけど
ある程度わかってきたら
そのまま他に利用できることがほとんどなので
どれを使わなきゃいけないみたいなことは
MSテストを使用した問題解決
あんまり気にしなくてもいいかなと思います
調べてたシェア率みたいなことで言うと
今Xユニットが多分一番人気ならしいし
そこはそれぞれ自分の好きなものを
使うぐらいの感じでもいいんですけど
僕はMSテスト使い慣れてるので
MSテストで説明しようかなって思ってます
一応ソリューション作ったっていう前提にして
新規でファイルを作って
Ippei Usami
どれだっけ
新しい項目でいいのかな
これあんま作ったことない
あるやつを利用させてもらおうか
こんな感じで今回は167なんで
167みたいなのをちょっと一個作ります
167っていうクラスを一旦作って
全部一体消します
テスト系クラスだけある状態で
ここにあるこのメソッドだけを
Ippei Usami
ローカルに持ってきます
こんな感じですかね
テストケースを作って
Ippei Usami
メソッドを作って
最初はこんな感じ
テストメソッド1に対して
Ippei Usami
今回の問題が
これが問題なんですけど
このナンバーズっていう
イントの配列が渡ってきて
ターゲットっていう数値を持ってますと
この中から2つの数字を取ってきて
このターゲットになる
1番目だと2と7を足せばターゲットになるし
2番目だと1番目と3番目を足せば6になる
っていうターゲットがあるので
それをそのインデックスを
アウトプットとして返してください
という問題です
それをここに同じように書いてみますと
そのまま持ってくるとこんな感じ
ナンバーズは2,7,10,1,15
ターゲットは9
エクセプテッドが0と1
これビルドさっき取ってないのはなぜだ
Ippei Usami
この書き方は
ちなみにこれC♯の12かな
12からこの書き方ができます
□からこう
古いやつだとこうじゃないと書けないですね
これを最新の書き方で書くとこうなります
Ippei Usami
.NET8を入れてないと多分この書き方できないかも
同じように入れたらこういうふうに返せるので
Ippei Usami
こういう形にしますと
これでこのQSAMを自分で実装してみましょう
というのが今回の主題というかやり方です
皆さんもうやってきてるんでしたっけ
何だったら
全く同じ問題じゃないんで
QSAMとほとんど同じなんですけど
全く同じではできないので
Ippei Usami
これを今からみんなで15分30分くらいかけてやってみましょうか
準備できましたか
Ippei Usami
私今準備できてるのはプロジェクトまで作ったんだけど
テスト環境までちょっと作ってないな
どうとかはなんとなくわからないけど
そこにたどり着くかちょっと今自信ない
このテストプロジェクトは今起動してます
Ippei Usami
プロジェクト自体はVisual Studio 2020で作っています
ただちょっとコードを隠した準備ができるかというのを
ちょっと今手伝いましょう
手伝いましょうか
ビルド修正のステップ
Ippei Usami
コピったりしたら早いとこだったらすぐ手伝いますけど
ちょっと今で終わりますか
Ippei Usami
今回の問題見てて相当されてないと難しいなと
思ってたんですけど
Ippei Usami
今ソロトークで書いたんじゃなくてそうかと思って
一回ちょっとこれ抜きます
僕もこれスイッチ置きます
Ippei Usami
準備するところからちょっとスタートしてるんで
ちょっと待っちゃったのでここで終わります
Ippei Usami
全くお気になさらずに
確かにコパイロットも答え言ってきましたね
これで言ってくるんですかもう
言ってきます
Ippei Usami
なんで判別できるの
これ別の問題となんで判別できるの
入力値の答えでわかっちゃう
多分入力値と答えでしょうね
Ippei Usami
あげてる人いるでしょうか
さらにコパイロットの提案を良くしたかったら
多分この問題をコピってコメントにして貼ると
多分さらに精度が良くなると思います
Ippei Usami
仕様の方を渡そうかな
こんな感じにすれば
Ippei Usami
答えが出ちゃう
今私ができた頃は
Visual Studio 2020に対して
Ippei Usami
ソフィションの中にCシャープのプロジェクトと
MSテストのプロジェクトを作ったところかな
まずMSテストの
これある状態なので
Ippei Usami
コードを持っていきましょうか
これが答えを書くべきコードになるので
Ippei Usami
これは元々テスト対象の関数ですよね
これぷらぷらですね
Ippei Usami
シャープに書いて
そうでしたね
ついついCシャープ
ぷらぷらでやってもいいですけど
Ippei Usami
今回はシャープでやってもらったほうがいい
テスト前に書いちゃったんですよ
ユニットテストのところに
Ippei Usami
ユニットテストのところに書いちゃった
じゃあこれがプラスなので
プラスの中に
そこに書いちゃって
さっき書いたやつを
資料のリンクを
コンパスかツイッターですけど
ツイッター今フォローしてましたっけ
Ippei Usami
ツイッターなんか使ってないのよ
そうですか
Ippei Usami
テストコードだよね
このURL今売ってます?
若干めんどくさいけど
Ippei Usami
打つのは何も取れない
URLですか?
はい
ちょっと小さいですけど
mti
Ippei Usami
nnmですね
mti.github.io
Ippei Usami
これ
これが用意ですね
slash
slave
Ippei Usami
sol
ソルブね
ソルブ
ごめんなさい
ソルブ
Ippei Usami
ビートコード
ビートコード
ビートコード
これでいけるんじゃないですか
これで
Ippei Usami
これピントかな
ちょっと
こっちこびれないのか
失礼
ここでこびれれば残った
Ippei Usami
スライドの前についた
なんか映った映った
こびれますね
これを
こびれますね
今日テストコードだね
Ippei Usami
はい
テスト
こっちだこっちだ
パラメタライズテストの実装
Ippei Usami
そうでしたっけ
テスト
ごめんなさい
失礼しました
こっちはね
こっちですね
これね
こっち今戻り値がないんで
Ippei Usami
リターン
リターン
Ippei Usami
ビルド通りますね
これ気になるけど
そうですね
Ippei Usami
失敗
ビルドが失敗したのは
なんていうか
これ.NETいくつですかね
Ippei Usami
.NET7
7
ランケージを多分
発信すれば
Ippei Usami
プロパティね
オブジェクトのプロパティね
うーん
ランケージどうやってやればいいんだっけ
Ippei Usami
ちょっと待ってくださいね
点を設定だけにすれば
確かにいけたはずで
ランケージ
Ippei Usami
発信とか
おそらく
そんなに大した問題じゃないはずなんですけど
それぞれでもいいかもしれない
えっと
このCSプロジェ開いて
ここですね
Ippei Usami
ここに
このランケージバージョンっていうのを
多分プレビューとかで入れれば
Ippei Usami
こうですね
これでいけるはず
Ippei Usami
ちょっと待ってね
ここダブルクリックしたら
ダブルクリックした
このヌラブラの後ぐらいに
Ippei Usami
ランケージバージョン
ラングバージョンか
Ippei Usami
ラングバージョン
ラングバージョン
でプレビュー
これでビルドしたらいかないですかね
Ippei Usami
改めて
やっぱり
Ippei Usami
ダメだな
単純な問題だと思う
別の問題ってことですか
Ippei Usami
ここに
カッコ
カッコの対応をちゃんと
持ったけれど
なんかなるのではないのかな
あー
あーいいいい
そうか
一個取れないんだよ
まずはこっち
ただちょっとこれが
気になるけど
やっぱりこれ
Ippei Usami
言語でダメだっていう
プレビューバージョン
それを
ラングバージョン
Ippei Usami
プレビューバージョン
言語バージョンで
プレビューで受け入れるはずだな
言語バージョンプレビューって
最初の試写とか
ロックネットのバージョン
言語バージョンで受け入れるはずなので
Ippei Usami
多分配列を返さないと
返せばいいんじゃないかな
じゃあもう
あまり考えずに
そうですね
Ippei Usami
これいいのかな
とりあえず
うーん
それでも確かにいいな
9行目って言ってないのか
9行目と
20行目か
Ippei Usami
20行目
9行目はダメか
Ippei Usami
職種がいる
でも赤くなくなった気がする
Ippei Usami
こうですか
試写
これこう言われてるのは
ダメ
その書き方じゃダメかも
ニューの
Ippei Usami
イントの
0なくして
そうですね
Ippei Usami
これでいいんじゃないかな
Cシャープはなかなか
Cシャープはなかなか
Ippei Usami
たくさん使わないと
いろいろ聞かないと
でもさっきのはいけましたね
上の
9行目と11行目が
ダメなんで
新車の新しい書き方が
うまくいってないので
Ippei Usami
ニューの
たぶんそれでいけるんじゃないかな
下のやつは
先のカッコなくした
イントとカッコなくした
Ippei Usami
カッコいらない
その仕方でいけるんじゃないかな
Ippei Usami
上のカッコなくせば
こっちの
これでたぶんいけるんじゃないかな
これもダメ
四角カッコやめて
まず空カッコで
そのあとは
Ippei Usami
たぶんこれでいけるんじゃないかな
すみませんね今から
いえいえいえ全然お気になさらず
Ippei Usami
準備が
OKですね
Ippei Usami
すみません
ドライバー映った
まずいったん解ければいいと思っているので
どういう風でもよいです
Ippei Usami
ゴリ押しなら解ける方法は簡単だと思います
ゴリ押しなら面白い
他の人も待ちましょう
Ippei Usami
デュートコード通した方がいいですか
デュートコード通した方が
今のローカルのやり方だと
テストが一つしか通らないので
そのテストの書き方ですけど
Ippei Usami
さらに
もう一段階上げようかなと思っていて
エンドさん一回
このテストメソッド
こうやって書いたじゃないですか
これ3パターンぐらい
もともとのサイトには書いてあったと思うんで
書き方的には2つあって
これを量産する形
もう一個こう書いて
テストメソッドに作って
こっちを書き換えるという方法も
あるんですけど
別のやり方を説明しようかな
と思っていて
この
ナンバーとかターゲットとか
エクセプテットって
テスト1,2,3見てもらえば分かる通り
型が全部決まってるじゃないですか
Ippei Usami
そういうものは
パラメタライズテストという方法で
書けるので
こっちで書く方がいいかなと思うので
その書き方を今説明します
Ippei Usami
えっと
MSテストの
書き方になりますけど
二重ループによる配列の並べ替え
データロードという書き方が
あります
今実際これちょっと見せますけど
こんな感じ
要は
性的に決まってるものに関しては
ここに
羅列して書くことができるので
今実際ナンバーってこんな感じなんで
ターゲットが9
エクセプトが01なんで
こう書いて
ここのデータロードを書いたときは
引数がここに使えるようになるので
Ippei Usami
ターゲット
エクセプト
こう書く形になります
これを書き方をすると
何がおいしいかというと
データローがいくつでも並べられる
ここだけ書き換えれば
これが1つ目のテストになって
次のデータローが2つ目のテストになって
次のデータローが3つ目のテストになるので
メンテナンシビリティが
良くなる
実際に今これ
リートコードのテストを書いてみると
2問目が
1と6なんで
ここは2と3
4の6で
答えが
1と3
Ippei Usami
だから1と3
3問目が
1と2か
Ippei Usami
これ1と2ですね
これプラス1
多分配列の
リネックスじゃなくて
Ippei Usami
プラス1
1問目の2と3と
若干だけ違うところは
ここが違うはず
微妙に違います
もし1問目の2と3と
全く同じにやると
これハマるかなと思うので
こんな感じですね
こんな感じで書くと
パラメタライズなテストができるようになるので
実際にテストをしてみると
1番目2番目3番目というのが
ここに入ってくるので
プラスよりは
パラメータでテストしたほうが
Ippei Usami
いいかなって
間違えちゃった
気合なら1番簡単にできると思う
Ippei Usami
レーラーが
レーラーでやれば書けばできそうな気がするんですけど
二重ループいける?
どんな二重ループ?
二重っていうか
リンクとか使えばたぶん
Ippei Usami
もういらない
そうですね
でもそれでも結局なんか
Ippei Usami
力技完成なんで
何かも変わらないので
見た目はちょっと気になると思うんで
何かが必要なのは変わらないので
一旦今日はステップバイステップで
いこうと思っているので
二重ループで解いてもらってもいいかなって
Ippei Usami
思います
時間切れの演習だ
考えすぎなところある
しばらくこれ書いてあるの分かっちゃう
何でだろう
実際に解けたら
リードコーナーのほうの
2サブのところに
コードを貼ってもらって
サブネットってやれば
ログインしてれば
リードコードのほうで
全テストを同時にしてくれます
Ippei Usami
ステップバイス
リードコーナーで
小人の歌フェイスがいるんだ
Ippei Usami
歌フェイス?
1番
13の1番
Ippei Usami
歯がちょっといる
なるほど
Ippei Usami
思ったよりいろいろ書いてる
もう一人できたら
レビューっぽい感じに
しておこうかなって
Ippei Usami
思います
リードコードの1番
2つの合計って意味では
同じ問題なんですけど
ここにヒントも書いてあるので
Ippei Usami
なんとなくヒントを見ながらに しようかなって思います
本当に強引な方法は
全ての可能な数字のシェアを 検索することですが
Ippei Usami
それでは時間がかかりすぎます
全部回せるみたいな感じですね
完全性のために強引なソリューションを 試してみるのが最善です
つまりそれでもいいから解いてみろって 言ってる気がします
Ippei Usami
すげえかと思う
ほんまに工業6条ぐらいだと思うんだけど
ちょっとね
とりあえず頭使っちゃう
最近帰れないからどうやったかな
これランタイムの評価もしてくれます
ランタイム?
実行時間も
早いか遅いかまで
Ippei Usami
それはどうするか
テスト結果のほうでやると
順位っぽいものまで出してくれますね
Ippei Usami
順位の変化とかみたいな
これはちょっと後で 説明しようかと思ってましたけど
Ippei Usami
そこは頑張らないほうがいいです
計算量の話とかをした後で
その理由とかはちゃんと言うつもりですけど
ここを早くするには
まずは計算量を抑えることがあって
それよりも早くしようとしだすと
本質的ではない考えが必要になってくるし
リートコードの裏の事情というか
Ippei Usami
教えてもらった話で言うと
課金したほうが若干早くなる
CPUの性能が良いものになるから
解くときも良いものになるので
Ippei Usami
順位が上がりやすい
そこを頑張ってもしょうがないかなと思うので
なので計算量を上げて早くするというのは
頑張りましょうと思うんですけど
1位を目指しましょうは
だいぶ違った方向性の努力になってくるので
Ippei Usami
やめたほうがいいかなと思う
どうですか?
笑ってしまうな
アルゴリズム問題解いてると
普段使わない頭のルールを使う感じがするので
Ippei Usami
久しぶりに閉じてきやすいな
多分時間以外になっちゃう
そうですね
そろそろ1回考えてた時間にはなってきたので
どうですかみんな?
Ippei Usami
もうちょい考えたいのか
1回解いた人の話を聞きたいかというと
もうちょい考えたいのか
考えるじゃなくても力が足らない
うさみさんも?
そうですね
それが終わったら
Ippei Usami
遠藤さんの立ち方を聞きましょうか
今ちょっと変わらなくなりました
前のやつまでできます
それでもいいですけどね
本質的にはあんまり変わらないので
Ippei Usami
うさみさんもうちょいだけ待ちましょうか
無意味じゃないですか
うまくやったような感じですけど
内側と外側が書いてきて
ようやく外側が書きかけたんだけど
さてどうやって終了条件を決めようか
終了条件は?
あと最期的に
どこから最期にしようか
最期は使わなくてもいけますね
Ippei Usami
最期使わなくてもいけます?
いけますね
多分ね複雑に考えすぎてる気が
後半を見ても分かる
それはめっちゃ知りました
Ippei Usami
そう考えちゃったでしょ
ただ方針は
絵も非常に長いと思ってるんだけど
どこにしようかなと思った
感動しに来ました
え?なんで?
多分ダメだったやつだ
捕まらなかったときに戻るしかないって
Ippei Usami
いる気がしますね
答えは一応絶対あるよっていう
答えは絶対あるって言ってますけど
一旦入力しておけば
解くことの重要性
プロジェクト部とかだったら
最高に例外
例外プロジェクトから
Ippei Usami
頂いた方がいいと思うんですけど
思いました
誇りまし
誇りまして
Ippei Usami
確かに
一応ね
はい
Ippei Usami
簡単に
じゃあ遠藤さんがどう書いたかを
ちょっと聞きますか
Ippei Usami
これ繋げますか
こっちに来てもらっていいですか
Ippei Usami
そうですね来てもらったほうがいい
はいじゃあ遠藤さんちょっと
応募を出してもらいながら
Ippei Usami
反省を
自分にやったのに3パターン
3パターンそんなに?
3パターン僕が用意したやつです
ちなみに遠藤さん
じゃあ二重ループよりも
Ippei Usami
早い方法で解いてもらっていいですか
はい
まず二重ループから
話をするのがいいかなと
思っているので
Ippei Usami
同じ数字入る
コードしたやつ
これが最初のやつ
なんとなくどう考えたかを
説明しながら
説明してもらえますか
Ippei Usami
まずこういう
一つ目
こういうメソッドを用意して
ここには小順の
数字があります
ここには2つの
ターゲット1の数字があります
配列を12あるいは0から
配列の最初から最後まで
Ippei Usami
並べていきます
もう一つのループを用意して
Ippei Usami
ループ中のインデックスを
次から最後まで
Ippei Usami
はいはいはい
どんどん並べていきます
そのまま
ターゲットを用意してもらったら
プラスインチしたわけです
素晴らしい
二重ループのお手本のような
Ippei Usami
答えかなって思います
そうですね
計算量の考え方
ちなみに計算量の考え方って
Ippei Usami
知ってる人います?
考え方の話?
Ippei Usami
あ、そうです
これ計算量いくつかって
計算量の話を
少し先にしようかなって思うので
一旦変わってもらおうかな
Ippei Usami
変わってもらいます
はい
ここからはちょっと説明を
Ippei Usami
説明ページ
パラメトライズテスト書いて
僕も結構同じ感じで解いてます
二重ループ作って
ここはif文にして
遠藤さんはコンティニューしてましたっけね
Ippei Usami
これがノットの時は
ここでリタニカル
ほとんど一緒のコードかなって思います
アルゴリズム問題を解く時の
鉄則というか考え方で
Ippei Usami
このコードの計算量はいくつですかっていうのを
基本的には意識して解く方が良いです
はい
計算量これ実際に
intのナンバーズに入ってきてるのが
テスト1だったら4個あったと思うので
一つ目のテストだったらOの4
まず最初のループは4回回る
二個目のループは
4-i-1からなんで3回回る
二つ目のテストは3個あたりが入ってたので
連打数は3なので
Ippei Usami
3と2だし
最後のテストは2個入ってたので
2と1が入りますと
まず計算量を考える時は
実際にいくつになるかなっていうのを
考えてみます
計算量を解く時には
Ippei Usami
ルールみたいなのがあります
すごく簡単に言うと
Ippei Usami
例えば
このループって二重ループになってるので
二重ループの場合は
xかけるxになるので
x次乗みたいな考え方をします
その場合より正確に書いていくと
さっき言った4とか5みたいな数字が出てくると思うんで
5xの次乗を足す10x足す2みたいな
そういう形に計算量自体はなると思います
ただし最高次数
つまりこの場合だと
xの次乗が一番大きくて
次が10のxで
最後がxがない状態なので
最高次数である
まず5xの次乗だけを考えて
残りの少ないやつに関しては
Ippei Usami
切り捨てます
さらに係数
今回だと5xの次乗なんですけど
5をなくします
つまりこれの計算量は
xの次乗
nを使うことが多いので
oのnの次乗
Ippei Usami
っていう考え方になります
計算量は
今チキした方がいいって言ったんですけど
まずはやっぱ問題なんで
解くことが重要なので
計算量云々は
解いて後に考えることが良いかなと思ってて
ほとんどの問題は層あたりで解けば
大体は解けるはずなので
まずは解きましょう
二分探索の計算量
解けた後に
計算量っていうのを考える
っていう習慣を作るのが
いいかなって思います
この
5以外は落とすとか
係数を無視するっていうのが
僕もこれ最初意味が分からなかったんですけど
なんでこれをこういう風に考えられるか
Ippei Usami
っていうのが一つが
nで回した時の回数と
nの次乗の時の回数みたいなのを
比較した数字があって
例えばnを100回回した場合に
もしそれが20ループになってて
nの次乗だったら
そのループが何回回るかというと
1万回回るんですよね
ここが例えば2
Ippei Usami
つまり
20ループじゃなくて
20ループが2回回るだったら
200回にしかならないわけなんですよね
だけどnの次乗だったら
1万回になるんですよね
200回と1万回って
もう言ったら誤差みたいなもんだので
そこは気にしなくてもいいだろう
Ippei Usami
っていう考え方なんですよね
だからこの上に書いてあるような
log n n n log n n 次乗
かどうかっていうのは
気にする必要があると思うんですけど
これが5nなのか10nなのかっていうのは
基本的にはさっぴいて考えてしまえば
Ippei Usami
良いっていう考え方です
1問目をやめた理由はなぜかというと
あれ2nで解けるんですよね
20ループにした場合
そうすると計算量の話をした時に
Ippei Usami
nの次乗じゃなくてnになってしまうので
多分nの解き方
最適な解き方
最速の解き方なので
ちょっとこの説明をするのに
あんまり良くないなって思ったので
Ippei Usami
今回はあの問題をちょっと変えました
実際グラフで見ると
すごく分かりやすいと思うんですけど
nの次乗の時は
もうまっすぐに進まずに
反比例的に進んでしまうので
実際これでも100回がnの次乗だったら1万回
1万回ぐらい回すことって
全然あると思うんですけど
1万回だったら100万回を越してしまうので
実践ではほぼほぼ使えないんじゃないか
っていうレベルになります
なので理想論として
計算量を求めるときっていうのは
n二乗以上だと
そのループを1万回回すってなっただけでも
100万回回るので
実践的には結構使いづらい状態になってしまうので
できればnログn以下を目指すのが
Ippei Usami
いいとされています
nログnだったら1万回回しても
13万回
これでもちょっと多いんですけど
実践で耐えるぐらいなのかなっていうのが
Ippei Usami
このグラフの考え方なので
でもさっきも言った通り
細かい2nとかはわりとどうでもいい
っていう考え方をしないといけない
話し手1はいどうぞ
Ippei Usami
話し手2はい
話し手21個前の計算だと
2nで解けるか分かりません
話し手2ああ
えっと1問目って
ここ多分2個見ればすぐ
一緒にある問題
話し手2ああ
だから
Ippei Usami
話し手21問目?ごめんなさい
話し手2今回リードコードの
1問目じゃなくて
Ippei Usami
107問目にしたじゃないですか
167問目にしたじゃないですか
Ippei Usami
話し手2最初に出てた
話し手2あの問題って
ここが2で解けるんですよね
ナムレンジじゃなくて
ここが2になってしまうと
ここの計算量って
Ippei Usami
Oの2になっちゃうんですね
話し手2定数になっちゃうってこと?
話し手2そうそう定数になっちゃう
だから2nになるんで
このn事情にならないんで
話が静かになるんでやられました
そういう話で
Ippei Usami
話し手2そうだったよ問題が
私に言い忘れてたんだ
言い忘れてたんだ
話し手2わかりません
はい
話し手2言い忘れてた
話し手2元の問題いきましょうか
Ippei Usami
話し手2元の問題は
話し手213の1
リードコードの1
Ippei Usami
話し手2今回の問題1番ですよね
話し手2はい
これは
まずこの数字全部をループで回して
そのループの中で2個
Ippei Usami
次のだけ見れば多分解けるんですね
話し手2高いで
話し手2はい2回ですね
話し手2でもワーストケースでは
Ippei Usami
M以上じゃないんですよね
話し手2そうだね
話し手2多分ちょっと今パッと
Ippei Usami
話し手2そう
ワーストケースの条件
話し手2はい
話し手2M以上じゃないの
話し手2M以上ですね
話し手2M以上でしか解けないなと
これだけ見るとダメなはず
話し手2ダメでしたっけ
Ippei Usami
話し手2問題が多分
324と悩んでた場合
3つに2見れば
Ippei Usami
終わるってわけではない
話し手2最悪ケースは
今日全部知られた
話し手2これじゃ解けなかったでしたっけ
話し手2全部舐める必要性は少なく
Ippei Usami
2問目は全部舐めないと
話し手2じゃあ僕の勘違いかも
Ippei Usami
失礼しました
これで解けると思ったけど
Ippei Usami
これじゃ解けないのか
話し手2それはできないパターンがあります
Ippei Usami
1問目は少ないと思って
今さっき言ったのが
大正論だったら報道でしか解けないと思う
話し手2なるほど
僕多分いろいろやった時
勘違いしたのかもしれない
1問目でもよかったんですけど
あえて違う問題にしたのは
Ippei Usami
それはそれで面白いかと思った
話し手21問目だと
1問目にならないより
効率よくならないよなと思って
話し手2はいはいはい
ごめんなさいちょっとミスりました
でもう一つと
で結構これ重要な注意点なんですけど
ライブラリを使ったり
リンクを使ったりすると
Cシャープで書けると思うんですけど
そのライブラリも
当然中では計算してますと
だから一見この上のやつ
二重ループに見えない形だと思うんですけど
ファーストってどうやって実装するかっていうのを
ちょっと考えてみると分かるんですけど
ファーストってその数字が出てくるまで
ループで回して
見つかったら終わるってやるんですよね
ってことはループを書いてるんですよね
つまりこの一見一重のループしかないようにやって
内容的にどうやって考えるかと
二重ループになってるので
計算量はNの事情になります
なのでライブラリ使うときは
ライブラリの計算量も若干意識する必要があります
アルゴリズム問題解くときは
縛りプレイでライブラリ使わない
みたいなことをする人も中にはいるので
そういうことを意識してみると
ライブラリ使うときでも
どれが早いかなみたいなことは
意識しやすくなるかなって思います
ハッシュを使う方法
こっちのテストの方の話なんで
Ippei Usami
遠藤さん計算量さらに早い解き方もしてみたんでしたっけ
はい
じゃあそれを聞きつつ
早いかどうかは実際に測ったわけではないので
これの一個前にCで書いたんですよ
Ippei Usami
Cシャープの解き方を
それからCシャープに移植というか
なるほど
Cシャープから入ったら
遠藤的に書けなかったか
井上さんも計算量で言えばN事情じゃない?
Ippei Usami
多分リンク使ってるだけなので
多分N事項だと思います
多分そう
外の最初ループ回して
Ippei Usami
残りの部分から
ファインドインデックスしてるだけなんで
なるほど
ファインドインデックスの実装が分からないんで
あれなんですけど
リンク使ってるから
二つ目です
Nログ2
Ippei Usami
NログN
バイナリーサーチを
配列が小順という前提で
バイナリーサーチを使います
同じように配列を順に舐めていって
Ippei Usami
そこから
次の要素から最後までの間で
数値を探します
探す数値はターゲットマイナス
今のインデックスの数値で
計算できます
ナンバーで配列から
バリューでファインドという
Ippei Usami
数値を
iから
iじゃないな
iプラス1
修正すると
iプラス1から
最後の要素
バイナリーサーチをしていきます
Ippei Usami
それがファインドインデックスという
リソットです
リフトとライトのインデックス
を順にして
Ippei Usami
センターを探して
そのセンターのインデックス
求める値が大きいか小さいかで
Ippei Usami
どんどん
インデックスを変えていきます
最後まで計算して
Ippei Usami
センターのところが
インデックスの値が
Ippei Usami
求める値と同じだったら
インデックスを加えします
見つからなかったら
Ippei Usami
ルールを変えます
という風にして求めます
2分探索で
要素が5個あったら
真ん中を見に行って
大きいか小さいか見て
大きい方にあればこっちに行って
というので
Ippei Usami
ポンポンポンで行けるという話です
それは計算量でいうと
ログNですよね
ループで回せるので
NのログNなので
Ippei Usami
NログNで入ります
これ多分相当されてなくても
Ippei Usami
NログNなんですねきっと
相当されてないってことじゃないですか
同じ相当を最初にかけてしまう
Ippei Usami
相当されてしまうってことですね
NログNです
Ippei Usami
NログNにNログNを足しても
多分NログN
素晴らしい
その通りです
相当は相当の種類によって
計算量に変わるんですけど
基本的にはワーストでもNの事情
最速でもNログN
多分Nで相当する方法って
ラッキーパターンならあるかもしれないですけど
計算量は必ず最悪で考えるので
一番悪いケースで考えると
NログNより速い相当アルゴリズムは
Ippei Usami
僕がしてる限りではないはず
なので他がどういうことをしてようが
NログNよりは速くできないんですけど
今回相当しなくても解ける問題だったし
相当できる問題であっても
最初に相当してしまえば
計算量がNログなので
Ippei Usami
NログNまで落とすことは可能です
アルゴリズムの計算量の比較
Ippei Usami
これはNログNで解けるという感じで
コードマネーかけてるのは素晴らしいです
確かにコードマネーかけなかった
そうですよね
NログNで解けそうな感じ
Ippei Usami
二分の短冊で
さらに3問目も出てる
これだった
ハッシュを使う方法
多分大西さんが言ってた
リクシュナリーを使うという
Ippei Usami
リクシュナリーですね
リクシュナリーを最初からのものを用意して
最初何も要素がないので
Ippei Usami
値が入っていたら
ちょっとここ置いといて
まずは
フェアとなる値
ターゲットマイナス
現在の要素で計算できるので
これをキーとして
ここに入ってなかったら
Ippei Usami
インデックスを突っ込みます
次回次の要素に入った時に
インデックスの
ナンバーか
数
要素をキーとして
この要素
次のインデックスの要素をキーとして
それがあったら取得できたら
その値が
Ippei Usami
求められた値に
キーにして
分析します
Ippei Usami
素晴らしい
Nになるはずなんですが
ハッシュという
基本的にはNなんですか
Ippei Usami
そうです
ハッシュはNじゃなくて
O1かな
N回のループと
ハッシュはOの1なので
両方合わせてもONなので
Ippei Usami
これはNで解けてます
素晴らしい
僕もこれNで解いてやったので
Ippei Usami
ほとんど一緒です
どっちの解き方でもそんなに変わらないですけど
先にディプショナリーに
値を突っ込んでおいて
もう一回ループ回して
トライゲットバリューで回すという形をしてます
唯一同じ時があるので
その時だけ弾いてやれば
Ippei Usami
この形でONで回すことができます
これは割とNのロジックとほとんど一緒かなと思います
もう一つ計算量の話をクラスでします
計算量というのは実は二つあります
一般的に計算量と言ったら時間計算量
つまり何回もONすか
どれくらい時間がかかるかという考え方をします
もう一つ計算量という考え方は空間計算量
Ippei Usami
これはメモリをどれくらい使うかという考え方をします
実際最初の解き方だと
メモリをほとんど使っていない
これはメモリを全く使っていないので
時間計算量はOのNの事象
Ippei Usami
空間計算量はこれはOの1になります
さっきの江藤さんと僕の解いたやつ
これに関しては時間計算量はOのN
Ippei Usami
空間計算量はDictionaryにとって
配列の要素の数分だけのDictionaryが送られるとなると思うので
空間計算量もOのNになります
今日の8時半まででしたっけ 30分早めたけど
終わる方向に行った方が多分いいですよね
ちなみにこの2SUMは時間計算量はON
Ippei Usami
空間計算量はOの1で解く方法があります
つまりDictionaryを使わなくても解けます
これ解いてきたんでどうしようかな
今言うか考えますかみたいな話ですけど
ネタバレするかどうかどっちでもいいですよ
ヒントはポインター的な考え方をして
1個ずつ見ていくときに最初と最後
両方から見ていくという考え方をすると
Dictionaryを使わなくても解ける
Ippei Usami
最初と最後はわかんない
想定されている前提ですか
基本的にはそう
Ippei Usami
一応誤解として想定されている前提なんで
本来であれば見なくていいやつは確かに省ける
そうです
今日は誤解言っちゃいましょうか
これが時間計算量がONで
Ippei Usami
空間計算量がOの1の解き方です
レフトとライトを持って
レフトは点灯
ライトは前に回します
それで1個ずつ見ていって
最初と最後の合計値は終わりだし
違った場合はどっちが正しいかを見て
状況を進めていく
というのを繰り返すと
Dictionaryを使わなくても進むので
空間計算量としてはメモリを使っていないので
メモリを使うように解くことができる
空間計算量は
普通の仕事でやっているときに
気にすることは基本的にはないかなと思うんですけど
アルゴリズムの問題を解くときは
より最善の解き方をしたほうがいいとされているので
時間計算量は早いけど
空間計算量をたくさん使うよりは
どっちも少ないというのを目指していくと
今回の問題に関しては
Ippei Usami
これがベストアンサーかなって思います
リートコードだけじゃないかもしれないけど
Ippei Usami
こういうサイトでお金払ってなかったら
貧弱なメモリとか貧弱なCPUとか
こういうやつがあるので
Ippei Usami
何も考えずに全部にして突っ込んだりすると
計算がずっと時間がかかってしまったりして
Ippei Usami
時間切れになって
もしあったとしても
タイムオープンとかになりますか?
なります
さっきの表の話で
それこそNの事情みたいな解き方をしていると
そもそもリートコードでタイムアウトだって解けないやつとかがあって
これは多分NログN以上にすれば解けるんですけど
現実感覚が高まらないことがあるので
まずさっき言った通りNの事情で解いてみる
これはすごい大事な考え方なんですけど
問題によってはリートコードは
それ以上全問正解できないようなケースがあるので
NログN以下を目指しましょう
空間計算量は
こういうアルゴリズム問題を解くときの
何て言うんだろう
模型ぐらいの可能性で考えてもいいと思うんですけど
より良い解き方が基本的にはあるかなっていうのを
突き詰めていくと
Ippei Usami
こういう空間計算量も下げるという解き方になります
今日はこんな感じで
テストの書き方とかで
いくつか紹介しようかなと思ってたやつとか
オーナークリップページみたいなのも作ってきたんだけど
これもぜひやればいいかなと思っているので
次回何にするかはまだ決めてません
イージーをもうちょっと繰り返してやるか
2問目ミディアムみたいな問題を解いていくのが
いいかなって思ってて
次回初参加の人がいなかったら
2問目でもいいかなって僕は思ってました
初参加の人がいるんだったら
イージーの方が多分いいかなって思ってて
計算量の話は初参加の人がいたら
僕は必ずしようと思っているので
ペース的にはゆっくり進むことになるかもしれないし
さっきチラッと言った
いろんなテストの書き方の作法みたいなことも
その一つとその二つを盛り込んでいったら
いいかなと思っているので
パターンによってはアルゴリズム自体の解説をした方が
いい時とかも多分出てくると思うので
そういうのをやりつつ
実際にみんなで解いた上で
次回の予定とアルゴリズム問題へのアプローチ
コードについていろいろ話すみたいな会議ができたら
いいかなって思ってます
はい、そんな感じで
Ippei Usami
今日はありがとうございました
