ﾕﾕﾕﾕﾕ

webエンジニアです

Designing Data-Intensive Applications を読むにさきだって

本棚

f:id:jnsato:20201213190703j:plain

　年末年始の課題図書を紹介する。といっても紹介するのは一冊だけである。一冊だけではあるが、骨太な一冊を選んでいる。積読を消化するよりも絶対これを読みたい！　というホットな気持ちで手に入れた本であるため、初々しいアティチュードを記録する目的で書く。

　それは Designing Data-Intensive Application というオライリー社の一冊で、『データ指向アプリケーションデザイン』のタイトルで邦訳もされている。

データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理

データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理

  • 作者:Martin Kleppmann
  • 発売日: 2019/07/18
  • メディア: 単行本（ソフトカバー）

　nand2tetris （これは今夏読んだ）と並んで teachyourselfcs.com で強くプッシュされていた一冊である。 nand2tetris は「コンピュータ・アーキテクチャ」のカテゴリの入門書であるが、他方のこちらは「分散システム」の項目に分類されている。

　nand2tetris は読者が手を動かしながら学ぶことを要求していたのに対して、こちらは個別の技術の使い方に深入りすることはなく、一般性の高い理論書として読みやすい構成になっているとの評判である。なにより原著の出版は2017年であり、いわゆる正統派のテキストにしてはまだまだ若く、トピックとしても老いていない。古びていないどころか、たかだか出版後3年にして国内外で高く評価されているのは、なににも増してこのテキストの有効性をあかし立てている。

　さて、内容について、目次をみるとおよその関心内容がわかる。おおよそ三部に大別されており、それぞれが注目するのは次のような項目群である。

「分散システム」をトピックとしつつ、「マイクロサービス」という語句がフィーチャーされていないのが秀逸であるとおもう。実際、上に並べたヘッドラインの文言は、古典的で骨太な概念を中心に肉付けされたものという印象を与え、賞味期限の早いバズワードには最初から目もくれないスタンスが気に入った。

　序説から少しだけ抜粋する。

CPU clock speeds are barely increasing, but multi-core processors are standard, and networks are getting faster. This means parallelism is only going to increase. (xiii)

これに関連してもう一箇所。

We call an application data-intensive if data is its primary challenge--the quality of data, the complexity of data, or the speed at which it is changing--as opposed to compute-intensive, where CPU cycles are the bottleneck. (xiii-xiv)

　システムの価値はデータに宿るということ、これは言われてみれば当たり前の話であるが、真理としてひろく一般に浸透しているかというと怪しいところがある。僕自身、データは大事であると心がけたり、チームに対して主張することはあっても、それはどちらかというと直感的で、理論的支援を持たないアイデア（要するに「データが壊れると後始末でひどい目をみる」という経験則）に過ぎなかった。同じ主張をするに及んでも、背景の文脈をきちんと整理できているかどうかが鍵になる。その意味でも、一冊の書籍の議論に沿いながら、知識を体系立てて入力できる機会に興奮が高まっている。

「分散システム」というと、なんだか Google の入社試験で設計させられるような、厳かで近寄りがたい構築物のような響きがある。しかし複数台構成で冗長化した単純なウェブシステムもまた、ひとつの分散システムにほかならない。つまるところ、分散システムとはいまや空気のように当たり前のアーキテクチャであり、ある意味では誰にでもできるが、正しく理解して運用するには正しい知識が必要であることに変わりはない。

　サーバーレスであるとかマイクロサービスというようなバズワードはいったん傍において、そうした個々の技術や概念を要請することになった中心的な議論はなんであるのかを学ぶこと、そしていわゆるトレンド技術がそれらの問題をどういう形式において解決できるかということ。そのあたりをより具体性をもって眺められる目を獲得するつもりで、年末年始はこの本に向き合おうとおもう。

AtCoder で緑難度の問題を解けるように稽古している

生活

　競技プログラミングの練習、いわゆる「精進」を11月から再開している。

　9月から10月までは、仕事探しの一環でカジュアル面談に多く参加してみたり、面接対策に時間を割いていて、しばらく間が空いていたのだった。コンテストへの参加もしばらくご無沙汰になっており、9月に茶色レーティングになってからはとくに、勉強時間も参加時間も捻出できていないのであった。

　いま、仕事探しがひと段落を迎えたところで、あらためて稽古にいそしんでいる。

　再開直後は感覚がやや離れている感覚があったが、これはすぐに回復させられた。もともと夏あたりの時点では「ABCで問題Cまでを30分前後で攻略できること」を目標にしていた。この方針である程度の手応えこそ得られ、結局問題Cまでしか考慮にいれない戦略であって、その先は運任せになってしまっていた。茶色難度までを効率的に攻略することに集中できても、その先の難度の問題を解く実力は必ずしも向上しなかった。つまるところ、問題Cまでをスピーディに回答できても、そのさきでさらにスコアを積めるとは限らないし、問題Cまでの時点で躓いてしまうと挽回するのがこの上なく困難になってしまうわけである。

　端的にいって、次のステップに進むべきときなのだろう。そこで、最前よりはABCの問題Dにおよそ相当する、緑色難度の正答率をあげることを目標において取り組んでいる。問題集としては、 AtCoder Problems のトレーニングモード で難度 HARD の百題を先頭から順に取り組んでいる。

　やってみると慣れるものなのか、わりにうまく解くことができることも多く、手応えは感じられるし、それが心地よい。6問に1問程度、うまく方針を立てられずに解説に助けを求めてしまうものの、およその精度としてはそう悪くないし、さらに練習を積むことで改善できるイメージも湧いている。一問あたりの回答時間もおよそ40-60分ほどに抑えられているから、本番のコンテストでもいくらかは使い物にできるのではないかとおもっている。

　ちなみに同じトレーニングモードで中級をコンプリートしたのが8月末であった。そのときの記事がこちらになる。

jnsato.hateblo.jp

　これを終えた直後から2ヶ月以上中断していたわけだが、まだまだ成長できていることを感じられて非常に励みになる。さしあたり、この調子で稽古を積んでいけば、向こう2-3ヶ月中にはレーティングを緑に更新できるくらいの手応えはある。せっかく最初から C++ を選んで取り組んでいるのだから、そのアドバンテージを活かせるレベルまで早く到達したいともおもうが、これはまだまだ身の丈に合わない願いだろう。

　成長を感じられることが何より嬉しいことである。そしてこの感触は、日々コツコツと稽古を積み重ねてこそ心地よく感じられる。ひとまずは目の前の問題群を順繰りに解いていくこと、そしてきちんと本番コンテストに継続的に取り組むこと、このあたりの緩いハードルを目標においてのんびりと続けていきたい。

bundle update --conservative で狙った gem だけをアップデートする

Ruby TIL

TL;DR

ミニマムなバージョンアップを行いたいときは bundle update --conservative を使おう

gem の更新

　ライブラリのバージョンアップをしようとしているとする。単に bundle update と叩いてすべての依存を一括でバージョンアップするのは、差分を追うことがまず不可能になってしまうから、個別のライブラリをひとつずつアップグレードしていきたい。

　功利的にも、例えば LRU 方式で一日ひとつずつのライブラリをアップグレードしていく、くらいのやり方であれば、それなりの頻度で更新を行っていけるし、チームに対してもよい影響を与えていけるだろう。

　というわけで、個別のライブラリをターゲットに bundle update を実施したいわけであるが、必ずしもそれで十分ではないことがある。変更範囲を最小限に bundle update を実行するには、 --conservative オプションを使おう、というのが今日の学びである。

サンプル

　適当な Gemfile と Gemfile.lock を用意してみた。

　Gemfile に記載された3つの gem のうち、 Gemfile.lock に定義されたバージョンと最新バージョンの乖離をテーブル化するとこうなる。

name current_version upstream_version
capistrano 3.11.0 3.14.1
capistrano-bundler 1.4.0 2.0.1
capistrano-rails 1.4.0 1.6.1 
# frozen_string_literal: true

source "https://rubygems.org"

git_source(:github) {|repo_name| "https://github.com/#{repo_name}" }

group :development do
  gem 'capistrano'
  gem 'capistrano-bundler'
  gem 'capistrano-rails'
end

GEM
  remote: https://rubygems.org/
  specs:
    airbrussh (1.4.0)
      sshkit (>= 1.6.1, != 1.7.0)
    capistrano (3.11.0)
      airbrussh (>= 1.0.0)
      i18n
      rake (>= 10.0.0)
      sshkit (>= 1.9.0)
    capistrano-bundler (1.4.0)
      capistrano (~> 3.1)
      sshkit (~> 1.2)
    capistrano-rails (1.4.0)
      capistrano (~> 3.1)
      capistrano-bundler (~> 1.1)
    concurrent-ruby (1.1.7)
    i18n (1.8.5)
      concurrent-ruby (~> 1.0)
    net-scp (3.0.0)
      net-ssh (>= 2.6.5, < 7.0.0)
    net-ssh (6.1.0)
    rake (13.0.1)
    sshkit (1.21.1)
      net-scp (>= 1.1.2)
      net-ssh (>= 2.8.0)

PLATFORMS
  ruby

DEPENDENCIES
  capistrano
  capistrano-bundler
  capistrano-rails

BUNDLED WITH
   2.1.4

　この設定のプロジェクトについて、 capistrano-rails だけを最新バージョンに更新してみよう。

単に bundle update capistrano-rails を実行する

　単に bundle update capistrano-rails と実行すると、差分としてはこうなる。

   specs:
     airbrussh (1.4.0)
       sshkit (>= 1.6.1, != 1.7.0)
-    capistrano (3.11.0)
+    capistrano (3.14.1)
       airbrussh (>= 1.0.0)
       i18n
       rake (>= 10.0.0)
       sshkit (>= 1.9.0)
-    capistrano-bundler (1.4.0)
+    capistrano-bundler (2.0.1)
       capistrano (~> 3.1)
-      sshkit (~> 1.2)
-    capistrano-rails (1.4.0)
+    capistrano-rails (1.6.1)
       capistrano (~> 3.1)
-      capistrano-bundler (~> 1.1)
+      capistrano-bundler (>= 1.1, < 3)
     concurrent-ruby (1.1.7)
     i18n (1.8.5)
       concurrent-ruby (~> 1.0)

capistrano-rails だけを更新することを意図したつもりが、依存先の capistrano と capistrano-bundler も同時に更新されている。依存は解決されているため現実的に問題ないかもしれないとはいえ、例えば capistrano-bundler のメジャーバージョンが意図せず上がってしまっているのは実に気持ちが悪い。あくまで capistrano-rails を単体で更新するにはどうするのがよいだろう？

--conservative オプションを与えて実行する

　bundle update capistrano-rails --conservative とオプションを追加してあげればよい。結果、次の通りにきちんと狙った gem だけが更新できており、依存先の更新を巻き込んでしまわずに済んでいる。

   specs:
     airbrussh (1.4.0)
       sshkit (>= 1.6.1, != 1.7.0)
     capistrano (3.11.0)
       airbrussh (>= 1.0.0)
       i18n
       rake (>= 10.0.0)
       sshkit (>= 1.9.0)
     capistrano-bundler (1.4.0)
       capistrano (~> 3.1)
       sshkit (~> 1.2)
-    capistrano-rails (1.4.0)
+    capistrano-rails (1.6.1)
       capistrano (~> 3.1)
-      capistrano-bundler (~> 1.1)
+      capistrano-bundler (>= 1.1, < 3)
     concurrent-ruby (1.1.7)
     i18n (1.8.5)
       concurrent-ruby (~> 1.0)

　conservative というと必ずしもいい響きに聞こえないけれども、ことライブラリの更新というタスクについていうと、保守的に進めて悪いことなんかないと思っている。というより、デフォルトの振る舞いが --conservative であることを期待していた身にとっては、オプションを明示しない限り変更範囲が最小とならないというのはちょっと意外であった。思わぬ形でえた学びとして、正しく Today I Learned であった。

「決断をしない」という決断をすること

本棚

アーキテクトの目的は、方針とは無関係に詳細を決めながら、方針をシステムの最も重要な要素と認識するシステムの形状を作ることである。こうすることで、詳細の決定を延期や留保することができる。1

　メールマガジンの配信システムを実装している。

　配信基盤には外部システムを利用している。外部システムの API を自社システムにつなぎこむだけだし、ひとまずは実験的に送信してみたいというクライアント要望から、急なスケジュールで実装を進めることになった。

　配信 API の呼び出しを抽象化するクラスを設計し、リクエスト/レスポンスのデータ構造も外部システムの仕様書通りにモデリングできた。つまり、要望通りにひとまず「実験的な送信」を行える環境はそろったわけである。

　実現したい振る舞いは十分実装できているから、あとはクラスを呼び出してレスポンスを検査する10行ばかりの簡単なスクリプトを作るだけ、というところで、追加要件があがってきた。いわく、クライアントが事前に用意した配信リストに沿って配信するのではなく、一定の条件でユーザーを抽出して動的に配信リストを作成し、あとでそのリストを提出してほしいのだという。

　初回配信日はすでに決まってしまっており、あわてて配信履歴の記録を実装しなければ、と焦ったメンバーが、急ごしらえでテーブルを設計した。みると配列として定義されたカラムがあり、そこにメールアドレスの配列を愚直に格納する構造となっている。

　Postgres の Array 型を使った設計で、確かに使い所によっては便利なデータ構造かもしれないが、少なくともこのユースケースでは不適格だという直感があった。たしかに現状求められる数百、数千の配列を適当に保存するだけなら耐えられるかもしれないが、まんがいち将来数十万、数百万と配信対象が拡大するとどうなってしまうかわからない。おそらく保存するだけなら耐えられるだろうが、「この数百万の配列対象の中に任意のメールアドレスが含まれているか調べてほしい」など検索系のユースケースが生じてしまうと、おそらく立ち行かなくなる。かと言って、実際に配信システムが本採用されて、やがて数百万単位の配信が実行されるようになるまで成長するかどうかはまだわからないし、検索要件まで含まれるようになるかどうかもわからない。まだわからない要件のために最適化を追求するのは、文字通りのオーバーエンジニアリングに陥ってしまうだろう。

　言ってみればこういう二律背反が生じてしまったとみなすこともできるだろう。

  • スケーラビリティをはなから捨てた設計を本番投入してしまうか
  • 設計をクリーンにするために求められるスケジュールは満たせないと謝罪するか

　とはいえ、この命題は誤っている。しかし（しばしば起こりうることだが）この誤った命題に基づいて議論してしまうと、きっと「技術の理解できないビジネスサイド」と「頭でっかちで顧客要望に対応できないエンジニア」が、互いに偏見をなすりつけあって、醜い闘争に至ってしまうだろう。

　僕のたどり着いた答えはこうである。

  • スケジュール上、入念な設計を検討する余裕はないが、かといって不十分な設計を本番投入する必要もない
  • メールアドレスのリストを保存したいだけなら、一時ファイルに保存して適当なストレージにしまっておくだけでよい

　これでひとまず顧客要望は実現できるし、不十分な設計を本番投入するリスクもなくなる。将来的にやはりテーブル設計が必要なら、それを検討する時間稼ぎもできる。ファイルに出力してストレージにアップロードするだけのコードなら簡単に書いて簡単に捨てられるわけで、負債化したスキーマを管理したり、本番DBでデータ移行しなければならないようなことも避けられる。まさに三方よしの打開案であって、我ながらよいアイデアを出せたと満足することができている。

　あとから振り返ると、この判断はまさに『クリーン・アーキテクチャ』に書いてあるような発想であるし、そう考えると、アーキテクトとしても正しい判断だったのだろうとあらためて満足を深めている。

ソフトウェアをソフトに保つには、できるだけ長い期間、できるだけ多く選択肢を残すことである。では、「残すべき選択肢」とは何だろうか？　それは、重要ではない詳細である。2

「メールマガジンを配信する」という大目標がすでに実現できているとき、「誰に配信したか記録する」というのは、重要とはいっても副次的な要件である。それは決して雑に管理すべきではないが、厳密な設計が求められる場面というわけでもない。大事なのは、そこにスケーラビリティが求められるのかどうか、誰もまだ知らないということである。

　しかし単に「配信対象者を出力すること」が求められているだけだと考えると、出力装置としてデータベースを使わなければならない、というのは、これは思い込みである。単に出力先を選択するのであれば、テーブルを作るのにも ORM につなぎこむのにも工数がかかり、そしてやがて変更したり廃棄するときにもまたコストがかかる RDBMS に出力するよりも、単にファイルに書き込むだけの方が遥かに安上がりだろう。

　適切なテーブル設計は、それが必要とされたときに考えればよいし、ひとまずは時間稼ぎさえできていれば、やがてより時間が詳細な要件を明らかにしてくれるはずである。アンクル・ボブはこういっている。

決定を遅延できれば、その分だけ適切に作るための情報が数多く手に入る。3

　手前味噌にほかならないが、不確実な未来を織り込んで判断をくだせた自分に満足できた経験には違いないので、記念としてブログに書き残しておく。「判断をくだした」といっても「いまは判断すべきでないという判断をした」というわけで、先延ばしにしたことを体よくいっているだけではあるが、アーキテクトの態度としてはそれで間違っていないらしい。

　エンジニアとして判断や意思決定が求められる場面は大小さまざまある。今回は自分なりに達成感が残せたためこうして振り返っているが、より精度を高め、より複雑な問題に対処するためには、結局のところより多くの判断に立ち合い、このようにそれを振り返る機会を持てるよう努めるべきなのだろう。

　少なくともこの一件で、考え方としてはおよそ間違っていない方針を持てているらしいことがわかり、いくらか自信も深められたので、今後は試行数を増やして経験を積んでいきたいなと感じている。「アーキテクト」という職能についてあまり深く考えたことはないものの、結局のところ「いま決めるべきこと」と「いま決めなくてもいいこと」の境界を正しく認識できていれば、おのずと正しい道筋は見えてくるのかもしれない。そのあたりの感覚もこのさき研ぎ澄ませていければ幸福だと思う。

  1. Clean Architecture　達人に学ぶソフトウェアの構造と設計 (アスキードワンゴ) Kindle版. Loc. 2270↩

  2. Clean Architecture　達人に学ぶソフトウェアの構造と設計 (アスキードワンゴ) Kindle版. Loc. 2263↩

  3. Clean Architecture　達人に学ぶソフトウェアの構造と設計 (アスキードワンゴ) Kindle版. Loc. 2285↩

任意の区間で任意の整数の倍数を数える

TIL Ruby

　Codility の問題をいくつか解いてみていて、どうにも解けずに諦めてしまった問題があった。匙を投げて解法を検索してみて、あまりにスマートに解けるものだから、なおさら悔しい思いをしている。そこで供養の意味も込めて振り返りをまとめておく。

　当該の問題は Lesson 5 の count_div である。リンクは以下に貼る。

app.codility.com

　 A, B, K の3つの整数が与えられ、 [A, B] の区間に含まれる K の倍数の個数を数え上げる。

　制約として定式化すると次の通りである。

  • \{ i:A\leq B,i\ mod\ K= 0\}
  • 0\leq A\leq B\leq 2,000,000,000
  • 1\leq K\leq 2,000,000,000

　A から B までを愚直にイテレートする解がまず思い浮かぶが、これでは計算量が O(B - A) であるから制約に照らすと許容できない。で、自前のテストケースを用意した上で効率化する方法を考えてみるのだが、どうにもうまく仕様を満たせない。 A = 0 の場合、 A = B = 0 の場合、 A\ mod\ K = 0 の場合、 B\ mod\ K = 0 の場合 ... などのケースを同時に満たすことができず、いっけん簡単に見えるにもかかわらず解ききることができずうろたえてしまった。なお利用したテストケースは gist として公開してある。

count_div_test.rb · GitHub

　バグがあるというよりは単に計算の帳尻が合わないということが自分でも痛いほどわかっていて、コーディングスキルというよりも数学的思考の弱さを突きつけられているようで、解いていて本当に辛かった。結局は検索エンジンに頼って正答例を得てしまったわけだが、5行で実装されているその解法をみるにつけても、自分で解答にたどり着けなかった悔しさが募るばかりである。

　そこで、ここでは正当例のコードを基に証明も考えてみた。もちろん証明してから解ければ申し分ないし、本来はそうありたいわけだが、あいにくその力がなかったということで、振り返りも兼ねてまとめる。

証明

定義

  • r = A\ mod\ K \left( r\geq 0\right)
  • m = A\ -\ r\ \left( 0\leqq m \lt r\right)

とおく。m は A 以下の最大の K の倍数ということになる。

手続き

　 [A, B] の区間における K の倍数の個数を考える。

  1. a = 0 のとき
    • m = A より [m,B] の区間について考えればよい
  2. a > 0 のとき
    • 便利のためにこの場合も [m, B] の区間を数え上げる。
    • m は [A, B] に含まれない倍数であるが、 [m, B] について解を求めて、最後に -1 を加えれば結局 [A, B] についての解が得られる

　というように、 [m, B] の範囲における K の倍数を数え上げるという方針で考えればよい。さらにこれを変形して [0, B-m] としても、範囲内に含まれる倍数の個数は変わらないのは明らかである。

　以上より、問題の条件を求める計算式は (B - m) / K + 1 となる。 [0, B-m] の区間には 0 が含まれ、これも K の倍数であるから、最後に 1 を加えている。

　コードとしてはこうなる。

def solution(a, b, k)
  r = a % k
  m = a - r
  answer = (b - m) / k + 1
  answer -= 1 if r > 0
  answer
end

おわりに

　こういった整数論的な問題は、僕にとっては明らかな苦手分野だ。問題文をみたときにはすでにこのような思考を組み立てられる頭脳を持つ人もいるのだと思うとまったく恐ろしい。

　同じ土俵で勝負することは到底敵わないわけであるから、こうしてきちんと復習はしつつも、自分の勝てる土俵を見つけないといけない、そしてそこで戦う根性を身につけなければならない、と改めて考えさせられる契機となった。もっとうまくなりたいと思うが、それは当然、もっと修行しなければいけないという意味にほかならない。とはいえこのほかにも学びたいものはたくさんあるわけで、どの優先順位で何をやるかをよく考えて取り組まないと、二兎を追うだけの結果となりかねない。

配列を任意の個数の部分集合に均等に分割するアルゴリズム

Ruby TIL

　長さ N の配列があり、それを M 個の部分集合に均等に分割したい。

　制約を簡単に定義するとこうなる。

  • 0 <= N
  • 1 <= M <= 100

TL;DR

active_support/core_ext/array/grouping の Array#in_groups がそのものズバリである。

誤ったロジック

　3年前の自分が実装したロジックをざっくり書くと、それはこんなものであった。仮に N = 10, M = 3 とおいている。

def generate_array(size)
  i = 0
  Array.new(size) { i += 1 }
end

def solve(arr, m)
  group_size = (arr.size + m - 1) / m
  arr.each_slice(group_size).to_a
end

N = 10
M = 3

arr = generate_array(N)
solve(arr, M)
# => => [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10]]

　これだと一見 M 個の部分集合に分割できたようにはみえる。しかし各部分集合に属する要素数は [4, 4, 2] となっている。 [4, 3, 3] と均等に分割したいところである。

　それだけではない。3年越しに見つけた問題点は次である。

N = 0 のとき

　Array#each_slice に 0 を渡すと ArgumentError (invalid slice size) が発生してしまう。

N / group_size != M のとき

　例えば N = 6, M = 4 のときを考えてみよう。

N = 6
M = 4

arr = generate_array(N)
solve(arr, M)
# => [[1, 2], [3, 4], [5, 6]]

　4個の部分集合に分割するはずが、3つにしか分割できていない。group_size を切り上げで計算してしまっているため、部分集合あたりの個数を正しく計算できていないのである。

def solve(arr, m)
  group_size = (arr.size + m - 1) / m
  arr.each_slice(group_size).to_a
end

　要するに、誤ったロジックであるわけである。

　配列の操作であるから、標準 API に便利メソッドがありそうな気がする。で、 ruby-doc.org で Array から Enumerable から、それらしいメソッドを探してひたすら読んでいたが、代替できそうなものは見当たらない。「自前で実装するしかないのか…」と思い始めたとき、 active_support/core_ext にそのものズバリな API を見つけた。

Array#in_groups

　手短に改善後のコードを示すと、こうなる。

require 'active_support/core_ext/array/grouping'

def generate_array(size)
  i = 0
  Array.new(size) { i += 1 }
end

def solve(arr, m)
  arr.in_groups(m, false)
end

　N = 0 で空集合に対して実行しても ArgumentError を吐かずに、M個の部分集合を作ってくれる。

N = 0
M = 4

arr = generate_array(N)
solve(arr, M)
# => [[], [], [], []]

　また先ほどうまく機能しなかった N = 6, M = 4 のケースでも、部分集合の個数はあっているし、きちんと均等に分割されてもいる。

N = 6
M = 4

arr = generate_array(N)
solve(arr, M)
# => [[1, 2], [3, 4], [5], [6]]

　ここで終わってしまってはそれまでだから、せっかくなので Array#in_groups の実装も覗いてみよう。

あるべきアルゴリズム

https://github.com/rails/rails/blob/v6.0.3.4/activesupport/lib/active_support/core_ext/array/grouping.rb#L62-L86

def in_groups(number, fill_with = nil)
  # size.div number gives minor group size;
  # size % number gives how many objects need extra accommodation;
  # each group hold either division or division + 1 items.
  division = size.div number
  modulo = size % number

  # create a new array avoiding dup
  groups = []
  start = 0

  number.times do |index|
    length = division + (modulo > 0 && modulo > index ? 1 : 0)
    groups << last_group = slice(start, length)
    last_group << fill_with if fill_with != false &&
      modulo > 0 && length == division
    start += length
  end

  if block_given?
    groups.each { |g| yield(g) }
  else
    groups
  end
end

　コメントに書かれていることがすべてではあるが、言われてみると「なるほど！」と単純に納得できるだけのシンプルなアルゴリズムである。

  # size.div number gives minor group size;
  # size % number gives how many objects need extra accommodation;
  # each group hold either division or division + 1 items.
  division = size.div number
  modulo = size % number

　配列の長さを分割したい個数で除算して、ひとつの部分集合あたりの要素数を division に定義している。 modulo は剰余であり、この個数にあたる部分集合については、 division + 1 個の要素を持つことになる。

　ところで Integer#/ ではなく Integer#div を使っている。Integer#/ は 引数のクラスに応じて返り値のクラスが決定されるのに対して、 Integer#div は引数のクラスに関わらず Integer が返り値となる。つまりはこういうことである。

4 / 2.0
# => 2.0

4.div 2.0
# => 2

　Integer#div は ActiveSupport の拡張ではなく、 Ruby 標準の API である。これも知らなかった。

　本題に戻ろう。続いてのコードはこうである。

  # create a new array avoiding dup
  groups = []
  start = 0

　分割後の部分集合を格納するための配列と添字を初期化している。 #dup を忌避するとあるが、この後の処理を読めば #dup がないのは妥当であるように思われ、コメントの意図はよくわからない。

  number.times do |index|
    length = division + (modulo > 0 && modulo > index ? 1 : 0)
    groups << last_group = slice(start, length)
    last_group << fill_with if fill_with != false &&
      modulo > 0 && length == division
    start += length
  end

　length で次の部分集合の要素数を決定している。 modulo 個の部分集合は division + 1 個の要素を持つという冒頭のコメントの実装である。 Array#slice で length 個分の部分集合を添字ベースで切り出したものを、変数 last_group として定義し、ただちに groups に代入している。次行では、各部分集合の要素数を揃えるために、 fill_with を last_group に破壊的に追加している。あらかじめ last_group にこの処理を施しておくのではなく、 groups << last_group を実行した後で last_group << fill_with としているのが面白い。 if fill_with != false とあるように、 #in_groups の第二引数に false を渡しておけば、要素数は埋められない。説明は省略したが、上で書いたコードについても fill_with = false としてある。最後に start += length ですでに分割した要素数だけ添字をずらして、イテレートブロックは終了である。

  if block_given?
    groups.each { |g| yield(g) }
  else
    groups
  end

　最後にブロックを与えられたときの動作が定義されているが、これは触れるまでもないだろう。

　計算量は部分集合の個数を M として O(M) である。冒頭で制約は 1 <= M <= 100 と与えたから、配列がいくら長くてもこのアルゴリズム単体としては十分問題なく動作できる。

　と、 Array#in_groups のアルゴリズムをみて思ったことを徒然なるままに書いた。結論として、表題のアルゴリズムを Ruby で実装するのであれば ActiveSupport のサポートを借りれば十分であるし、別言語で実装するのであっても ActiveSupport の実装を参考にすれば十分満足のいくアルゴリズムができるだろう。

ruby-doc のバグを報告した

Ruby

　ruby-doc.org が一部落ちていたので報告した。正しい報告先を探すのがたいへんだったので備忘録で書いておく。

　落ちていたのは ruby 2.7.2 の標準ライブラリのドキュメントで、 stringio や time などいくつかのページが 404 を返していた。それから HTML の title 要素が Ruby 2.7.7 と誤って記載されていた。

　これはコントリビュートのチャンス？　と思ってリソースを探したが、報告先として指示されている documenting-ruby.org は 2016 年で更新が止まっているし、リンク先の github リポジトリ（ documenting-ruby/ruby  ）も 2015 年以来停止している。他にもあらゆるリンクが死んでしまっていてどうにもならない。

　仕方がないのでメールを書いた。バグ報告のリンクが運用停止されている以上、報告したところでなしのつぶてだろうな...と思っていた。ところが予想を裏切ってその日の夜（アメリカ時間の朝かな？）には返信がきて、次の朝（日本時間）には直っていた。

　というわけで、メールの到達率を過小評価してはならない、という教訓をえた。きちんと書けば読んでもらえるし、すぐに対応してもらえることもあるようだ。

　もっとも本記事の執筆時点ではまだスタイルシートが 404 を返してしまっているみたい。自動生成の doc をホストするだけなのになんでこうもろもろ壊れているのかは謎のまま。メールでその辺りも尋ねてみたのだが、華麗にスルーされた。