FORCIAアドベントカレンダー2019 14日目の記事です。 2019新卒入社の東川です。この記事ではシャッフルランチという社内交流企画で現れた最適化問題に対して、強化学習を適用した事例についてご紹介します。 ! 2019年12月時点の情報です （※記事が古いため、リンク先が失われている場合があります） シャッフルランチとは フォルシアで行っているシャッフルランチとは業務上の関わりの薄い社員同士のコミュニケーション促進のために月一回開催している社内企画であり、Slackの特定のチャンネルにjoinした参加希望者を自動的に3-4人のグループに分けて、それらのグループでランチに行くと

FORCIAアドベントカレンダー2019  14日目の記事です。 2019新卒入社の東川です。この記事ではシャッフルランチという社内交流企画で現れた最適化問題に対して、強化学習を適用した事例についてご紹介します。 シャッフルランチとは フォルシアで行っているシャッフルランチとは業務上の関わりの薄い社員同士のコミュニケーション促進のために月一回開催している社内企画であり、Slackの特定のチャンネルにjoinした参加希望者を自動的に3-4人のグループに分けて、それらのグループでランチに行くというものです。シャッフルランチの費用は会社が負担しています。 （開催の背景については こちらの記事 、技術的側面については こちらの記事 をご覧ください） 幸い社内でも好評であり、毎月60人強の社員が継続して参加しています。 フォルシアのシャッフルランチの特徴は、グループ分けが完全にランダムではなく、 参加者間の会社での関わりができるだけ小さくなるように グループ分けされているという点です。これにはできるだけ普段の業務で関わりのない人と交流してほしいという運営側の意図があります。参加者間の「会社での関わり」の指標としては「Slackの共通で加入しているチャンネルの数」を使用しており、これを 親密度 と呼ぶことにします。会社での関わりが薄い2人の社員は共通で加入しているSlackチャンネルの数も少ないと考えられるためです。 組み合わせ最適化としてのシャッフルランチ シャッフルランチを最適化問題として定義するには何らかの指標が必要です。 グループ内のコスト をグループに属する2者間の親密度の合計とし、 グループ分けのコスト を、全グループのグループ内のコストの総和として定義します。このコストが最小化されるとき、会社での関わりができるだけ小さくなるようなグループ分けになっているはずです。 わかりやすい例として、人を3人ずつのグループへ分割して考えましょう（図1）。 まず、2者間の関係性を点数化し、図1(a)のような図を作成します。続いて、図1(b)のような3人ずつのグループ分けを考えます。この時「グループ内のコスト」はそれぞれ5+3+5(=13), 8+1+5(=14)であり、「グループ分けのコスト」は13+14=27です。図1(c)の「グループ分けのコスト」は70であり、図1(b)のグループ分けは図1(c)のグループ分けに比べて、参加者間の会社での関わりが小さいグループ分けになっているということができます。 図1: 6人組を3人+3人のグループに分割する場合。数字は2者間の共通のチャンネルの数を表します。 図(b)の「グループ分けのコスト」は27で、図(c)の「グループ分けのコスト」は70です。 シャッフルランチの組み分けにおいて会社での関わりができるだけ小さい組み分けを探し出すことは重要であり、実際アンケートを見ると「普段関わりのない人と話す機会ができてよかった」という声がたくさんあります。一方で、上記の設定にしたがって「グループ分けのコスト」を最小にするグループ分けを求めるのは、以下の2つの観点から難しい問題です。 考えうる組み合わせが膨大である 上の6人を分ける問題ではグループ分けの数は 6 ! / ( 3 ! × 3 ! ) = 20 通りで全探索が可能です。一方、この組み合わせの数は全体の人数とともに爆発的に増えます。例えば、60人を4人ずつのグループに分ける場合の数は 60 ! / ( 4 15 × 15 ! ) ≒ 6 × 10 60 通りあり、これを網羅的に調べるのは現実的ではありません。 グループ分けのコスト を最小化するのは難しい ある一つのグループ分けに対して グループ内のコスト を最小化するのは簡単ですが、一つのグループ分けを最小に使用すると往々にして他のグループのコストが上がってしまうことがあります。 グループ内のコストの最小化と全体のコストの最小化はトレードオフの関係にあり、ちょうど良いところを定量的に決めるのは難しい問題です。 上記2つの問題に対して、流行りの強化学習が適用できるのではないかと思い、実際に試してみました（あと私自身、強化学習に触れてみたかったという理由もあります）。 以下では、そのインストール方法とサンプルコードを中心に説明します。深層学習や強化学習のライブラリやフレームワークを使用するのは私にとって今回が初めてでしたが、そのインストールの簡便さとコーディングのインターフェースの簡単さには感銘を受けました。 この記事が、組み合わせ最適化問題をできるだけ手軽に解きたい、深層強化学習のライブラリに触れてみたいという方の一助になれば幸いです。 強化学習とは？強化学習に必要な各種フレームワークとライブラリのインストール 強化学習とは近年流行している機械学習の一つの分野であり、GoogleのAlpha Goでも使用されている技術として一躍注目を集めました。機械学習には大まかに教師あり学習、教師なし学習、強化学習の3つの分野があります。 教師あり学習：多数の教師データを基に入出力の関係を学習するものです。画像分類などに使用されます。 教師なし学習：多数のデータを基にデータのカテゴライズを学習するものです。クラスタリングなどに使用されます。 強化学習：多数の試行錯誤を基に最適な戦略を選び出し、「価値」を最適化するものです。 教師なし学習や教師あり学習では多数のデータが必要ですが、強化学習では必要ありません。多数回の試行錯誤を通してデータが作成され、それを基に自律的に学習が進むからです。 強化学習の最適戦略の探索において、AIの核となる技術である深層学習が使用されており、しばしば深層強化学習と呼ばれることもあります。以下では深層強化学習の中でもQ学習、とそこで用いられる手法であるDQN(Deep Q Network)にフォーカスして解説します。 強化学習の問題設定 強化学習では、 エージェント とエージェントが制御する対象である 環境 を考えます。強化学習で重要になる概念が選択 action 、状態 state 、観測データ observation 、報酬 reward です(図2)。 エージェントは各ステップで何らかのactionを選択し環境のstateが変化します。環境は変化後のstateに対してobservationを計算し、observationとrewardを返却します。エージェントは多数の試行錯誤からactionとobservation, rewardの関係性を学習し、rewardを最大化するような最適戦略を導き出します。 今回の例では環境はグループ分けの全体であり、actionは例えば2つのグループの人を交換するという操作、observationは各グループの点数などです。rewardは現在のグループ分けのコストに-1をかけたものであり、rewardの最大化はグループ分けのコストの最小化と同値です。 一点注意するべき点はrewardを最大化する戦略に収束させるためには、取りうるactionの値(action_space)とstateの取りうる値の空間(observation_space)を適切に選ばなければいけないしないということです。人間の学習プロセスがそうであるように、可能なactionが著しく少なかったり、stateから抽出された値がrewardの最大化にあまり関係のないものだったりする場合、強化学習を通して上手い最適戦略が得られない場合もあります。 図2: 強化学習の基本概念。エージェントはactionに対するstateの挙動を見て、試行錯誤しながらrewardを最大化します。 例は今回のグループ分けの最適化において使用されたものを表します。 今回は強化学習ライブラリとしてkeras-rl+gymを使用しました。強化学習のフレームワークに触れるのは私にとって初めての経験でしたが、離散最適化問題のソルバーとして強化学習を用いることのメリットとして以下のような点を感じました。 ライブラリの導入コストが低く、必要となるコーディングも少ない フレームワークにしたがって、直感的に書くことができる デバッグツールと可視化ツールが豊富で開発がしやすい tensorflow, keras, keras-rl, gymのインストール keras とはPythonで書かれたニューラルネットワークライブラリであり、その使いやすさから深層学習の研究と実践で広く使用されています。今回はバックエンドとして tensorflow を使用するので、それもインストールします。インストールはpipを使って以下のコマンドで出来ます。 pip install tensorflow pip install keras 深層強化学習をするために、さらに keras-rl と OpenAI gym をインストールします。keras-rlとはkerasを利用してDQNなどの深層強化学習を実装できるライブラリであり、gymは強化学習に必要な一連の変数を定義するために必要なライブラリです。下で見るように上述のaction, stateなどの枠組みはgymのクラスを継承することで作成できます。 git clone https://github.com/matthiasplappert/keras-rl.git pip install ./keras-rl pip install gym 強化学習による最適なグループ分けの探索 問題設定と強化学習の環境との対応 n m 人を n g 人ずつのグループに分けることを考えます。すべてのメンバーにインデックス i ( = 1 , 2 , . . . n m ) を貼ります。各グループ分けを表現するために長さ n m の配列 G を考え、 i 番目の人がグループ G [ i ] に属しているとします。 例えば、 G [ 3 ] = 1 であれば 3 番目のメンバーはグループ 1 に所属しているという形です(図3(a))。 i とメンバー j の親密度を R [ i , j ] として、これを行列要素に持つような n m × n m 行列 R を定義し、これを親密度行列と呼ぶことにします(図3(b))。この時、グループ分け G に対して g 番目のグループのコストとグループ分け全体のコストはそれぞれ図3(c), (d)のように表現されます。 図3: グループ分け G と親密度行列 R 、コスト C の説明。 χ は定義関数で χ ( t r u e ) = 1 , χ ( f a l s e ) = 0 です。 今回の問題と強化学習の変数との対応は下表の通りです。stateはグループ分け G 、rewardは − C です。actionは G から新しいグループ分け G ′ を生成する操作であり、例えばメンバーの入れ替えなどであり、observationは例えば現在のグループからメンバーの入れ替えをした時の点数の変化などをとります。 state グループ分け G (図3(a))、例: [ 0 , 2 , 1 , 2 , 0 , 1 ] ( 6人を3グループに分ける場合) action 新しいグループ分け G ′ を作る操作、例: メンバー 2 と 3 の入れ替え G = [ 0 , 1 , 2 , 2 , 0 , 1 ] ⇒ G ′ = [ 0 , 2 , 1 , 2 , 0 , 1 ] observation 例: 各グループの点数 reward グループ分けのコストに − 1 をかけたもの ( − C ) (図3(d)) 表1: 強化学習の変数state, action, observation, rewardと今回の問題との対応 学習環境の定義 最適化の環境を表すクラス（下では GroupingEnv としています）はgymのクラスcore.Envを継承して作成します。 class GroupingEnv(gym.core.Env): # クラスの定義 core.Envを継承するには5つのメソッドstep, reset, render, close, seedと3つのプロパティaction_space, observation_space, reward_spaceを実装する必要があります。 step : 各ステップで実行される関数です。actionを引数に取り、observation, reward, is_done（終了条件を満たしたかどうか）, infoを出力します。今回のケースでは、actionの値にしたがってメンバーを入れ替える⇒メソッドget_observationで入れ替え後の状態に対して観測データを得る⇒メソッドget_rewardで報酬を計算する⇒終了条件を満たしているかを判定する、の4ステップを入れました。 # 各ステップで実行される操作 def step(self, action): self.time += 1 # step1: actionに戻づいてグループ分けを更新する self.grouping = self.exchange_member(self.grouping, action).copy() # step2: 観測データ(observation)の計算 observation = self.get_observation() # step3: 報酬(reward)の計算 reward = self.get_reward(self.grouping) # step4: 終了時刻を満たしているかの判定 done = self.check_is_done() info = {} return observation, reward, done, info infoは必要なければ空ディレクトリにします。 reset : 状態の初期化をする関数です。出力はstateから得られる観測データobservationとします。今回は以下のようにランダムなグループ分けに初期化するようにしました。 def reset(self): # 変数の初期化。ランダムなグループ分けに初期化する self.time = 0 self.grouping = self.get_random_grouping() return self.get_observation() # ランダムなグループ分けを得るための関数 def get_random_grouping(self): grouping = list(range(self.n_group)) * int(self.n_member / self.n_group) random.shuffle(grouping) return grouping render , close , seed : render, close, seedはそれぞれ、環境の可視化、終了時の処理、乱数の固定を表す関数です。特に必要なければ、passとします。 def render(self, mode): # 画面への描画 pass action_space : action_spaceとはactionの取りうる値の空間を指します。actionとして2人のメンバーの入れ替えを採用しているため、メンバー n m に対して、actionとしては n m × ( n m − 1 ) / 2 通りの選択肢あります。これだとメンバー数の増加とともに学習のコストが増大してしまうため、今回は「可能なactionの集合に対してactionにしたがって組み替えたときのコストを計算し、コストの小さい10通りのうち何番目を選ぶか」という設定にしました（かなり経験的な方法に寄せています）。 self.n_action = 10 self.action_space = gym.spaces.Discrete(self.n_action) # actionの取りうる値 ここで gym.spaces.Discrete(N) は N 個の離散値の空間を表します。 observation_space : observation_spaceとは観測データの取りうる値の空間を表します。今回の場合、上記のコストが小さくなるような10通りのメンバーの入れ替えのコストを観測データとしました。 self.observation_space = gym.spaces.Box(low=-10, high=10, shape=(self.n_action,)) # 観測データの取りうる値 必要に応じてstateからobservationを計算するための関数 get_observation 、rewardを計算するための関数 get_reward 、終了条件を満たしているかを判定する関数 check_is_done を定義します。 最後に学習の終了条件を定義します。今回は終了条件は単純に「ステップ数の上限(20回)を超えたら終了する」としました。 # 終了条件を判定する関数 def check_is_done(self): # 最大数に達したら終了する return self.time == self.max_step 出来上がったコード全体は以下の通りです。 import gym.spaces import copy import numpy as np import random class GroupingEnv(gym.core.Env): metadata = {'render.modes': ['human', 'rgb_array']} def __init__(self, relationship_matrix, n_group, n_member): self.relationship_matrix = relationship_matrix # 2者間の関係性を表す行列 self.n_member = n_member # 全体のメンバー数 self.n_group = n_group # グループの数 self.grouping = list(range(self.n_group)) * int(self.n_member / self.n_group) # グループ分け self.group_id_list = list(range(n_group)) # groupのidのリスト self.n_action = 10 self.action_space = gym.spaces.Discrete(self.n_action) # actionの取りうる値 self.observation_space = gym.spaces.Box(low=-10, high=10, shape=(self.n_action,)) # 観測データの取りうる値 self.time = 0 # ステップ self.max_step = 20 # ステップの最大数 self.pair_list = self.get_pair_list() self.candidate_list = [] # 各ステップで実行される操作 def step(self, action): self.time += 1 # step1: actionに戻づいてグループ分けを更新する self.grouping = self.exchange_member_action(self.grouping, action).copy() # step2: 観測データ(observation)の計算 observation = self.get_observation() # step3: 報酬(reward)の計算 reward = self.get_reward(self.grouping) # step4: 終了時刻を満たしているかの判定 done = self.check_is_done() info = {} return observation, reward, done, info def reset(self): # 変数の初期化。ランダムなグループ分けに初期化する self.time = 0 self.grouping = self.get_random_grouping() return self.get_observation() def render(self, mode): # 画面への描画 pass def close(self): # 終了時の処理 pass def seed(self): # 乱数の固定 pass # 報酬を計算する関数 def get_reward(self, grouping): return -1 * self.total_grouping_cost(grouping) # 報酬 = グループ分けgroupingのコスト*(-1) # 観測データを計算する関数 def get_observation(self): grouping = self.grouping.copy() candidate_list = [] for pair in self.pair_list: id1, id2 = pair cost = self.get_reward(self.exchange_member_pair(grouping, id1, id2)) candidate_list.append([id1, id2, cost]) self.candidate_list = sorted(candidate_list, key=lambda x:-x[2])[0:self.n_action] return [cand[2] for cand in self.candidate_list] # 終了条件を判定する関数 def check_is_done(self): # 最大数に達したら終了する return self.time == self.max_step # actionの値に応じて、2人のグループを交換する関数 def exchange_member_action(self, grouping, action): new_grouping = grouping.copy() id1, id2, cost = self.candidate_list[action] new_grouping[id1] = grouping[id2] # id1のメンバーとid2のメンバーを交換 new_grouping[id2] = grouping[id1] return new_grouping # id1, id2のメンバーを交換する関数 def exchange_member_pair(self, grouping, id1, id2): new_grouping = grouping.copy() new_grouping[id1] = grouping[id2] new_grouping[id2] = grouping[id1] return new_grouping # ランダムなグループ分けを得るための関数 def get_random_grouping(self): grouping = list(range(self.n_group)) * int(self.n_member / self.n_group) random.shuffle(grouping) return grouping # グループ分けのコストを計算する関数 def total_grouping_cost(self, grouping): return sum([self.group_cost(grouping, group_id) for group_id in self.group_id_list]) # グループgroup_idのコストの計算 def group_cost(self, grouping, group_id): group = [i for i, _x in enumerate(grouping) if _x == group_id] n_pair = len(group) * (len(group) - 1) return self.relationship_matrix[np.ix_(group, group)].flatten().sum() / n_pair # 可能なペアの列挙 def get_pair_list(self): pair_list = [] for id1 in list(range(self.n_member)): for id2 in list(range(self.n_member)): if id1 定義された環境を使って学習環境を定義します。例えば20人を4つのグループに分割する問題を考えるときは以下のようにします（親密度行列 R は本来Slackから取得される情報を使って定義されるべきですが、今回は簡単のため乱数を要素とする行列としました）。 # 組み分けの環境の定義 n_member = 20 n_group = 4 n_action = 10 # 親密度行列の定義 # NOTE: ランダム行列で代用 relationship_matrix = np.array([random.random() for _ in range(n_member ** 2)]).reshape(n_member, n_member) env = GroupingEnv(relationship_matrix, n_group, n_member) ニューラルネットワークの定義と訓練 続いて、この環境に最適な行動を求めるためのモデルをニューラルネットワークで求めます。 from keras.models import Sequential from keras.layers import Dense, Activation, Flatten from keras.optimizers import Adam from rl.agents.dqn import DQNAgent from rl.policy import BoltzmannQPolicy from rl.memory import SequentialMemory # ニューラルネットワークの構造を定義 model = Sequential() model.add(Flatten(input_shape=(1,) + env.observation_space.shape)) model.add(Dense(128)) model.add(Activation('relu')) model.add(Dense(n_action)) model.add(Activation('linear')) print(model.summary()) # モデルの定義をコンソールに出力 # モデルのコンパイル memory = SequentialMemory(limit=50000, window_length=1) policy = BoltzmannQPolicy(tau=1.) dqn = DQNAgent(model=model, nb_actions=n_action, memory=memory, nb_steps_warmup=50, target_model_update=1e-2, policy=policy) dqn.compile(Adam(lr=1e-3), metrics=['mae']) ニューラルネットワークの中間層は1個としました。 モデルの訓練は以下の通りです。 # 訓練 history = dqn.fit(env, nb_steps=5000, visualize=False, verbose=2, nb_max_episode_steps=300) 訓練中は以下のようなレコードが出て、rewardやmean_qの推移が表示されます。 mean_qは学習の進み具合を表すパラメータであり、これの収束は学習が終了したことを表します。 200/5000: episode: 1, duration: 2.922s, episode steps: 200, steps per second: 68, episode reward: -298.082, mean reward: -1.490 [-1.593, -1.376], mean action: 31.190 [0.000, 63.000], mean observation: 0.547 [0.000, 1.000], loss: 0.052949, mae: 1.083208, mean_q: -0.088404 400/5000: episode: 2, duration: 1.784s, episode steps: 200, steps per second: 112, episode reward: -298.902, mean reward: -1.495 [-1.593, -1.376], mean action: 31.120 [0.000, 63.000], mean observation: 0.547 [0.000, 1.000], loss: 0.011003, mae: 2.727983, mean_q: -2.161458 600/5000: episode: 3, duration: 1.781s, episode steps: 200, steps per second: 112, episode reward: -298.719, mean reward: -1.494 [-1.590, -1.388], mean action: 32.490 [0.000, 63.000], mean observation: 0.547 [0.000, 1.000], loss: 0.048550, mae: 4.750234, mean_q: -3.986667 最後に評価をします。ログを記録するために、 rl.callbacks.Callback を拡張したクラス EpisodeLogger を作成し、 dqn.test のコールバックとして渡します。このように簡単に学習過程のログが作れることもkeras-rlの魅力の一つです。 import rl.callbacks # ログを記録するためのクラスの定義 class EpisodeLogger(rl.callbacks.Callback): def __init__(self): self.rewards = {} def on_episode_begin(self, episode, logs): self.rewards[episode] = [] def on_step_end(self, step, logs): episode = logs['episode'] self.rewards[episode].append(logs['reward']) episode_logger = EpisodeLogger() nb_episodes = 100 dqn.test(env, nb_episodes=nb_episodes, visualize=False, callbacks=[episode_logger]) テスト中は以下のようなレコードが出て、各エピソードの終了時点でのrewardが出力されます。 Testing for 100 episodes ... Episode 1: reward: -60.495, steps: 20 Episode 2: reward: -61.666, steps: 20 Episode 3: reward: -59.772, steps: 20 上では100個のランダムなグループ分けを初期値として、最適化をしています。ステップごとのrewardの平均は図4左のように推移し、ステップとともにrewardが増加（すなわちグループ分けのコスト C が減少）していることがわかります。 random_sampling = [env.get_reward(env.get_random_grouping()) for _ in list(range(10000))] import matplotlib.pyplot as plt plt.plot(mean_reward_list, label='N={}'.format(nb_episodes)) plt.xlabel('step', fontsize=18) plt.ylabel('mean reward', fontsize=18) plt.legend(loc='upper right', fontsize=18) plt.show() # plt.savefig('mean_award.png') 図4右は各エピソード終了時点でのrewardの頻度分布です。青のヒストグラムはN=10000でランダムにグループ分けを生成したときの頻度分布であり、強化学習を用いた最適化の方法のほうが系統的に良い結果を与えていることがわかります。 図4: (左)ステップ数に対するrewardの推移（100回平均）。 (右)エピソード終了時点でのrewardの値のランダムサンプリングとの比較 最後に この記事ではシャッフルランチで出てきた離散最適化問題を例にして、強化学習により離散最適化問題の解法について紹介しました。今回実装してみて、組み合わせ最適化問題のソルバーに強化学習のフレームワークを使用することにはいくつかのメリットがあると感じました。 手軽。ライブラリをインストールして、動くものを作るまでそこまで時間がかからない action, reward, step, resetなどライブラリで使用されている用語が直感的で実装しやすい 組み合わせ最適化問題には汎用的な解法がなく難しいところがありますが、強化学習のライブラリであるkeras-rl + gymを組み合わせることで、お手軽にそこそこの精度のものが開発できるのではないかと感じました。各ステップでの実行プロセスやリセット時の操作、ログ出力などスクラッチで書くとなかなか大変ですが、ライブラリの使用でそのコストを大幅に下げることができます。実際、上の程度の量であれば、ライブラリのインストールから動くものを作るまで半日程度の時間があれば十分でした。 一方で以下のような難しさも感じました。 observationとして与える特徴量やactionとして取りうる選択肢を決めるのが難しい。うまいobservation, actionの組み合わせを与えないと全く学習してくれない 変更できるパラメータがネットワークの構造や訓練の各種パラメータなど多岐にわたり、チューニングが難しい 特に一点目については試行錯誤が必要であり、苦労しました。AIだからうまく学習してくれるかなと思って、observationとして次元が大きな特徴量を加工せずにそのまま入れたり、actionの選択肢の数を大きくしてみたりしたのですがほとんど学習が進みませんでした。 実際に、上ではobservationやactionとして取りうる選択はほとんど経験的な方法を採用してしまっており強化学習の良さを殺してしまっていると感じました。また、今回実装したものが深層強化学習を使用しないアルゴリズムよりも良いものであるかどうかは非自明です。 何をどう学習させるか、AIを使うのは簡単ですが、その「気持ち」と「ふるまい」を理解して使いこなすのは難しいものだと感じました。

FORCIAアドベントカレンダー2019  13日目の記事です。 旅行プラットフォーム事業部の小海です。 まもなく創業20周年となるフォルシアですが、フォルシアの技術・検索プラットフォーム Spook は日々進化を続けています。 膨大で複雑なデータに合わせて、最適な検索を実現するための「技術基盤」であるSpookには様々な技術が使われていますが、昨年から今年にかけて新しいWebアプリケーションフレームワークを開発・導入しました。 この記事では、その新しいWebアプリケーションフレームワークの技術的な側面ではなく、検討・開発・導入に至るまでの道のりを紹介します。 Webアプリケーションフレームワークとは？ 「Webアプリケーションフレームワーク」とは、ブラウザなどで動作するWebアプリケーションを効率的に開発するためのフレームワークです。案件によってサイトやページ構成などは異なりますが、「URLの解釈」「htmlを作成」「データベース接続」など基本的に必須の共通機能が多くあります。「Webアプリケーションフレームワーク」を使用することで、これら様々な共通する機能を1から作る必要がなくなります。 世の中には「Ruby on Rails」「Django」「Angular」「Vue」などがあり 、多くのWebエンジニアがそれらを利用してWebアプリを開発しています。 背景 フォルシアには、2004年頃と2013年頃にそれぞれ作られた社内製フレームワークが2つあります。これらのフレームワークはとても深く考えて作られており、今まで多くのサイトを生み出してきました。 しかし、急速に成長し続けるWeb業界の新しい技術や考え方・デバイスに追随できていない部分が少なからずあり、新しい言語や技術が世の中に出るたび、社内の新フレームワークを求める機運が次第に高まってきました。 きっかけ そんな中、エンジニアたちのディスカッションで新フレームワークの話があがり、新フレームワーク検討が本格化してきました。新フレームワークを開発する場合に何が必要かを洗い出した結果、下記の検討が必要となりました。 言語はどうするのか 世の中にあるものか社内製を開発するか 言語やコミュニティの将来性・信頼性 実行速度 学習コスト 世の中に存在するフレームワークのメリット・デメリットや、社内製フレームワーク開発のメリット・デメリットを話し合う中で、実際にハッカソン形式で様々な言語やフレームワークを使ってみようということになりました。 ハッカソン ハッカソンの企画は当時新卒2年目だったエンジニアが主体となって2018年3月に行われました。オンライン参加を含めると参加者はなんと20名！有志のみの参加だったのですが、フォルシアのエンジニアの半数近くが参加となり、エンジニア一丸となって様々なフレームワークを使いながらお題のWebアプリを作成しました。 それぞれが使いたい言語やフレームワークを持ち寄った結果、使用された言語は8言語・フレームワークは15種類となりました。ハッカソンの最後に会議室でお寿司を食べつつ、参加者同士が作成したアプリを見ながら言語やフレームワークのメリット・デメリットを話し合いました。 当時新卒6年目だった私は言語はTypeScript、フレームワークは Hapi を使用して参加しました。先輩や後輩たちの実装・発表が素晴らしく、とても勉強になったのを強く覚えています。 新フレームワーク導入・開発チームの発足 ハッカソンで実際に使ってみた後、様々な言語やフレームワークのメリット・デメリットを洗い出し、2018年4月に新フレームワーク導入・開発チームが発足しました。ハッカソンを主催した新卒3年目のエンジニアがリーダーとなり、そのほかに同じく新卒3年目エンジニアが2人、私の4人がメンバーとなりました。 その後キャリア入社のエンジニアなど強力なメンバーを加え、様々な課題に立ち向かいながらSpookへの新フレームワーク導入・開発を進めることとなりますが、開発秘話・技術的な内容などはまた別の機会にゆっくりお話しできればと思います。 チームの合言葉は「やっていくぞ」。どんな課題にも前向きに取り組んでいく気持ちを表した言葉です。 新フレームワークをリリース 新フレームワークの導入検討・開発をチームで進めていく中で、新しい技術・考え方などを取り入れるポジティブな対応だけではなく、既存の監視ツールへの対応など多くの課題が出てきました。それらをチームで乗り越え、今年の5月にようやく初版をリリースすることができました。 別の記事でも紹介されている「 社内のエンジニア向け勉強会 "devゼミ" 」などで新フレームワークのハンズオンなどをしながら社内への告知を行いました。 その後、社内の新規案件などに採用され、片手で数えきれないほどのアプリで使われ始めています。様々な案件で使用されながら随時フィードバックをもらいつつ、チーム一丸となってフレームワークの改修を進めています。 今後のSpookを支える技術の導入・開発に携われていることに感動と感謝を感じつつ、これからも前向きに「やっていくぞ」。 おわりに 冒頭に記載した通り、Spookは日々進化しています。そしてこれからも進化を続けていきます。社外の方にフォルシアやSpookの話をするとき、エンジニアの業務内容として「Spookを使う仕事なの？作る仕事なの？」という質問をいただくことが多くあります。 フォルシアのエンジニアは明確に「使うひと」「作るひと」を分けず、技術部全体で一丸となってSpookをより良いものにしていくために日々努力を続けています。 そこには若手やベテランなどの垣根は存在せず、それぞれが得意分野を持ち寄りながら議論を重ねて改善をしていく文化があります。 フォルシアではエンジニアを募集しています！興味を持たれた方は こちら からお問い合わせ頂ければと思います。

FORCIAアドベントカレンダー2019  11日目の記事です。 旅行プラットフォーム事業部の佐藤です。 7月に、エンジニアの教育活動の一環として行っている" devゼミ "をご紹介しましたが、開始から8ヶ月目となる今でも受講者が減ることなく継続的に開催が続き、今日までに23回ものゼミが行われました。これまでに受講したことのあるエンジニアは社内全エンジニアの約7割、講師を務めたエンジニアは約4割と、当初の想定を超えるものとなりました。また、これまでに行った講師・受講者向けのアンケートにおいても非常に高い満足度を得ています。 そこで今回は、満足度の高い状態で継続的にdevゼミを開催してきて得た気づきをご紹介します。 これまでに開催されたゼミ過去10回のタイトル一覧 dockerさわってみよっかー！ 外部講師によるISUCON勉強会 旅行商材ウルトラクイズ SQLの計算量を意識してみよう 社内の新フレームワークで始めるReact+Redux PostgreSQL index事始め&複合indexを使ってみよう GitLab CI/CDであそぼ フォルシアワークフローツールをソースコードレベルで理解する 社内ライブラリを使ってみよう作ってみよう サーバ構成・スペックの見積もり方法～入門編～ 講義で扱う対象・進め方がイメージできるようなタイトルにしています。 継続的な開催をするために 下記のdevゼミの目的を達成し、組織に根付かせるためには継続的な開催がカギとなります。そこで、ここでは継続的な開催をする上で重要だと気づいた点について述べようと思います。 エンジニア全体の技術力の底上げ 学ぶ習慣づくり 教える習慣づくり 講師の満足度をあげよ！ ゼミは講師のおかげで成り立っていると言っても過言ではありません。講義を「やってみたい」と思ってもらえること、さらに講義実施後に「やってよかった」「勉強になった」と言ってもらえるようにすることが最も重要です。 講師がゼミで扱う内容に迷いが不安がある場合は、抱え込まないように運営チームと一緒に話し合い、明確にしていきます。 また、初めて講師を務めるエンジニアに対しては、運営チームが各回に参加して、気づいたことを元に進め方について適宜フォローします。 さらに、これまで講師をしたエンジニアから特に好評なのが、ゼミ開催後に参加者から集めたフィードバックです。「フィードバックをもらえること自体が嬉しい」「参加者の率直な意見をもらえてありがたい」「思っているよりも受講者は前向きだということがわかった」といった声が挙がっています。 リアクションをするという点では同様に、フィードバックだけではなく講義中にもたくさんリアクションを行うことが大切だと思います。実際に、社内のメンバー同士だからこそできる面白いツッコミやガヤが入ることで、講師・受講者ともに楽しんでいる様子もしばしば見受けられました。 受講者の満足度をあげよ！ 講師だけではなく受講者が「参加してよかった」と感じて再び参加してくれることも、もちろん大切です。前回 devゼミをご紹介した記事 でも記載していますが、当初の企画の狙い通り「0ベースから、実際に使うところまでできるのが良い」という感想が多く寄せられています。 また、一度講師をやったことがあるエンジニアとしては、講義の進め方自体も大変勉強になります。 例えば、先日 西山さん が行った「Prometheusで自分の開発環境をモニタリングしてみよう」という講義では、ハンズオンの際にdockerのイメージを受講者に配布して、そのイメージを用いて作成したコンテナを用いて各自課題に取り組みました。そのため、各受講者の開発環境に依存することなくスムーズにハンズオンが進められていて、今後のゼミ開催にあたって大変勉強になりました。 エンジニアの関心を聞き逃すな！ 継続開催するにあたり、ゼミで扱うテーマも継続的に選出していかなければなりません。そのためには、社内で「〇〇って新入社員向けの講義のテーマとしては扱っていないけど、うちのエンジニアは知っておいたほうがいいかもね」や「〇〇の良さを他のエンジニアにも知ってもらいたいなあ」といった声を（特にslackのメッセージなどで）聞いた際には、運営チーム内ですぐに共有します。 また、各エンジニアが今どのようなことを行っているのかということも、休憩スペースで話しかけたりランチに一緒に行ったり、社内のドキュメントを読んだりしてキャッチアップすることを心がけています。各エンジニアが取り組んでいることは思っている以上に多様で、またそれらが他のエンジニアにも知られていないことって多いなと思います。 たまに刺激を入れてみよ！ 今年の9月には運営チームメンバーのエンジニアのご友人を招いて、 ISUCON に向けた講義を行っていただきました。ISUCONに特化した内容から社内では使われていない便利なツールやノウハウまで教えていただき、さらにゼミ終了後の懇親会では、講師の方が所属する会社の中身の様子や取り組みなどをざっくばらんにお話しいただきました。私自身も、一エンジニアとして非常に良い刺激をもらえました。 今後の課題 一方で、今後の開催に当たり下記のような課題も残されています。 テーマが実業務に関わることに偏りがちである 参加者が新卒入社のエンジニアに偏りがちである どうしても業務優先になってしまい、なかなか参加できない人がいる 参加できなかった人へのフォローが足りない 内容の検討や資料の準備など講師の負担が大きめである etc. いずれも継続性を考えた場合、うまく仕組みを作っていくことが必要かと思います。来年のdevゼミ運営チームの課題ですね。 おわりに devゼミを通して気づいたことは、まず向学心の高いエンジニアが社内に多いということです。回数を重ねても受講者が減らないことや、「この講義、やりたいです！」と運営チームが声を掛けずとも積極的に手を上げて講師を引き受けてくださるエンジニアが複数いることも驚きました。 また、上述のようにフィードバックはモチベーション維持に非常に重要だということがわかりました。これは勉強会やエンジニアに限った話ではなく、普段の仕事においても同様で、互いに小さなことでもフィードバックや何らかのリアクションを送り合うことの大切さを改めて気づきました（仕事だけでなく、日常生活でも活かせそうですね）。 私自身devゼミ運営チームとしてほぼ毎回ゼミに参加しているため、実は運営チームメンバーが一番勉強させてもらっているのではないかとも思います。また講師や受講者とのやりとりを通して、普段の業務で関わる機会が少ないエンジニアの興味や強み、人となりを知ることはとても楽しいです。さらに、受講者や運営チームだけでなく、講師が「講義中も楽しかった」と言ってくれたり、エンジニアのボトムアップというdevゼミのコンセプトに共感してくれる社員が多いことが、何より嬉しいです。 エンジニア勉強会の企画を考えている方々に、この記事が少しでも参考になれば幸いです！

FORCIAアドベントカレンダー2019 10日目の記事です。 検索プラットフォーム事業部の澁谷です。 皆さん、システムコールって意識していますか？ 昔からあるデバック方法の一つですが、最近の開発で「システムコール」を意識することも少なくなっている気がします。今回はシステムコールのデバックコマンド [strace ] の紹介がてら、postgresql で実行したSQLの挙動を眺めてみます。 システムコールとは？ システムコールとは、コンピュータ上で実行中のプログラムが、オペレーティングシステム（OS）のカーネルの特権的な機能を呼び出す仕組み。ネットワークを利用した通信、ファイルへの入出力、新しいプロセスの生成、プロセス間通信などは、システムコールを使用することで実現されます。 なお、CPU・メモリ上の計算であればシステムコールは発生しません。 どうやってトレースする？ linux (ubuntu ) の strace コマンドを使用し、トレースしたいプロセスのPIDを事前もしくは実行中に調べ、strace コマンド の [p]オプションへ指定すると確認することができます。 例えば、apache の親プロセスをトレースすると以下のようになります。 select,read.fstat,write,waitid などがシステムコールになります。 $ sudo strace -p 1339 strace: Process 1339 attached select(48, [3 5 6 7 8 9 11 12 13 15 18 19 20 22 23 26 27 29 32 34 35 37 39 41 43 44 45 47], [], [7 8 9 11 12 15 19], NULL) = 1 (in [23]) read(23, "[20194:20194:1128/134821.397022:"..., 8192) = 117 read(23, 0x55e2ab413285, 8075) = -1 EAGAIN (Resource temporarily unavailable) fstat(14, {st_mode=S_IFREG|0640, st_size=5046, ...}) = 0 write(14, "[20194:20194:1128/134821.397022:"..., 117) = 117 read(3, 0x7ffc0e3bf577, 1) = -1 EAGAIN (Resource temporarily unavailable) waitid(P_ALL, 0, {}, WNOHANG|WEXITED|WSTOPPED|WCONTINUED, NULL) = 0 select(48, [3 5 6 7 8 9 11 12 13 15 18 19 20 22 23 26 27 29 32 34 35 37 39 41 43 44 45 47], [], [7 8 9 11 12 15 19], NULL^Cstrace: Process 1339 detached <detached ...> 事前準備 検証用データの作成 検索用情報を持つテーブル foo と検索情報に紐づくテキスト情報を持つ bar テーブルを作成。内部結合を行った際の処理と、select句内でサブクエリを記述し取得した際の処理をそれぞれトレースします。 用意するデータのイメージは以下の通り 検索用情報テーブル (foo) ID1 ID2 ID3 bit1 bit2 bit3 1 3 100 true true true 2 5 300 true true false ... ... ... ... ... ... 10000 17 500 false false true テキスト情報テーブル (bar) ID1 text1 1 ふなっしー 2 くまもん ... ... 10000 素敵坊主 今回の検証用SQLで得られる結果（id2 - bit3 は返却対象から外しています） ID1 ID2 ID3 bit1 bit2 bit3 text1 1 3 100 true true true ふなっしー 2 5 300 true true false くまもん ... ... ... ... ... ... ... 10000 17 500 false false true 素敵坊主 -- 検索用情報テーブル CREATE TABLE foo ( id1 int4, id2 int4, id3 int4, id4 int4, bit1 bit(1), bit2 bit(1), bit3 bit(1), bit4 bit(1) ); insert into foo select n as id1, n as id2, n as id3, n as id4, '1'::bit as bit1, '1'::bit as bit2, '1'::bit as bit3, '1'::bit as bit4 from ( SELECT GENERATE_SERIES(1, 10000) as n )x; -- テキスト情報テーブル CREATE TABLE bar ( id1 int4, text1 text ); insert into bar select n as id1, 'hoge'::text as text1 from ( SELECT GENERATE_SERIES(1, 10000) as n )x strace で プロセスをトレースする準備 straceコマンドでSQL実行中のプロセスをトレースするため、SQLを実行するアプリケーションpgadmin からSQLを実行しPIDを確認します。 $ ps -ax | grep postgres | grep SELECT 28495 ? Rs 10:34 postgres: forcia forcia 10.0.2.2(64164) SELECT ここでは PID 28495が得られたので、そのプロセスを追跡していくこととします。 同一の処理結果となる ２つのSQLを比較 SQL1.内部結合で取得 select b.text1 from foo a inner join bar b using(id1); -- explain analyze "Hash Join (cost=319.00..506.12 rows=5184 width=32) (actual time=4.277..9.833 rows=10000 loops=1)" " Hash Cond: (b.id1 = a.id1)" " -> Seq Scan on bar b (cost=0.00..115.84 rows=5184 width=36) (actual time=0.013..1.626 rows=10000 loops=1)" " -> Hash (cost=194.00..194.00 rows=10000 width=4) (actual time=4.253..4.253 rows=10000 loops=1)" " Buckets: 16384 Batches: 1 Memory Usage: 480kB" " -> Seq Scan on foo a (cost=0.00..194.00 rows=10000 width=4) (actual time=0.005..2.116 rows=10000 loops=1)" "Planning time: 0.086 ms" "Execution time: 10.485 ms" SQL2.セレクト句にサブクエリを記述 select (select text1 from bar b where b.id1 = a.id1) as text1 from foo a; -- explain analyze "Seq Scan on foo a (cost=0.00..1890194.00 rows=10000 width=32) (actual time=1.801..19942.947 rows=10000 loops=1)" " SubPlan 1" " -> Seq Scan on bar b (cost=0.00..189.00 rows=1 width=5) (actual time=1.015..1.990 rows=1 loops=10000)" " Filter: (id1 = a.id1)" " Rows Removed by Filter: 9999" "Planning time: 0.078 ms" "Execution time: 19946.171 ms" SQL1,SQL2それぞれの処理速度(Execution time)を見ると、SQL1の10.485ms に対して、SQL2は19946.171 msで、SQL2はSQL1よりも約2000倍遅い。 SQL1、SQL2の実行プランを比較すると、bar テーブル の処理はどちらもシーケンシャルスキャンですが、rows/loops の処理方法に違いがあることがわかります。 SQL1: Seq Scan on bar b (cost=0.00..115.84 rows=5184 width=36) (actual time=0.013..1.626 rows=10000 loops=1 ) SQL2: Seq Scan on bar b (cost=0.00..189.00 rows=1 width=5) (actual time=1.015..1.990 rows=1 loops=10000 ) この時のSQL1,SQL2のシステムコールを眺めてみよう SQL1 のシステムコールの統計情報 $ strace -p 28495 -c % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 0.00 0.000000 0 3 write 0.00 0.000000 0 10 lseek 0.00 0.000000 0 7 brk 0.00 0.000000 0 4 sendto 0.00 0.000000 0 6 3 recvfrom 0.00 0.000000 0 3 epoll_wait ------ ----------- ----------- --------- --------- ---------------- 100.00 0.000000 33 3 total SQL2 のシステムコールの統計情報 $ strace -p 28495 -c % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 0.00 0.000000 0 3 write 0.00 0.000000 0 10009 lseek 0.00 0.000000 0 4 sendto 0.00 0.000000 0 6 3 recvfrom 0.00 0.000000 0 3 epoll_wait ------ ----------- ----------- --------- --------- ---------------- 100.00 0.000000 10025 3 total 上記より、SQL1のlseekが10回呼ばれているのに対して、SQL2の lseek は10009回呼ばれていることがわかります。 lseek はファイルの読み書きを行うためにポインタを移動する際に呼ばれるシステムコール。 先のexplain analyzeの結果を合わせてみると、SQL1 SQL2で実行したシーケンシャルスキャンの処理の違いは以下のように推測することができます。 SQL1: foo テーブルに対し、bar テーブルを１回のHDDアクセスで10000レコード取得。それを1回のループで処理。 SQL2:foo テーブルに対し、bar テーブルを１レコードずつHDDへアクセスしてデータを取得。それを10000回繰り返し処理。 つまり、SQL2の様に select 句でサブクエリを記述するとそのレコード毎に評価されることがシステムコールからも読み取れることがわかりました。 SQL2のシステムコールを減らしてみる 冒頭のシステムコールの説明で「CPU・メモリ上の計算であればシステムコールは発生しない」と書きました。 先のSQL2では、10000レコードの処理を行う際に1レコードずつファイルディスクリプタへアクセスをしていたが、メモリに乗っていればシステムコールは発生しないはず。検索情報テーブル(foo)とテキスト情報テーブル(bar)が結合するカラムにそれぞれインデックスを作成し試してみます。 create index _idx_foo on foo (id1); create index _idx_bar on bar (id1); SQL3 (SQL1 with index) "Hash Join (cost=289.00..620.50 rows=10000 width=5) (actual time=5.295..10.963 rows=10000 loops=1)" " Hash Cond: (a.id1 = b.id1)" " -> Seq Scan on foo a (cost=0.00..194.00 rows=10000 width=4) (actual time=0.008..1.429 rows=10000 loops=1)" " -> Hash (cost=164.00..164.00 rows=10000 width=9) (actual time=5.272..5.272 rows=10000 loops=1)" " Buckets: 16384 Batches: 1 Memory Usage: 558kB" " -> Seq Scan on bar b (cost=0.00..164.00 rows=10000 width=9) (actual time=0.007..2.447 rows=10000 loops=1)" "Planning time: 0.196 ms" "Execution time: 11.648 ms" SQL4 (SQL2 with index) "Seq Scan on foo a (cost=0.00..83219.00 rows=10000 width=32) (actual time=0.022..61.605 rows=10000 loops=1)" " SubPlan 1" " -> Index Scan using _idx_bar on bar b (cost=0.29..8.30 rows=1 width=5) (actual time=0.004..0.005 rows=1 loops=10000)" " Index Cond: (id1 = a.id1)" "Planning time: 0.068 ms" "Execution time: 63.099 ms" 実行プランを Explain analze で SQL4(SQL2 with index) の処理速度を確認すると 63.099 ms と、SQL2の 19946.171 ms から大幅に改善したのがわかります。では、この時のシステムコールを確認してみましょう。 SQL3 (SQL1 with index)のシステムコールの統計情報 $ strace -p 28495 -c % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 0.00 0.000000 0 3 write 0.00 0.000000 0 12 lseek 0.00 0.000000 0 4 sendto 0.00 0.000000 0 6 3 recvfrom 0.00 0.000000 0 3 epoll_wait ------ ----------- ----------- --------- --------- ---------------- 100.00 0.000000 28 3 total SQL4 (SQL2 with index)のシステムコールの統計情報 $ strace -p 28495 -c % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 0.00 0.000000 0 3 write 0.00 0.000000 0 11 lseek 0.00 0.000000 0 4 sendto 0.00 0.000000 0 6 3 recvfrom 0.00 0.000000 0 3 epoll_wait ------ ----------- ----------- --------- --------- ---------------- 100.00 0.000000 27 3 total SQL4のシステムコールがSQL1と同等レベルまで改善しているのがわかります。 SQL2が遅かった原因 is 何？ 処理速度が遅かったSQL2にインデックスを張ったら性能が改善しました。ある意味当然の結果ではありますが、ここではシステムコールの発生が抑えられていることが確認できています。 SQL2のボトルネックを考えた時、シーケンシャルスキャンのロジックがそもそも遅いのか、それとも、ファイルディスクリプタへのアクセスが頻発することによるI/Oのオーバーヘッドが遅いのか、どちらなのでしょうか。 例えば、後者がボトルネックであれば、HDDをSSDに変えればアプリケーションの修正ではなくH/Wのレイヤーで性能を改善することができる、という検討もできます。 これを切り分けるために、SQL2の実行プランかつシステムコールの発生を抑えるSQLを組み立てて確認してみます。 SQLの準備 ここでは with句を使用して試してみます。with句で作成したデータは同一セッション内でメモリ内保存され後続処理で再利用する特性があり、この特性を生かして、予めメモリ内で展開したデータを元にSQL2と同等の処理が実行するSQL5を作成してみます。 SQL5 (with句使用) with baz as ( select id1, text1 from bar ) ,fug as ( select id1 from foo ) select (select text1 from baz b where b.id1 = a.id1) as text1 from fug a; -- explain analyze "CTE Scan on fug a (cost=339.00..2250539.00 rows=10000 width=32) (actual time=4.304..36537.863 rows=10000 loops=1)" " CTE baz" " -> Seq Scan on bar (cost=0.00..155.00 rows=10000 width=9) (actual time=0.015..1.356 rows=10000 loops=1)" " CTE fug" " -> Seq Scan on foo (cost=0.00..184.00 rows=10000 width=4) (actual time=0.020..13.423 rows=10000 loops=1)" " SubPlan 3" " -> CTE Scan on baz b (cost=0.00..225.00 rows=50 width=32) (actual time=1.833..3.648 rows=1 loops=10000)" " Filter: (id1 = a.id1)" " Rows Removed by Filter: 9999" "Planning time: 0.078 ms" "Execution time: 36543.400 ms" SQL5 のシステムコールの統計情報 strace -p 28495 -c % time seconds usecs/call calls errors syscall ------ ----------- ----------- --------- --------- ---------------- 0.00 0.000000 0 3 write 0.00 0.000000 0 10 lseek 0.00 0.000000 0 3 brk 0.00 0.000000 0 4 sendto 0.00 0.000000 0 6 3 recvfrom 0.00 0.000000 0 3 epoll_wait ------ ----------- ----------- --------- --------- ---------------- 100.00 0.000000 29 3 total システムコールの回数だけ見ると、SQL1、SQL3、SQL4と遜色ないレベルにありますが、SQL2のexplain analyzeの結果と比較すると処理速度が悪化しています。 このことから、このSQLにおけるボトルネックはファイルディスクリプタへのアクセスが頻発していることではなく、実行プランがシーケンシャルスキャンになっており、CPUの演算処理で時間がかかっていることだと判断できます。 例えば、SQL2がボトルネックになった場合、SSDを導入しても改善効果は乏しい、ということが推測できると思います。 CTE Scan on fug a (cost=339.00..2250539.00 rows=10000 width=32) (**actual time=4.304..36537.863** rows=10000 loops=1) さいごに SQLを通してシステムトレースを眺めてみましが、ファイル・ネットソケットのopen/closeが適切に行われていない、ブラックボックス化されたライブラリ動作が遅かった、などを調査する手法としてシステムコールをトレースするのは有効だったりします。 触ったことが無い方、調査等で困った時にふと思い出して頂ければ幸いです。

FORCIAアドベントカレンダー2019 9日目の記事です。 旅行プラットフォーム事業部エンジニア2年目の籏野です。 フォルシアでは常に2名のエンジニアがオンコール対応を行えるように体制を整えています。 ほとんどのエンジニアが持ち回りで担当するのですが、入社後誰もがすぐにオンコールとしての対応を行うことはできません。 そこで、フォルシアに入社したエンジニアに対して、オンコール対応のためのトレーニングを実施しています。 昨年、私はこのトレーニング用の環境を整備しました。 今回はこの環境整備の話をしつつ、実際にどのようなトレーニングを行っているのかを紹介したいと思います。 トレーニング環境整備 フォルシアにはオンコール対応のトレーニング環境は元々存在していたのですが、構成情報などがあまり管理されていない状態でした。これではトレーニング中に何か起こった時に元に戻すのが大変です。 そこで今回、Ansibleを用いてトレーニング環境の構成情報を管理するようにしました。 フォルシアでは近年Ansibleを用いて各環境を構築しており、必要なミドルウェアやツール群を入れるための設定が多く用意されています。 これらを利用することによって、当時1年目の私でもまっさらな状態のサーバー上にトレーニング用の環境を構築することができました。また、Ansibleを用いたことで、私以外の社員でもコマンド一つでトレーニング環境を構築し直すことができます。 フォルシアが導入したAnsibleの話は12日に公開予定のアドベントカレンダーの記事でも紹介する予定ですので そちら もご覧ください。 トレーニングの様子 オンコールトレーニングは社内で構築されたトレーニング用環境で行われており、ここでトレーナーが様々なアラートを発生させます。 アラート発生時にはSlackに通知が流れるようになっています。 これは本番環境でのアラート時も同様で、トレーナー/トレーニーが本番環境さながらの状態でやり取り・対応を行っていきます。 全ての対応を終え、最後にスレッド内で「対応完了」とつぶやくことでトレーニングが完了します。 このつぶやきに反応して、社内botが「おつかれ」のスタンプと社内チケットの自動起票を行ってくれます。 ※本番環境ではこのチケットを元に月次のアラート発生件数の確認や恒久対応の必要なチケットの選別を行います。 アラートと言ってもその内容はさまざまであり、初めのうちはその原因調査や対応内容の判断に時間がかかってしまうことも多くあります。 しかし、このようなトレーニングを繰り返し行うことで、実際のオンコール対応時に落ち着いて対応を行うことができるようになるのです。 最後に 今回紹介した「オンコールトレーニング」はフォルシアに入社した際に受ける研修の一つです。 このトレーニング以外にもフォルシアでは様々な研修を用意しており、(特に新卒入社社員のような)経験の少ないエンジニアも安心して業務に取り組めるような環境を用意しています。 少しでもフォルシアに興味のある方はぜひ こちら へ！

この記事はCI/CD Advent Calendar 2019 8日目の記事です。 こんにちは。8日目のアドベントカレンダー記事を書かせていただきます、エンジニアの山門です！ 現在は旅行プラットフォーム事業部で大手旅行会社のシステム開発を担当しています。 突然ですが皆さん、CI/CD しているでしょうか？ 社内ではレポジトリ管理にGitLabを使用しているのですが、これまでGitLab CI/CD は使用していませんでした。 ここ最近になり、GitLab CI/CD の魅力に気づいた社内の各所で使われ始め、私自身も使い始めてみたので、そもそもどうやって使うんだ？という導入部分の紹介ができ

この記事は CI/CD Advent Calendar 2019  8日目の記事です。 こんにちは。8日目のアドベントカレンダー記事を書かせていただきます、エンジニアの山門です！ 現在は旅行プラットフォーム事業部で大手旅行会社のシステム開発を担当しています。 突然ですが皆さん、CI/CD しているでしょうか？ 社内ではレポジトリ管理にGitLabを使用しているのですが、これまでGitLab CI/CD は使用していませんでした。 ここ最近になり、GitLab CI/CD の魅力に気づいた社内の各所で使われ始め、私自身も使い始めてみたので、そもそもどうやって使うんだ？という導入部分の紹介ができればと思います。 そもそも CI/CD って？ ここ最近 CI/CD というワードをよく耳にするようになりましたが、実際どういったものなのでしょう。 概要 参照元 ざっくり以下のような役割を果たしており、開発段階の効率をあげるプロセスがCIで、運用段階の効率をあげるプロセスがCDのようなイメージです。 CI(Continuous Integration): 継続的インテグレーション ビルド 単体テスト 結合テスト CD(Continuous Delivery): 継続的デプロイ ソースコードレビュー ステージング環境へのデプロイ 本番環境へのデプロイ GitLab CI/CDはこのどちらの機能も有している便利ツールなのです。 今回はCIにフォーカスして、その導入を実践していただければと思っています。 GitLab CI/CDとは GitLab CI/CDは GitLabの機能の一機能で、アプリケーションのビルドや単体テストのオペレーションを自動化し、品質維持を手助けしてくれるツールです。 GitLab CI/CDで動作する各jobはプロジェクトに関連しているため、プロジェクトの特定のブランチ更新や、mergeをトリガーにしてjobを呼び出します。 こんな感じのイメージ 参照元 レポジトリにpushした後にGitLabがjobをキックし、テスト等々実行してくれるものだと思っておいていただけると良いかと思います。 メリット フォルシアでは以下のような点が良いと感じ、GitLab CI/CDの利用を開始しました。 社内のレポジトリ管理にGitLabを使っているため、GitLab上でbuildやtestが完結し、使うツールをまとめることができる レポジトリと結びついているので、branchやMRとの連携が容易 設定を .gitlab-ci.yml というファイルでコード管理することができる GitLab Runner GitLab CI/CDを利用するにあたってGitLab Runnerの存在が不可欠です。GitLab RunnerはGitLabがmerge等のトリガーを検知した際に、実際にjobを実行し、結果をGitLabに返してくれるツールです。中身はGoで書かれており、GNU/Linux, macOS, Windowsといった様々な環境で動作可能なのが特徴です。 また、Executorというjobの実行形式を変えることで、各人の環境に合わせた選択をすることが可能です。 Runnerの種類 RunnerにはShered RunnersとSpecific Runnersの2種類の利用方法があります。 Shared Runners 複数のプロジェクトのjob実行を共有のRunnerで処理する方式 現在実行されているjobの数が最も少ないプロジェクトから処理が実行される Specific Runners 特定のプロジェクトのjobのみを実行する方式 基本的に実行リクエストが来た順に処理が実行される Executorの種類 Runnerはjobを実行するプラットフォームに応じてExecutorとよばれるjobの実行形式を選択します。 主なExecutorとして、以下のようなものがあり、フォルシアでは推奨でもあるDocker Executorを利用しています。 Shell Executor Runnerが導入されているサーバー上で、build,test等を実行 Docker Executor Docker APIを通してDocker Engineと接続することによりコンテナから各build,test等を実行 Virtual Box Executor VM上のSSHを経由してbuild,test等を実行 SSH Executor RunnerからSSH接続可能なサーバに対して、コマンドをSSH経由で送信してbuild,test等を実行 Kubernetes Executor Kubernetes API経由でクラスタ上のPodを作成してbuild,test等を実行 準備 Runnerのinstall フォルシアではオンプレでGitLabを利用しており、そこに新しくCI/CDの実行環境を用意しました。 ここでは事前準備としてRunnerのinstallをします。 ここでは、以下の前提の上で話を進めます。 GitLab が乗っているサーバがある -- A Runnerを動かすサーバ(Dockerがinstallされている)がある -- B A,Bがネットワーク的につながっている RunnerのContainerを実行 今回はRunnerをDocker imageでinstallしていきます。 こちら の公式ドキュメントが参考になるかと思います。 まずはRunnerのContainerを起動。 docker run -d --name gitlab-runner --restart always \ -v /srv/gitlab-runner/config:/etc/gitlab-runner \ -v /var/run/docker.sock:/var/run/docker.sock \ gitlab/gitlab-runner:latest Runnerの登録 次にRunnerの登録を行うのですが、登録にはあらかじめurlとtokenが必要になるので、各自取得する必要があります。登録するRunnerの種類によって以下の流れでurlとtokenを知ることができます。 Specific Runners登録の場合 各自追加したいレポジトリの CI/CD -> Ruuners Shared Runners 登録の場合 管理者権限で Admin Area -> Runners Specific Runners登録の場合のurlとtokenの記載場所例 モザイク箇所にurlとtokenが記載されています 情報が揃った方は実際に登録してみましょう。下記コマンドを打つと、対話ベースでRunnerの登録が行えます。 docker run --rm -t -i -v /srv/gitlab-runner/config:/etc/gitlab-runner gitlab/gitlab-runner register Runtime platform arch=amd64 os=linux pid=6 revision=577f813d version=12.5.0 Running in system-mode. Please enter the gitlab-ci coordinator URL (e.g. https://gitlab.com/): <取得したGitLab url> Please enter the gitlab-ci token for this runner: <取得したtoken> Please enter the gitlab-ci description for this runner: [3b2bf8a2a755]: <このrunnerを表す名称(gitlab-runner01)> Please enter the gitlab-ci tags for this runner (comma separated): <カンマ区切りでタグを設定(docker,sample)> Registering runner... succeeded runner=snZhRtXu Please enter the executor: docker-ssh, ssh, docker-ssh+machine, kubernetes, docker, parallels, shell, virtualbox, docker+machine, custom: <使用するexecutorを入力(docker)> Please enter the default Docker image (e.g. ruby:2.6): <使用するexecutorを入力(alpine:latest)> Runner registered successfully. Feel free to start it, but if it's running already the config should be automatically reloaded! 問題なく完了すれば、無事Runnerの登録完了です！ 登録したレポジトリの CI/CD -> Ruuners を見ると、登録したRunnerが以下のように画面に表示されているはずなので、早速動かしていきましょう！ 早速始めてみる 社内ではShared Runnerを使用しているため、以下Shared Runnersのケースで進めます。 .gitlab-ci.yml の違いはtagsの設定くらいなので、Specific Runnersの方は、 公式 を参考にtagsの設定を適宜入れていただければと思います。 まずは自身がいじれるレポジトリでissueなどを使って適当にbranchを作成します。 その後、レポジトリルートに .gitlab-ci.yml を作成し、以下コードを追加してみましょう。 image: node test1: script: - npm install - npm run test (testがない方は echo "this is test1" のようにechoするだけでも問題ありません) 追加したらadd&commit&pushでレポジトリに反映しましょう。 自分のレポジトリの CI/CD -> Pipelines を見てみると、以下のようにgit上でtestが実行されるはずです。 注意 submodule周りで怒られているとなった場合、以下記述をimageプロパティと同じ高さに記載するとうまくいくかもしれません variables: GIT_SUBMODULE_STRATEGY: recursive GitLab CI/CDはデフォルトではsubmoduleを引っ張ってこないため、対象のレポジトリがsubmoduleを持っている場合に必要になるプロパティです 設定 内容 none(デフォルト) submoduleは引っ張ってこない normal トップレベルのsubmoduleのみ引っ張ってくる recursive submoduleの中にあるsubmoduleといった入れ子構造も引っ張ってくる 参考 やったこと 今書いていただいたのは、ミニマムでGitLab CI/CDを利用する方法です。 GitLab CI/CDは .gitlab-ci.yml という設定ファイルを、レポジトリルートに配置することで実行することができます。 image 使用するDocker イメージを指定 今回はnpmを使う関係でnodeのイメージを利用しています test1 job名 job名は .gitlab-ci.yml の中で 一意 になっている必要があります script Runner上で実行されるスクリプトやコマンドを指定 scriptはjobの中で 必須 stage, pipelineを追加してみる お次はstageという考えを導入し、pipelineを組んでみましょう。 先ほどの .gitlab-ci.yml に少し記述を追加します。 image: node stages: - build - test build: stage: build script: - echo "this is build stage" test1: stage: test script: - npm install - npm run test ここでは新たにstagesパラメータを導入し、build,testの2つのステージを追加します。 また、jobにstageパラメータを追加し、どのjobがどのstageに属するかを指定しています。 stages ビルド、テスト、デプロイといった大きな塊を表す定義の一覧 stage 各jobをどのステージに割り当てるかを指定 同じステージのjobは並列で実行 される 基本的に 前のステージのjobが全て成功しないと、次のステージのjobは実行されない この状態で更新してpushしてみると、GitLab上でpipelineが自動的に組まれます。簡単ですね。これにより、ビルドが成功したらテストをやってデプロイまで、といった流れを簡単に組むことができます。 注意 1jobに対して1コンテナが立ち上がる ので、各jobは独立していることに注意しましょう ES6やTSのプロジェクトで、build jobで npm run build したからといって、testのjobでbuildせずにtestを走らせると失敗してしまいます！ jobの並列実行 引き続き今度は、同じstageで複数のjobを設定し、jobを並列で実行してみましょう。 image: node stages: - build - test build: stage: build script: - echo "this is build stage" test1: stage: test script: - npm install - npm run test test2: stage: test script: - echo "test1 and test2 are run simultaneously" そろそろ皆さん慣れてきたかもしれませんが、testステージにtest2というjobを追加しました。この状態でpushすると、buildステージが成功した後に、testステージのjobが並列で実行されるはずです。 もう少しやってみる 最低限の導入という意味ではここまでで十分なのですが、せっかくなので以下2点も合わせてやってみましょう。 branchによる実行jobの変更 各jobの前後への処理の追加 image: node stages: - build - test before_script: - npm install after_script: - echo "this is executed after each job" build: stage: build script: - echo "this is build stage" only: - branches except: - master test1: stage: test script: - echo "this is test1" - npm run test only: - branches except: - master test2: stage: test script: - echo "this is test2" only: - branches except: - master test3: stage: test before_script: - echo "before_script is overwritten" script: - echo "this is test3" only: - master いきなり増えましたが、追加したパラメータの説明を以下に記載します。 before_script scriptの前に行うタスクを定義 環境の設定や、npm installなどの、どのjobでも実行されるようなタスクを記載 after_script scriptの後に行うタスクを定義 only 指定したブランチ、およびタグの更新があった場合のみjobを実行 except 指定した以外のブランチ、およびタグの更新があった場合のみjobを実行 onlyパラメータと併用することが多い やりたいことが増えてくると、jobの数が増加し、pipeline実行にかかる時間が長くなってきてしまうのですが、こういったパラメータを利用することで、時間の短縮や、必要な場面でのみjobを実行することができるようになります。 パラメータはネストが深い方で上書きする(グローバル宣言したものよりローカル宣言したものが強い)ようになっており、test3では、グローバルに宣言されている before_script を上書きし、 npm install が実行されないようになっています。 補足: 特定のjobだけ別のimageを使いたいという意図で、jobの中にimage指定をして上書きすることはよくあります この状態でpushするとbuild,test1,test2が実行され、masterにmergeされた際はtest3だけが実行されます。 パラメータはこの他にもたくさんあり、例えば以下のようなパラメータを使用することもできます。 設定 内容 記述例 variables job内で利用される変数定義 variables:       GIT_SUBMODULE_STRATEGY: recursive tags 実行するRunerのタグを指定 tags: docker allow_failure 失敗することを許可するか否かを指定 allow_failure: true when 特定の条件にマッチした場合のみjobを実行 when: on_failure retry 失敗したときのretry回数を設定 retry: 2 公式のページ がかなり丁寧に書かれているので、困ったらそちらを見ると良いと思います。 MRの作成 .gitlab-ci.yml を導入することでMRでも恩恵を受けることができます。 実際にMRを作成し、画面を見てみると、これまでなかったpipelineの表示が出てくるため、pipelineが成功してmergeという運用が新たにできるようになります。 対象のMRのpipelineが実行中の場合、mergeボタンが「Merge when pipeline succeeds」という表示になり、レビュアーがOKと判断し、このボタンを押しておけば、pipeline成功時に自動でmergeをしてくれるようになります。 buildや単体テストによるチェックはCIに任せて開発効率をじゃんじゃん上げていきましょう！ (ちょうどいい画像が用意できなかったため公式から引っ張ってきました) 参考までに実際に今回のMRをmergeしたときに走るpipelineです。 設定した通りmasterではtest3のみ実行されています。 終わりに 駆け足でしたが、ざっとGitLab CI/CDについて理解・実践していただき、導入コストの低さと利便性を感じていただけたのではないかと思います！これを機に導入を検討されてみてはいかがでしょうか。 フォルシアでは技術の知見を共有しあうdevゼミという試みがあり、本記事もそこでの発表を元に、まとめ直したものをご紹介しております(devゼミについての紹介は こちら をご覧ください)。 GitLab CI/CD は 公式ドキュメント がかなり丁寧に書かれており、そちらを見れば何かしらヒントがあるので、導入の際はぜひ読んでいただければと思います。 1push,1MR単位でCIを実施して、ソースコードの品質維持・向上を担ってくれているので、実際に開発者、レビュワーが実装に集中して業務に取り組めるようになったと感じています。 GitLab CI/CD に限らず、今後CI/CDが当たり前のものになっていくといいですね。

FORCIAアドベントカレンダー2019 7日目の記事です。 検索プラットフォーム事業部エンジニアの小孫です。 旅行会社のサイトで主に列車の検索画面を担当しています。最近注目の鉄道ニュースといえば、来年5月から運行される「WEST EXPRESS 銀河」ですよね。通常の指定席料金で乗れる夜行特急ということで、旅の選択肢がまた一つ増えますね！ さて、アドベントカレンダー7日目は、鉄道ではなく「船」の話をします。突然ですが、ギリシャ語で「水先案内人」を何というかご存知でしょうか。 そうです。κυβερνήτηςですね。 すみません。Kubernetesです。クバネティスです（発音はたぶん）。 このところ本番環境での利用が増加しているこのKubernetesについて、フォルシアでの導入の検討過程についてお話します。 Kubernetesの技術的な話というよりは、フォルシアでの新しい技術への取り組みについて、Kubernetesを一例としてお伝えしようと思います。 個人的きっかけ 新人の頃に同期がSlackで共有した記事に、「いまどきdockerを使ってない会社なんてすぐに辞めるべき」みたいなことが書いてありました。当時フォルシアの業務ではdockerを使っていなかったので、これは辞めるべきなんか！？と焦りました（嘘です。全然焦ってないです）。 しばらくしてKubernetesというものを耳にしました。いま流行りの「コンテナオーケストレーションシステム」らしい。よくわからん。 そもそもどう発音するのが正解？くーべるねてぃす？きゅばねてぃす？ というわけで本を買って少し勉強してみました。 フォルシアでの導入を考える その後デブサミに行く機会があったので、Kubernetes関係のセッションを探してみました。すると結構ある！早速登録して話を聞きに行きました。 会場で「Kubernetes触ったことあるよ〜って人？」は3割くらい、「本番運用してるよ〜って人？」は数%で、思っていたよりも少ない。日本での普及はこれからだが、世界的には本番運用も珍しい技術ではない、とのことでした。 さて、このイベントで特に知りたかったのは、フォルシアのサービスでもKubernetesを導入できるのか、する意味があるのか、という点でした。ちょうど登録したセッションの中に、長年運用してきたアプリをマイクロサービス化してKubernetesに移行中、というものがありました。 お、参考になりそう！と思い、セッション後に登壇者に話を聞きに行ってみました。 が、フォルシアのようにオンプレで運用している顧客サービスが多い場合には、Kubernetes移行はコスパが悪いと思う、という話でした。 うーん、まあたしかに。 登壇者の会社でも、Kubernetes移行したのはクラウド運用の自社サービスだけということでした。 というわけで、どうしたもんかなあ、と思っているうちに月日は流れていきました。 季節は巡り 社内で絶賛開発中の案件で、開発環境にdockerを使っているという話が出てきました。コンテナ化＝マイクロサービス化というイメージが強く、アプリのフレームワークから考え直さないといけないかなと思っていましたが、そう難しく考える必要はありませんでした。 1プロセス1コンテナの原則に従いミドルウェアごとにコンテナを作って、docker-composeで管理する、という構成でした（これでフォルシアを辞める理由がなくなった！）。 さらに、ログ分析のためにオンプレサーバでKubernetesの利用を始めた！という事例も出てきました（独力でKubernetesを運用し始めた凄腕エンジニアのHさん、恐るべし）。 機運高まる！ このように社内でコンテナ化、Kubernetes利用の機運が高まってきた中、フォルシアのサービスでコンテナをどう活用していくか、という内容でエンジニアでディスカッションを行いました。 開発環境でdockerを使うのは、特に大規模アプリの開発で便利 本番環境でのKubernetesの利用は、運用やリリースのコストが下がり、顧客にとってもフォルシアにとってもメリットがある Spook の性質上、データの永続化が不要なので、コンテナとの相性が良い 顧客サービスでKubernetesをいきなり導入するのは現実的ではないので、自社サービスから段階的に実績を作っていきたい という感じで、今後の方向性をはっきりさせることができました。 そしてこのディスカッションを受けて、早速Spookの簡単なアプリをGKEに乗せてみました！ （実際にはアドベントカレンダーまでに、ということでがんばりました。アドベントカレンダー駆動開発ですね） まだまだKubernetesを触り始めたばかりですが、来年のアドベントカレンダーでは実際に本番環境に導入した話をしたいです。 最後に 今回のKubernetesのように、フォルシアでは新しい技術に関するディスカッションや、実際にその技術を使っているエンジニアによるゼミ形式の講義を毎週社内で行っています。新しい技術に触れながらも、地に足を付けて開発に取り組む環境が整ってきたと感じています。 そんなフォルシアに興味を持った方は、ぜひ こちら まで！

JavaScript 2 Advent Calendar 2019 6日目の記事です。 こんにちは。2019年新卒入社エンジニアの中曽です。 私は経済学部卒で、入社してから本格的にプログラミングに触れ始めました。 現在の業務ではJavaScriptというプログラミング言語を主に使用しており、この記事では、経済学部卒という背景と合わせて経済学の問題をJavaScriptで解いてみます。 フォルシアには経済学部卒のエンジニアも少なからず在籍し活躍しており、この記事を読んで経済学部の方もプログラミングをやってみたいと思う機会になれば幸いです。もちろん経済学部ではない方でも、経済学に興味を持ってもらうきっかけになると嬉しいです。 ゲーム理論 初めに、何の問題を解くかを決定する必要がありますね。 例えば、ミクロ経済学には消費者理論・生産者理論であったり、マクロ経済学には貨幣市場・労働市場であったりテーマにできそうなものは色々あります。 その数ある問題の中で、日常生活でも関わってくる場面があり興味を持ってもらいやすいと思うので、ゲーム理論を取り上げたいと思います。 簡単に説明すると、ゲーム理論とは、複数の利害関係を持つプレイヤーがいる状況で、それぞれの利得を考えて合理的に意思決定を行う理論のことです。 先程日常生活でも関わってくる場面があると述べましたが、例えば野球での打者と投手の駆け引きもゲーム理論のフレームワークを使って表現することができます。 囚人のジレンマ 次に、ゲーム理論の思考方法に関して有名な例題を出して説明します。 ある犯罪によって2人の容疑者が逮捕され、それぞれが 意思疎通のできない別々の部屋 で尋問を受けている。 この時、2人がとる行動は「自白する」or「自白しない」の2択で、それぞれの行動の結果、下記の判決がくだされることが予め分かっているものとします。 片方が「自白する」、もう一方は「自白しない」を選択した場合 「自白する」を選択した方は無罪(懲役0年) 「自白しない」を選択した方は懲役10年 両方が「自白しない」を選択した場合は、両方が懲役1年 両方が「自白する」を選択した場合は、両方が懲役5年 これを標準型ゲームとして表現し、図示すると、下の表のようになります。 「自白する」をA、「自白しない」をBとし、1文字目にプレイヤー1の選択が来るようにしています。例えばAB(0, -10)は、プレイヤー1が「（A）自白する」、プレイヤー2が「（B）自白しない」場合となります。 プレイヤー1 ＼ 2 （A）自白する （B）自白しない （A）自白する AA (-5, -5) AB (0, -10) （B）自白しない BA (-10, 0) BB (-1, -1) 上の図を説明すると... プレイヤー2が「（A）自白する」と考えると、プレイヤー1の利得は 「（A）自白する」を選択した場合→ -5 「（B）自白しない」を選択した場合→ -10 →「（A）自白する」を選択した方が利得が大きくなる プレイヤー2が「（B）自白しない」と考えると、プレイヤー1の利得は 「（A）自白する」を選択した場合→ 0 「（B）自白しない」を選択した場合→ -1 →「（A）自白する」を選択した方が利得が大きくなる プレイヤー1はプレイヤー2の選択によらず、常に「（A）自白する」を選択したほうが利得が大きくなります。プレイヤー2の目線で考えた場合も同じような結果になります。 それぞれのプレイヤーは個人の利益を優先して考えた場合、相手がどちらの選択をする場合で考えても「（A）自白する」を選択した方が得になります。 選択したものに 〇 を付けてみます。 プレイヤー1 ＼ 2 （A）自白する （B）自白しない （A）自白する AA ( 〇 -5, 〇 -5) AB ( 〇 0, -10) （B）自白しない BA (-10, 〇 0) BB (-1, -1) その結果、AA(-5, -5)がお互いに合理的な判断をした結果となります。これは ナッシュ均衡 になっています。どちらにも 〇 が付いていますね。 ナッシュ均衡をもう少し説明すると、ナッシュ均衡とは「全てのプレイヤーが本人以外の行動を所与として、全てのプレイヤーが互いに最適な戦略を取っている状態」となります。ナッシュ均衡から自分だけが戦略を変更しても利得を上げることができない状態となります。 ちなみに、全体としてはBB(-1, -1)が最適なのにも関わらず、お互いに合理的な判断をした結果AA(-5, -5)がナッシュ均衡となります。これが 囚人のジレンマ と呼ばれる所以です。 実際に解いてみる 下記の利得表で表現される標準型ゲームのナッシュ均衡を求めるプログラムを作成したいと思います。 プレイヤー1 ＼ 2 A B A AA (a, b) AB (c, d) B BA (e, f) BB (g, h) プログラムとして表現する際に、利得表を下記のデータ構造で表現し、関数を作成するにあたり、下のような入力と出力を設定します。 入力 const result = { "AA": {player1: a, player2: b}, "AB": {player1: c, player2: d}, "BA": {player1: e, player2: f}, "BB": {player1: g, player2: h} } 　1つ目の戦略をA、2つ目の戦略をBとしており、player1の戦略を1文字目に表しています。 　"AA"等の下位のオブジェクトは、player1,2のそれぞれの利得を示しています。 出力 ナッシュ均衡を、AA, AB, BA,BB が含まれる配列の形で返す。 　 ex) ["AA"] 実装 それでは、コードを書いていきます。 　 // ナッシュ均衡を求める関数 const calcNash = (obj) => { // 相手のそれぞれの選択に対する最適な選択を決める const p1Strategy1 = getMaxOption(obj, "player1", ["AA", "BA"]); const p1Strategy2 = getMaxOption(obj, "player1", ["AB", "BB"]); const p2Strategy1 = getMaxOption(obj, "player2", ["AA", "AB"]); const p2Strategy2 = getMaxOption(obj, "player2", ["BA", "BB"]); // 2人のプレイヤーが同じ選択をする場合、ナッシュ均衡となる const nash = [p1Strategy1, p1Strategy2].filter(elm => { return elm === p2Strategy1 || elm === p2Strategy2; }); return nash; }; // 利得が最大になる選択を決定する関数 const getMaxOption = (obj, player, array) => { // 適当に初期値を設定(利得の最小値より小さくする必要がある) let maxProfit = -100; let maxOption = ""; array.forEach(elm => { Object.keys(obj).forEach(key => { if (key === elm && obj[key][player] > maxProfit) { maxProfit = obj[key][player]; maxOption = key; } }); }); return maxOption; }; const result = { "AA": {player1: -5, player2: -5}, "AB": {player1: 0, player2: -10}, "BA": {player1: -10, player2: 0}, "BB": {player1: -1, player2: -1} }; console.log(calcNash(result)); // ['AA'] コードの説明 書いたコードについて説明します。 ナッシュ均衡を求める関数(calcNash)とは別に、利得が最大になる選択を決定する関数(getMaxOption)を分けて作成しました。 getMaxOption関数で相手のそれぞれの選択に対する最適反応を求めた後、calcNash関数でナッシュ均衡を求めるという流れになっています。 getMaxOption関数での処理 array.forEach...引数で指定された配列に対して繰り返し処理を行います。 ex) ["AA", "BB"] Object.keys(obj).forEach...引数で指定されたオブジェクトに対して繰り返し処理を行います。 if文での処理...配列の要素とオブジェクトのkeyが合致している、かつ指定されたプレイヤーの利得が、以前選択した利得より大きくなる場合に、maxProfitとmaxOptionを更新します。 calcNash関数での処理 p1Starategy1等などの定数...getMaxOption関数を呼び、相手のそれぞれの選択に対する最適な選択を決めます。 nash定数...filter関数を使用してプレイヤー1に対して繰り返し処理をすることで、両プレイヤーが同じ選択をした場合にのみ返り値を渡す配列に結果を抜き出します。 囚人のジレンマのケースで考えると、 プレイヤー1が選択をする際、p1Strategy1で"AA"、p1Strategy2で"AB"が選ばれます。 プレイヤー2が選択をする際、p2Strategy1で"AA"、p2Strategy1で"BA"が選ばれます。 よって、両方が"AA"の選択を行うため、"AA"がナッシュ均衡として返されるという処理になっています。 確率を含めたゲーム理論 しかし、上記では対応できないケースもあります。 例えば、次のようなケースです。 流行の先端を行くリーダーと、リーダーの真似をしようとするフォロワーという2人のプレイヤーがいる。 リーダーにとってはフォロワーと異なる服を着ると利得が高いが、フォロワーにとってはリーダーと同じ色を着ると利得が高い。 リーダー ＼ フォロワー （A）赤色の服 q （B）青色の服 1 - q （A）赤色の服 p AA (-1, 〇 1) AB ( 〇 1, -1) （B）青色の服 1 - p BA ( 〇 1, -1) BB (-1, 〇 -1) ナッシュ均衡を求めようとしても、お互いの選択が一致するものが無いため求めることができません。 この場合、複数の戦略を確率的に混ぜる「混合戦略」というものを行うということになり、期待される利得を最大化するようにそれぞれの選択確率（どちらの服を選ぶかどうかを決める確率）を求め、その確率が均衡点となります。 これに対して、先のコードで求められるのは、「純粋戦略」のナッシュ均衡といわれ、「純粋戦略」とは与えられた状況に対して、毎回同じ行為のみを行う種類の戦略のことを指します。 例えば、上記の例の場合でリーダーが赤色の服を選ぶ確率を p 、フォロワーが赤色の服を選ぶ確率を q とすると、リーダーの期待される利得はフォロワーの選択確率によって変わるので、 赤色の服を選んだ場合: u(赤色の服) = AA(-1) × q + AB(1) × (1-q) = -2q + 1 青色の服を選んだ場合: u(青色の服) = BA(1) × q + BB(-1) × (1-q) = 2q - 1 となります。( u(x) は x を選んだときに期待される利得とします。) u(赤色の服) > u(青色の服)となるのは、 -2q + 1 > 2q - 1 すなわち q のとき u(赤色の服) -2q + 1 すなわち q > 1/2 のとき u(赤色の服) = u(青色の服)となるのは、 -2q + 1 = 2q - 1 すなわち q = 1/2 のときです。 これをまとめると、 q のとき、 p = 1 (「(A)赤色の服」を選ぶ) q = 1/2 のとき、 0 q > 1/2 のとき、 p = 0 (「(B)青色の服」を選ぶ) となります。 同様にすると、フォロワーについては、 p のとき、 q = 0 (「(B)青色の服」を選ぶ) p = 1/2 のとき、 0 p > 1/2 のとき、 q = 1 (「(A)赤色の服」を選ぶ) となります。 これを基に、それぞれのプレイヤーが相手の選択確率に対する反応を図示した曲線（最適反応曲線と呼ばれる）のグラフの交点が、混合戦略におけるナッシュ均衡となります。 それでは、コードを書いていきます。 引数は純粋戦略と同様な形にし、出力は次のように設定します。 出力 配列の中に、ナッシュ均衡となる確率のペアを配列として入れて返す。 　 ex) [[0.5, 0.5]] // ナッシュ均衡を求める関数 const calcNash = (obj) => { // 相手のそれぞれの選択に対する最適な選択を決める const p1Strategy1 = getMaxOption(obj, "player1", ["AA", "BA"]); const p1Strategy2 = getMaxOption(obj, "player1", ["AB", "BB"]); const p2Strategy1 = getMaxOption(obj, "player2", ["AA", "AB"]); const p2Strategy2 = getMaxOption(obj, "player2", ["BA", "BB"]); let nash = []; const p1Prob = calcProbability(obj, "player2"); const p2Prob = calcProbability(obj, "player1"); nash.push([p1Prob, p2Prob]); if (p1Strategy1 === p2Strategy1 ) { nash.push([1,1]) } if (p1Strategy2 === p2Strategy2) { nash.push([0,0]) } return nash; }; const getMaxOption = (obj, player, array) => { // 適当に初期値を設定(利得の最小値より小さくする必要がある) let maxProfit = -100; let maxOption = ""; array.forEach(elm => { Object.keys(obj).forEach(key => { if (key === elm && obj[key][player] > maxProfit) { maxProfit = obj[key][player]; maxOption = key; } }); }); return maxOption; }; // 戦略を選択する確率を算出する関数 const calcProbability = (obj, player) => { const prob = player === "player1" ? (obj["BB"][player] - obj["AB"][player]) / (obj["AA"][player] - obj["AB"][player] - obj["BA"][player] + obj["BB"][player]) : (obj["BB"][player] - obj["BA"][player]) / (obj["AA"][player] - obj["BA"][player] - obj["AB"][player] + obj["BB"][player]); return prob; }; const result = { "AA": {player1: -1, player2: 1}, "AB": {player1: 1, player2: -1}, "BA": {player1: 1, player2: -1}, "BB": {player1: -1, player2: 1} }; console.log(calcNash(result)); // [[0.5, 0.5]] 処理として加えたのは、calcNash関数において、calcProbability関数を呼び出し確率を求めるという部分です。 calcProbability関数での処理 ここの確率は、各プレイヤーがAを選んだ時とBを選んだ時のそれぞれの期待利得が合致する確率を求めます。例えばプレイヤー1の期待利得は、プレイヤー2の確率によって左右されるので、p2Probの引数に、"player1"が入ってこの関数は呼び出されます。 また、確率を求める式は、例えば -2q + 1 = 2q - 1 といった式を予め移項して処理するようにしています。 calcNash関数での処理 ナッシュ均衡時の確率p1Prob1,p2Prob（p1Prob: プレイヤー1がAを選択する確率、p2Prob: プレイヤー2がAを選択する確率）の組み合わせを返します。 if文を追加したのは、混合戦略において上で求めた確率（グラフ上の交点になる）の他に、下の図のように(0, 0), (1, 1)で交点を持つ場合があるからです。確率を用いる混合戦略の中でも、各プレイヤーがそれぞれ相手がAという行動をするならば自分もAを行い、相手がBという行動をするならば自分もBを行った方が利得が高い場合です。 これは純粋戦略における場合と同じ要領で求めることができるので、先に使用したgetMaxOption関数を再度利用しています。下の問題がその例です。 男女の争い 男(プレイヤー1)＼ 女(プレイヤー2) （A） 野球を見る q （B）買い物に行く 1 - q （A）野球を見る p AA (4, 1) AB (0, 0) （B）買い物に行く 1-p BA (0, 0) BB (1, 4) 相手がどちらを選択するかは絶対的には決定されないが、もし相手がを野球を見るなら一緒に野球を見た方が利得が大きく、買い物に行くなら買い物に行った方がお互い利得が大きいといった内容ですね。 関数の実行結果は下記のようになります。 console.log(calcNash(result)); // [ [ 0.8, 0.2 ], [ 1, 1 ], [ 0, 0 ] ] まとめ この記事では経済学の分野からゲーム理論を取り上げ、JavaScriptを使って、標準型ゲームの混合戦略も含めたナッシュ均衡を求めました。 この記事でゲーム理論について興味が出てきたという方がいれば、もっと調べてもらえると嬉しいです。 一方、ゲーム理論は分かるけどもプログラミングに関してはあまり経験がないという方も、この機会に触れてみるのも面白いと思います。 フォルシアでは、需要量を予測し、供給量に応じて最適な販売価格を提示するダイナミックプライシングを扱っています。計量経済学的な面白さもある分野なので、興味のある方はぜひ 話を聞きに来てみてください 。

FORCIAアドベントカレンダー2019 5日目の記事です。 検索プラットフォーム事業部の田中です。 フォルシアでは、最新の技術をプロダクトに取り込むということにも果敢に挑戦していますが、一方でレガシーコードの改善や日々の運用の改善にも力を入れています。 今回は、過去にAPIテストを自動化するための Frisby.js のバージョンが0.85と古くなっていたため、今更ですが最新の2.xに置き換えた話をします。 Frisby.js とは APIのブラックボックステストを自動化するためのフレームワークで、JavaScriptの定番のテストフレームワークのJestベースで書かれています(2.0の途中でJasmineからJestに変更になりました)。APIテストフレームワークのデファクトになりつつある人気のツールです。 最初のコミットは2011年と長く愛されています。ながらくv0.85からリリースがありませんでしたが、1系をとばして2017年の7月にv2.0がリリースされました。 v0.x からv2.x へ 変更点については こちら にもありますが、独自のラッパーを書くのではなく、Jest(またはJasmine)の作法に則る形でテストを書けるようになりました(it -> expect で書けるようになった)。 より詳細な、変更点や思想は メインコミッターのブログ の記事を読むと良いかと思います。 v0.x のコード var frisby = require('frisby'); frisby.create('should get user Joe Schmoe') .get(testHost + '/users/1') .expectStatus(200) .expectJSON({ id: 1, email: 'joe.schmoe@example.com' }) .toss(); v2.x のコード var frisby = require('frisby'); it('should get user Joe Schmoe', function() { return frisby.get(testHost + '/users/1') .expect('status', 200) .expect('json', { id: 1, email: 'joe.schmoe@example.com' }); }); 基本的にはJestの文法に従って、frisby->create->get->expectXX->toss を frisby->get->expect('XX') と変えていくだけです。 型のチェックは、JavaScript の型を指定していた箇所が Joi のオブジェクトを指定するように変わっています。 これにより、さらに細かいバリデーションができるようになっています。 v0.x expectJSONTypes('*', { hoge: String }) v2.x expect('jsonTypes', '*', { hoge: Joi.string() }) また v2.x から expectJSON(...) の代替として expet('json', ...) と expect('jsonStrict', ...) がありますが、json は指定したものが一致していれば良い jsonStrict は完全に一致している必要があります。 移行時に実際に困ったところ 基本的には、v0.x と v2.x は同等のものが用意されており置き換えていくだけですが、いくつか考慮が必要だった点があるので記載します。 配列同士の比較が厳密な比較になってしまう 例えば下記のようなレスポンスがあったとします。 [ { hoge: 1, fuga: 2 } ] v0.x では下記でテストをパスしていました。 expectJSON( '*', [ { hoge: 1 } ] ) v2.x では下記はFailになってしまいます。 expect( 'json' '*', [ { hoge: 1 } ] ) 下記のように指定する必要があります。 expectJSON( '*.0', { hoge: 1 } ) expectJSON でできていた関数の評価ができない v0.x では expectJSON の中で下記のように評価関数を実行することができました。 expectJSON( { message: function(val) { expect(val).toBe('hoge'); } } ) v2.xではこれができなくなっています。そこでかなり力技ですが、下記のように再帰的に評価するようなカスタムマッチャーを作ればこれを実現できます。 const getPathVal = (response, prefix, results) => { results = results || []; for (let key in response){ const path = prefix ? prefix + '.' + key : key; if (typeof response[key] === 'object') { if(Array.isArray(response[key])) { response[key].forEach((item, i) => { getPathVal(item, path + '.' + i, results); }); } else { getPathVal(response[key], path, results); } } else { results.push({path: path, val: response[key]}); } } return results; }; beforeAll(() => { frisby.addExpectHandler('jsonf', (response, path, expected) => { frisby.utils.withPath(path, response.json, (jsonChunk) => { getPathVal(expected).forEach((item) => { frisby.utils.withPath(item.path ,jsonChunk, (actual) => { // valがfunctionの場合はmatcherが設定されているのでそれを評価する if(typeof item.val === 'function') { item.val(actual); } else { expect(actual).toBe(item.val); } }); }); }); }); }); frisby.get(host).expect( 'jsonf', '*', { message: function(val) { expect(val).toBe('hoge'); } } ); ちなみにこのカスタムマッチャーを定義しておくと、配列同士の比較が厳密な比較になってしまう問題も解決できます。 フォームデータ形式のpostリクエストの指定の仕方が変わった v0.x ではPOSTでリクエストを送る場合は引数にオブジェクトを指定すれば、よしなに body を application/x-www-form-urlencoded の形式に変換して送ってくれていたのですが、v2.0 では下記のようにする必要があります(formDataで指定もできますがここでは割愛します)。 const body = { hoge: 1, fuga: 2 }; const frisby = require('frisby'); const qs = require('qs'); frisby.setup({ request: { headers: { 'Content-Type': 'application/x-www-form-urlencoded' } ).post(host, qs.stringify(body)).; さいごに すごく地味な作業ですが、こういったツール類も新しいものに移行していくと、新機能を使えるなど色々と恩恵を受けられます。最初からバージョンアップを見越して、テストコードにロジックを書き過ぎないようにしたり、正解データをコードとは切り離して持っておいたりすることなどが重要です。ちょっと重い腰を上げてバージョンアップしていきましょう。

この記事は Competitive Programming (1) Advent Calendar 2019 &nbsp3日目の記事です。 フォルシア株式会社でエンジニアをしている松本です。業務ではRustでインメモリデータベースを開発しています。 日常生活においても、最短経路を求めたいことはよくあると思います。例えば旅先でホテルまでの行き方を調べているとき、ボルダリングでオブザベをしているとき、知り合いを何人挟めばトランプ大統領につながるか考えているとき、マンムーにフリーズドライを遺伝させたいとき、おそらくあなたは最短経路について考えています。 例示した構造は頂点と辺からなるグラフとして表現することができ、グラフ上のある点からある点への最も短い経路を見つける問題を最短経路問題と言います。この記事では、Rustで最短経路問題を解くアルゴリズムであるダイクストラ法とワーシャルフロイド法を実装します。最短経路長だけを求めるのではなく、経路復元と呼ばれる最短経路の出力も実装します。 単一始点からの最短経路 まずは単一始点からの最短経路を求めましょう。負の距離を持った辺が無い場合、 ダイクストラ法(Dijkstra's algorithm) というアルゴリズムが知られています。これは、既に最短経路で到達した頂点群(A)のどれかと隣接している頂点のうち、最も始点からの距離が短い頂点をAに追加していくアルゴリズムです。 なんとRustの公式ドキュメントで std::collections::binary_heapのサンプル としてダイクストラ法の実装が例示されています(アルゴリズムの本体部分を抜粋したものが下記)。 // Dijkstra's shortest path algorithm. // Start at `start` and use `dist` to track the current shortest distance // to each node. This implementation isn't memory-efficient as it may leave duplicate // nodes in the queue. It also uses `usize::MAX` as a sentinel value, // for a simpler implementation. fn shortest_path(adj_list: &Vec<Vec<Edge&gt&gt, start: usize, goal: usize) -> Option<usize> { // dist[node] = current shortest distance from `start` to `node` let mut dist: Vec = (0..adj_list.len()).map(|_| usize::MAX).collect(); let mut heap = BinaryHeap::new(); // We're at `start`, with a zero cost dist[start] = 0; heap.push(State { cost: 0, position: start }); // Examine the frontier with lower cost nodes first (min-heap) while let Some(State { cost, position }) = heap.pop() { // Alternatively we could have continued to find all shortest paths if position == goal { return Some(cost); } // Important as we may have already found a better way if cost > dist[position] { continue; } // For each node we can reach, see if we can find a way with // a lower cost going through this node for edge in &adj_list[position] { let next = State { cost: cost + edge.cost, position: edge.node }; // If so, add it to the frontier and continue if next.cost データの持ち方 グラフを表現する方法として、各頂点について隣接する(ある辺の両端になっている)頂点リスト(あるいは辺の情報)を保持する隣接リスト(adjacency list)と、各頂点対について共有する辺があればその辺の情報を記録する隣接行列(adjacency matrix)があります。ダイクストラ法は隣接している頂点を効率よく見つけたいため、隣接している頂点リストを保持する隣接リストを使うほうが効率が良いです。 例としてこのような有向グラフを隣接リストで表現すると下記のように表すことができます。 let graph = vec![ vec![Edge { node: 2, cost: 10 }, Edge { node: 1, cost: 1 }], vec![Edge { node: 3, cost: 2 }], vec![ Edge { node: 1, cost: 1 }, Edge { node: 3, cost: 3 }, Edge { node: 4, cost: 1 }, ], vec![Edge { node: 0, cost: 7 }, Edge { node: 4, cost: 2 }], vec![], ]; 経路復元 さて、上述の実装では最短経路長だけが返却され、具体的な経路は明らかではありませんでした。具体的な経路を求める方法を考えましょう。 出力したい経路情報 path = [start, ..., goal] とstartから各頂点への最短経路長情報 dist について考えます。 d= dist[path[i]] であるとき path[i-1] は d' = dist[path[i-1]] かつ頂点i-1から頂点iへ距離d-d'の辺を持っているはずです。このような頂点を探すことで最短経路を最短経路長の情報から復元することができます。この方法を素直に実装するとVを頂点数、Lを経路長として最悪計算量O(V^2・L)になってしまいます。 最短経路を求める際に１つ前の頂点情報を記録することでO(L)で復元することができます。下記の実装では pre_node に記録しながら最短経路長を更新しています。 use std::cmp::Ordering; use std::collections::BinaryHeap; use std::usize; // BinaryHeapに渡すStateの実装 #[derive(Copy, Clone, Eq, PartialEq)] struct State { cost: usize, position: usize, pre_node: usize, } impl Ord for State { fn cmp(&self, other: &State) -> Ordering { other .cost .cmp(&self.cost) .then_with(|| self.position.cmp(&other.position)) } } impl PartialOrd for State { fn partial_cmp(&self, other: &State) -> Option<Ordering> { Some(self.cmp(other)) } } struct Edge { node: usize, cost: usize, } fn shortest_path( adj_list: &Vec<Vec<Edge>>, start: usize, goal: usize, ) -> Option { let mut dist: Vec = (0..adj_list.len()).map(|_| usize::MAX).collect(); let mut pre_nodes: Vec = (0..adj_list.len()).map(|i| i).collect(); let mut heap = BinaryHeap::new(); dist[start] = 0; heap.push(State { cost: 0, position: start, pre_node: 0, }); while let Some(State { cost, position, pre_node, }) = heap.pop() { if cost > dist[position] { continue; } pre_nodes[position] = pre_node; if position == goal { let mut v = goal; let mut path = vec![goal]; while v != start { path.push(pre_nodes[v]); v = pre_nodes[v]; } path.reverse(); return Some((cost, path)); } for edge in &adj_list[position] { let next = State { cost: cost + edge.cost, position: edge.node, pre_node: position, }; if next.cost 具体的なグラフと始点・終点を与え、結果が正しいことを確認しましょう。 fn main() { let graph = vec![ vec![Edge { node: 2, cost: 10 }, Edge { node: 1, cost: 1 }], vec![Edge { node: 3, cost: 2 }], vec![ Edge { node: 1, cost: 1 }, Edge { node: 3, cost: 3 }, Edge { node: 4, cost: 1 }, ], vec![Edge { node: 0, cost: 7 }, Edge { node: 4, cost: 2 }], vec![], ]; // fn shortest_path( // adj_list: &Vec<Vec<Edge>>, // start: usize, // goal: usize, // ) -> Option assert_eq!(shortest_path(&graph, 0, 1), Some((1, vec![0, 1]))); assert_eq!(shortest_path(&graph, 0, 3), Some((3, vec![0, 1, 3]))); assert_eq!(shortest_path(&graph, 3, 0), Some((7, vec![3, 0]))); assert_eq!(shortest_path(&graph, 0, 4), Some((5, vec![0, 1, 3, 4]))); assert_eq!(shortest_path(&graph, 4, 0), None); } 全点対間の最短経路 続いて、全点対間の最短経路を求める ワーシャルフロイド法(Warshall-Floyd Algorithm) についても実装していきましょう。 データの持ち方 各頂点対について辺を持っているかを高速に調べたいため、隣接行列を使用します。隣接リストで表現したのと同じグラフは隣接行列では下記のように表せます。 let mut adj_matrix = vec![ vec![None, Some(1), Some(10), None, None], vec![None, None, None, Some(2), None], vec![None, Some(1), None, Some(3), Some(1)], vec![Some(7), None, None, None, Some(2)], vec![None, None, None, None, None], ]; ※ None は辺がないこと、 Some(x) は距離xの辺があることと対応しています。 経路復元 ダイクストラ法と同様に１つ前の情報を保持しておいて、終点から始点へ後ろ向きに遡っても良いのですが、 next[i][j] =「頂点iから頂点jに行くとき、頂点iの次に通る頂点」 というように更新していくことで、直感的に前からたどることができるようになります。 実装を示します。上述の adj_matrix を dist として下記の warshall_floyd 関数に渡します。 fn warshall_floyd(dist: &mut Vec<Vec<Option<usize>>>) -> Vec<Vec<usize>> { let n = dist.len(); let mut next = vec![]; // next[i][j] = j で初期化 for i in 0..n { next.push((0..n).map(|j| j).collect::<Vec<usize>>()); } for k in 0..n { for i in 0..n { for j in 0..n { if let (Some(dik), Some(dkj)) = (dist[i][k], dist[k][j]) { if dist[i][j].is_none() || dist[i][j].unwrap() > dik + dkj { dist[i][j] = Some(dik + dkj); next[i][j] = next[i][k]; } } } } } next } 隣接行列を最短経路の行列と見て破壊的に更新しながら、次の頂点を記録します。 更新された最短経路の行列と次の頂点を記録した行列を始点から終点にたどることで経路復元が可能です。 fn shortest_path( dist: &Vec<Vec<Option<usize>>>, next: &Vec<Vec<usize>>, start: usize, goal: usize, ) -> Option { if dist[start][goal].is_none() { return None; } let mut path = vec![start]; let mut node = start; while node != goal { path.push(next[node][goal]); node = next[node][goal]; } Some((dist[start][goal].unwrap(), path)) } こちらも同様に動作が確認できます。 fn main() { let mut dist = vec![ vec![None, Some(1), Some(10), None, None], vec![None, None, None, Some(2), None], vec![None, Some(1), None, Some(3), Some(1)], vec![Some(7), None, None, None, Some(2)], vec![None, None, None, None, None], ]; let next = warshall_floyd(&mut dist); assert_eq!(shortest_path(&dist, &next, 0, 1), Some((1, vec![0, 1]))); assert_eq!(shortest_path(&dist, &next, 0, 3), Some((3, vec![0, 1, 3]))); assert_eq!(shortest_path(&dist, &next, 3, 0), Some((7, vec![3, 0]))); assert_eq!(shortest_path(&dist, &next, 0, 4), Some((5, vec![0, 1, 3, 4]))); assert_eq!(shortest_path(&dist, &next, 4, 0), None); } まとめ 最短経路問題について具体的な経路を求める方法の解説とRustでの実装例を示しました。 私はまだ実務で最短経路問題を解いたことはありませんが、グラフ理論の別の問題である最小費用流のアルゴリズムが使える場面があり、色々なアルゴリズムを知っておくことは大切だと考えています。 GoogleカレンダーとSlackからの情報で「グループ分け」シャッフルランチはじめました～テクノロジー編～ 皆さんも好きな言語でいろいろなアルゴリズムを実装してみてください。 また、フォルシアには競技プログラミング部があり、先日行われた PG BATTLE 2019 では企業の部248チーム中9位の成績を収めました。フォルシアで働くことに興味がある方は AtCoderJobs からぜひご連絡ください！

FORCIAアドベントカレンダー2019 2日目の記事です。 ! この記事は2019年12月時点での最新バージョン、v6.2.0を対象に執筆されています。 記事で紹介している基本的な使い方は2026年1月現在最新のv7でも動作します。ただし、v6→v7のメジャーアップデートの際に一部の破壊的変更が加えられたため、本番環境で使用する際は公式の移行ガイド を参照してください。 2016新卒入社の龍島です。最近業務でexpress-validatorのSchema-Validationを利用しているのですが、あまり丁寧な情報がなく、利用方法がわからない部分がありました。そこで前日の光山の記事

FORCIAアドベントカレンダー2019 2日目の記事です。 2016新卒入社の龍島です。最近業務でexpress-validatorのSchema-Validationを利用しているのですが、あまり丁寧な情報がなく、利用方法がわからない部分がありました。そこで 前日の光山の記事 に触発され、ソースを読んで調べてみました。少しでも同じ悩みを持っている方の役に立てれば幸いです。今困っている！使い方を早く知りたい！という方は「 Schema-Validationの設定方法 」の章を読んでいただければと思います。 express-validatorとは 公式ドキュメント の説明を借りると、 express-validator is a set of express.js middlewares that wraps validator.js validator and sanitizer functions. Node.jsのwebアプリケーションフレームワークである Express 上で ミドルウェア として validator.js の機能を利用して、フィールドをバリデート、サニタイズできるようにしたものです。 利用方法は下記のような感じです（公式ドキュメントより）。 const { check, validationResult } = require('express-validator'); app.post('/user', [ // username must be an email check('username').isEmail(), // password must be at least 5 chars long check('password').isLength({ min: 5 }) ], (req, res) => { // Finds the validation errors in this request and wraps them in an object with handy functions const errors = validationResult(req); if (!errors.isEmpty()) { return res.status(422).json({ errors: errors.array() }); } User.create({ username: req.body.username, password: req.body.password }).then(user => res.json(user)); }); ミドルウェアとして check('${field名}').isEmail() などとするとフィールドがメールアドレスの形式かチェックできるといった次第ですね。 チェックはchainingが可能で、 check("password") .isLength({min: 5}) .isInt() とすれば長さが5以上で数字のみのバリデーションが可能です。 Schema-Validation 公式ドキュメント にもある通り、フィールド名をキーとしてオブジェクトでバリデーションの定義を記述できるものです。複数ページで共通のバリデーションを行う場合や、定義を動的に生成する際に便利そうですね。公式ドキュメントのサンプルを簡略化したものを載せておきます。 const { checkSchema } = require('express-validator'); app.put('/user/:id/password', checkSchema({ id: { // The location of the field, can be one or more of body, cookies, headers, params or query. // If omitted, all request locations will be checked in: ['params', 'query'], errorMessage: 'ID is wrong', isInt: true, // Sanitizers can go here as well toInt: true }, password: { isLength: { errorMessage: 'Password should be at least 7 chars long', // Multiple options would be expressed as an array options: { min: 7 } } }, firstName: { isUppercase: { // To negate a validator negated: true, }, rtrim: { // Options as an array options: [[" ", "-"]], }, }, // Wildcards/dots for nested fields work as well 'addresses.*.postalCode': { // Make this field optional when undefined or null optional: { options: { nullable: true } }, isPostalCode: true } }), (req, res, next) => { // handle the request as usual }) フィールド名をキーとすることや、 in で対象のlocationを絞れること、 errorMessage でエラーメッセージを定義することは読み取れますが、 isInt はbooleanを設定しているのに対して、 isLength はオブジェクトで options があったり、 rtrim は options が二重配列だったりと、どのように設定していけばよいのか読み取ることは難しいです。ドキュメントから読み取れなければソースを読みましょう。簡単にソースを読めるのはOSSのいいところです。 以下、isIntなどmethodに対する設定値（true, Object, Arrayなど）をソースに倣って methodCfg と呼ぶことにします。 ソースを読む v6.2.0のソースを読んでいきます。checkSchemaは このあたり です。40行程度しか無いのでサクッと読めそうですね。 全体をざっと見ると、各fieldに対してValidationChainを作って配列で返しているようです。 const chain = check(field, ensureLocations(config, defaultLocations), config.errorMessage); で作成したValidateChainオブジェクトに対して (chain[method] as any)(...options); でoptionsを引数としてmethod（isIntなど）を実行して、chainingしています。つまり最初に例として出した check("password") .isLength({min: 5}) .isInt() の形を作っているわけですね。 気になっているmethodCfgに何を入れればよいかという点は、下記のあたりを見るとわかります。 let options: any[] = methodCfg === true ? [] : methodCfg.options || []; if (options != null && !Array.isArray(options)) { options = [options]; } options という変数に対して methodCfg がtrueもしくは methodCfg.options が無ければ空配列、 methodCfg.options を代入します。またoptionsが配列でなかった場合は配列化していますね。このoptionsが先程のmethod実行時の引数にスプレッド演算子で展開されて渡され、n個目の要素が第n引数となります。 Schema-Validationの設定方法 ソースを読んだことでSchema-Validationの設定方法が見えてきました。 設定可能なmethod check() にchainで繋げられるものがmethodとして利用可能なので、validatorjsの validators や sanitizers はもちろん、express-validator独自である validation 、 sanitization のadditional-methodsもが利用可能です。 methodCfgの設定方法 各methodで、引数が必要なく in や errorMessage も指定しない場合は true を設定しておけば良いです。 id: { isInt: true } 引数が必要な場合はoptionsとして設定します。 password: { isLength: { options: { min: 7 } } } // => check('password').isLength({min: 7}) 引数が複数ある場合は配列にして渡します。※ matchesはmodifierも引数に取れます。 text: { matches: { options: ['abc', 'i'] } } // => check('text').matches('abc', 'i') 引数に配列を渡す場合は注意が必要です（これにハマりました...）。 sort: { isIn: { options: [['recommend', 'lowPrice', 'highPrice']] } } // => check('sort').isIn(['recommend', 'lowPrice', 'highPrice']) 配列はスプレッド演算子で展開されてmethodに渡されるため、配列を渡したい場合は二重配列にする必要があります。 その他は公式ドキュメントのサンプルの通り in でfieldの場所を指定できたり、 errorMessage でバリデートエラー時のエラーメッセージを設定できたりします。 さいごに 公式ドキュメントのサンプルに大体のことは書いてありますが、やはり不明な部分のソースを読んでみるとかなり理解が深まりますね。今回の該当部分以外にもValidationChainの仕組みなどを読んでみましたが、参考になる部分も多かったです。 時間を見つけて今後はExpress本体やvalidator.jsの実装などをソースコードリーディングしようと思います。

FORCIAアドベントカレンダー2019 1日目の記事です。 2019年アドベントカレンダー第1回目の記事を担当させて頂きます、エンジニアの光山です。 現在は経営企画室に所属して、新プロダクトの企画、開発に携わっています。 デファクトスタンダードとなっているPandas 私はちょっとしたデータの確認や加工から、大規模データの分析まで、Pandasをよく利用します。 Pandasとは、Pythonユーザにとってはデファクトスタンダードとなっているライブラリで、データの 入出力 加工 可視化 などを簡単に行うことができる、素晴らしいライブラリです。 例えば、ファイルの入出力については

FORCIAアドベントカレンダー2019 1日目の記事です。 2019年アドベントカレンダー第1回目の記事を担当させて頂きます、エンジニアの光山です。 現在は経営企画室に所属して、新プロダクトの企画、開発に携わっています。 デファクトスタンダードとなっているPandas 私はちょっとしたデータの確認や加工から、大規模データの分析まで、 Pandas をよく利用します。 Pandasとは、Pythonユーザにとってはデファクトスタンダードとなっているライブラリで、データの 入出力 加工 可視化 などを簡単に行うことができる、素晴らしいライブラリです。 例えば、ファイルの入出力については、read_XXX、to_XXXという名前のメソッドで、多くのファイル形式がサポートされています。csvやjsonなどの基本的なファイル形式はもちろんのこと、HTMLやSQL（RDB）、さらにはカラムナフォーマットであるparquetの読み込みもサポートされており、なかなか面白いです。 私は業務上Excelのデータを扱うことも多いのですが、read_excelメソッドを使用すれば、ExcelのファイルをそのままDataFrame形式で読み込むことが可能なので、大変重宝しています（read_excelメソッドは内部的にはxlrdモジュールを使用しています）。 どのような入出力メソッドがあるか、興味のある方はぜひ 公式ドキュメント をご覧ください。 弊社の場合、ORMを使用せず直接SQLを書く機会が多いので、SQLライクにデータを扱うことができるPandasは非常に取っつきやすいライブラリです（余談にはなりますが、昨年から2年連続でSQLを徹底的にチューニングする 検索高速化インターンシップ も開催されるほど、弊社はSQLのチューニングにこだわっています）。 OSSのソースコードを読む利点 前述の通りPythonでのデータ処理に必須と言っても過言ではないPandasですが、ソースコード自体は読まれたことが無い方も多いのではないでしょうか。 Pandasに限らず、ライブラリのソースコードを読むと、ドキュメントに記載の無い挙動についても理解することができるので、知識として定着しやすいです。 何より、有名なOSSは設計自体が美しく、読んでいて楽しいです。もちろん、自分自身の実装の参考にもなります。 そこで、今回はこのPandasのソースコードを読んでみようと思います。 Pandasの繰り返し処理とパフォーマンスについて 今回はPandasの繰り返し処理に着目します。Pandasのパフォーマンスについては検索すると多くの記事がヒットすることから、関心の高い領域と言えるでしょう。 Pandasにおいて、繰り返し処理をするメソッドはいくつか提供されています。代表的なものは下記でしょうか。 iterrows（DataFrame） apply（Series、DataFrame） map（Series） 例えば、数値配列の各要素を二乗する処理は、それぞれのメソッドで下記の通り記述することができます。 import numpy as np import pandas as pd def square(x): return x ** 2 df = pd.DataFrame({'col1': np.arange(100000)}) # iterrows result = [] for idx, row in df.iterrows(): result.append(square(row['col1'])) df['col2'] = pd.DataFrame(result) # apply (for DataFrame) df['col2'] = df.apply(lambda x: square(x['col1']), axis=1) # map df['col2'] = df['col1'].map(square) 処理時間は下記の通りです。メソッド間でかなりの差が開いていますね。 iterrows: 15.8s apply: 3.1s map: 0.1s これらのメソッドは、それぞれどのような実装がされているのでしょうか。ソースコードの中身を読んでみようと思います。 iterrows Pandasでは、重要なメソッドは coreディレクトリ 以下に記述されています。ソースコードをcloneして目当てのメソッドをgrep等で探すこともできますし、公式ドキュメントに記載されているソースコードへのリンク（iterrowsのドキュメントは こちら ）から辿ることもできます。気になるメソッドのソースコードを簡単に確認することができるようになっているのは嬉しいですね。 iterrowsメソッドの記述は下記です。 def iterrows(self): columns = self.columns klass = self._constructor_sliced for k, v in zip(self.index, self.values): s = klass(v, index=columns, name=k) yield k, s （ソースコードは こちら ） for文で繰り返し処理を実行して、行単位で都度Seriesを生成しています。処理としてはいたってシンプルであることが分かると同時に、都度Seriesをインスタンス化しているためパフォーマンス上問題あることも明白ですね。実際、Pandasを普段お使いの方にはお馴染みだと思いますが、iterrowsを使用する方法はパフォーマンスの観点から推奨されていません。 なお、iterrowsメソッドの挙動については コメント（=公式ドキュメント） にも記載があります。iterrowsメソッドだけでなく、Pandasの各メソッドは記述が非常に簡潔であることと、ドキュメントが充実していることが特徴です。 apply (DataFrame.apply) 次に、applyメソッドを読んでみましょう。 applyメソッドは、SeriesとDataFrameそれぞれに対して実装されています。今回はDataFrame.applyの方を読んでみます。 applyメソッドはソースコードを辿ればすぐに分かる通り、 FrameApplyクラス を使用しています。 さらに読み進めると、（Numpyのユニバーサル関数を引数として渡した場合などは異なる処理となりますが、通常の関数を引数とした場合は）apply_series_generatorメソッドで実質的な処理を実行していることが分かります。 # apply_series_generator内 series_gen = self.series_generator # 中略 for i, v in enumerate(series_gen): results[i] = self.f(v) keys.append(v.name) series_generator内で列単位または行単位のデータを生成し、都度関数（self.f()）を呼び出しています。apply実行時には、都度関数の呼び出しコストがかかることを考慮する必要があることが分かります。 map 最後に、3つのメソッドで最速の結果が出た mapメソッド です。 mapメソッドについても同様に処理を辿っていくと、_libs/lib.pyx内の map_inferメソッド に辿り着きます。 pyxという拡張子からも分かる通り、map_inferメソッドはCythonで記述されています。 CythonのコードはCにコンパイルされるので、C並みの実行速度を得ることができます。これがmapメソッドのパフォーマンスが圧倒的だった主な理由ですね。 DataFrameではなくSeriesに対しての処理で完結させることができるのであれば、この3つのメソッドの中ではmapメソッドがパフォーマンス的に最も優れています（なお、今回は各メソッドの相違点を際立たせるために、意図的にDataFrame.applyを登場させましたが、Series.applyであれば、今回の検証方法においてSeries.mapと同等のパフォーマンスが出ています）。 余談ですが、さらにパフォーマンスを向上させたい場合は Dask を使用して処理を並列化する 実行の遅い処理をCythonで記述する などの方法もあります。 （ 公式ドキュメント には、Numbaを使用する方法なども紹介されています。） さいごに 今回は繰り返し処理に着目してソースコードを読んでみました。実際にPandasには多くの実装上の工夫がなされており、読むべき項目はたくさんあります。 自分が使うOSSのソースコードを読むことは勉強になりますし、何か問題が発生した場合でもソースコードレベルで原因究明ができる安心感が生まれます。 Pandasについては、（if分岐が多く、参考にしない方が良さそうな記述もあるものの、）コメントは非常に丁寧に書かれており読みやすいと思いますので、自分が使用しているメソッドについてなど、気になった箇所から少しずつ読んでみてはいかがでしょうか。 Pythonの場合、機械学習であればscikit-learn、WebフレームワークであればFlaskのソースコードなども読んでみると学びが多いと思います（複数のライブラリを読み比べてみると、それぞれの違いがはっきりと現れてまた発見があります）。

こんにちは。旅行プラットフォーム事業部エンジニアの谷井です。 早いもので、明日から12月ですね。街はもうすっかりクリスマスムードになり、オフィスのあるミライナタワーでもすでに綺麗なツリーとイルミネーションが飾られています。 クリスマスの雰囲気は毎年のことながら胸が弾みますが、IT業界での12月のもうひとつの楽しみと言えばアドベントカレンダーですね！ アドベントカレンダーとは 元々はキリスト教において、待降節（advent）にクリスマスまでカウントダウンするためのカレンダーで、毎日一つずつ日付の窓を開き、中に入っているお菓子や小さな贈り物を楽しむものが一般的です。 この風習になぞらえて、インターネット上では12月1日からクリスマスまでの25日間、特定のテーマや団体に関するブログ記事を毎日1件ずつ、持ち回りで投稿するお祭りが様々なサイトで開催されています。 FORCIAアドベントカレンダー2019　12月1日より始動 さて、フォルシアでも昨年に引き続きFORCIA CUBEにてアドベントカレンダー企画を行います！ 明日12月1日から12月25日まで、若手からベテランエンジニアまで25人の社員が登場し、主に技術的なトピックの記事を公開していきます。 （2018年のアドベントカレンダーは こちら からご覧ください！） 詳しくはぜひ毎日の更新を楽しみにしていただければと思いますが、以下のようなテーマの記事が登場する予定です。 Gitlab CI/CD Ansible Rustで競プロ wasm こちらはほんの一例で、フロントエンドからバックエンドまで様々な領域を手掛けるフォルシアらしく、幅広いテーマの記事をお届けします。 新しい記事が公開されたら、下記の特集ページに追加していきます。 『FORCIA アドベントカレンダー2019』 また、更新情報はフォルシアのSNSでも告知しますので、ぜひフォロー&チェックしてくださいね。 Twitter: @forcia_pr Facebook: @forciapr

みなさま初めまして。2019年新卒入社の東川です。 前回はフォルシアで行っているシャッフルランチについて、運営面において工夫した点をご紹介しました。 普段関わりのない社員同士をマッチングシャッフルランチはじめました～企画編～ 今回は、シャッフルランチの「グループ分け」について、技術的に取り組んだことをご紹介します。 技術的な課題 シャッフルランチの開催に当たっては、以下のような2つの技術的な課題がありました。 参加者の日付の割り振りをどうするか シャッフルランチでは、参加者の負担を減らすため、参加表明からグループ分け、日程調整までを自動で行っています。これを実行するためには、参加者の予定をカレンダーから自動で取得し、予定の空いている日にランチを入れる仕組みが必要です。 参加者のグループ分けをどうするか シャッフルランチの目的は、普段の業務で関わりの薄い社員同士で一緒にランチに行き、親睦を深めることです。このためには参加者間の「会社での関わり」を点数化し、それが小さくなるようなグループ分けを探し出す必要があります。 前回のシャッフルランチでは6月17日(月)から21日(金)までの5日間に計76名が参加し、次のような2段階の操作で4人ずつのグループに分けました(図1)。 ステップ1では、シャッフルランチと他の予定が重複しないように、76名の参加者を5つの曜日グループに振り分けました。ステップ2では、会社での関わりが小さくなるように、曜日グループを4人ずつのランチグループに分けました。 図1：シャッフルランチのグループ分けの方法 ステップ1：参加者の日付の割り振り 弊社では社員の予定をGoogleカレンダーで管理しています。GoogleカレンダーのAPIを使用することで、各参加者のカレンダーが取得でき、各曜日のランチタイムが空いているかどうかがわかります。 76名の参加者の各曜日グループへの振り分けは最大2部マッチング問題の一種であり、以下のようにして 最大フロー問題 （ソースからシンクにどれだけ水を流せるか計算する問題）に帰着され、Dinicのアルゴリズムを使って解くことができます。 まず、ソースから各参加者に容量1の辺、各参加者からランチに行ける曜日に容量1の辺を張ります。続いて、各曜日からシンクへ容量16の辺を張ります(図2)。参加者の割り振りは、ソースからシンクへの流量、即ちランチに参加できる人の人数を最大化するような流れを計算することで得られます。 Dinicのアルゴリズムは、次のような3つのステップからなります。 参加者を参加可能な日に順に埋めていく。 予定の調整が出来ない人が来た場合、予定の調整が出来る人を別の日に移す。 2の処理を全員が枠に入れるか、枠に入れない人がいなくなるまで繰り返す。 終了時点での、各参加者から曜日への辺で正のフローがある辺を探すことで「誰がどの曜日に参加するか」を求めることができます。 図2：各参加者の曜日グループへの割り振りを、最大フロー問題として扱うためのグラフ構造。 (参加者から曜日グループへの矢印は容量1の辺を表します) ステップ2：曜日グループ内の参加者の組み合わせ 続いて、16名(12名)の曜日グループを、「参加者間の会社での関わりが小さくなるように」4人ずつのグループに分けます。 シャッフルランチの振り分けでは、社員間の「会社での関わり」の指標として、「Slackで共通のチャンネルに加入している数」を用いることにしました。これは、会社での関わりが薄い2人の社員は共通で加入しているSlackチャンネルの数が少ないと考えられるからです。また、Slackのチャンネルの情報を使用することは、指標がリアルタイムで更新されるというメリットもあります。 ステップ2.1：Slackからの情報取得 Slackからの情報取得は3つのステップからなります。 まず、Slackの2つのAPIのメソッド、 channels.list と users.info を使用し、チャンネル一覧と全メンバーの情報（IDと名前）を取得します。 続いて、各チャンネルに対してメソッド channels.info を使用し、各チャンネルのメンバーのIDを取得します。 そして、取得した情報を組み合わて、誰がどのチャンネルに入っているかを求め、任意の2人の参加者間の共通のチャンネルの数を計算します。 以上の操作で、図3(a)のような社員間の関わりを点数化したような図が出来上がります（説明を簡単にするため、曜日グループのメンバーが6人で、これを3+3のグループに分けるような場合を考えています）。 ステップ2.2：グループ分けの最適化 最後に、最適なグループ分けの計算をします。あるグループ分けのコストを、グループ内の共通のチャンネル数の合計の全グループに対する総和として定義します。このコストが最小になるようなグループ分けが関わりの薄い社員同士のグループ分けになっていると期待されます。 例えば、図3(b)のグループ分け(A-E-FとB-C-D)の点数は(14 + 5 + 7) + (20 + 19 + 5) = 70でコストが高く、会社での関わりの深いメンバー同士でグループ分けがされています。 一方、図3(c)のグループ分け(A-B-DとC-E-F)の点数は(5 + 5 + 3) + (1 + 5 + 8) = 27でコストが低く、会社での関わりの薄いメンバー同士でグループ分けができていることがわかります。 コストの最小化には、ランダムサンプリングと山登り法を組み合わせた方法を使用しました。これはランダムに生成されたグループ分けから始めて山登り法により局所最適解を求め、局所最適解のうち最もコストの低いグループ分けを選び出すものです。 これにより、シャッフルランチの醍醐味である組分けのランダム性を楽しみながらもコストの低いグループ分けを求めることが可能になります。 図3：曜日グループ内の参加者のグループ分け （数字は2者間の共通のチャンネルの数を表します） 開発について 開発は私を含む新卒1年目の社員2人と4年目の社員1人の合計3人で行われました。 全体の開発を、 Googleカレンダーからの予定の取得と参加者の曜日グループへの振り分け Slackからの情報の取得 グループ分けのコストの最小化 という3つのパートに分割し、1人1つ担当する形で進めました。 開発期間が2週間しかなく、通常業務と並行しての作業は難しいところもありましたが、並行作業により時間を短縮できたこととデータの受け渡し方法について3人の連携が取れていたことにより、無事シャッフルランチの開催日に開発を間に合わせることができました。 得られたグループ分けは参加者からも好評であり、「よくシャッフルされていた」「普段業務で関わることのない人と話すことができた」という感想をもらいました。 今後の課題 ただし、組分けのロジックについてはまだまだ改善が必要です。上記の方法ではコストの最小化を曜日グループの中でしか行っていませんが、曜日グループをまたいだ人の入れ替えを考えたほうがより全体のコストを最小化することができると期待されます。 また、今回のシャッフルランチでは会社での関わりの指標として共通のSlackチャンネルの「数」を使用しましたが、これは社員間の関係を点数化するうえで最適な指標とは言えません。 Slackのチャンネルには、会話量やメンバー数の大小で多種多様なものがあるもかかわらず、すべてのチャンネルの寄与を同等に扱ってしまっているからです。 各チャンネルに会話量やメンバー数に応じた重みづけをつけることで、より精密に社員間の関係を点数化する事ができると期待されます。 今後これらの課題を改善して、より良い制度にしていきたいです。

旅行プラットフォーム事業部の龍島です。今回は技術的な内容として、Swagger(OpenAPI)とnpmパッケージ周りのことについて書きます。 フォルシアではAPIを作成する際、案件によってはSwaggerを利用しています。その定義ファイルをいい感じに書ける環境をnpmパッケージを組み合わせて作ったよ。というお話です。 Swaggerとは？ SwaggerとはREST API 仕様を記述するフォーマットです（ 公式 ）。 このフォーマットで書くと何が嬉しいかというと、下記のようなことができます。 API 仕様書HTMLの自動生成 API サーバのスタブの自動生成 API クライアントのソースコード自動生成 Swaggerに準拠したフォーマットで記述することによって、定義ファイルを配布するだけで、利用者はスタブの作成やクライアントのラッパーを作成することができます。とても便利ですね。 課題 利用を始めた段階では、定義ファイル(以下swagger.yml)の執筆に Swagger Editor を利用していました。自動で文法チェックを行ってくれたり、右側に表示されるプレビューが即時に変更されたりすることはかなり便利でしたが、いくつか欠点もありました。 swagger.ymlを分割できない Swagger Editorはswagger.ymlが一つであることが前提とされています。しかしAPI仕様が複雑、膨大になるに連れて一つのyamlファイルでなく、複数に分割して管理がしたくなってきます。 お気に入りのエディタは使えない Swagger Editor自体かなり書きやすくは作られていますが、やはり使い慣れたエディタには敵いません。フォルシアではいろいろなエディタ(Vim, Emacs, Sublime, VSC ode, ...)のユーザがいるため、どんなエディタでも書けると嬉しいなと考えるようになりました。 解決策 swagger.ymlを分割する How to split a Swagger spec into smaller files こちらの記事を参考に、ファイル分割を可能にしました。JSON ReferenceというJSONで外部ファイルを参照できるようにする（まだドラフトの）機能があり、それを用いています。記事の著者が npmパッケージ も公開しているため、それをそのまま用いました。 内部的にはyamlファイルをパースしてjsonに変換した後に、 whitlockjc/json-refs というJSON Referenceを実行するライブラリで結合しているようです。 npmのwatchライブラリを用いて、分割したファイルのいずれかに変更があれば結合するスクリプトが走り、swagger.ymlが生成されるように設定しました。 好みのエディタで書く Swagger Editorを使わない場合、swagger.ymlからHTMLを作成できるツールが必要になります。標準で用意されている swagger-ui や bootprint-openapi などいろいろと選択肢はありますが、今回は見た目の良さを重視して ReDoc-cli を利用しました。これは好みだと思うので好みのものを選べば良いと思います。 swagger.yml分割の際と同様に、生成されたswagger.ymlの更新をwatchし、更新されると自動的にHTMLが生成されるよう設定しました。 ブラウザのオートリロード swagger.ymlを分割し、swagger.ymlからHTMLを作成できるようになりましたが、Swagger Editorで実現できていたリアルタイムプレビューが実現できていません。webpackで実現されている HMR などのように、ブラウザに手を触れること無く変更結果をみたいですよね。HTMLに更新があれば自動的にブラウザ側が更新される仕組みにできないかと考えました。 調べていると light-server というパッケージが目的に一致していそうでした。説明には下記のような記述があります。 A simple static http server Trigger browser reload if watched files change 重厚長大な仕組みは作りたくなかったため、シンプルで欲しい機能のあるlight-serverを利用することにしました。 package.jsonに下記のように書いておけば ./build/html 以下のhtmlファイルに変更があった場合にページを開いているブラウザが自動的にreloadされます。 "watch:html": "light-server -s ./build/html -p 4000 -w \"./build/html/**/*.html # # reload\"" これで完全に目標は達成されました！ まとめ Node.jsやnpm周りを触っていると本当にエコシステムが充実していて、やりたいと思うことは大体いくつかのパッケージを組み合わせれば可能になります。利用できるものは利用し、必要なものがなければ自分で作って公開することでよりエコシステムを充実させていければいいなと考えています。 フォルシアでは共により良いものを効率的に作っていけるエンジニアを募集しています！ 新卒の方は こちら 、 キャリアの方は こちら からご確認ください。

旅行プラットフォーム事業部の龍島です。今回は技術的な内容として、Swagger(OpenAPI)とnpmパッケージ周りのことについて書きます。 フォルシアではAPIを作成する際、案件によってはSwaggerを利用しています。その定義ファイルをいい感じに書ける環境をnpmパッケージを組み合わせて作ったよ。というお話です。 Swaggerとは？ SwaggerとはREST API仕様を記述するフォーマットです（公式）。 このフォーマットで書くと何が嬉しいかというと、下記のようなことができます。 API仕様書HTMLの自動生成 APIサーバのスタブの自動生成 APIクライアントのソース