ネットの海の片隅で

技術ネタの放流、あるいは不法投棄。

排他的リソースに対するスケジュールの重複判定をSQLでシュッとやる

突然ですが、排他的にしか利用できないリソースに対するスケジュールの重複判定の問題を考えてみようと思います。 典型的には「ある会議室では同時に複数の会議を開催できない」というようなスケジューリングの問題です。

ある既存のスケジュールを下の図のピンクで示します。

すると、そこに対して新規にスケジュールを追加するときのパターンは既存のスケジュールの始点と終点のまたぎ方によって分けられ、黄色と青色を合わせて全部で6パターンあります。 *1

f:id:s_osa:20161126233115p:plain

このうち、黄色はピンクと重複している部分があるもの(invalidなスケジュール)、青色は重複していないもの(validなスケジュール)です。

新規に追加するスケジュールがinvaidな黄色の場合にエラーを返したいのですが、4パターンもあって場合分けが大変そうです。

というわけで、青色のパターンから考えます。

青色になる条件

黄色と違って、青色になる条件は比較的簡単です。

  • 新規追加するスケジュールの終点が既存のスケジュールの始点よりも前にある
  • 新規追加するスケジュールの始点が既存のスケジュールの終点よりも後にある

のいずれかですね。

したがって、新規追加するスケジュールの始点と終点をそれぞれSn, En、既存のスケジュールの始点と終点をそれぞれSe, Eeとすると、青色になる条件はEn < Se OR Sn > Eeとなります。

黄色になる条件

青色になる条件がわかったので、元々求めたかった黄色になる条件を求めます。

新規追加するスケジュールは黄色か青色のいずれかになるので、青色にならなければ黄色です。

したがって、さっき調べた青色になる条件を使うとNOT (En < Se OR Sn > Ee)と書けます。

ド・モルガンの法則を使って変形するとNOT (En < Se) AND NOT(Sn > Ee)

もう一歩整理してEn > Se AND Sn < Eeです。

シンプルになりました。

SQL

この条件を使って、これから挿入しようとするスケジュールが既存のスケジュールと重複していないかどうか調べるSQLを書くことができます。 *2

select
  *
from
  rooms
  inner join events on rooms.id = events.room_id
where 
  roooms.id = ROOM_ID
  and En > events.start_at
  and Sn < events.end_at
;

さいごに

このような重複判定をApp側で複雑に場合分けしてバリデーションしていたコードがあったのでこのエントリを書きました。

手続きで温かみある感じではなく、スパッと宣言的に判定していきたい気持ちです。

*1:議論が煩雑になって面倒なので、ここでは境界値を含むことはないこととします。

*2:テーブル定義はなんとなく察してください。

MIX PENLa-PRO のカスタム色設定

ミックスペンラプロといえば全国のP御用達のペンライトですが、このペンライトは色の並びがよくわからない感じになっています。

参考:コンサートペンライト/MIX PENLa-PRO

MIX PENLa力が低いと、「あの色どこだっけ?」とか「あ、このピンクじゃない! もう少し淡い色が欲しい!」みたいなことがよくあります。

そこで、カスタム色設定機能を使って、色相環的に色が並ぶようにしました。 直感的に色を探すことができるようになったことによって、ガールズの応援に集中することができます。

順序 色番号 色名
1 1 レッド
2 2 エンジレッド
3 3 ローズ
4 18 ピンク
5 19 ピーチ
6 20 サクラピンク
7 23 ラベンダーパープル
8 22 パープル
9 21 バイオレット
10 4 ブルー
11 7 アクアブルー
12 5 ライトブルー
13 6 アイスブルー
14 24 ホワイト
15 17 エメラルドグリーン
16 16 ペパーミントグリーン
17 13 グリーン
18 15 ライトグリーン
19 14 イエローグリーン
20 8 イエロー
21 9 ライトイエロー
22 12 ヤマブキオレンジ
23 11 パッションオレンジ
24 10 オレンジ

Rubotyでくじびきをする

Ruboty pluginを書いたので簡単に紹介しておきます。

使い方

GitHubにも書いてありますが ruboty kujibiki の後にカンマ区切りの文字列を渡すと、そのうちの1つをランダムに選んで出力します。

> ruboty kujibiki 1,2,3,4,5
5
> ruboty kujibiki 1,2,3,4,5
2

実装には Array#sample を使っています。

きっかけ

職場で「誰がご飯炊く?」となったときに、今まではirbを起動して Array#sample を実行した上でスクリーンショットをSlackに貼って担当者を決めていました。

ただ、この方法だと抽選が個人のPCで実行されるため公平性が担保されていませんでした(実行した人が当たった場合に引き直しが行われている可能性が排除できない)。

そこで、Slack上ででくじびきできれば良いということでさくっと書きました。

書いているときに思ったこと

Array#sample には乱数生成器を渡せます。 そこで SecureRandom を渡そうとしたのですが、渡す乱数生成器はrandメソッドを実装している必要があるのに対して、SecureRandomrandを実装していないことが判明しました。

あと、Random クラスはメルセンヌ・ツイスタを使っているのでそれなりに良い擬似乱数を返すはずですが、今回のユースケースに本当に適しているのか自信がありません。