銀行員からのRailsエンジニア

銀行員からのRailsエンジニア

銀行員から転身したサービス作りが大好きなRailsエンジニアのブログです。個人で開発したサービスをいくつか運営しており、今も新しいサービスを開発しています。転職して日々感じていること、個人開発サービス運営のことなどを等身大で書いていきます。

Waiting for table metadata lockとオンラインDDLについて【MySQL5.6】

MySQLで「Waiting for table metadata lock」のエラーが発生して、詳しく知りたくなったので、関連しているオンラインDDLとともに調べ、手元で試してみたことをまとめました。

MySQLのバージョンは 5.6、ストレージエンジンは InnoDB です。

この記事の多くは、MySQL 公式ドキュメントの以下のページを参考に書いています。
公式ドキュメント①:14.11.1 オンライン DDL の概要
公式ドキュメント②:14.11.2 オンライン DDL でのパフォーマンスと並列性に関する考慮事項

f:id:ysk_pro:20200708084439p:plain

DDLとは

DDL は Data Definition Language の略で、データ定義言語です。
SELECT などのテーブルのレコードを操作するものではなく、データベース自体を操作するものを指します。
CREATE, ALTER, DROP などが DDL です。

対して、SELECT, UPDATE, DELETE などの、テーブルのレコードを操作するものは DML(データ操作言語、Data Manipulation Language)と呼ばれています。

オンラインDDLとは

MySQL5.6より前のバージョンでは、一部を除いたDDLは、テーブルの全ての行のコピーやDDL実行中のDMLのブロックを必要とするコストの高い操作でした。
そのため、DDLを行うためにはサービスをメンテモードにするなどの対応が必要でした。

これに対し、MySQL5.6で拡張されたオンラインDDLは、テーブルコピーを行わず、実行中のDMLのブロックも必要とせずにDDLを行えるようになりました。
テーブルコピーとDMLブロックが不要なDDLをオンラインDDLと呼んでいますが、テーブルコピーは不要だがDMLブロックは必要などといったDDLも一部存在します。

公式ドキュメント① にオンラインDDLについての詳しい説明があります。

オンラインDDLを有効にするために特別なことをする必要はなく、オンラインDDLが可能な場合はオンラインDDLが適用されます。
このことは、MySQL公式ドキュメント 14.11.3 オンライン DDL の SQL 構文 に記載があります。

ただ、全てのDDLがオンラインDDLに対応している訳ではありません

オンラインDDLに対応しているDDL

公式ドキュメント① に、それぞれのDDLでオンラインDDLの何の操作が可能かが一覧表でまとまっています。

一覧表で「インプレース?」が「はい」になっているものがテーブルのコピーが不要なDDL、「並列DMLを許可?」が「はい」になっているものがDDL実行中にDMLの実行が可能なものです。

ざっくりですが、よく行う操作だと、カラムのデータ型変更以外はほぼオンラインDDLに対応していると思って良いと思います。

便利な機能として、DDLに「ALGORITHM=INPLACE, LOCK=NONE」というオプションをつけて実行すると、オンラインDDLでない場合は実行せずにエラーを返してくれます
「ALGORITHM=INPLACE」は、テーブルをコピーしない INPLACE 方式でDDLを実行することを指定し、「LOCK=NONE」はDDL中にロックせずに並列DMLを可能にすることを指定します。これらのオプションは、指定した方法でDDLが実行できない場合にエラーにします。
確実にオンラインDDLで実行したい場合は、このオプションをつけてDDLを実行すると良さそうです。
ALGORITHM=INPLACE は公式ドキュメント①、LOCK=NONE は公式ドキュメント②の中で説明されています。

また、DDLを実行した際にテーブルコピーを行ったかどうかを確認できます。
DDL実行のレスポンスが「0 row affected」の場合、テーブルがコピーされずにDDLが実行されています。
こちらは、公式ドキュメント② で説明されています。

オンラインDDLができないカラムの型変換で、実際にオプションを試してみました。

まずオプションをつけずに実行すると問題なく成功しました。

mysql> ALTER TABLE `users` CHANGE `age` `age` varchar(255) DEFAULT NULL;
Query OK, 4800 rows affected, 2 warnings (0.19 sec)
Records: 4800  Duplicates: 0  Warnings: 2

レスポンスが「4800 rows affected」となっているので、テーブルコピーが行われたと分かります。

オプションをつけて実行すると想定通りエラーとなりました。

mysql> ALTER TABLE `users` CHANGE `age` `age` varchar(255) DEFAULT NULL, ALGORITHM=INPLACE, LOCK=NONE;
ERROR 1846 (0A000): ALGORITHM=INPLACE is not supported. Reason: Cannot change column type INPLACE. Try ALGORITHM=COPY.

INPLACE 方式だとできないので、テーブルコピーを伴う COPY 方式で実行してね、というエラーが発生しています。

Ruby on RailsのMigrationでオプションをつける方法

私は普段 Ruby on Rails を書いており、Rails の Migration で前述のオプションをつける方法を調べました。

私が調べた限り、execute で任意のDDLを実行する以下の方法で行うしかなさそうでした。

class Test < ActiveRecord::Migration
  def up
    execute "ALTER TABLE `users` COMMENT 'test', ALGORITHM=INPLACE, LOCK=NONE"
  end
  def down
    execute "ALTER TABLE `users` COMMENT '', ALGORITHM=INPLACE, LOCK=NONE"
  end
end
== 20200706064613 Test: migrating =============================================
-- execute("ALTER TABLE `users` COMMENT 'test', ALGORITHM=INPLACE, LOCK=NONE")
D, [2020-07-06T16:15:50.402667 #2523] DEBUG -- :    (15.1ms)  ALTER TABLE `users` COMMENT 'test', ALGORITHM=INPLACE, LOCK=NONE
   -> 0.0155s
== 20200706064613 Test: migrated (0.0156s) ====================================

execute を使った任意のDDL実行については、こちらの記事を参考にしました。
Execute SQL in Rails migrations - Josua Schmid - Medium

migration時に実行されるSQLを確認する方法は、こちらの記事を参考にしました。
Rails で migrate 時に実行される SQL を確認する - volpe’s diary

オンラインDDLの注意点とWaiting for table metadata lock が発生するケース

オンラインDDLには注意点があり、オンラインDDLの開始前、完了前にそれぞれ短時間ではあるものの排他的アクセスが必要となります。
つまり、オンラインDDLの開始前と完了前にDDLの対象テーブルに実行中のトランザクションがあった場合、そのトランザクションがコミットまたはロールバックするまで待機する必要があります。

さらに、オンラインDDLトランザクションの完了を待機している状態で同じテーブルへDMLを実行すると、DMLの対象レコードがトランザクションの対象レコードと別であってもオンラインDDLと同様に待機状態になってしまいます。

このようなケースで、待機状態になっているDDLDML が Waiting for table metadata lock の状態になっています。
メタデータ(meta data)とは、カラム名、データベース名などのデータベースについての情報のことです。
トランザクション中のメタデータの変更を防ぐため、メタデータのロックをかけており、DDLを実行すると Waiting for table metadata lock となります。

トランザクションが長引いたりすると、Waiting for table metadata lock がたまり続けて障害の引き金になる可能性もあります。

詳細は 公式ドキュメント②と、こちらの公式ドキュメントに記載されています。
8.10.4 メタデータのロック

Waiting for table metadata lock が発生するケースを実際に試してみる

トランザクション中にDMLを行うケース

まずはオンラインDDLを実行しないケースを試してみます。

mysql> start transaction;
Query OK, 0 rows affected (0.01 sec)
mysql> update users set name='test2' where id=1;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0

別セッション

mysql> select last_name from users where id=2;
+-----------+
| name      |
+-----------+
| taro      |
+-----------+
1 row in set (0.00 sec)

トランザクションを実行しているレコードと、DML を行なっているレコードが別で、where は index が効いているカラムに対して行なっているので、トランザクション中でも DML は正常に完了しています。

トランザクション中にオンラインDDLDMLを行うケース

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)
mysql> update users set name='test' where id=1;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0

別セッション

mysql> ALTER TABLE `users` CHANGE `gender` `gender` int(11) DEFAULT 2 NOT NULL COMMENT 'test comment';

(応答なし)

別セッション

mysql> select name from users where id=2;

(応答なし)

この時に、show full processlist を実行すると、応答なしとなっている2つのセッションが「Waiting for table metadata lock」となっています。

そしてトランザクションを commit すると、応答がなかった2つのセッションで応答が返ってきました。

おわりに

オンラインDDLが可能なDDLだからといって、何も考えずにDDLを行うのは危険ですね。
ただ、トランザクションが長時間発生しないテーブルであれば、オンラインDDLを実行するオプションをつけて実行することでリスクはかなり小さく抑えられそうです。

公式ドキュメントを読み込み、手元で実際に試してみると理解がかなり深まりますね。

MySQLの理解がまだまだ浅いので、バージョンが古いですが、過去読んだこの2冊を読み直していこうかな、と思っています。

現場で使える MySQL (DB Magazine SELECTION)

現場で使える MySQL (DB Magazine SELECTION)

間違えている箇所や説明が分かりにくい箇所等あれば、コメントなどでご教示いただけると大変ありがたいです。

attr_accessor(attr_writer)でインスタンス変数をセットするときはselfを省略できない【Ruby】

こんにちは。

最近 メタプログラミングRuby を読んだので、印象に残ったところをブログにまとめています。

今回は、Rubyのアクセスメソッド attr_writer, attr_accessor でインスタンス変数をセットするときにレシーバ(self.)を省略できないことについてまとめました。

サンプルコード

かなりシンプルなこちらのコードを実行すると何が出力されるでしょうか?

class Sample
  attr_accessor :name

  def set_name
    name = 'デフォルト太郎'
  end
end

sample = Sample.new
sample.set_name
puts sample.name #=> ?

ほぼ同じ内容をTwitterのアンケート機能で聞いてみた結果がこちらです。

attr_accessor は Sample クラス内に以下のコードを自動で定義してくれるので、name= メソッドによってインスタンス変数がセットされて「デフォルト太郎」と出力されそうな気がしますが、実際は何も出力されません

def name
  @name
end

def name=
  @name = name
end

この予想に反した結果となっている原因は、set_name メソッドにあります。

「name = 'デフォルト太郎'」が、ローカル変数の name に値を代入しているのか、attr_accessor で生成された「name =」メソッドをレシーバを省略して呼び出しているかが Ruby に判断できずRuby では前者(ローカル変数への代入)を採用することになっています。

よって、set_name メソッドはローカル変数の name に値を代入しているだけとなり、sample.name は 定義されていない インスタンス変数 @name を参照しているため、何も出力されないという挙動になっていました。

set_name メソッドを以下のようにすれば「デフォルト太郎」と出力されるようになります。

def set_name
  self.name = 'デフォルト太郎'
end

先ほどは省略していたレシーバ(self.)を明記することで、「name =」メソッドを呼び出していることが明確になったためです。

また、アクセスメソッドを使用せず、インスタンス変数に直接値を入れる以下の形でも「デフォルト太郎」が出力される挙動にすることができます。

def set_name
  @name = 'デフォルト太郎'
end

おわりに

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

意図しない挙動を避けるためのコードを2種類紹介しましたが、実務のコードでは self. をつける形もインスタンス変数に直接値を入れる形も見かけるので、どちらを選ぶかは好みな気がします。

メタプログラミングRuby では、今回取り上げたような Ruby の小ネタ的な話も色々と紹介されており面白いのでおすすめです。

メタプログラミングRuby 第2版

メタプログラミングRuby 第2版

【技術書まとめ26】リファクタリング Rubyエディション

こんにちは。

今回は、リファクタリング Rubyエディション を読みました。

本書は様々なリファクタリングのパターンについて、Rubyを使って説明している名著です。

学ぶことが多かったので、ポイントを定期的に見返せるよう記事にまとめました。 

特にいいなと思ったリファクタリングのパターンは、サンプルコードを使って解説したブログへのリンクを貼っていますので、気になるパターンがあれば合わせてご覧ください。

f:id:ysk_pro:20200611081009p:plain

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

  • リファクタリングとは、外から見えるふるまいを変えずに、ソフトウェアの内部構造を変えること
  • リファクタリング目的は、ソフトウェアをわかりやすくし、安いコストで変更できるようにすること

 

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

  • ほとんどのリファクタリングは、プログラムに間接的な階層を導入する。つまり、大きなオブジェクトや大きなメソッドを分解して、複数の小さなオブジェクトやメソッドにしている。間接化によって以下のメリットが得られる
    • ロジックの共有を実現する
    • メソッド名などで意図を説明できる
    • 変更箇所を他の部分から分離できる
  • プログラムが扱いにくくなる要因としては以下の4つがあり、これらが存在した場合はリファクタリングを検討すべき
    • 読みにくい
    • ロジックの重複がある
    • 機能の追加によって、動いているコードを書き換えなければならなくなる
    • 条件分岐が複雑
  • ソフトウェアでは、使われていない柔軟性は悪である。この柔軟性は、メンテナンスのために時間を食い、バグが入る余地を作り、リファクタリングをかけにくくする

 

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

  • リファクタリングを活用してソフトウェアを開発するときには、機能の追加を行う時間とリファクタリングを行う時間をはっきりと区別した方がよい
    • 機能を追加するときには、既存のコードを書き換えない。ただ新しい機能を追加することに専念する。最初に失敗するテストを追加し、テストを成功させる
    • リファクタリングする時には機能を追加しないようにし、コードの改造だけに力を注ぐ。テストの追加も行わない
  • バグレポートを受け取ったら、まずバグが浮かび上がるようなテストを書く。バグを突き止めるとともに、同様のバグがテストをすり抜けないようにするため

 

パフォーマンスについて

  • システムの内部で何が行われているかを正確に知っていたとしても、パフォーマンスは推測せずに計測すべき推測の10回に9回は正しくない
  • パフォーマンスの面白いところは、実際に分析してみると、実行時間の大半がコードのごく小さな一部で消費されていることである。コード全体に平等に最適化をかけると、実行時間の短いコードを最適化することになり効率が悪い

 

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

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

 

メソッド・フィールドの移動
  • メソッドは、そのメソッドが使用するデータを持つクラスに割り当てるべき
  • 条件分岐は、他のオブジェクトでなく自分自身のデータに基づくべきであり、他のオブジェクトのデータで条件分岐している箇所はクラスの移動を検討する
  • メソッドやフィールドをどのオブジェクトに管理させるかは、オブジェクトの設計でもっとも重要な判断の1つである。最初から正解にたどり着くのは難しいので、リファクタリングを使って設計を変えていけばよい

 

メソッドの抽出
  • 何かコメントを書くべきと感じる場合、コメントではなくメソッドに抽出することを考える。このときメソッド名はコードの仕組みではなく、目的に基づいてつける。メソッド名がコードの目的を説明しているなら、たった1行のコードであってもメソッド呼び出しに変える価値がある。コメントを探すとメソッド抽出すべきところが見つかりやすい
  • 値を返すことと、オブジェクトの状態に変化を与えることを同時に行なっているメソッドがある場合、問い合わせ用と更新用のメソッドに分割する。こうすることで再利用しやすくなる
  • ほぼ同じコードによる2つのメソッドがあり、違いはメソッドのちょうど中頃にある場合、重複部分を抽出してブロック付きのメソッドにして、違いの部分を yield で実行させると良い。この手法は「サンドイッチメソッドの抽出」という名前がついている(詳細をまとめたブログ記事

 

ポリモーフィズム
  • case文を見かけたら、ほとんどの場合はポリモーフィズムを利用することを検討すべき。case文の少なさは、オブジェクト指向らしいコードが持つ特徴の1つである。メリットとしては、新しい型を追加した時に存在している全ての条件式を探す必要がなくなり、新しいクラスを作って適切なメソッドを提供するだけでよくなる(詳細をまとめたブログ記事
  • 広い意味では同じようなステップを同じ順序で実行しているように見えるが、ステップが全く同じだとは言えない複数のメソッドは、共通部分をスーパークラスに移してポリモーフィズムに仕事をさせ、異なるステップはそれぞれがサブクラスで実行させる。この種のメソッドをテンプレートメソッドと呼ぶ。Rubyでは、モジュールのextendを使ったテンプレートメソッドの作成も可能である。モジュールをextendするクラスがーパークラスの役割を果たして共通部分を格納し、モジュールが特別なふるまいを実装する(詳細をまとめたブログ記事

 

クラス・モジュールの抽出
  • クラスが常に全てのインスタンス変数を使うわけではない場合がある。そのような時は、クラスの抽出、モジュールの抽出、サブクラスの抽出を検討する
  • 1つのクラスが異なる理由でたびたび書き換えられる時には、理由ごとにクラスを分けることを検討する
  • モジュールの抽出で、モジュールをインクルードするクラスを対象として呼び出したいクラスメソッドがある場合は、モジュールに included フックを作り、includedフックにクラスメソッドの定義を移す(詳細をまとめたブログ記事

 

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

 

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

 

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

 

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

 

おわりに

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

 

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

また、値段もトップクラスでした(笑)

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

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

こんにちは。

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

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

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

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

こんにちは。

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

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 の過去問の解いた割合

AtCoder Scores の精進グラフ

 

アルゴリズムを学ぶこと

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

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

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

 

Ruby を卒業すること

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

AtCoder Problems の言語別に解いた数のページ

オールRubyでした(笑)

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

 

おわりに

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

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

目指せ青色!!

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

こんにちは。

最近 リファクタリング Rubyエディション を読みました。本書はリファクタリングの様々なパターン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エディションでは、このブログよりもリアルのコードで解説しており分かりやすかったので、ご興味ある方は是非ご覧ください。

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

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

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

はじめに

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

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

問題

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 の値でイワシたちをグルーピングしてみましょう。

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_iB_i最大公約数で割る必要があります。例:[1, 2] と [2, 4] は同じグループとして扱いたいためです。
  • A_i が 負の場合は、A_iB_i 両方に -1 を掛けて、A_i は必ず正の値にする必要があります。例:[-1, 2] と [1, -2] は同じグループとして扱いたいためです。


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

A_i × A_j = - B_i × B_j

  • A_iB_i のどちらも 0 のケース

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

  • A_iB_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 いただければ返信させていただきます。

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