Kaigi on Rails 2023に登壇して、Seedデータをいい感じに整備する話をしました
アーカイブ公開されました🙇♂️
発表内容について
発表資料はこちらです!
seeds.rbを地道に書く代わりに、ローカルのアプリを操作していい感じのデータを整えて、それをCSV出力して次回からSeedファイルとして使えばいいのでは?みたいな話をしました!
弊社ではHerokuのreview-apps(Pull Request毎の検証環境)をかなり活用しているのですが、ビルド直後のSeedデータが不十分なためにチーム全体の開発効率が落ちている感覚があり、それを解決するために取り組んだのが今回の発表内容です。
サンプルコードはこちらです。
もしお手持ちのアプリで試される場合、db/seeds.rbの調整が必要になりそうです。 弊社アプリでは、日付だけでなく曜日の差分調整処理を入れたり、Shrineの画像アップロード処理を入れたり、なども実は行っています。
発表を終えるまでの振り返り
プロポーザル提出
RubyKaigi 2023のKaigiEffectを受けた頃からこのネタを提出しようかなと考えていたので、プロポーザルを書くのは割とスムーズでした。大倉さんのアドバイス通り、detailsまで入念に書いたのが功を奏したのか、めでたく採択していただき、技術系カンファレンスに初登壇させていただくことになりました。
資料作り
DB試験後の10月2週目あたりから始めました。こちらも思ったよりスムーズに進められましたが、「もしかしたらめちゃくちゃ訳の分からないことを言ってるのでは?」みたいな思いが常にあり(今もありますが)、他の人に見劣りしないか不安でした。しかし、少なくとも社内でapproveされて業務に貢献できていること、合議制の審査でdetails込みで採択していただいていることから、価値があると信じてやるしかないなという感じでした。
社内(上司の@geeknees、私と同じくFBC出身の@haruna_tsujita)で2回、家庭内(ESMの@kasumi8ponがいます)で2回のリハーサルをしました。「神は細部に宿る」という言葉が好きなのですが、いろんな視点からフィードバックをいただけたおかげで入念に修正し、完成度を一段階上げることができました。
発表当日
登壇の1時間くらい前からそわそわしてました。当日は台本を読むだけ、時間配分も完璧という状態でしたが、緊張する原因は発表内容の不安から来ているので、今さらあたふたしても仕方のないことでした。最前列あたりに日頃からお世話になっている方々が来てくださったのが心強かったです。発表は無難に終えられました。もしまたこのような機会があれば、その時はもう少し遊びを取り入れられる気がします。
発表後
X(旧Twitter)、それから対面でも色々な反応をいただけて嬉しかったです。中でも、@makicamelさんにお声掛けいただき、お互いの発表について気付けば30分ほど話し込んでいたのが一番印象に残っています。何年も前から、私が一方的に発表を拝見しているような方なので、このような時が来るとは想像していませんでした!
これネガティブな意味ではなくて、しおいさんとは別の方向性で貢献できる方向を見つけつつあり、kaigionrailsもその一つなのでありがとう最高!!!という意味です😂 https://t.co/lShcbA4iRW
— ごぐたん (@gogutan) 2023年10月28日
こちらはその時のこぼれ話です!
振り返ってみて
2020年12月に株式会社キャタルに入社し、実は今月からテックリードになりました。
偉大な先輩が何人もいるので、この方々と比べて自分は価値を出せていないのではないか…と思うことが度々あったのですが、最近はもう少し気楽で、まあプロダクト開発はチームプレイだし、各々が強みを活かして全体でいい感じになればいいよな〜くらいの気持ちで構えています。
そんな中で今回のKaigi on Railsにて、データベース周り、全体最適化、みたいな自分の興味分野で登壇させていただくことができ、一つの節目になった感があります。 前職を退職後に充電期間、フィヨルドブートキャンプを経て、Webエンジニアとして約3年、まあまあ遠いところまできたなという感じです。
このような素敵な機会をくださったKaigi on Railsの運営、スポンサー、携わってくださった全ての皆様ありがとうございました!!
RubyKaigi 2023に行ってきました!
2回目の参加でした! 非常に良い体験でしたので、印象的だった出来事やセッションを中心に振り返りたいと思います。
0日目
ありがたいことに弊社から4泊5日の旅程をお許しいただきましたので、今回はKeebKaigi 2023に参加する @kasumi8pon とともに前日入りをしました。
Ready for RubyKaigi! pic.twitter.com/7EyveMVUWw
— ごぐたん (@gogutan) 2023年5月10日
まず私たちを出迎えてくれたのは、松本駅のRubyist歓迎横断幕でした!わくわく感が高まります。このように地域との連携を密に開催されるのは、やはりRubyKaigiならではの特色なのでしょうか。今回のRubyKaigiでは、地域の飲食店で使える3000円分のバウチャークーポンが参加者に配られましたが、こういった丁寧な施策の一つ一つがRubyKaigi全体の体験を素晴らしいものにしているのだと感じました。
バウチャーがお店で使えるの、金銭的なメリットもあるけどそれ以上に地域に受け入れられてる感が嬉しかった。お店に入ったら「RubyKaigiですか?」って聞いてもらえたり。
— 🎹 (@p_ck_) 2023年5月14日
バウチャークーポンを使った飲食は確かに心地良かったです!こういった期間限定の施策って、現場の方々まで行き届いていなかったり(例えばクーポンを出したら「なんだこれ?」という顔をされたり)といったことが起こりがちだと思うのですが、どの飲食店でもスムーズに受け入れてくださりました。ささいな点ですが、こういった心遣いが浸透しているのも嬉しいですね。
1日目
想像以上のRubyistの多さに圧倒されました!!!昨年も現地とオンラインのハイブリッド開催でしたが、コロナ禍真っ只中につきどちらかと言えばオンライン寄りといった印象でした。しかし今年は会場にて圧倒的多数のRubyistを目の当たりにし、Rubyコミュニティのパワーを改めて感じ取りました。
Matz Keynote
Matzのブラックジョークを嗜みつつ、MatzとともにRubyの30年間の歩みを振り返るキーノートでした。調べてみたところ、私がRubyを書き始めたのは2019年4月でしたので、Rubyの歴史と比べるとまだまだひよっこ、私が知らないRubyの発展の経緯もたくさんありました。全体としては、Matzと熱心で優秀なRubyistたちによってRubyは発展を続けていて、それによって私は人生が救われるほどの恩恵にあずかっており、感謝してもしきれないということを感じました。前職をやめた後に出会った言語がRubyでなかったら、私はWebエンジニアになれていなかった可能性が高いです。
Flat earth believerとして生きていく #rubykaigi
— ごぐたん (@gogutan) 2023年5月11日
これは地球平面説信者のように頑なに型を書かないRubyを揶揄した言葉ですが、これからもMatzとともにFlat earth believerとして生きていきたい所存です。
なおこちらは私が書いたほぼ最古のRubyのコードです。歴史が感じられます。
Submission #5074887 - AtCoder Beginner Contest 086
# 整数の入力 a,b =gets.chomp.split(" ").map(&:to_i); # 偶数か奇数の判定 if a % 2 == 1 && b % 2 == 1 print("Odd") else print("Even") end
Make Regexp#match much faster
ReDoS(処理に時間のかかる正規表現を用いた攻撃手法)の概要と、それを避けるためにRubyの内部実装を改善して多くの処理をO(N)
まで落としたこと、今後の展望(処理に時間がかかる正規表現には警告を出せるようになるかも、DFAを用いた実装でさらに高速化したい)といった内容で、競プロerとしてかなりときめくタイプのお話でした。正規表現はオーダー数が読みにくく難しいケースがありますが、我々が意識することなく高速化の恩恵を受けられるのは実用的で助かります。Ruby 3.2にはRegexp.linear_time?
でO(N)
かどうか確認できるメソッドが追加されているとのことで複雑な正規表現を描いた時には試したいと思います。
UTF-8 is coming to mruby/c
UTF-8をfrom scratchでmruby/cに実装されるというお話です。私は文字コードには全然詳しくないですが、ストーリーや視覚的な工夫が随所に見られて引き込まれました(Before implementationからのバイト数の見分け方など興味津々でした)。人それぞれ興味が異なるのってめちゃくちゃ面白いですよね。満遍なくやろうとすると「やらなきゃ…」の後ろ向き思考になりがちですが、強みを伸ばすのって本当に大事だなと考えていました。
2日目
Implementing "++" operator, stepping into parse.y
Not a parser expertとして拝聴しました!しおいさんのお話は試行錯誤を追っていく冒険感があって好きです(勝手にしおいメソッドと呼んでいます)。Integer#succ
のエイリアスっぽく呼んでみたらどうだろう〜とか、Not a parser expertでも(全然分からないけど)入り込んでいける仕掛けがたくさんあり面白かったです。
Optimizing YJIT’s Performance, from Inception to Production
今回1番の感銘を受けたのがこちらのKeynoteでした。YJITにかけるShopifyの皆様の尽力が私の想像を超えており、Maxime個人の大学時代の研究まで遡ると数え切れないほどの年月とのことでした。技術的なことは雰囲気だけ(ベンチマークが難しいとかコンパイルの優先度の戦略があるとか)しか理解が及びませんでしたが、とにかく難しそうなことは分かりました。にもかかわらず、lazyな私たちのために簡単にパフォーマンスを改善できるように日々尽力されているとのことで頭が上がりません。
3日目
Ruby Committers and The World
Rubyの長期的な展望をなんとなく把握しつつ、コミッターの皆様がわいわいするのを見ることができるセッションです。話題が多岐にわたり、ほぼ全編英語とのことでかなり難しくはありますが、2日目のEN Keynoteと同様、コミッターの皆様の苦労話や日々の考えに直接触れられる機会というのはそれだけで貴重です。
Parsing RBS
エディタが何もかもいい感じにやってくれたらとても幸せ、実演デモが興味深かったです。難解なところは「Soutaroさんのイギリス英語っぽい発音かっこいいな〜」と思いながらふわふわ聞いていたことを告白いたします。
イベントなど
公式的なイベントには
- RubyKaigi 2023 Official Party(Day 1)
- RubyKaigi 2023 After Party sponsored by STORES(Day 3)
- RubyMusicMixin 2023(Day 3)
の3つに参加しました!いずれも素晴らしかったですが、特にDay 3の2つではRubyKaigi終了後の開放感もありコミュニケーションが捗りました。
RubyKaigi 2023 After Party sponsored by STORES
人がかなり多く会場が手狭だったのですが、料理とお酒はおいしかったですし、慣れたあたりでいろんなお話ができました。
今日はつなぐ横丁でオーストラリアの方と3分くらい話したので、DMM英会話をサボってもセーフとします
— ごぐたん (@gogutan) 2023年5月13日
おかげで元気に生き延びています、命の恩人ありがとう!!!しかもこの前、私の友人もフィヨルドに誘いました!!!!!Rubyの輪が繋がってます!!!!!!!!!
— ごぐたん (@gogutan) 2023年5月13日
@risacan に人生救われた人々の集いが発生したり、@imaharuTech と遭遇して共通の知人である @shifumin (私にとっては昔からのぷよぷよ友人)について語ったり、フィヨルドブートキャンプでお世話になった方々や @kasumi8pon が普段お世話になっているESMの方々とも話が弾みましたし、想像以上に楽しみました!!もしかしてこれがRubyKaigiの力なのか……?
RubyMusicMixin 2023
ガチで最高のイベントはじまった pic.twitter.com/DTIQHvPaIS
— ごぐたん (@gogutan) 2023年5月13日
pixivだいすき #RubyMusicMixin2023 pic.twitter.com/xb9yLYAxz8
— ごぐたん (@gogutan) 2023年5月13日
そして極め付けはこちらのクラブイベント。音ゲーマーなので爆音を浴びつつお酒を飲むだけで意味分からないくらい楽しくなってしまいました。しかもRubyistしかいないという異様な空間で、爆音のため人間の話す言葉は5%くらいしか分かりませんでしたがとにかく最高でした。pixiv本当に大好き。
松本のご飯とか
ビールいただきました!!!! #rubykaigi pic.twitter.com/WVxT5uVQaX
— ごぐたん (@gogutan) 2023年5月12日
ホテルブエナビスタのバイキングに @igaiga555 さんに連れて行ってもらいました🙇♂️🙇♂️めちゃくちゃおいしかった〜! pic.twitter.com/DLIOIcEPLh
— ごぐたん (@gogutan) 2023年5月13日
どう見ても電器屋さんで休憩しています #rubykaigi pic.twitter.com/gcc7BMbtFu
— ごぐたん (@gogutan) 2023年5月13日
satisfying pic.twitter.com/BEeuoChg3u
— ごぐたん (@gogutan) 2023年5月14日
冒頭にも挙げましたが、松本を存分に満喫しました。とにかく街がオシャレでご飯がおいしいという印象です。また来たい!そして来年は沖縄!
#kaigieffect
英語をやるぞという人をたくさん観測しました!実は私も最近また英語に取り組んでいます。やはり人間同士の会話はAIによって代替することのできない価値のある体験だということで、意識的に英会話に振っています。そしてKaigi on Rails 2023に何か出してみたいなという機運もあります。やっていくぞ!
まとめ
ここに書き切れない素敵な体験が他にもたくさんありました!RubyKaigiに携わってくださった全ての皆様、本当にありがとうございます。Rubyコミュニティっていいな〜。最近、友人を2人フィヨルドブートキャンプに招待したのですが、より自信を持って勧めることができるようになりました。とにかくRubyに出会えて良かったです。
コマンドラインで遊べるぷよぷよ one-puyo の npm モジュールをリリースしました
ぷよぷよは、同じ色の「ぷよ」が 4 つ以上くっつく(上下左右に隣接する)と消えるパズルゲーム。2019 年には国体の文化プログラム競技タイトルとして採用されるなど、今最も熱い eSports の 1 つ!
one-puyo は「なぞぷよ」(ぷよぷよにおける詰将棋のようなもの)のシンプル版で、ぷよを 1 つ置くだけで連鎖を楽しめるミニゲームです。
公開場所
必要なもの
Node.js のインストール
遊び方
「連鎖のタネ」が表示されるので、どこかの列に 1 つだけぷよを置いて連鎖を作り、画面上の全てのぷよを消すことができればクリア。
オプション
-e
(Easy…3 連鎖問題)
-n
(Normal…4 連鎖問題: デフォルト)
-h
(Hard…5 連鎖問題)
-s
または-t
(5 問連続で解くタイムアタックモード)
絵文字の表示について
macOS Terminal 以外の環境では、絵文字の代わりに色付きの記号で動きます。
問題生成について
フィールドにいい感じにぷよを設置(3 連鎖問題なら、緑を 3 個、赤を 3 個、青を 3 個、緑を 1 個、赤を 1 個の順番で置きつつ、同じ色は列が離れすぎないようにするといった感じ)
ぷよの設置→連鎖発火を全通り試す
全部消せた選択肢があればOK、なければやり直し
のような、割と力任せの実装です。
計算量オーダーは、
フィールドの高さ: H
フィールドの幅: W
連鎖数: C
ぷよの種類: N
とすると大まかに、
フィールド生成: O(C * N)*1
設置全探索: O(W * N)
連鎖発火: O(H * W)
全体: O(C * N2 * H * W2)
となり、H = 10, W = 6, C = 4, N = 4 とすると、1 回のフィールド生成には O(23040) の重めの定数倍処理がかかるはずです。
よって許容できる計算量オーダーを O(10 ^ 7) とすると、400 回程度のフィールド生成には耐えてくれそうなので、まあ 400 回も試したら問題作れるでしょ!ということで実装しました。(これ完全に AtCoder だ…元々は問題テンプレートを用意するつもりでした)
実際に動かしてみると、4 連鎖問題までは一瞬、5 連鎖問題は 1 〜 2 秒程度の生成時間がかかります。タイムアタックモードだと回答中に問題を先読みするので、5 連鎖問題でも割と快適に遊べると思います。
学べたこと
JavaScript の基礎的文法から非同期処理までざっと習得できました。今 Vue.js の学習をしていますが、おかげでスムーズに進められています。
遊んでみた感想
問題生成機能を付けたらかなり面白くなりました!ぷよぷよ初心者でも、お手軽に連鎖の爽快感が味わえると思います。
ぷよらー的にはタイムアタックモードも面白いのですが、記録を狙うと「何か消えそうなところにとりあえず置いてみる」になりがちなので、「生成された問題をじっと見つめてみる」のも面白いなと感じました。たまに「なるほど……」と思うような連鎖が出てきます。😊
今後の機能追加について
さらにアルゴリズム力が高まったら -l
(Lunatic…6 連鎖以上の問題)を追加したいです!
*1:落下処理を使って毎回上から 1 個ずつ降らせていたため O(C * N * H) でしたが、高さをメモして O(C * N) に改善しました。
Ruby の delete_ats メソッドを書いた(配列の複数要素を O(N) で高速に削除)
何をしたいか
配列の添字を複数同時に指定して、下記のようにまとめて削除したい。
array = [3, 6, 1, 9, 7, 8] array.delete_ats([1, 3, 4]) array #=> [3, 1, 8]
さらにこの計算量を改善して、高速に動かしたい!(計算量やオーダー記法 O(⋅) については、参考ページを最後に掲載しました)
実装
オープンクラスを使って、見かけ上同じ動きをするメソッドを Array クラスに4つ追加してみました。
class Array # being_deleted must be sorted # 後ろから順番に削除(頭から削除すると、削除の度に添字がずれるため) # O(N^2)? def delete_ats_1(being_deleted) being_deleted.reverse.each do |deleted| self.delete_at(deleted) end end # being_deleted に self の index が含まれる場合は削除(線形探索) # O(N^2) def delete_ats_2(being_deleted) self.delete_if.with_index do |_, i| being_deleted.include?(i) end end # delete_ats_2 を改善 # being_deleted に self の index が含まれる場合は削除(二分探索) # O(NlogN) def delete_ats_3(being_deleted) self.delete_if.with_index do |_, i| being_deleted.bsearch { |deleted| deleted >= i } == i end end # self と being_deleted を順番に回しつつ、削除しない物を tmp に詰める # O(N) def delete_ats_4(being_deleted) tmp = [] current = 0 self.each_with_index do |a, i| if being_deleted[current] == i current += 1 else tmp << a end end self.replace(tmp) end end
ベンチマーク
実装
require 'benchmark' require_relative '../lib/delete_ats.rb' ARRAY_SIZE = gets.to_i array_1 = (0...ARRAY_SIZE).to_a array_2 = array_1.dup array_3 = array_1.dup array_4 = array_1.dup being_deleted = 0.step(ARRAY_SIZE - 1, 2).to_a Benchmark.bm do |x| puts ("ARRAY_SIZE: #{sprintf("%.0e", ARRAY_SIZE)}") x.report("1:") { array_1.delete_ats_1(being_deleted) } x.report("2:") { array_2.delete_ats_2(being_deleted) } x.report("3:") { array_3.delete_ats_3(being_deleted) } x.report("4:") { array_4.delete_ats_4(being_deleted) } end
配列の要素を 1 つずつ飛ばしながら順番に削除し、その実行時間を計測します。
結果比較
配列サイズ 10 ^ 4
user system total real ARRAY_SIZE: 1e+04 1: 0.002244 0.000012 0.002256 ( 0.002352) 2: 0.259646 0.001245 0.260891 ( 0.264851) 3: 0.007171 0.000162 0.007333 ( 0.007628) 4: 0.000715 0.000032 0.000747 ( 0.000747)
配列サイズ 10 ^ 5
user system total real ARRAY_SIZE: 1e+05 1: 0.213257 0.001253 0.214510 ( 0.216350) 2: 25.813206 0.159038 25.972244 ( 26.720222) 3: 0.087369 0.000814 0.088183 ( 0.090878) 4: 0.007199 0.000207 0.007406 ( 0.007442)
delete_ats_2
は O(N2) のため、ここでオーダー数が 1010 に達してしまい、許容時間を超えてしまいました。
配列サイズ 10 ^ 6
user system total real ARRAY_SIZE: 1e+06 1: 28.544373 0.241101 28.785474 ( 31.156171) 3: 0.941576 0.006753 0.948329 ( 0.960607) 4: 0.074461 0.002314 0.076775 ( 0.077585)
delete_ats_1
も O(N2) 相当の計算量かと思いましたが、delete_at
メソッドが思ったよりも早く動きました。しかし配列サイズ 105 までが限界のようです。
配列サイズ 10 ^ 7
user system total real ARRAY_SIZE: 1e+07 3: 11.047709 0.104127 11.151836 ( 11.707355) 4: 0.749899 0.028396 0.778295 ( 0.805788)
O(NlogN)の delete_ats_3
は配列サイズ 106 が限界です。
配列サイズ 10 ^ 8
user system total real ARRAY_SIZE: 1e+08 4: 7.132723 0.149687 7.282410 ( 7.398004)
O(N)の delete_ats_4
も配列サイズ 108 はさすがに厳しかったです。
まとめ
計算量を O(N) まで落とした delete_ats_4
のメソッドであれば、配列サイズ 107 程度まで、添字を複数同時に指定して素早く要素を削除できるようになりました!
※添字は事前に昇順でソートされている必要があります。
※マイナスの添字には対応していません。
テストコード
こんな感じで簡単にテストを動かして、全てのメソッドの動作を確認しました。👀
require 'test/unit' require_relative '../lib/delete_ats.rb' class TestDeleteAts < Test::Unit::TestCase def setup @array = [3, 6, 1, 9, 7, 8] end def test_delete_ats_4 @array.delete_ats_4([0, 3, 5]) assert_equal @array, [6, 1, 7] end def test_delete_ats_4_when_including_exceeding_index @array.delete_ats_4([0, 3, 5, 6]) assert_equal @array, [6, 1, 7] end def test_delete_ats_4_when_index_is_empty @array.delete_ats_4([]) assert_equal @array, [3, 6, 1, 9, 7, 8] end end
参考ページ:計算量(オーダー記法)について
要素数やループ回数などをオーダー記法 O(⋅) で表現することで、プログラムの中でどこが実行時間のボトルネックとなるかがわかり、実行時間を当てずっぽうではなく高精度で予測することができます。 ざっくりとした一例を挙げると、Ruby では 107 の一重ループが実行時間的に限界です。
Ruby の破壊的メソッド( uniq! など)が nil を返す場合について
破壊的メソッドとは
レシーバ自身を変更するメソッドのこと。下記コードではshuffle!
が破壊的メソッドで、レシーバ自身の中身をシャッフルしています。そのため、配列のobject_id
はシャッフル前と同じです。
一方、shuffle
は非破壊的メソッドのため、新たなobject_id
が生成され、そこにシャッフルされた配列が格納されています。元の配列の中身は、シャッフル前と変わっていません。
array = ["A", "B", "C", "D"] array.object_id #=> 70124212665900 array.shuffle! array #=> ["C", "A", "D", "B"] array.object_id #=> 70124212665900 new_array = array.shuffle new_array #=> ["B", "A", "C", "D"] new_array.object_id #=> 70124212665360 array #=> ["C", "A", "D", "B"] array.object_id #=> 70124212665900
破壊的メソッドの戻り値について
破壊的メソッドは、レシーバ自身の変更を主な目的として使われますが、非破壊的メソッド同様にちゃんと戻り値が返ってきます。そのため、下記のようにメソッドチェーンをして、簡潔にコードを書くこともできます。
array = ["B", "D", "A", "C"] array.sort!.reverse! array #=> ["D", "C", "B", "A"]
破壊的メソッドが nil を返す場合について
ただし、破壊的メソッドが nil を返す場合には要注意です。
array = ["A", "B", "C", "D"] array.uniq! #=> nil array #=> ["A", "B", "C", "D"] array.uniq #=> ["A", "B", "C", "D"]
uniq!
は重複する要素を削除する破壊的メソッドですが、重複する要素が存在しなかったため、戻り値としてnil
が返ってきました。(戻り値がnil
なだけで、配列の中身がnil
になったわけではありません)
一方、非破壊的メソッドのuniq
は、別のobject_id
を生成し、元の配列と同じ要素の配列を返しています。
これは一見、破壊的メソッドの戻り値が不親切なようにも見えます。しかし、下記のようにレシーバが変更されたかどうかで処理を分けたい場合には便利です。
array = ["A", "B", "C", "D"] if array.uniq! array else "arrayは変更されませんでした" end #=> "arrayは変更されませんでした" array_2 = ["A", "B", "B", "C"] if array_2.uniq! array_2 else "array_2は変更されませんでした" end #=> ["A", "B", "C"]
nil を返すメソッドと、そうでないメソッドについて
このように、レシーバが変更されなかった場合にnil
を返す破壊的メソッドは多くあります。
(例:select!、comact!、flatten!、uniq!、reject!など)
一方、レシーバが変更されることを前提としていて、必ずレシーバ自身を返す破壊的メソッドもあります。
(例:shuffle!、sort!、sort_by!、reverse!、rotate!、delete_ifなど)
sort!
したけど既にソート済みのために順番が変わらなかった場合や、shuffle!
でたまたま元の並びと同じ順番になった場合も、レシーバ自身が返ってきます。
面白いのは、reject!
とdelete_if
の違いです。いずれもレシーバに対する変更の挙動は同じですが、レシーバが変更されなかった際の戻り値が異なります。(reject!
はnil
、delete_if
はレシーバ自身)
とはいえ、どのメソッドの戻り値が nil
になる可能性があるのかは混乱しやすいため、戻り値が必要な時に気を付けるようにすれば良いと思われます。
戻り値が nil であることに気付かないとこうなる
目的:配列の中で、2番目に大きな数字の「種類」を出力したい。(例えば [100, 50, 10, 100] の時は 50 を出力したい)
重複した数字があるかもしれないから、uniq!
で重複を排除してから降順に並べ替えて、2番目に大きな数字を出力するだけだな、簡単〜!
↓
失敗例
numbers = [10, 50, 1, 100] numbers.uniq!.sort! { |a, b| b <=> a } puts numbers[1] #=> 2:in `<main>': undefined method `sort!' for nil:NilClass (NoMethodError)
😇😇😇
上記の例では、配列の中に重複した要素が存在しておらず、uniq!
がnil
を返すためにエラーとなりました。
解決策
numbers = [10, 50, 1, 100] numbers.sort! { |a, b| b <=> a }.uniq! puts numbers[1] #=> 50
sort!
は必ずレシーバ自身を返してくれるので、この順番なら正常に動きます。ただしこれだと重複する要素がたくさんある場合、実行に時間がかかってしまうため、
numbers = [10, 50, 1, 100] numbers.uniq! numbers.sort! { |a, b| b <=> a } puts numbers[1] #=> 50
無理にメソッドチェーンをせずに、こちらのほうがいいかもしれません。
参考
B - 心配性な富豪、ファミリーレストランに行く。 - AtCoder
上記の問題で、何故かいくつかのケースでWA(誤答)が出たためにuniq!
の戻り値について調べていたところ、破壊的メソッドにもいろいろな挙動があることが分かりました。
rubyの破壊的メソッドと非破壊的メソッドのパフォーマンス比較 - Hack Your Design!
なお非破壊的メソッドの場合は、毎回object_id
を新たに生成するため実行速度が落ちる点に注意が必要です。
Ruby 配列における find と bsearch の違い(ブロックの書き方に注意)
配列の中から特定の値を探す時に find メソッドを使うことができますが、配列がソートされている場合には、 bsearch メソッドを使うことでより高速に探索することができます。ここでは、それぞれの特徴と使い方を比較します。
find(線形探索)とは
先頭から順に比較して値を探す方法です。
メリット:ソートされていない配列を探索できる
デメリット:最悪のケースでは、配列の最後の要素まで確認する必要があるため時間がかかる
find の使い方
array = [7, 15, 0, 4, 12, 19, 10] array.find { |x| x == 12 } #=> 12
bsearch(二分探索)とは
ソート済み配列の中央の値を見て、探索したい値が中央より右側・左側のどちらにあるかを判断することで、候補を絞りながら探す方法です。
メリット:配列の要素数が多い場合でも、高速に探索することができる
デメリット:配列がソートされていないと使うことができない
bsearch の使い方(誤)
sorted_array = [0, 4, 7, 10, 12, 15, 19] sorted_array.bsearch { |x| x == 12 } #=> nil
これで find と同じように 12 を探し出して…いません!find と同様にブロックを渡しましたが、これでは意図した通り動かないようです。
bsearch の使い方(正)
落ち着いてリファレンスを参照してみます。
find-minimum モード(特に理由がない限りはこのモードを使う方がいいでしょ う)では、条件判定の結果を以下のようにする必要があります。
求める値がブロックパラメータの値か前の要素の場合: true を返す
求める値がブロックパラメータより後の要素の場合: false を返す
🤔🤔🤔🤔🤔
つまりどういうことか図解すると…
このように、求める値とそれより右側が全て true になるようにブロックを渡してあげると、1番左側の 12 を探し出してくれます!
これを踏まえて、正しいコードがこちらです。
sorted_array = [0, 4, 7, 10, 12, 15, 19] sorted_array.bsearch { |x| x >= 12 } #=> 12
配列が降順にソートされている時
sorted_array = [19, 15, 12, 10, 7, 4, 0] sorted_array.bsearch { |x| x <= 12 } #=> 12
降順でも使えます!
昇順の時と同様、求める値である 12 以後が true になれば良いので、比較演算子を逆向きにしています。
bsearch の使いどころ
- 元から配列がソートされている
- 配列はソートされていないが、何度も探索する必要があるため、前準備としてソートしてしまった方が良い
上記のような状況で効果的です。
備考
AtCoderで bsearch を使うドンピシャの問題(Ruby実装例)があって感激しつつも、思い通りに動く時と動かない時があり少しハマったので、リファレンスを調べて記事にまとめてみました。ソート済みの配列には bsearch !
参考一覧
module Enumerable (Ruby 2.6.0)
instance method Array#bsearch (Ruby 2.6.0)
instance method Array#bsearch_index (Ruby 2.6.0)
添字を取得したい時は bsearch_index が使えます。
AtCoder AGC 033 A - Darker and Darker (図解、Ruby実装例)
問題概要
H × W の盤面があり、各マスは「白(.)」「黒(#)」に塗られている。1 秒ごとに、各黒マスの上下左右に隣接している白マスを黒く塗る。全マスが黒になるのに何秒要するかを求めよ。
例
2秒後に全マスが黒くなるため、答えは2秒。
方針
- 盤面を全探索して、黒マスの上下左右に白マスがあれば黒く塗る作業を繰り返す
- 全ての白マスについて、最寄りの黒マスまでの距離を調べる
などの方法はTLEが予想されるため、
- 黒マスの座標をキューに格納し、上下左右を黒く塗る作業を繰り返す
という方針とします。(幅優先探索)
また、黒く塗るのに要した秒数を管理するため、
- 白マスは -1 (未探索)
- 黒マスは黒く塗るのに要した秒数
とする、数字バージョンの盤面を操作します。
図解
3秒後に黒塗りしたマスは存在しないため、答えは2秒。
Ruby実装例(コメント付き)
Submission #5998528 - AtCoder Grand Contest 033
存在しない盤面の枠外を黒塗りしないように、if文の条件には注意が必要です。
感想
コンテスト中はACを出せませんでしたが、何とか他の方のコード例を解読することができたため、実装して図解多めで記事を書いてみました。
今回は、
- 同じマスを繰り返しチェックしないように、黒マスの座標を格納する配列を用いたこと
- 若い秒数から塗りつぶしていくために、配列(キュー)を用いた幅優先探索を用いたこと
がポイントとなりました。幅優先探索を効果的に使えたのは初めてだったため、なかなか面白かったです。
参考
キューはshift
、スタックはpop
を使って操作します。