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クライアントのソース

こんにちは。技術本部の川口です。このブログでも再三紹介していますが、フォルシアではRustでインメモリデータベースを書いています。 社内にRustの良さを啓蒙したい Rustが書けるエンジニアに来て欲しい という企みのもと、RustのLT会「Shinjuku.rs」を開催しています。 先日1月16日に、Shinjuku.rsの第二回を開催しました！ イベント詳細： https://forcia.connpass.com/event/110888/ 当日の様子 LTの前に、フォルシアのmatsumotoから、インメモリデータベースの紹介。300万点の商品データを使用したサンプルアプリのデモンストレーションでは、キーワード検索をしながらインタラクティブに商品群が切り替わる様子を紹介し、会場からは「はや！」「キーワード打ち終わる前に検索終わってない？」（先読み検索ではないのでそんなことはないのですが、それぐらい速く見えたということですね！）などの歓声が上がりました。 LTでは、Rust-jp（日本のRustコミュニティ）のマスターヨーダのみなさんが集結し、ハイレベルながらも分かりやすいLT会でした。Rust初心者にも優しい！ 発表スライド みなさんのスライドはこちらです。 RustでGPGPU | termoshttさん RustでGPGPUプログラミングをするためのフレームワークであるaccelについてご紹介いただきました。proc_macroを使用して、アセンブラコードをRustのコードに埋め込んでコンパイルするという仕組みがすごい。 ターミナル遊び | GolDDranksさん ターミナルのRAW_MODEを使用して、インタラクティブなゲームを作った際の学びをご共有いただきました。 void | κeenさん どんな型にもなれる発散型を使うと、ヴァリアントを持たないenumであるVoidが実装でき、面白い性質を持っているというお話でした。前日にLTを引き受けていただいたにもかかわらず面白いLTをしていただき本当にありがとうございました。 その式、値ですか？場所ですか？ | qnighyさん 値と場所を意識しながら書くと、書きやすくなるというお話でした。 スライドは公開されていませんが、下記のお二人にもLTをしていただきました。 RustでTDD | せいさん mockers , mockito の紹介とライブコーディングをしていただきました。 「Rust 超初心者が頑張って勉強するの巻」 | ieiriyukiさん Rust By Example を毎日写経する勉強法をご紹介いただきました。 みなさまLTありがとうございました！ 今後もやっていくぞ 参加者の方々や社員にとても好評なので、Shinjuku.rsは奇数月に定期開催していきたいと考えています。内容は変えずに1人10分のLT会として、人数も増やしすぎないことで、開催負荷をできるだけ下げて末永く続けていきます。 さっそく第三回の告知を出したのですが、一瞬で満員になってしまいました！すごい。。。 イベント詳細： https://forcia.connpass.com/event/117142/ Rustを書きたいエンジニア、大募集！ 散々宣伝していますが、フォルシアではRustを書きたいエンジニアを大募集しています！ キャリア採用情報： https://www.forcia.com/jobs/career/

FORCIAアドベントカレンダー2018 25日目の記事です。 技術本部の夏目です。アドベントカレンダー最終日の今回は、CTFについて記事を書きます。 「CTF」とは、「Capture The Flag」 の略称です。文字通りの意味では、相手陣地の旗を奪い合うゲームのことを指しますが、Wikipediaでは、 コンピュータセキュリティの分野におけるキャプチャー・ザ・フラッグは、コンピュータセキュリティ技術の競技である。 ことを意味します。 出典元： Wikipedia「キャプチャー・ザ・フラッグ」 問題の種別は多岐にわたり、幅広い情報通信技術に関する知識が求められ、またパズル的な要素もあり興味深いです。中でも「Web」の問題に関しては安全な Web アプリケーションを作る上での脆弱性対策とは逆のアプローチで参考になります（CTFの真髄は他の分野にある気もしますが...）。 CTFを作ってみる 回答するだけではなく、実際にCTFを作成してみました。 下記のWebアプリケーションから、フラグを見つけてください。 http://210.129.12.173/index.php フォーマットは "FORCIA{XXXXXXXXXXXXXXXXX}" です。 注意事項 http://210.129.12.173/ 以外にはアタックを仕掛けないでください。 ブルートフォースアタックは仕掛けないでください。 2019/01 を目処にサーバを停止し、取り下げます。 さいごに 作ってみての writeupは、後日、問題取り下げ後に追記予定です。 フォルシアからエンジニアの皆さまに贈るこの問題に、是非チャレンジしてみてください！ 良いクリスマスを！！

技術本部の羽間です。フォルシアでは、主に大手旅行会社の検索システムの開発をしています。旅行業界では、旅行商品の在庫・料金が目まぐるしく変動するため、データ鮮度がとても重要です。そこで、システム間のデータ連携バッチの処理時間を少しでも短くできないかということで、Zstandard（zstd）による改善を検討してみました。 zstdとは 2015年からFacebookに所属するYann Collet氏によって開発された可逆圧縮アルゴリズムで、2016年8月にBSDライセンスでオープンソースソフトウェアとして公開されています。 ポイントは、zip・gzip・zlib等で採用されている圧縮ア

FORCIAアドベントカレンダー2018 22日目の記事です。 技術本部の羽間です。フォルシアでは、主に大手旅行会社の検索システムの開発をしています。旅行業界では、旅行商品の在庫・料金が目まぐるしく変動するため、データ鮮度がとても重要です。そこで、システム間のデータ連携バッチの処理時間を少しでも短くできないかということで、Zstandard（zstd）による改善を検討してみました。 zstdとは 2015年からFacebookに所属するYann Collet氏によって開発された可逆圧縮アルゴリズムで、2016年8月にBSDライセンスでオープンソースソフトウェアとして公開されています。 ポイントは、zip・gzip・zlib等で採用されている圧縮アルゴリズム「Deflate」よりも圧縮展開速度・圧縮効率に優れているという点です。Deflateは圧縮展開速度・圧縮効率のバランスが良く、長らく速度・効率の両面で上回るものが現れていませんでした。 詳細は公式サイトに載っていますが、公式ベンチマーク（ https://facebook.github.io/zstd ）結果によると、 圧縮展開速度は2倍以上、圧縮効率も5％〜10％程度改善されていることがわかります。 インストール方法 2018年12月現在では、自分でmakeせずともdpkg・apt, rpm・yumでzstdがサポートされています。 Ubuntu 18.04の場合 apt install zstd CentOS7 の場合 yum install zstd # epelレポジトリが有効になっていない場合は以下手順で有効にしてください。 #レポジトリの状態を確認 yum repolist all # epelレポジトリのインストール yum install epel-release # epelレポジトリを有効化 yum-config-manager --enable epel 基本的な使い方 圧縮 $ zstd fileName # => fileName.zst が生成されます # アーカイブもしたい場合 $ tar -cf dirName.tar.zst --use-compress-program=zstd dirName # もしくは $ tar -c dirName | zstd > dirName.tar.zst ※圧縮速度よりも、圧縮効率に重きを置きたい場合は、圧縮レベル1-22(デフォルト:3)を指定することも可能です。 複数コアで圧縮 # 4コアマルチスレッドで圧縮したい場合 $ pzstd fileName -p 4 # アーカイブもしたい場合 $ tar -cf dirName.tar.zst --use-compress-program="pzstd -p 4" dirName # もしくは $ tar -c dirName | pzstd -p 4 > dirName.tar.zst 解凍 $ zstd -d fileName.zst # 展開もしたい場合 $ tar -xf dirName.tar.zst --use-compress-program=zstd # もしくは $ zstd -dc dirName.tar.zst |tar -x 複数コアで解凍 # 4コアマルチスレッドで解凍したい場合 $ pzstd -d fileName.zst -p 4 # 展開したい場合 $ tar -xf dirName.tar.zst --use-compress-program="pzstd -p 4" # もしくは $ pzstd -dc -p 4 dirName.tar.zst |tar -x 検証してみた pzstd vs pigz 私が担当しているアプリのバッチ処理の一部にpigz(Parallel gzip)で複数のファイルを圧縮し、送信する処理があります。そのケースを想定して、185ファイル、計9124MBのtsvを圧縮・展開した場合で、pzstdとどのくらい性能に差異があるか簡易な検証をしてみました。 結果は次の通りです。 圧縮 解凍 処理時間、CPU使用率、ファイルサイズ、いずれもzstdが優れた結果となりました。ファイルサイズが小さければ、サーバー間で通信する際に有利ですし、処理時間、CPU使用率が低ければ、リアルタイムでの圧縮処理に応用しやすく、有用ですね。 また、解凍処理では思ったように差が現れませんでしたが、CPUのiowaitが高かったことから推測するに検証環境のディスクI/Oがボトルネックとなってしまっていたようでした。高性能なディスクを使用して検証を行えば、差がでるものと思います。 さいごに pigz、gzipの代替として、zstdを導入することで圧縮展開処理時間・圧縮効率の改善が見込めると分かりました。今後はバッチ処理への組み込みを進める予定です。簡単に導入できて、効果も見込めますので皆さんも検討されてみてはいかがでしょうか。本記事が少しでも皆さんの参考になれば幸いです。

FORCIAアドベントカレンダー2018 19日目の記事です。 技術本部の武田です。今回の記事では、レビューフローの一部を自動化し効率化するツールを、 TypeScript を使って作成する方法をご紹介します。フォルシアではGitのリポジトリ管理に GitLab を利用しています。社内のリポジトリには大きく分けて次の2種類があります。 各プロジェクト毎のリポジトリ 社内共通ライブラリ、ツール類のリポジトリ このうち、社内共通で利用するライブラリ、ツール類のリポジトリを改修する場合は以下のようなレビューフローがあります。 改修をした人（レビュイ）は Merge Request (GithubでいうPull Request)を作成する レビュアを2人選定 レビュイ、レビュア間でコードレビュー 完了後、リポジトリ管理者にレビュー完了を連絡 マージ 今回はマージリクエストの状態をチェックして、レビュアを選定する部分を自動化してみます。 今回作成するツールの処理の流れ 以下のような処理フローにしました。 assignee (レビュア) が設定されていない Merge Request の一覧を取得 GitLab のユーザ一覧を取得し、ランダムに assignee を選出 Merge Request の assignee を選出したユーザに設定 Slack に通知 GitLab API を利用する GitLab では様々な API が用意されています。 今回は、以下の3つを利用します。 ユーザの一覧を取得する Users API プロジェクトの情報を取得する Projects API Merge Resuest の情報を取得や assignee を変更するために Merge requests API 直接APIを実行しても問題なさそうですが、GitLab の API を wrap してくれた npm package があったのでこちらを利用してみました。 ユーザの一覧、および assignee が設定されていない Merge Request は以下のように取得できました。 // active なユーザを取得する const activeUsers = await api.Users.all({ active: true }); 今回は特定のプロジェクトにおける Merge Request に絞るため、プロジェクトの ID を取得します。 const projects = await api.Projects.search("プロジェクト名"); const targetProject = projects.find( (project: any) => project.namespace.name === "グループ名" && project.name === "プロジェクト名" ); const projectId = targetProject.id; 対象のプロジェクトの Merge Requests のうち assignee の設定がないものは以下のように取得できます。 // opened の Merge Requests のうち assignee の設定がないものを取得する const unassignedMergeRequests = await api.MergeRequests.all({ projectId, state: "opened", assignee_id: 0 }); 上記で取得した Merge Requests に対してランダムにユーザを設定する場合は次のようにできます。 unassignedMergeRequests.forEach(async (mergeRequestInfo: any) => { // ランダムにユーザを選出 const randomUser = activeUsers[Math.floor(Math.random() * activeUsers.length)]; // 対象の Merge Request の iid を取得 const mergeRequestIid = mergeRequestInfo.iid; // 対象の Merge Request を編集し、assignee をランダムに選出したユーザに変更 await api.MergeRequests.edit(projectId, mergeRequestIid, { assignee_id: randomUser.id }); }); 非常に簡単にユーザの一覧取得、assignee の設定されていない Merge Request の取得、assignee の設定ができました。GitLab の API を利用して、色々な業務改善ができそうです。 Slack に通知する assignee がこのツールで設定された場合に Slack の Incoming Webhook を利用して通知するようにしてみました。こちらも簡単に実装できます。 const payload = { fallback: `レビュー依頼: ${mergeRequestTitle}`, pretext: `プロジェクト名: <${projectUrl}|${projectName}>`, color: "good", fields: [ { title: "レビュー依頼", value: `<@${assignee}> <${mergeRequestUrl}|${mergeRequestTitle}>のレビューをお願いします` } ] }; const resp = await fetch(webhookUrl, { method: "post", body: `${JSON.stringify(payload)}` }); const resultText = await resp.text(); 以下が通知例です。 さいごに 非常に簡単に GitLab API を利用して便利なツールを作成することができました。今回はランダムにユーザを選出しましたが、どのユーザが適切かを判別するアルゴリズムを導入するのも良さそうです。 他にも 一定期間動きのないチケットを通知する thumbs up sign が2人以上から付いていたら「マージできます」とリポジトリ管理者に通知する などなど便利そうな機能がたくさん思い浮かびます。日々改善を加えて業務効率をアップしてくれるツールに仕上げていきたいです。 フォルシアではこうした業務効率の改善に興味のあるエンジニアも募集しています。お気軽にご連絡いただければと思います。 エントリーをご希望の方： 採用応募フォーム 採用に関するご質問・面談をご希望の方： 採用お問い合わせフォーム

QiitaのAnsible Advent Calendar 2018 12日目の記事です。 技術本部の西山です。FORCIAでは少数精鋭で顧客のサービスを担当するため、フルスタックエンジニアとしての活躍が求められます。私自身もWebエンジニアですが、インフラ寄りも積極的にキャッチアップしており、最近ではAnsibleやServerspecを利用してのサーバ構築自動化プロジェクトにも従事していました。 今回は、Ansibleのplaybookを健全化するためにAnsible-lintを導入した話を紹介します。 導入の背景 FORCIAではサーバ構築時にAnsibleを利用しており、現在では下記の様にAnsibleのplaybookが肥大化してきています。 [forcia@localhost]$ pwd /data/git-repos/configuration ### repository root [forcia@localhost]$ find ./ -type f -name "*.yml" -exec wc -l {} \; | awk '{sum+=$1} END {print sum}' 5465 ### playbookの合計行数 今後のAnsibleの実装を進めていくに当たり、playbookのlinterである Ansible-lint を導入してコードの秩序を保っていきたいと思います。 導入手順 Ansible-lintのinstall Ansible-lintの document を参照してインストールする。 依存モジュールを明確にするため、requirements.txtを利用 ansible-lint==3.5.1 pipでinstall [forcia@localhost]$ pip3 install -r requirements.txt configuration fileの用意 document を参照して設定ファイル(.ansible-lint)を用意する。 .ansible-lintの中身 exclude_paths: - ./common_script/ - ./ansible/bin/ - ./ansible/module/ - ./ansible/apps/ parseable: true quiet: true skip_list: - skip_this_tag # skipするタグを指定 - skip_this_id # skipするidを指定 use_default_rules: true verbosity: 1 ※設定項目の意味は こちら を参照 CLIで実際に動かしてみる [forcia@localhost]$ pip3 install -r requirements.txt 動きました。 [forcia@localhost]$ ansible-lint ./ansible/**/*.yml -p | wc -l 35 35個のエラー。思ったよりは多くないですがlinterを導入した甲斐がありました。 CIの設定 precommitの設定 フォルシアでは、nodeを触る機会が多いので、package.jsonに npm run precommit の定義を書くことが多いですが、今回はAnsibleなので、Pythonのお作法に則ります。 ※設定方法は 公式 を参照 requirements.txtにpre-commitモジュールを追加 ansible-lint==3.5.1 pre-commit==1.12.0 pre-commitモジュールをインストール [forcia@localhost]$ pip install -r requirements.txt .pre-commit-config.yamlの作成 - repo: https://github.com/ansible/ansible-lint.git rev: v3.5.1 hooks: - id: ansible-lint files: \.(yaml|yml)$ pre-commitの設定内容をgitに反映 [forcia@localhost]$ pre-commit install 以上でcommitの度にlinterが走るようになりました。 Ansible-lintに触れて感じたこと Ansible-lintを導入してみて良かった点は playbookの記述方法をルール化できたことです。今回は下記のエラーが見つかり、修正できました。 [forcia@localhost]$ ansible-lint ./ansible/**/*.yml -p | awk '{ print $2 }' | sort | uniq -c 14 [E201] ### Trailing whitespace 3 [E202] ### Octal file permissions must contain leading zero 5 [E301] ### Commands should not change things if nothing needs doing 10 [E305] ### Use shell only when shell functionality is required 3 [E502] ### All tasks should be named E202: permission設定する場合は755でなく0755のように4桁で書きなさいなど、yamlのlinterでは気づけない、playbook特有の事項も指摘してくれるので大変使い勝手が良いと感じました。 一方、下記を課題に感じたのでcontributionしていけたらと思っています。 Ansible-lintにエラー箇所を自動修正してくれるformatter機能があると修正が楽で嬉しい 実行時間が長く(設定方法が悪いのかもしれませんが)、linter実行速度に改善の余地がありそう さいごに 今後は、今回対応できなかった下記の点について、順次対応を進めていきたいと考えています。 社内jenkinsサーバでもlinterをチェックするjobの設定する こちらを参考に、独自ruleを作成する documentのreadmeに一部記述が古い箇所があったのでプルリクを出す(早速contributionチャンス！) Ansibleのlinterを検討している方の参考になれば幸いです。

Qiitaのkaggle Advent Calendar 2018 10日目の記事です。 技術本部の原です。フォルシアでは、Google Hotel Ads のデータ配信システムの開発・運用や、Spook の検索ログなどのデータ分析を行っています。 データ分析においては、さまざまな試行錯誤が必要です。そのときには、1行から数行のプログラムを実行することと、結果を確認することを繰り返して、対話的にデータ処理を行うと効率良くデータ分析ができます。 Jupyter Notebook は、そのような対話的なデータの処理に加え、その実行過程を自らの注釈を加えながら記録ができる、データ分析には大

Qiitaのkaggle Advent Calendar 2018 10日目の記事です。 技術本部の原です。フォルシアでは、Google Hotel Ads のデータ配信システムの開発・運用や、Spook の検索ログなどのデータ分析を行っています。 データ分析においては、さまざまな試行錯誤が必要です。そのときには、1行から数行のプログラムを実行することと、結果を確認することを繰り返して、対話的にデータ処理を行うと効率良くデータ分析ができます。 Jupyter Notebook は、そのような対話的なデータの処理に加え、その実行過程を自らの注釈を加えながら記録ができる、データ分析には大変便利なツールです。対話的分析による効率の良さに加え、分析の再現性の確保、他人へのプレゼンテーションも同時に実現します。筆者もJupyter Notebook 、そしてその後継であるJupyter Lab が無くては何も仕事にならないくらい愛用しています。 この記事では、Jupyter Notebook、 Jupyter Lab、そして、作業記録や再現性の確保には欠かせないNotebook ファイルのバージョン管理について紹介します。 Jupyter とは python の対話的コンソールとして ipython があります。その ipython に、Markdown による注釈を追記できるようにしたのが ipython Notebook、さらに、 python 以外の言語 で利用できるように拡張されたのが、Jupyter Notebook です。Notebook を自分で分析をした記録として作成するのはもちろんのこと、それを他の人と共有することも容易で、github でも Notebook の共有ができるようになっています。 また、データ分析に限らず、python のコード実行を対話的に行い、その結果をスクリプトとして保存することで、効率よくスクリプトの開発を行うことができます。 Jupyter Notebook を使ってみよう ご自分のマシンにインストールしなくても、お試しであれば http://jupyter.org/try から使ってみることができます。 上のURLのページに現れる"Try Jupyter with Python" をクリックして開くと以下のようなページが現れます。 これが Jupyter Notebook の画面です。このお試しページでは、3つのセルにわたってMarkdownでインストール方法が書かれていますが、気に入ったらそのマニュアルにしたがって、ご自分のマシンにインストールをしてみてください。 一番下のセルをフォーカスした状態（"You can also..." から始まるブロックをクリックする）で、 "b" を押せば、新しいセルが下に追加されます（上に追加したい場合は "a"）。 出てきたセルの中に、"1+1"と入力して Shift+Enter を押してみます。そうすると、下に計算結果である"2" が表示されましたね。 データ分析においては最初に大きなデータを読み込むことが多いですが、分析のためのコードをスクリプトで記述して書き換えたたびに毎回実行すると、そのデータの読み込みに時間がかかってしまい、分析作業が非効率になってしまいます。Jupyter Notebook を使って対話的に分析すれば、データの読み込みは1回で済みますし、そのデータを用いたいろいろな試行錯誤を、データをそのたびに読み込むことなく実行できて便利です。 Jupyter Lab 最近になって、Jupyter Notebook の後継である Jupyter Lab が広まりつつあります。Jupyter Notebook の機能に、ファイルブラウザ、コンソール、テキストエディタ、ターミナルなどの機能を付加したものです。まさに、オールインワンの環境です。今後、開発の中心は Jupyter Notebook から Jupyter Lab に移っていく予定です。 Jupyter Lab も http://jupyter.org/try の "Try JupyterLab"をクリックすることで試用することが出来ます。 これが画面の一例です（上の試用ページにおいて、"Run"-> "Run All Cells"を実行すると、計算が実行されてこのページのような表記になります）。 Jupyter Notebook と比べると、 左側にファイルブラウザーをはじめとしたメニューがある notebook の上部にタブがあって、複数のファイルを同時に開ける などに気がつきます。 いろいろなデモのファイルがあるので、触ってみるとどんなことができるのか、理解が進むのではないかと思います。 Jupyter Lab の便利なところ 複数ファイルをタブで開ける! データ分析をするときには、いろいろなファイルを開きながら作業を行うことも多いです。そのときに、Jupyter Lab では、複数ファイルを同時に開いて、それをタブで切り替えることが出来ます。また、ファイルを選択するときには、左側メニューにあるファイルブラウザが便利です。 セルの順序の入れ替えがマウスのドラッグでできる！ これは画期的！下の方で下書きを兼ねて試行錯誤して、固まったコードを簡単に適切な場所に移動することが出来ます。 Jupyter Lab でハマってしまうところ コピー & ペースト マウスでコピー＆ペーストをしたい部分を選択しておいて Ctrl + C, Ctrl + Vとやりたいところですが、できないようです。ならばと、右クリックでブラウザのメニューからコピー & ペーストをしてやろうと思うのですが、右クリックすると Jupyter Lab のメニュー(セルの操作など)が出てきてしまい、コピー & ペーストができません。ブラウザの右クリックメニューを出すには、Shift を押しながら右クリックをします（普段はマウスを使わずにキーボードで操作をしている身としては面倒ではありますが）。 なお、"Setting"メニューの中に "Text Editor Keybind" という項目があり、"Sublime", "vi", "emacs" などが選択できるようになっています。しかし、これはNotebookではなく、テキストエディタ機能でのキーバインドの選択になっており、Notebook のキーバインドには影響を与えないようです。 覚えておくと便利なキーバインド 編集モード(カーソルがセルの中にあるとき) Shift-Enter: セルのコードを実行する Tab: 変数などの補完 Shift-Tab: 関数などのヘルプの表示 Tab: Esc: 編集モードから抜け出す 編集モード(カーソルがセルの中にあるとき) Shift-Enter: セルのコードを実行する Tab: 変数などの補完 Shift-Tab: 関数などのヘルプの表示 Tab: Esc: 編集モードから抜け出す 編集モード以外（セルがフォーカスされている場合） a:上に新しいセルを挿入する b:下に新しいセルを挿入する m: セルを Markdown モードに切り替える dd: セルを削除する Enter: 選択されているセルの編集モードに入る Notebook ファイルのバージョン管理 分析作業を記録し、再現性を確保するためには、Notebook ファイルのバージョン管理は必須だと筆者は考えています。Jupyter Notebook や Jupyter Lab で生成されるNotebook ファイル (拡張子: .ipynb、以下、「ipynb ファイル」という)は、JSONで記述されたテキストファイルですので、git などでバージョン管理が出来ますが、後述の通り、Notebook 上での変更と ipynb ファイルのJSONで記述されたファイルの変更の対応が直感的ではないことが多く、工夫が必要です。 ここでは、ipynb ファイルのバージョン管理に便利な Extensions をいくつか紹介します。 Extension とは？ Jupyter Notebook や Jupyter Lab は、拡張機能(Extension)をプラグインすることが出来ます。 https://github.com/topics/jupyterlab-extension には数多くの Jupyter Notebook/Lab のExtension が一覧になっています(Jupyter Notebook 用の Extension の多くは Jupyter Lab でもそのまま使えます)。 バージョン管理に便利な Extension jupyterlab-git jupyterlab-git は、git のGUI操作盤を画面左側のメニューに追加します。 この Extension は、様々なメニューが表示されるようになった Jupyter Lab ならではのものです。 インストール方法は、リンク先のページを参照してください。簡単にできます。 インストールが終わってJupyter Lab を再起動すると、左側メニューに git のロゴ で表示されるタブが追加されます。ここに、staged (git add されたファイル)、Changed (git の管理下にあるが git add して staging されていないファイル)、Untracked (git の管理下にないファイル)が表示されます。各ファイルの名前の先頭にマウスをあわせると表示される上矢印がついたボタンをクリックすると git add することが出来ます。 git add されたファイルを git commit するには、change log をテキストボックスに記入して✓ボタンをクリックします。 git そのものの操作は、Terminal でやったほうが早いという方はそれでもいいでしょうが、このExtensionを使うことで、git 管理がされていないファイルや、変更が加えられたのにコミットされていないファイルがすぐにわかるようになることがポイントです（これはすごく重要！）。 nbdime すでに述べたように、ipynb ファイルは JSON で記述されていますが、ユーザーが入力したコードや出力結果だけでなく、さまざまな属性が記録されています。 たとえば、上の図で、一番上のセルに"1+2"となっていたものを図のように"1+3"に変更したときの ipynb ファイルの git diff による差分は以下のようになります。 $ git diff diff --git a/test1.ipynb b/test1.ipynb index d1a3dbe..6c021ff 100644 --- a/test1.ipynb +++ b/test1.ipynb @@ -2,22 +2,22 @@ "cells": [ { "cell_type": "code", - "execution_count": 2, + "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ - "3" + "4" ] }, - "execution_count": 2, + "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "1+2" + "1+3" ] }, { コード本体の他にも差分が生じることが分かります。これだと、一見、何が変わったのかよくわかりません。 そこで、 nbdime をインストールします（インストール方法はリンク先を参照）。これをインストールすると、いくつかのコマンドがインストールされます。その一つ、 nbdiff をipynb ファイルが置かれているディレクトリ上でターミナルから実行すると、 $ nbdiff nbdiff test1.ipynb (HEAD) test1.ipynb --- test1.ipynb (HEAD) (no timestamp) +++ test1.ipynb 2018-12-02 22:07:46.881431 ## replaced /cells/0/execution_count: - 2 + 3 ## modified /cells/0/outputs/0/data/text/plain: - 3 + 4 ## replaced /cells/0/outputs/0/execution_count: - 2 + 3 ## modified /cells/0/source: - 1+2 + 1+3 という差分表示が得られます。これは git diff の表示を編集したものになっています。前よりは見やすくなったものの、まだわかりづらいかもしれません。 そこで、 nbdiff-web をターミナルで実行すると、Webブラウザーに次のようなページが表示されます。 この表示なら、どこが変更になったのかが一目瞭然です。ipynb ファイルの差分表示にはこの Extension は欠かせません。 なお、 $ nbdime config-git --enable --global を実行すると、ipynb ファイルに対する git diff を nbdiff によるものに置き換えることも出来ます。 jupytext 少し別のアプローチとしては、jupytext を活用する方法があります。 jupytext を用いると、ipynb ファイルを保存する際に Markdown や出力を取り去ったスクリプト(python なら .py ファイル)を同時に出力することができます。その機能を使ってpy ファイルを自動出力させて、オリジナルの ipynb ファイルと py ファイルの両方を git でバージョン管理をすれば、py の履歴を見ることでユーザーが作成した入力コードの履歴を簡単に追うことが出来ます。 この jupytext は、別の用途でも非常に便利に使えます。このツールの最大の特徴は ipynb ファイルとこのツールによって変換されたファイルが双方向に連動していること。jupytertext が出力した py ファイルをお好みのエディタで編集した後に、jupyter 側の ipynb ファイルを再読み込みすれば、py に加えた修正が ipynb ファイルにも反映されます。ですので、ipynb ファイルの代わりに同時出力される py ファイルの編集（リファクタリングなど）を使い慣れた別のエディタで行い、それを ipynb ファイルに戻すことも可能です。 作者による デモの動画 も参考になるかもしれません（英語による講演ですが）。ぜひ使ってみてください。 さいごに データ分析には欠かせない Jupyter Notebook や Jupyter Lab 。データ分析だけでなく、スクリプトの開発にも便利に使えます。まずは上のデモページから体験してみてください。また、Jupyter Notebook をすでに使っている方は、ぜひ、Jupyter Lab も試してみてください。より便利に使える事が実感していただけると思います。 筆者は git が大好きで、Notebook ファイルのバージョン管理にもつかっていますが、Jupyter Notebook を使い始めたばかりの時には、差分を見てもNotebookの何が変わっているのかがよくわからないので、Notebook ファイルについては git はただのバップアップツールになっていました。しかし、ここに書いたような手法を見つけてからは、Notebook ファイルのバージョン管理も不自由なく行えています。また、jupytertext はバージョン管理だけでなく、使いなればエディタを活用しながら Jupyter も使える優れものです(Emacs からは離れられない筆者にとっては、Emacs も Jupyter Lab も活用できる革命的なExtensionでした)。 この記事がこれからJupyter を使う方、また、使い始めている方への助けになれば幸いです。

FORCIAアドベントカレンダー2018 の9日目の記事です。 技術本部の高橋です。これまで何度も解いてみようと思っては跳ね返され続けたこのDP、いわゆるナップサック問題に、緑コーダーの私が改めて挑戦してみました。 緑コーダーとは、 Atcoder でレーティングが800～1199の人です。ちょっと競プロやってますというレベルで、AtCoderのC問題は解けるけど、D問題が解けないくらいの人だろうと自分では考えています。 すでに、動的計画法 / ナップサック問題の解説は多くありますが、この記事が少しでも私と同じような人の役に立てば幸いです。 DP？ナップサック問題？ DPとは 突然ですが、「DP」と言われて何のことだか分かりますか？ データプロセッサー、ダブルプレー...色々なものの略称として使われるようですが、フォルシアでは、主に次の3つの意味で使われることが多いです。 Dynamic Package（ダイナミックパッケージ） 旅行商品の一つ。飛行機や新幹線などの交通手段とホテルなどの宿泊施設を利用者が自由に組み合わせて旅行プランを作成できる。 Dynamic Pricing（ダイナミックプライシング） 需要と供給の状況に応じて価格を変動させる仕組み。売上の向上と潜在需要の創出を実現し需給をコントロールする。 Dynamic Programming（動的計画法） 「動的計画法」と呼ばれるアルゴリズムの一つ。問題を複数の部分問題に分割し、部分問題の計算結果を利用して全体の最適化をはかる。 今回ご紹介するのは、3つ目にご紹介した Dynamic Programming（動的計画法） 。 (01)ナップサック問題とは DPを使って解く典型的な問題の一つです。初心者がまず詰まる問題で、例えが古いかもしれませんが、高校数学のベクトルのような存在だと自分は考えています。例に漏れず、私も自分で実装しようとすると手が止まってしまい、何度解説を見てもしっくりきませんでした。 ナップサック問題概要 DPを理解するために 典型的な01ナップサック問題の設定だと、なんだかわくわくしないので、今回は、予算1000円でサイゼリヤに行って、同じものを頼まずに摂取できる最大のカロリーを求めるという問題にしてみました。メニューは自分がサイゼリヤに行ったらよく食べるものをチョイスしました。 メニュー [品名], [カロリー], [値段], [塩分] やわらかチキンのサラダ,134,299,1.2 半熟卵とポークのサラダ,433,599,2.3 ほうれん草のソテー,80,189,1.0 フレッシュチーズとトマトのサラダ,169,299,1.1 プロシュート(パルマ産熟成生ハム),225,399,2.7 辛味チキン,333,299,2.3 チョリソー(辛味ソーセージ),380,399,2.5 マルゲリータピザ,568,399,2.5 パンチェッタのピザ,646,399,2.4 アラビアータ,591,399,3.7 ミートソースボロニア風,538,399,3.6 ミラノ風ドリア,519,299,2.7 半熟卵のミラノ風ドリア,609,368,2.9 柔らかチキンのチーズ焼き,549,499,2.0 ミルクジェラート,100,199,0.1 イタリアンプリン,216,249,0.1 ※塩分はなにか広げられるかと思って入れてみましたが、今回はそこまで手が出なかったので全く使っていません。 まずは全探索から始めてみよう とは言ったものの、正直この全探索を作るのはなかなか難しかったです。次の2つが特に難しかった点です。 再帰でやるということを思い浮かばなかったら出来ない気がする 2^(メニューの数) 回for文を回して、bitでやるとかなのでしょうか... 再帰でやるとなっても、引数をどうするのか、どういう関数にするのかが難しい カロリーは引数として取らなくていいのか n品目まで食べたとき、なのか、n品目以降なのか 全探索は再帰を使うというイメージがあったので、色々見ながらなんとか作ってみました。 今回は、n=0から始めて、n+1品目以降のメニューだけで選んだときに得られるカロリーを返す関数として考えてみました。プログラムは以下のとおりです。 コード # ファイルの読み込み with open('menu.csv') as fi: menu = fi.readlines() for i in range(len(menu)): menu[i] = menu[i].strip().split(",") for j in range(1,3): menu[i][j] = int(menu[i][j]) menu[i][3] = float(menu[i][3]) yosan = 1000 # n+1品目以降のメニューで得られる最大のカロリーを求める関数 # 1品目はmenu[0]なので日本語とずれている def zentansaku(n,ryoukin): # もう料理が残っていなければカロリーは得られない if n == len(menu): return 0 # menu[n]の料金が予算内であれば、menu[n]を食べた場合と食べなかった場合を確かめる if ryoukin + menu[n][2] <= yosan: taberu = zentansaku(n + 1, ryoukin + menu[n][2]) + menu[n][1] # [1]はカロリー [2]は料金 tabenai = zentansaku(n + 1, ryoukin) if taberu >= tabenai: return taberu else: return tabenai else: tabenai = zentansaku(n + 1, ryoukin) return tabenai print(zentansaku(0,0)) # 1品目から0円使った状態での最大のカロリーを求める 出力結果 1498 やりました、再帰を使っての全探索は出来ました。そのメニューを食べるか食べないかで、maxを使わずに、いちいち`taberu`, `tabenai`に代入したのは、それぞれの値が何を指すのか一旦整理してみようと思ったり、日本語に近づけてみようと思ったという意図があります。 続いて、この全探索を高速化するメモ化。これはかなり直感的な手法で、すぐに理解できたので実装してみました。おまけに、再帰関数がどのように自分を呼び出していくのか、プログラムのどこを辿っていくのかを見てみようと思って色々出力してみました。これ以下のコードではファイル読み込みの部分は省略します。 コード # (ファイル読み込み部分は省略) yosan = 1000 # メモ用の配列 memo = [[-1 for i in range(yosan+1)] for j in range(len(menu)+1)] def zentansaku(n,ryoukin): indent = " " * (n + 1) # メモされてたらその値を利用する if memo[n][ryoukin] != -1: return memo[n][ryoukin] if n == len(menu) - 1: return 0 if ryoukin + menu[n][2] <= yosan: print(indent,"| 食べてみる",n,ryoukin,menu[n][2]) taberu = zentansaku(n + 1, ryoukin + menu[n][2]) + menu[n][1] print(indent,"| 食べない",n,ryoukin) tabenai = zentansaku(n + 1, ryoukin) if taberu >= tabenai: # メモに記録 memo[n][ryoukin] = taberu print(indent,"[b]",menu[n][0],"を食べよう！ ret:",taberu," / ",n,ryoukin,menu[n][2]) return taberu else: print(indent,"[!]",menu[n][0],"を食べないほうがたくさん食べれるようだ... ret:",tabenai, " / ", n,ryoukin,menu[n][2]) # メモに記録 memo[n][ryoukin] = tabenai return tabenai else: print(indent,"| 食べられない(お金がない)",n,ryoukin) tabenai = zentansaku(n + 1, ryoukin) # メモに記録 memo[n][ryoukin] = tabenai print(indent,"[x] お金がないので",menu[n][0],"は食べられない...ret:",tabenai," / ",n,ryoukin,menu[n][2]) return tabenai print(zentansaku(0,0)) 出力結果 | 食べてみる 0 0 299 | 食べてみる 1 299 599 | 食べられない(お金がない) 2 898 | 食べられない(お金がない) 3 898 | 食べられない(お金がない) 4 898 | 食べられない(お金がない) 5 898 | 食べられない(お金がない) 6 898 | 食べられない(お金がない) 7 898 | 食べられない(お金がない) 8 898 | 食べられない(お金がない) 9 898 | 食べられない(お金がない) 10 898 | 食べられない(お金がない) 11 898 | 食べられない(お金がない) 12 898 | 食べられない(お金がない) 13 898 | 食べられない(お金がない) 14 898 [x] お金がないので ミルクジェラート は食べられない...ret: 0 / 14 898 199 [x] お金がないので 柔らかチキンのチーズ焼き は食べられない...ret: 0 / 13 898 499 [x] お金がないので 半熟卵のミラノ風ドリア は食べられない...ret: 0 / 12 898 368 [x] お金がないので ミラノ風ドリア は食べられない...ret: 0 / 11 898 299 [x] お金がないので ミートソースボロニア風 は食べられない...ret: 0 / 10 898 399 [x] お金がないので アラビアータ は食べられない...ret: 0 / 9 898 399 [x] お金がないので パンチェッタのピザ は食べられない...ret: 0 / 8 898 399 [x] お金がないので マルゲリータピザ は食べられない...ret: 0 / 7 898 399 [x] お金がないので チョリソー(辛味ソーセージ) は食べられない...ret: 0 / 6 898 399 [x] お金がないので 辛味チキン は食べられない...ret: 0 / 5 898 299 [x] お金がないので プロシュート(パルマ産熟成生ハム) は食べられない...ret: 0 / 4 898 399 [x] お金がないので フレッシュチーズとトマトのサラダ は食べられない...ret: 0 / 3 898 299 [x] お金がないので ほうれん草のソテー は食べられない...ret: 0 / 2 898 189 | 食べない 1 299 | 食べてみる 2 299 189 | 食べてみる 3 488 299 | 食べられない(お金がない) 4 787 | 食べられない(お金がない) 5 787 | 食べられない(お金がない) 6 787 | 食べられない(お金がない) 7 787 --------------------(略)-------------------- [b] パンチェッタのピザ を食べよう！ ret: 1355 / 8 0 399 [!] マルゲリータピザ を食べないほうがたくさん食べれるようだ... ret: 1355 / 7 0 399 [!] チョリソー(辛味ソーセージ) を食べないほうがたくさん食べれるようだ... ret: 1355 / 6 0 399 [b] 辛味チキン を食べよう！ ret: 1498 / 5 0 299 [!] プロシュート(パルマ産熟成生ハム) を食べないほうがたくさん食べれるようだ... ret: 1498 / 4 0 399 [!] フレッシュチーズとトマトのサラダ を食べないほうがたくさん食べれるようだ... ret: 1498 / 3 0 299 [!] ほうれん草のソテー を食べないほうがたくさん食べれるようだ... ret: 1498 / 2 0 189 [!] 半熟卵とポークのサラダ を食べないほうがたくさん食べれるようだ... ret: 1498 / 1 0 599 [!] やわらかチキンのサラダ を食べないほうがたくさん食べれるようだ... ret: 1498 / 0 0 299 1498 やったー、ナップサック問題解けた！と思いましたが、今回の主目的はDPを理解することでした。正直全探索も色々見よう見まねで書いたのですが、慣れるまでは天下り的にとりあえずやってみて、まずは理解を深める。そのうえで落ち着いて考えて自分で納得できるようにしていこうと思いました。 ちゃんとDPで解いた DPについて勉強した私が思うDPの肝 ある状態が、その前の状態の組み合わせで表されるものであれば、その状態を漸化式にして表して、それをプログラムに落とし込めば、DPになる DPは再帰ではなくfor文を使って表を順番に埋めていくもの コード # (ファイル読み込み部分は省略) yosan = 1000 # dp[i][j] = i番目までの品を使って j円使った時の 最大カロリー # menuの添字と違ってややこしいのは、dp[0]を何も食べないときとするので、 # dp[i][j]のiと日本語のi番目が対応することである。 # くどいようであるが、i番目の品 = menu[i-1]である。 # ex: dp[3][500]は3つ目まで(=menuの0~2)の商品を使って、500円まで使える時の最大カロリーを指す dp = [[-1 for i in range(yosan + 1)] for j in range(len(menu) + 1)] for i in range(len(dp[0])): # 初期条件 / 0番目の商品までを使う = 何も食べられない = 何円使っても0カロリー dp[0][i] = 0 # menu[n]を使って、 price円使った時の最大カロリーを順番に求めていく for n in range(len(menu)): for price in range(yosan + 1): # tabeta = n-1までのmenuと, price - menu[n][2]円の状態から、 menu[n]を食べた場合 # tabenai = n-1までのmenuと, price円の状態 if price - menu[n][2] >= 0: tabeta = dp[n][price - menu[n][2]] + menu[n][1] tabenai = dp[n][price] if tabeta >= tabenai: dp[n + 1][price] = tabeta else: dp[n + 1][price] = tabenai # priceがそもそもmenu[n][2]よりも安かったら、menu[n]を食べるという選択肢はないので、1つ前のpriceをそのまま使うほかない else: dp[n + 1][price] = dp[n][price] # 求める答えはlen(menu)番目までの商品を使い、yosan円まで使える時の最大カロリー。 print(dp[len(menu)][yosan]) # dpのテーブルを出力してみる # 横にyosan個あると見づらいので、50円刻みで出力する temp = [] for i in range(0,yosan + 1,50): # :が書式指定を行うための記号(演算子?)、_が埋める文字、<が左埋め、数字が桁数 temp.append('{:_<4}'.format(i)) for a in dp: temp = [] for i in range(0,len(a),50): temp.append('{:>4}'.format(a[i])) # >は右埋め(^は中央寄せ) print(" ".join(temp)) 出力結果 確かに上のメモ化再帰と同じ答えが出力されました！dpの表もなんだかそれらしくなっていて達成感があります。 当初の疑問点と今の理解 [Q1] なんでありえないような料金までfor文を回さないといけないのか。例えば50円と100円のメニューしかなければ、49円の状態とか存在しないのでは？ [A1] それはそうだけど、無駄になるだけで、実害はない。逆に、予算やカロリーが大きいと、大きい表を作らないといけなくなるので厳しい。その場合はもしかしたら工夫する必要があるかもしれない。 [Q2] dpの表をそうするというのはどうやったら思い浮かぶのか。 [A2] 慣れなのではないか。 [Q3] ある問題に対して表の作り方は一通りしかないのか。 [A3] 恐らくそんなことはない。何なら、この問題でも上記よりいい表の作り方がある可能性はある。制約に応じて表の持ち方を工夫するということは求められるのかもしれない。 感想 結局、ナップサック問題というのは、 dp[i][j] をどう作るかというゲームなのでは、ということと、どうやって漸化式を作るか、ということにかかっているのではないかということに、改めて気づきました。(それが思いついたら解けるんだろうし、それが思いつかないんですよと言いたい。) しかしながら、今回、漸化式を思いついたらdpで問題が解けるようになったことは、一つ大きい収穫だと思っています。0-originと、日本語の～番目であったり、dpの添字とがなかなかうまく揃わなかったのが難しい/ミスが起きそうなポイントだなと思いました。前処理でうまく揃えて解くべきだったかもしれません。 あと、結局出力されたカロリーを取るには、何を食べればよいのかというのがわからないなと思っています。社内の競プロ強い人に聞いたら方法はあるようでしたが、今回は一旦ここまでとして、それについても考えていきたいなと思います。 今回は同じメニューを頼まないという縛りでしたが、同じメニューを頼むとしたらどうするのか、個数制限があったらどうなるのか、とか、「予算内で カロリー/円 が最大になるのは」というのは一番 カロリー/円 の高いものを頼むだけになりそうなので、重複無しでm品以上頼むときの、という制約条件を付けるとどうなるのか、とか色々解いてみたくなりました。 自分には一生理解出来ないものとしてDPを扱っていましたが、今回親しみが持てました。現に、調べる中で 最長共通部分列 という問題もDPを使うと知り、興味を持って調べました。問題を見たときはどうやってDPを使うのか思い浮かびませんでしたが、解説を見てハッとし、同時にその解説が分かるようになっていることに気づいて非常に嬉しくなりました。いつか、DPを使う問題を、これはDPで解く問題だ！と気づいて、AC取れることを夢見て、これからも競プロを頑張りたいと思います。