概要
原著者の許諾を得て翻訳・公開いたします。
- 英語記事: That one time I used recursion to solve a problem | Arkency Blog
- 原文公開日: 2017/08/11
- 著者: Robert Pankowecki
- サイト: Arkency Blog
Ruby: 問題解決に「再帰」を使った話（翻訳）
少し前に私はある問題に取り組んでいたのですが、どうも満足の行くソリューションが見つかりませんでした。しかし、私がめったに使うことのないツール「再帰関数」のことをふと思い出した途端、問題が実はずっとシンプルであることに気づいたのです。
皆さまご存知のとおり、RubyのEnumerableの反復処理やActiveRecordのクエリはとてもよくできているので、問題解決にeach以外のものが必要になることなどめったにありません。そしてこのときは、eachを5とおりもの異なる方法で使おうとし、アプローチをさまざまに変えては失敗を重ねていました。
経緯
話の流れはだいたい次のような感じです。あるイベント向けのチケットを販売するプラットフォームがあるとします。イベントはレースやマラソンなどいろいろありますが、イベントの内容はまったく異なっています。プロやセミプロの競技イベントもあれば、開催の2年前から告知と販売が行われているイベントもあります。
参加者（スポーツ愛好家とでも言うべきでしょうか）は、主催者が求める必須データや追加データの入力を求められ、時には入力量が膨大になることもあります。入力項目にはチーム名、年齢、自己最高記録などそれらしいデータもあります。そしてこれらのデータは時間とともに移り変わるのです...。
また、このプラットフォームは多くのさまざまなイベント向けに追加サービスを提供しています。たとえば保険（何らかのアクシデントでイベントに出席できなかった場合など）や宅急便（ですよね😋）などです。サービスの種類によっては、これまた大量の追加データの入力を求められます。コンバージョン率を下げないために、私たちはユーザーが購入する前にはこうしたデータの入力を求めていません。そこで購入完了直後の最初のページでデータの入力をユーザーにお願いしていますが、データをすぐに入力しない顧客もいます（チケットが取れてうれしかったのでしょう）。
このため、そこから先のシナリオが多岐に渡ることになります。保険がまだ有効になってない場合とか、主催者の入力する情報が不十分な場合とか、ユーザーの希望どおりにチケットを郵送できない場合などの可能性もあります。しかし顧客に不満を感じさせたくありません。顧客には料金に見合う楽しさを感じていただきたいと思っています。そこで私たちはリマインダー機能を実装しました。これによって、不足しているデータの入力を求めるメールをユーザーが間欠的に受け取るはずです。ただしメールは頻繁すぎてもいけない（嫌がられるのが普通）し、頻度が少なすぎてもいけません（ユーザーが見落とす可能性）。
しかも、リマインダーは購入時になるべく近いタイミング（購入直後の、顧客が問題点を忘れずにいてくれる期間）、およびイベント開催日時が迫ってきたタイミング（試合や競技の1年前よりも開催1週間前の方が正しいデータを入力する気になれる）に行うのが最も効果的です。そして言うまでもなく、必要なデータがすべて入力されればリマインダーはもう送信されません。
私はそのためのアルゴリズムを実装したいと思いました。リマインダーの送信頻度は購入直後から開催日に向けて順次下げ、同様に開催日から購入日までは逆方向に頻度を下げます。そして両者は中間のどこかで一致するはずです。時間軸で表すと次のような感じになるでしょう。
問題点
当初のいくつかのアプローチは似たり寄ったりというかほぼ同一でした。時間軸を半分に分け、左から右へ反復処理しながらリマインダーを置くごとに間隔を倍にします（最大1か月）。右から左へも同様に反復処理しつつ間隔を倍にします。
しかしこのソリューションには大きな問題が1つあったのです。時間軸の中央付近で2つのリマインダーが以下のいずれかの状態になってしまいました。
- 間が空きすぎる
- 中間の時点のリマインダーが存在しないため、顧客の不満は減るもののその分問題は大きくなるケース
- リマインダーの間隔は最大でも1か月にしたいのに、場合によっては50日も空いてしまうことがある
- 間が狭すぎる
- 顧客の不満が大きくなるケース
- 直前と直後のリマインダーが1か月空いているにもかかわらず、その間のリマインダー同士の空きが2日しかないことがある
アプローチを3とおり試してみたのですが、ことごとく同じ点でつまづきました。
解決方法
おわかりですね。左から右への反復処理のソリューションと右から左への反復処理のソリューションを真ん中あたりでつなごうとしたことが問題だったのです。ではどうすればうまくいくのでしょうか？開始時点と終了時点の両方の側から同時に反復処理することです。
class Calculator
def initialize(current_time:, event_starts_time:)
@current_time = current_time
@event_starts_time = event_starts_time
@eb = ExponentialBackoff.new(12.hours, 1.month)
end
def compute
sub_compute(@current_time, @event_starts_time, 0).sort
end
private
def sub_compute(left_boundary, right_boundary, current_level)
duration = @eb.interval_at(current_level).seconds
available_time = right_boundary - left_boundary
if available_time >= 3*duration
[
new_left = left_boundary + duration,
new_right = right_boundary - duration,
] + sub_compute(new_left, new_right, current_level+1)
elsif available_time >= 2*duration
[
left_boundary + available_time/2,
]
else
[]
end
end
end
このコードは次のように動作します。
- 同時に2方向に処理を勧めます。販売の瞬間（
current_time,left_boundary）から右に進んで時間を進めます。そしてイベント開催の瞬間（event_starts_time,right_boundary）から左に進んで時間を戻します。 - 各ステップで特定の長さの時間を用います（12時間から始めます）
- 次のステップに進むたびに時間の長さを倍にします
- ただし最大は1か月です
- どのステップでも以下の3つのうちどれかに該当する可能性があります
- 直前の2つのリマインダーの間の時間が空きすぎて（
3*duration）リマインダーを少なくとも2つ（両側から1*durationずつ）足せる状況: この場合はリマイダーを追加して残り時間内で再帰的に処理を試行します。 - 直前の2つのリマインダーの間の時間が、ちょうど両者の中間にリマインダーが1つだけ収まる状況（たとえばリマインダー同士の間隔が76日、かつ期間が1か月に等しい場合）: この場合1か月という期間で分割されたリマインダーを置くには足りないので、前後のリマインダーからちょうど38日離れた時点にリマインダーを1つ足します。この場合（私が望んでいた）1か月を超えていますが、少なくとも2つのリマインダーが近づきすぎてはいないのでここではOKです。
- リマインダーを足せるほどの期間がもう残っていない状況
- 直前の2つのリマインダーの間の時間が空きすぎて（
わずか12行かそこらのコードに、このソリューションがすっぽり収まっています😀。
購入日とイベント開催日の間が数年以上空くことはないので、スタックオーバーフローの可能性については心配ありませんでした。期間がこれより伸びると、リマインダーを1年分算出するのにメソッド呼び出しが6つ必要です。
お知らせ
今週私たちArkencyは新刊「Domain-Driven Rails」を刊行いたしました。
総勢140ページに盛り込まれた10の秘訣を用いて、Railsアプリでよりよいアーキテクチャを達成できます。
Arkencyニュースレターをご購入いただくことで、常に最大ディスカウントおよび無料のRuby on Railsレッスンを毎週お受け取りいただけます。