ほとんどのリファクタリングは、プログラムに間接的な階層を導入する。つまり、大きなオブジェクトや大きなメソッドを分解して、複数の小さなオブジェクトやメソッドにしている。間接化によって以下のメリットが得られる
- ロジックの共有を実現する
- メソッド名などで意図を説明できる
- 変更箇所を他の部分から分離できる

プログラムが扱いにくくなる要因としては以下の4つがあり、これらが存在した場合はリファクタリングを検討すべき
- 読みにくい
- ロジックの重複がある
- 機能の追加によって、動いているコードを書き換えなければならなくなる
- 条件分岐が複雑

ソフトウェアでは、使われていない柔軟性は悪である。この柔軟性は、メンテナンスのために時間を食い、バグが入る余地を作り、リファクタリングをかけにくくする

リファクタリングの基本的な進め方

リファクタリングを活用してソフトウェアを開発するときには、機能の追加を行う時間とリファクタリングを行う時間をはっきりと区別した方がよい
- 機能を追加するときには、既存のコードを書き換えない。ただ新しい機能を追加することに専念する。最初に失敗するテストを追加し、テストを成功させる
- リファクタリングする時には機能を追加しないようにし、コードの改造だけに力を注ぐ。テストの追加も行わない

リファクタリングというのは、特別な時間を設けてすることではない。他のことをしたいときに、リファクタリングをすると役に立つので行うというものである

バグレポートを受け取ったら、まずバグが浮かび上がるようなテストを書く。バグを突き止めるとともに、同様のバグがテストをすり抜けないようにするため

パフォーマンスについて

システムの内部で何が行われているかを正確に知っていたとしても、パフォーマンスは推測せずに計測すべき。推測の10回に9回は正しくない

パフォーマンスの面白いところは、実際に分析してみると、実行時間の大半がコードのごく小さな一部で消費されていることである。コード全体に平等に最適化をかけると、実行時間の短いコードを最適化することになり効率が悪い

具体的なリファクタリング

名前の変更

名前の変更の価値は大きい。優れたコードは、自分がしていることを明快に伝えられなければならないが、変数名やメソッド名はそのための鍵を握っている

分かりやすくするために、名前を書き換えることをためらってはならない

メソッド・フィールドの移動

メソッドは、そのメソッドが使用するデータを持つクラスに割り当てるべき

条件分岐は、他のオブジェクトでなく自分自身のデータに基づくべきであり、他のオブジェクトのデータで条件分岐している箇所はクラスの移動を検討する

メソッドやフィールドをどのオブジェクトに管理させるかは、オブジェクトの設計でもっとも重要な判断の1つである。最初から正解にたどり着くのは難しいので、リファクタリングを使って設計を変えていけばよい

メソッドの抽出

何かコメントを書くべきと感じる場合、コメントではなくメソッドに抽出することを考える。このときメソッド名はコードの仕組みではなく、目的に基づいてつける。メソッド名がコードの目的を説明しているなら、たった1行のコードであってもメソッド呼び出しに変える価値がある。コメントを探すとメソッド抽出すべきところが見つかりやすい

値を返すことと、オブジェクトの状態に変化を与えることを同時に行なっているメソッドがある場合、問い合わせ用と更新用のメソッドに分割する。こうすることで再利用しやすくなる

ほぼ同じコードによる2つのメソッドがあり、違いはメソッドのちょうど中頃にある場合、重複部分を抽出してブロック付きのメソッドにして、違いの部分を yield で実行させると良い。この手法は「サンドイッチメソッドの抽出」という名前がついている（詳細をまとめたブログ記事）

ポリモーフィズム

case文を見かけたら、ほとんどの場合はポリモーフィズムを利用することを検討すべき。case文の少なさは、オブジェクト指向らしいコードが持つ特徴の1つである。メリットとしては、新しい型を追加した時に存在している全ての条件式を探す必要がなくなり、新しいクラスを作って適切なメソッドを提供するだけでよくなる（詳細をまとめたブログ記事）

広い意味では同じようなステップを同じ順序で実行しているように見えるが、ステップが全く同じだとは言えない複数のメソッドは、共通部分をスーパークラスに移してポリモーフィズムに仕事をさせ、異なるステップはそれぞれがサブクラスで実行させる。この種のメソッドをテンプレートメソッドと呼ぶ。Rubyでは、モジュールのextendを使ったテンプレートメソッドの作成も可能である。モジュールをextendするクラスがーパークラスの役割を果たして共通部分を格納し、モジュールが特別なふるまいを実装する（詳細をまとめたブログ記事）

クラス・モジュールの抽出

クラスが常に全てのインスタンス変数を使うわけではない場合がある。そのような時は、クラスの抽出、モジュールの抽出、サブクラスの抽出を検討する

1つのクラスが異なる理由でたびたび書き換えられる時には、理由ごとにクラスを分けることを検討する

before_save などのコールバックを共通化したいときは、included フックを作ったモジュールに抽出するとよい（詳細をまとめたブログ記事）

抽象スーパークラス（インスタンスを生成しないスーパークラス）を作る場合は、スーパークラスをモジュールにすると意図を正しく表現できる（詳細をまとめたブログ記事）

ガード節

条件分岐がネストされている場合は、まずはガード節が使えないかを検討する

ファクトリメソッド

オブジェクトを作成するときに単なる構築以上のことをしたい場合は、コンストラクタを取り除いてファクトリメソッドを作ると良い。例えば、作成するオブジェクトの種類を決めるために条件分岐を使っている場合などで有効となる（詳細をまとめたブログ記事）

委譲

manager = john.department.manager というコードがあったとする。これだと、manager の管理は Departmant クラスで行なっているということを呼び出し側が知っておかなければならず依存が発生する。委譲メソッドを使って john.manager で取得できるようにすれば、余計な依存を解消することができる（詳細をまとめたブログ記事）

サブクラスがスーパークラスのインターフェースの一部しか使っていない、あるいはデータの継承を望まない場合は、継承から委譲へ変更することを検討する。スーパークラスのインスタンスを参照するフィールドを作り、スーパークラスのインスタンスに処理を委譲するようにメソッドを修正して、継承構造を解消する（詳細をまとめたブログ記事）

その他

method_missing を使うとコードがわかりにくくなることが多いので、なるべく使わない方がいい

オブジェクトの代わりにnullを持っている可能性があり、コード中にnullかどうかの確認をしている箇所が多いとき、nullオブジェクトを導入するのが有効な場合がある（詳細をまとめたブログ記事）

おわりに

ここまで読んでいただきありがとうございます。

この本は今まで読んだ技術書の中でもトップクラスに学ぶことが多かったです。

また、値段もトップクラスでした（笑）

リファクタリング:Rubyエディション

「これなんかリファクタリングできないかなー」という時にこの本が手元にあると役立ちそうなので、手元に置いて少しずつ身につけていこうと思います。

2020-06-03

抽象スーパークラスからモジュールへ【リファクタリング Rubyエディションまとめ8】

リファクタリング Ruby

こんにちは。

最近 リファクタリング Rubyエディション を読みました。本書はリファクタリングの様々なパターンをRubyのサンプルコードを使って解説している名著です。

実務でも活かせそうなパターンが多く紹介されていたので、いいなと思ったパターンを1つずつブログにまとめています。

今回はその第8弾で「抽象スーパークラスからモジュールへ」についてまとめました。
オリジナルの Ruby のサンプルコードを使って説明しています。

前回の「サンドイッチメソッドの抽出」のまとめはこちらです。
サンドイッチメソッドの抽出【リファクタリング Rubyエディションまとめ7】 - 銀行員からのRailsエンジニア

f:id:ysk_pro:20200602083536p:plain

抽象スーパークラスからモジュールへとは
サンプルコード
- リファクタリング前
- リファクタリング後
おわりに

抽象スーパークラスからモジュールへとは

使えるタイミング

継承関係を持っているものの、スーパークラスのインスタンスを生成させたくない場合に有効です。

リファクタリング方法

スーパークラスをモジュールに書き換えて、サブクラスで include します。

このリファクタリングを使用する理由

例えば、Java ではクラスに abstract というキーワードをつけることで、そのクラスのインスタンスが生成されないようにできますが、Ruby には同じ機能はありません。

コンストラクタが呼び出された時にエラーする処理を書いても同じことは実現可能ですが、モジュールを使う方がインスタンスを生成させたくないという意図をはっきり伝えることができます。

サンプルコード

リファクタリング前

まずはリファクタリング前のコードです。

class Item
  def initialize(name, origin_country = nil)
    @name = name
    @origin_country = origin_country
  end

  def description
    puts "商品名:#{@name} / 補足:#{additional_description}"
  end
end

class DomesticItem < Item
  def additional_description
    '国内産です'
  end
end

class ImportedItem < Item
  def additional_description
    "#{@origin_country}で作られました"
  end
end

商品（Item）クラスを、国内産商品（DomesticItem）クラスと輸入商品（ImportedItem）クラスが継承しています。

次のように実行すると

DomesticItem.new('イヤホン').description
ImportedItem.new('スマートフォン', 'アメリカ').description

次の結果になります。

商品名:イヤホン / 補足:国内産です
商品名:スマートフォン / 補足:アメリカで作られました

このコードの問題点としては、スーパークラスである Item クラスのインスタンス化は可能なものの、Item クラスのインスタンスで description メソッドを呼び出すと additional_description メソッドが定義されていないためエラーになってしまう点です。

意図していないインスタンス生成（Item クラス）は出来ないようにしておくのが安全なので、リファクタリングを行います。

リファクタリング後

「抽象スーパークラスからモジュールへ」を使ってリファクタリングをすると下記のようになります。

module Item
  def initialize(name, origin_country = nil)
    @name = name
    @origin_country = origin_country
  end

  def description
    puts "商品名:#{@name} / 補足:#{additional_description}"
  end
end

class DomesticItem
  include Item

  def additional_description
    '国内産です'
  end
end

class ImportedItem
  include Item

  def additional_description
    "#{@origin_country}で作られました"
  end
end

変更点は、継承関係を解消して、モジュール化した Item クラスをそれぞれのクラスで include したのみです。

実行の仕方、結果は先ほどと同じになります。

おわりに

ここまでお読みいただきありがとうございます。

このリファクタリングはデザインパターンの1つである「テンプレートメソッドパターン」で使えそうだなーと思ったので、今回のサンプルコードは、テンプレートメソッドパターンを使ったものにしています。
テンプレートメソッドパターンについて詳しく知りたい方は、合わせてこちらをご覧ください。
ysk-pro.hatenablog.com

リファクタリング Rubyエディションでは、この記事の内容に加えてクラスメソッドが存在する場合のリファクタリングの仕方についても触れられていて参考になったので、ご興味ある方は是非ご覧ください。

リファクタリング:Rubyエディション

次回はまた違うパターンをまとめていきます！

前回の「サンドイッチメソッドの抽出」のまとめはこちらです。是非合わせてご覧ください。
ysk-pro.hatenablog.com

2020-05-31

AtCoderで水色になりました！【やってきたことやコンテスト中に意識していること】

AtCoder 競技プログラミング

こんにちは。

AtCoderで悲願の水色になりました！

悲願の入水キターーーーーーーー！！！！

めっちゃ嬉しい！！！

ysk1180さんのNOMURA プログラミングコンテスト 2020での成績：741位
パフォーマンス：1780相当
レーティング：1117→1206 (+89) :)
Highestを更新し、4 級になりました！#AtCoder https://t.co/6Q9qSdzYxl pic.twitter.com/B4eBHMWi31
— ゆうすけ@Railsエンジニア (@ysk_pro) 2020年5月30日

2019/9 に AtCoder を始めて、9ヶ月かかりました。始めた頃は、水色は遥か先のイメージだったのでとても嬉しいです！

緑色になるまでにやったこと、AtCoder とはそもそも何なのかや、続けるモチベーションなどについてはこちらの記事に書いているので、ご興味ある方は合わせてご覧ください。

ysk-pro.hatenablog.com

この記事では、緑色になってから水色になるまでにやってきたことやコンテスト中に意識していることを書こうと思います。

やったこと
コンテスト中に意識していること
やった方がいいと分かりつつやれていないこと
おわりに

やったこと

AtCoderのコンテストに出続けること

モチベが下がったりしても、とにかく毎週末コンテストに出続けました。

最近はたまに青色パフォも出るようになってきました。

f:id:ysk_pro:20200531155602p:plain — レーティングの推移

維持・微減を繰り返しながら、たまにガッと上がっている感じですね。

解けた問題も解説動画を見ること

コンテスト後に配信される解説動画は本当に神です。

AtCoder社の snuke さんの説明は、とても分かりやすくて学ぶことが多いです。

解けた問題でも、自分とは違う解き方やアプローチを学ぶことがあるので、極力見るようにしています。

コンテスト中に解けなかった問題を徹底的に復習すること

解けない問題を解けるようにすることが一番レベルアップに繋がると信じているので、コンテスト中に解こうとして解けなかった問題は徹底的に復習していました。

解こうとして解けなかった問題のみで、チャレンジすら出来なかった問題まではやっていません。1つのコンテストが終わったら、解けなかった1問を翌日に数時間かけて復習している感じです。

具体的には、前述の解説動画を何度も見たり、他の方の解説ブログを読んだり（「AtCoder ABC168 E」などと検索すると分かりやすい記事がたくさん出てきます）、同じ言語で通している方のコードを読むなどして理解をして、その後に自分で何も見ずに解いて、つまずいたらまた解説に戻って、というのを繰り返しています。

かなり時間がかかることもあり苦しいですが、その分これがレートの向上に一番効果があったと思います。

仲間とバーチャルコンテストをやったり、お互いに解説したりすること

幸運にも勤めている会社で同じ時期に AtCoder を始めた仲間が何人かいるので、その方々と休みの日にバーチャルコンテストをやったり、難しい問題をお互いに解説し合ったりしていました。

知り合いとワイワイやるのは楽しいですよね。

自分が行なった解説をブログにまとめてみたりもしました。
ABC168 E「∙ (Bullet)」の解説【AtCoder Beginner Contest】 - 銀行員からのRailsエンジニア

コンテスト中に意識していること

これまで29回コンテストに出場して多くの失敗をしてきました。そんな失敗などから学んで意識していることをまとめてみます。

とりあえず全探索を考えてみる

全探索が間に合うのであれば、全探索をするのが一番確実だと思っています。

「無理だろうな」と思ってもまずは全探索の計算量を考えて、間に合わない場合はそこから「どうやって計算量を下げようか」と考えるようにしています。

意外と全探索で間に合ってしまう問題も多く、間に合わない場合も考察の取っ掛かりになるので「とりあえず全探索を考える」というのは悪くないと思います。

実装に入ることを焦らずに、実験を繰り返して考察に時間をかけてから実装する

考察が中途半端なまま、焦って実装に入って泥沼にハマるというのを何度か経験して学びました。

考察に時間をかけて「これだ」という解法を見つけてから実装した方がスムーズに解き終わることが多いです。

また、糸口が見つからない時はノートとペンを使ってとにかく実験（色々なケースで試すこと）をしています。頭の中で考えるよりも、手を動かして実験をしていった方が糸口が見えてくることが多かったです。

固定してみる・逆から考えてみる

少しテクニック的な話になってしまいますが、1つの変数を固定したり、逆から考えてみるとシンプルになる場合があるので、詰まったらよく試しています。

やった方がいいと分かりつつやれていないこと

この記事のメインの部分はここまでですが、反省を込めてやれていないことも書いておこうと思います。

コンテスト以外に問題を解くこと

緑色になってから、若干モチベが下がったのと趣味の個人開発により時間を割きたくなったことから、それまで続けていた過去問を解くのをやめてしまいました。

どれだけ過去問を解いたか示す画像 — AtCoder Problems の過去問の解いた割合

アルゴリズムを学ぶこと

知り合いの青色 Coder の方に coursera の無料のアルゴリズムの講座をおすすめいただき、やろうやろうと思いながらなかなか手がつけられていません。

定番の蟻本も少しだけ読みましたが、積ん読になってしまっています。

典型のアルゴリズムでも使いこなせていないものが多いので（DPを本番で一度も通したことがないです..）、そろそろ向き合わないといけないなーと思っています。

Ruby を卒業すること

実行速度、解説の豊富さ、ライブラリの充実などのメリットから、c++ を使った方がいいと分かりつつ、なかなか Ruby を卒業できていません。

オールRubyでした（笑）

先日、Ruby では通せない問題（AGC44 B Joker）に初めてコンテスト本番でぶち当たって衝撃を受けたので、そろそろ c++ 覚えないとなあと思っています。

おわりに

できていないことも多いですが、毎週コツコツ続けることで徐々に結果が出てきて嬉しいです。

これからも無理せず、毎週のコンテストを楽しんでいこうと思います。

目指せ青色！！

2020-05-25

サンドイッチメソッドの抽出【リファクタリング Rubyエディションまとめ7】

リファクタリング Ruby

こんにちは。

実務でも活かせそうなパターンが多くあったので、いいなと思ったパターンを1つずつブログにまとめています。

今回はその第7弾で「サンドイッチメソッドの抽出」についてまとめました。
オリジナルの Ruby のサンプルコードを使って説明しています。

第6弾の「コンストラクタからファクトリメソッドへ」のまとめはこちらです。
コンストラクタからファクトリメソッドへ【リファクタリング Rubyエディションまとめ6】 - 銀行員からのRailsエンジニア

f:id:ysk_pro:20200524151911p:plain

サンドイッチメソッドの抽出とは
- 使えるタイミング
- リファクタリング方法
サンプルコード
- リファクタリング前
- リファクタリング後
おわりに

サンドイッチメソッドの抽出とは

使えるタイミング

ほとんど内容が同じメソッドが複数あり、違いがメソッドの途中（最初や最後ではない）にある場合に有効なリファクタリングです。

リファクタリング方法

Rubyのブロックを使用します。
差異の部分をブロック呼び出し（yield）にしてメソッドを定義します。
呼び出し元は、差異の部分をブロックで渡してメソッドを呼び出します。

サンドイッチメソッドの抽出という名前の通り、共通部分でサンドイッチしているイメージですね。

文章での説明よりサンプルコードを見た方が理解しやすいので、サンプルコードを見ていきましょう。

サンプルコード

リファクタリング前

まずはリファクタリング前のコードです。

class Person
  def sunny_day_activities
    puts 'work from home'
    puts 'running' # 晴れの日はランニングする
    puts 'play games'
  end

  def rain_day_activities
    puts 'work from home'
    puts 'taking a nap' # 雨の日は外に出たくないので昼寝する
    puts 'play games'
  end
end

かなりシンプルなクラスですね。

次のように実行すると

person1 = Person.new
person1.sunny_day_activities
person1.rain_day_activities

次の結果になります。

work from home
running
play games
work from home
taking a nap
play games

sunny_day_activities メソッドと、rain_day_activities メソッドは、それぞれの 2つ目の puts 以外ほとんど同じなので共通化したいですね。

リファクタリング後

「サンドイッチメソッドの抽出」を使ってリファクタリングをすると下記のようになります。

class Person
  def activities
    puts 'work from home'
    yield
    puts 'play games'
  end
end

次のように実行すると、先ほどと実行結果は同じになります。

person2 = Person.new
person2.activities { puts 'running' }
person2.activities { puts 'taking a nap' }

差異のある部分をブロックで渡し、yield でブロックを実行しています。

いい感じに共通化できましたね。

おわりに

ここまでお読みいただきありがとうございます。

リファクタリング Rubyエディションでは、このブログよりもリアルのコードで解説しており分かりやすかったので、ご興味ある方は是非ご覧ください。

リファクタリング:Rubyエディション

次回はまた違うパターンをまとめていきます！

（追記）
第8弾として「抽象スーパークラスからモジュールへ」についてまとめました。
是非合わせてご覧ください。
ysk-pro.hatenablog.com

2020-05-23

ABC168 E「∙ (Bullet)」の解説【AtCoder Beginner Contest】

AtCoder 競技プログラミング Ruby

はじめに

難しかったですね...！コンテスト中には余裕で解けませんでした...

僕が勤めている会社の競プロの集まりで、この問題を解説する機会があり、せっかくだったので噛み砕いてブログにしてみました。

問題

f:id:ysk_pro:20200523103429p:plain

問題文と制約のスクリーンショットです。
実際の問題のページはこちらです。
E - ∙ (Bullet)

考察

全探索の計算量を考えてみる

とりあえず、全探索の計算量を考えてみます。

N匹のイワシから1匹以上を選ぶ選び方なので、それぞれのイワシについて選ぶ or 選ばないの選択をしていき、最後に全てを選ばなかったケースを引けば良さそうです。

よって、O( $2^N$ ) となります。Nの制約は2 × $10^5$ なので圧倒的に間に合わないですね。他の方法を考えます。

解法

$A_i$ × $A_j$ + $B_i$ × $B_j$ = 0 という数式は、i と j が混ざっていて分かりにくいので、式変形をしてみます。f(j) = g(i) の形にできると考えやすくなることが多いです。

$\frac{A_j}{B_j}$ = - $\frac{B_i}{A_i}$ となります。一旦、簡略化のために A, B に 0 は入らないと仮定して考察を進めます。

ここで $I_i$ = $\frac{A_i}{B_i}$ とすると（ I はもちろん Iwashi の I です）

$I_j$ = - $\frac{1}{I_j}$

とすることができます。

少しまとめると、

それぞれのイワシの I は一意に決まる
I のイワシは、-1/I のイワシとのみ相性が悪く、それ以外のイワシとは相性は悪くない

ということが分かります。

イワシの相性は、I の値でのみ決まるので、I の値でイワシたちをグルーピングしてみましょう。

N匹のイワシだと考えにくいので、図のような具体的な例で考えてみます。

f:id:ysk_pro:20200523095944p:plain

イワシが6匹いて、I = 2 となるのが 2匹、I = - 1/2 が 3匹、I = 3 が1匹いるとします。

仲が悪くなってしまう I をペアにすると、ペア1、ペア2と分けられます。（ペア2は相方がいませんがペアとして考えます）

f:id:ysk_pro:20200523100136p:plain

この時、何通りの選び方ができるかを考えます。

まずペア1のみに絞って考えると、それぞれのグループ（I = 2 と I = -1/2）から同時に選べないので、

( $2^2$ - 1) + ( $2^3$ - 1) + 1

となります。（カッコは分かりやすくするためにつけています）

どういうことかというと、I = 2 のイワシと I = -1/2 のイワシは同時に選べないので、I = 2 のイワシのみを選ぶ場合と I = 1/2 のイワシのみを選ぶ場合で分けて考えて、最後に足すという方針で計算します。
I = 2 のイワシのみを選ぶ場合は、それぞれのイワシを選ぶ or 選ばないなので $2^2$ となり、全てのイワシを選ばないとしたケースは I = 2 のイワシを選んだことにならないので最後に 1 を引いています。これで $2^2$ - 1 になります。
I = -1/2 のイワシを選ぶ場合は同様に $2^3$ - 1 となります。
最後に +1 をしているのは、I = 2, -1/2 のイワシをどちらも選ばなくても、ペア1からの選び方として問題にはならないからです。（I = 2 のイワシと I = -1/2 のイワシが同時に選ばれなければOK）

ペア2に対しても同様に考えることができ、

( $2^1$ - 1) + 1

となります。

そして、ペア1 とペア2 は互いに独立しているので、それぞれのケース数を掛け合わせ、最後に 1匹も選ばないケースを除けば（問題の条件として1匹以上選ぶ必要があるため）全ての組み合わせを求められそうですね。

一般化すると、

相性が悪い I のグループ同士をペアにして、それぞれ x 匹、y 匹含まれるとすると、組み合わせの数は ( $2^x$ -1) + ( $2^y$ + 1) - 1 で求められる
それぞれのペアの組み合わせの数を掛け合わせると組み合わせの総数

となります。

したがって、I を全て求める → I の値でグループ化してグループに何匹ずつ含まれるか数える → グループをペアにして組み合わせの総数を求めるという感じでいけそうですね。

ただ今回、そのまま I = A/B を計算してしまうと、I は小数になるので誤差がでてしまう可能性があります。例えば、I が 0.(たくさん)1 と 0.(同じたくさん)2 は違う値なので別のグループとして扱うべきところ同じグループとしてしまう、みたいなイメージです。

小数だと誤差が出てしまいそうで怖いので、I を小数を使わない形で表現することにします。

やり方としては、I を A と B の配列で表現します。（やり方は他にも色々あると思います）
$I_i$ = [ $A_i$ , $B_i$ ] と表現します。

小数がなくなり誤差の問題はクリアできて嬉しいのですが、注意点がいくつかあります。

それぞれの値を $A_i$ と $B_i$ の最大公約数で割る必要があります。例：[1, 2] と [2, 4] は同じグループとして扱いたいためです。

$A_i$ が負の場合は、 $A_i$ と $B_i$ 両方に -1 を掛けて、 $A_i$ は必ず正の値にする必要があります。例：[-1, 2] と [1, -2] は同じグループとして扱いたいためです。

ここで、ここまで無視してきた 0 の扱いについても考えます。
0 で割ることはできないので、この式で考えます。

$A_i$ × $A_j$ = - $B_i$ × $B_j$

$A_i$ と $B_i$ のどちらも 0 のケース

どんなイワシとも相性が悪くなる最悪のイワシです。（ $A_j$ と $B_j$ に何が入ったとしても式が成り立ちます。）このタイプのイワシをクーラーボックスに入れたいときは、このタイプのイワシをただ1匹だけ入れるしかありません。よって、最悪イワシは何匹いるかを数えておき、最後に匹数を足せば良さそうです。

$A_i$ と $B_i$ のどちらかだけが 0 のケース

例えば、 $A_i$ が 0 だとすると、左辺は 0 になり、 $B_i$ は 0 ではないので、 $B_j$ が 0 のイワシと相性が悪くなります。つまり、A = 0 のイワシと相性が悪いのは B = 0 のイワシです。（このとき、A = B = 0 の最悪のイワシは別管理しているので考慮する必要はないです）
B = 0 のときは I = [1, 0]、A = 0 のときは I = [0, -1] とすることで、グループ化したイワシたちと同様に考えることができます。

実装

やっと、、やっと実装です！
Ruby のコードに適宜コメントを入れています。

MOD = 1000000007
N = gets.chomp.to_i

group = Hash.new(0)
worst_iwashi_count = 0 # 最悪のイワシを管理する変数

N.times do |i|
  a, b = gets.chomp.split.map(&:to_i)

  if a == 0 && b == 0 # 最悪のイワシのケース
    worst_iwashi_count += 1
    next
  end

  if a == 0 # A = 0 のイワシのケース
    group[[0, -1]] += 1
    next
  end

  if b == 0 # B = 0 のイワシのケース
    group[[1, 0]] += 1
    next
  end

  # 最大公約数でそれぞれを割る
  gcd = a.gcd(b)
  a /= gcd
  b /= gcd

  # 正負を揃える
  if a < 0
    a *= -1
    b *= -1
  end

  group[[a, b]] += 1
end

ans = 1

group.each do |(a, b), count|
  # ペアとなるグループに含まれるイワシの数を数える
  # ペアとして計算されたグループは、重複して計算されることを防ぐために削除する
  if b < 0
    pair_count = group[[-b, a]]
    group.delete([-b, a])
  else
    pair_count = group[[b, -a]]
    group.delete([b, -a])
  end

  ans *= (2 ** count - 1) + (2 ** pair_count - 1) + 1
  ans %= MOD
end

p (ans + worst_iwashi_count - 1) % MOD

このコードを提出したAtCoderのページはこちらです。
Submission #13492364 - AtCoder Beginner Contest 168

おわりに

考慮することが多くて難しいですね...！
これをコンテスト中に通せる人をほんと尊敬します。

この問題のポイントは、

f(j) = g(i) の形への式変形
グループごとに組み合わせ数を求めること
小数で誤差を出さないようにすること
0の扱い

だったと思います。
同じような考え方を使う問題が出てきたときに、この問題の解法を思い出して応用できるといいですね！

初めてAtCoderの解法をブログにまとめ、口頭で解説するというのをやってみました感想としては、めちゃくちゃ時間がかかりましたが圧倒的に理解が深まりました。

また機会があればやってみようと思います。

ご指摘・ご質問等あれば、ブログのコメント・TwitterDM いただければ返信させていただきます。

ここまでお読みいただきありがとうございました。

2020-05-20

コンストラクタからファクトリメソッドへ【リファクタリング Rubyエディションまとめ6】

リファクタリング Ruby

こんにちは。

実務でも活かせそうなパターンが多くあったので、いいなと思ったパターンを1つずつブログにまとめています。

今回はその第6弾で「コンストラクタからファクトリメソッドへ」についてまとめました。
オリジナルの Ruby のサンプルコードを使って説明しています。

第5弾の「タイプコードからポリモーフィズムへ」のまとめはこちらです。
タイプコードからポリモーフィズムへ【リファクタリング Rubyエディションまとめ5】 - 銀行員からのRailsエンジニア

f:id:ysk_pro:20200520070559p:plain

サンプルコード
- リファクタリング前
- リファクタリング後
おわりに

サンプルコード

リファクタリング前

文章での説明よりもコードを見た方が分かりやすいので、早速サンプルコードを見ていきましょう。
まずはリファクタリング前のコードです。

class Car
  def initialize(price)
    @price = price
  end

  def guarantee?
    false
  end
end

class ForeinCar < Car
  def guarantee?
    false
  end
end

class HighGradeCar < Car
  def guarantee?
    true
  end
end

Car（車）クラス、Carクラスを継承した ForeinCar（外車）クラス・HighGradeCar（高級車）クラスがあります。

imported = false
price = 200

car1 = if imported
         ForeinCar.new(price)
       elsif price > 100
         HighGradeCar.new(price)
       else
         Car.new(price)
       end
puts car1.guarantee? # -> true

作成するオブジェクトを決めるために条件分岐を使っています。また、複数箇所でオブジェクトを作成しており、同じ条件分岐が使われているとします。

このコードの問題点としては以下の点が挙げられます。

条件分岐のコードが重複していること
呼び出しているクラスと、オブジェクトが作られるクラス（ForeinCarなど）の結合度が強くなり、保守性が低くなっていること（例えば、ForeinCarクラスのクラス名や呼び出し方が変わると、呼び出し元のクラスも変更しなくてはいけなくなってしまいます）

リファクタリング後

「コンストラクタからファクトリメソッドへ」を使ってリファクタリングしていきます。

リファクタリングはシンプルで、先ほどの Carクラスに、オブジェクト作成のためのクラスメソッドを1つ追加するのみです。

class Car
  def self.create(imported, price) # ファクトリメソッド
    if imported
      ForeinCar.new(price)
    elsif price > 100
      HighGradeCar.new(price)
    else
      new(price)
    end
  end
end

create がファクトリメソッドです。

次のように実行すると結果はリファクタリング前と同じになります。

car2 = Car.create(imported, price)
puts car2.guarantee?

オブジェクトの作成は全てファクトリメソッドで行うようにすることで、コードの重複はなくなり、クラス間の結合度も弱くすることができました。

「コンストラクタからファクトリメソッドへ」という名前は、呼び出し元からコンストラクタを呼び出していた（newしていた）ものをファクトリメソッドを呼び出すように変える、という意味のようです。

おわりに

ここまでお読みいただきありがとうございます。

リファクタリング Rubyエディションでは、この記事とは別のサンプルコードで丁寧に説明されていて分かりやすかったので、ご興味ある方は是非ご覧ください。

リファクタリング:Rubyエディション

次回はまた違うパターンをまとめていきます！

（追記）
第7弾として「サンドイッチメソッドの抽出」についてまとめました。
是非合わせてご覧ください。
ysk-pro.hatenablog.com

2020-05-13

タイプコードからポリモーフィズムへ【リファクタリング Rubyエディションまとめ5】

リファクタリング Ruby

こんにちは。

実務でも活かせそうなパターンが多くあったので、特にいいなーと思ったパターンを1つずつブログにまとめています。

今回はその第5弾で「タイプコードからポリモーフィズムへ」についてまとめました。
オリジナルの Ruby のサンプルコードを使って説明しています。

第4弾の「nullオブジェクトの導入」のまとめはこちらです。
nullオブジェクトの導入【リファクタリング Rubyエディションまとめ4】 - 銀行員からのRailsエンジニア

f:id:ysk_pro:20200513080734p:plain

サンプルコード
- リファクタリング前
- リファクタリング後
おわりに
余談

サンプルコード

リファクタリング前

文章での説明よりもコードを見た方が分かりやすいので、早速サンプルコードを見ていきましょう。
まずはリファクタリング前のコードです。

class Fan
  attr_reader :type_code, :brand_level

  def initialize(type_code, brand_level)
    @type_code = type_code
    @brand_level = brand_level
  end

  def price
    case type_code
    when :ac_motor
      brand_level * 3_000
    when :dc_motor
      brand_level * 5_000
    when :no_wing
      brand_level * 7_000
    end
  end

  # priceメソッド以外にもtypeによる条件分岐が多くなっている
end

シンプルな Fan（扇風機）クラスです。
モーターのタイプを表す type_code（タイプコード）とブランドのレベルを表す brand_level（ブランドレベル）を渡してインスタンスを作成すると、価格を返す price メソッドが使用できます。

リファクタリングの名前にも入っている「タイプコード」というのは、この例の type_code のように、インスタンスの種類を表すために注入している要素のことを指します。

次のように実行します。

nomal_fan = Fan.new(:ac_motor, 1)
puts nomal_fan.price

dyson_fan = Fan.new(:no_wing, 5)
puts dyson_fan.price

balmuda_fan = Fan.new(:dc_motor, 10)
puts balmuda_fan.price

ブランドレベルは僕の主観です（笑）

結果は下記の通りとなります。

3000
35000
50000

バルミューダの扇風機は高いですね〜。

このコードの問題点は、case 文による条件分岐を行なっているところです。

今は price メソッドにしか case 文を使っていないので悪くないように見えるかもしれませんが、他のメソッドを追加する際に同じように case 文による条件分岐を作ると、case 文のところでコードの重複が発生してしまいます。

さらに、case 文が複数存在する状態で、新たなタイプコードを追加しようとした場合は、全ての case 文に修正を入れなければならなくなります。

これらが重なってくるとかなり辛い状況になってしまいます。

それでは、このコードをポリモーフィズムを使ってリファクタリングしてみましょう。

リファクタリング後

「タイプコードからポリモーフィズムへ」を使ってリファクタリングすると次のようになります。

class AcMotorFan
  attr_reader :brand_level

  def initialize(brand_level)
    @brand_level = brand_level
  end

  def price
    brand_level * 3_000
  end
end

class DcMotorFan
  attr_reader :brand_level

  def initialize(brand_level)
    @brand_level = brand_level
  end

  def price
    brand_level * 5_000
  end
end

class NoWindFan
  attr_reader :brand_level

  def initialize(brand_level)
    @brand_level = brand_level
  end

  def price
    brand_level * 5_000
  end
end

タイプコードそれぞれをクラスにし、それぞれのクラスで price メソッドを定義するようにしました。

次のように実行すると結果はリファクタリング前と同じになります。

nomal_fan = AcMotorFan.new(1)
puts nomal_fan.price

dyson_fan = NoWindFan.new(5)
puts dyson_fan.price

balmuda_fan = DcMotorFan.new(10)
puts balmuda_fan.price

case 文による条件分岐がなくなりましたね。

新たなメソッドを追加する際は、それぞれのクラスに新しいメソッドを書いていくだけでいいのでシンプルです。
また、タイプコードの追加もクラスを新たに作るだけで良くなりました。

「タイプコードからポリモーフィズム」という名前はそのままで分かりやすいですね。

おわりに

ここまでお読みいただきありがとうございます。

case文を使っている箇所を見つけたら「タイプコードからポリモーフィズム」が適用できないかをまず考えてみると良さそうですね。

リファクタリング Rubyエディションでは、様々なタイプのマウンテンバイクを題材に解説されていて分かりやすかったので、ご興味ある方は是非ご覧ください。

また、ポリモーフィズムについて本書に分かりやすい説明があったので引用します。

ポリモーフィズムの本質は、オブジェクトにどのようなタイプ（型）なのかを尋ね、その答に基づいてなんらかのメソッドを呼び出すようなことをせずに、単純にメソッドを呼び出すことである。呼び出されたオブジェクトは、自分の型に基づいて適切な処理を行う。
（リファクタリング Rubyエディションから抜粋）

リファクタリング:Rubyエディション

次回はまた違うパターンをまとめていきます！

（追記）
第6弾として「コンストラクタからファクトリメソッドへ」についてまとめました。
是非合わせてご覧ください。
ysk-pro.hatenablog.com

余談

最近暑くなり、扇風機選びに悩んでいたので扇風機を題材にしたサンプルコードにしてみました。
かなり悩んだ末に、個人的なブランドレベルが10のバルミューダの扇風機を購入しました！風が心地よく、コードレスが便利で大満足でした。

バルミューダ省エネ静音リビング扇風機 The GreenFan(グリーンファン) | EGF-1700-DK(ダークグレー×ブラック)

メディア:

リファクタリングについて

リファクタリングの基本的な考え方

リファクタリングの基本的な進め方

パフォーマンスについて

具体的なリファクタリング

名前の変更

メソッド・フィールドの移動

メソッドの抽出

クラス・モジュールの抽出

ガード節

ファクトリメソッド

委譲

その他

おわりに

抽象スーパークラスからモジュールへ とは

使えるタイミング

リファクタリング方法

このリファクタリングを使用する理由

サンプルコード

リファクタリング前

リファクタリング後

おわりに

やったこと

AtCoderのコンテストに出続けること

解けた問題も解説動画を見ること

コンテスト中に解けなかった問題を徹底的に復習すること

仲間とバーチャルコンテストをやったり、お互いに解説したりすること

コンテスト中に意識していること

とりあえず全探索を考えてみる

実装に入ることを焦らずに、実験を繰り返して考察に時間をかけてから実装する

固定してみる・逆から考えてみる

やった方がいいと分かりつつやれていないこと

コンテスト以外に問題を解くこと

アルゴリズムを学ぶこと

Ruby を卒業すること

おわりに

サンドイッチメソッドの抽出 とは

使えるタイミング

リファクタリング方法

サンプルコード

リファクタリング前

リファクタリング後

おわりに

はじめに

問題

考察

全探索の計算量を考えてみる

解法

実装

おわりに

サンプルコード

リファクタリング前

リファクタリング後

おわりに

サンプルコード

リファクタリング前

リファクタリング後

おわりに

余談

抽象スーパークラスからモジュールへとは

サンドイッチメソッドの抽出とは