こんにちは。旅行プラットフォーム事業部エンジニアの谷井です。 早いもので、明日から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取れることを夢見て、これからも競プロを頑張りたいと思います。

FORCIA アドベントカレンダー2018 の8日目の記事です。 技術本部の乙村です。最近、 Prettier というフォーマッターがきてると聞いたので、触ってみました。「いま ESL int の設定に沿ってフォーマットをしているけど、Prettier 導入したらどうなるか試してみたい」と興味を持たれている方向けに、その特徴と導入の仕方を紹介します。 Prettier とは Prettier は以下の特徴を持つフォーマッターです。( https://prettier.io/ #What is Prettier? より抜粋) An opinionated code formatter ("opinionated" である) Supports many languages (多言語サポート) Integrates with most editors (多くのエディターとの統合が可能) Has few options (限られたオプション) 公式サイトにある説明のとおり、Prettier は JavaScript 専用のフォーマッターではなく、HTML、CSS 、Markdown など広いファイル種類をサポートする汎用のフォーマッターです。また、Visual Studio Code や Vim などのエディターと統合し、ファイル保存時に自動でフォーマットさせることも簡単にできます。 ただやはり最大の特徴は "opinionated" であることだと個人的には思っています。直訳では「独断的な」とか「自説を曲げない」という意味ですが、意訳すると「みんなフォーマット方針ってどういうものがいいと思う？自分はこれがいいと思う！だから従ってね」ってことです。もっと具体的にいうと「インデント？空白2つに決まってるだろ！タブとかないわー」ってことです。マッチョですね。 方針があらかじめ決まっているので、フォーマットスタイルを変更できる余地もあまりなく、これが「限られたオプション」の特徴に繋がります。例えば、ESLint はスタイルに関するオプション( Rules - Stylistic Issues ) だけで180 近くあるのに対して、Prettier のオプション ( Options · Prettier )は 18しかありません。 公式サイトの Why Prettier? には以下のように書かれています。 By far the biggest reason for adopting Prettier is to stop all the on-going debates over styles. (Prettier を採用する最大の理由は、スタイルに関する全ての議論を止めるためです） Prettier はフォーマットツールでありながら、「これでいいんじゃない」というフォーマット方針も与えてくれるところにその独自性があります。不自由なようにも見えますが、逆に言えば「こちらで細かく決めなくてもいい感じにフォーマットしてくれる」という魅力があります。 Prettier の導入 JavaScript のフォーマットを目的とした Prettier の導入方法について説明します。 Prettier はあくまでフォーマッターなので、ESLint でいう no-unused-vars (未使用の変数を許可しない）などのコード品質にかかわる指摘と修正はできません（参考： Prettier vs. Linters ）。ですので、現実的にはリンターと併用するケースが多いはずです。ここでは、ESLint が既に導入されているという前提で、ESLint に Prettier によるフォーマットを統合する方法を紹介します。 Prettier のインストール 1. npm または yarn で、必要なパッケージ ( prettier , eslint-config-prettier , eslint-plugin-prettier )を インストールする npm i -D prettier eslint-config-prettier eslint-plugin-prettier 2. eintrc の extends の 最後 に Prettier 用の設定 plugin:prettier/recommended を追加する module.exports = { "extends": [ "standard", // https://github.com/standard/eslint-config-standard "my-awesome-format-rule", // ぼくが考えた最強のフォーマットルール "plugin:prettier/recommended" // Prettier の設定（★これが大事） ], } これで Prettier のデフォルト設定でフォーマットする準備ができました。 "plugin:prettier/recommended" の設定は Prettier のフォーマットルールを適用するだけでなく、既にあるフォーマットルール（この例だと "standard" と "my-awesome-format-rule" 内のフォーマットルール）を「無効にする」働きもしているため、extends の最後に書く必要があります。 動作確認 コマンドラインで eslint を実行してみて prettier/prettier という種類のエラーが出ていれば、それが Prettier によるフォーマット違反の指摘です。 $ npx eslint target.js 125:1 error Replace `↹↹↹↹↹↹[colName]·` with `··········[colName]` prettier/prettier これは「タブがフォーマットルールに違反しているので、空白に変換してください」というエラーですね。 eslint --fix で自動的に修正（フォーマット）が可能です。修正前後でどう変わるか確認してみてください。 自動フォーマットの設定 勝手にフォーマットしてくれないと全然嬉しくないので、 eslint --fix をセーブ時に自動的に行うようにします。設定はエディタごとに異なるので、お使いのエディタの設定方法を確認してください。 Integrations - ESL int - Pluggable JavaScript linter 私は Visual Studio Code を使っているので、 ESL int 用プラグイン のインストール セーブ時の自動Fixの設定 "eslint.autoFixOnSave": true を行いました。 フォーマットルールの調整 前述のとおり、Prettier は基本的なフォーマット方針を決められているところがウリですが、とはいえ今までインデントにタブを使っていたのが空白になるなど、「これまで使ってたフォーマット方針とあまりにギャップがありすぎる......」という感想を持つ方もいるかもしれません。この場合は rules に Prettier の設定を追加することで、ある程度調整が可能です。 ＜参考＞Options · Prettier https://prettier.io/docs/en/options.html 設定例 module.exports = { extends: ["airbnb-base", "plugin:prettier/recommended"], rules: { "prettier/prettier" : [ "error", { // 設定可能なオプションの一部. () はデフォルト値. printWidth: 100, // 行の最大長 (80) tabWidth: 4, // 1 インデントあたりの空白数 (2) useTabs: true, // インデントにタブを使用する (false) semi: false, // 式の最後にセミコロンを付加する (true) singleQuote: true, // 引用符としてシングルクオートを使用する (false) } ] } }; Prettier によるフォーマット例 以下は公式サイトでも紹介されている Prettierによるフォーマットの例ですが、Prettier の能力が分かる特徴的な例なのでここでも紹介します。関数呼び出しが1 行の最大長を超えているケースです。このケースは ESL int 単独でも指摘はできますが、修正はできません。 フォーマット前 （1 行が printWidth 設定(80 文字) を超えており NG） foo(reallyLongArg(), omgSoManyParameters(), IShouldRefactorThis(), isThereSeriouslyAnotherOne()); フォーマット後（引数ごとに改行を入れて見やすくしてくれる） foo( reallyLongArg(), omgSoManyParameters(), IShouldRefactorThis(), isThereSeriouslyAnotherOne() ); 例えばここで isThereSeriouslyAnotherOne() 引数を削除すると、80 文字以下になるため、 1 行でのフォーマットに戻ります。賢い。 導入してみた感想 実をいうと、私はこれまで自動フォーマットの機能を使っていなかったため、Prettier を試してみて「自動フォーマットって最高！！」と思いました。雑に空白やインデントを書いても、統一感のある綺麗な見た目にフォーマットしてくれます。 一方で、ESLint とエディタを連携させた自動フォーマットを習慣としてきた方にとっては、JavaScriptのフォーマットに限って言えば Prettier の導入はそれほど大きなメリットはないのでは、とも思いました。ただ、「Prettier によるフォーマット例」で示したような Prettier にしかできないこともあり、試してみる価値はあるのではないでしょうか。 また、Prettier でフォーマットされた結果を見て、「前後の統一感を考えると、ここは改行せずに 1 行で書いた方がいいだろう......」と修正したくなることもありました。思わず直してしまったりすると、Prettier が即「これが俺のやり方だ」と言わんばかりに容赦なくフォーマットし直してくれます。もうちょっと優しくして（融通利かせて）ほしいと思わなくもなかったですが、それは Prettier の思想とは違うのでしょうがないです。 今回少し試用してみた限りでは、全面的に導入に賛成とまでは判断できませんでしたが「スタイルについての細かい議論やレビュー指摘はやめて、コード書くことに集中しようぜ」というPrettier の方針はとても共感できます。導入も簡単で、初回リリースが 2017/1 とまだ若いツールなのに人気というのも納得です。引き続き注目していきたいと思います。

QiitaのRust Advent Calendar 2018 4日目の記事です。 技術本部の松本です。フォルシアではインメモリデータベースをRustで開発しています。本記事では、なぜRustを選んだかをご説明します。 速度 Rust は2015年に1.0がリリースされた比較的新しいプログラミング言語であり、「速度、安全性、並行性」をゴールとしています。 言語の選定にあたっては、動作速度が重要視されました。 Computer Language Benchmarks Game （ベンチマーク結果を公開しているサイト）によれば、RustはJavaやGoより高速で、C++並の速度が出ると言われています。実際に我々が検証した際も、RustはGoよりは高速で、Javaと異なりGCが無いため、Rustの方が好ましいという結果になりました。 ガベージコレクション(GC)が無い Rustでは所有権の概念を取り入れることで、いつメモリ上からオブジェクトが解放されるか、管理しています。そのためGCが必要なく、GCによるプログラムの停止を避けることが出来ます。技術検証時にJava実装を検討しましたが、GCが走るタイミングでレスポンスに時間がかかることがあり、安定して高速なレスポンスを返すインメモリデータベースの用途上、Rustに軍配が上がりました。 静的ディスパッチによるゼロコスト抽象化 Rustがなぜ速いのかという文脈で「ゼロコスト抽象化」というキーワードに言及される事が多いですが、少し噛み砕いて説明したいと思います。 Rustではジェネリクス(generics)とトレイト(trait)によって多相性(Polymorphism)をサポートしています。ジェネリック関数は同じ名前の関数に異なる型を渡すことができます。下記に例を示します。 use std::fmt::Debug; fn main() { fn print_debug (x: T) { println! {"{:?}", x}; } print_debug(1u8); print_debug("&str"); #[derive(Debug)] struct Point { x: i32, y: i32, } let origin = Point { x: 0, y: 0 }; print_debug(origin); } Rust Playgroundで動かしてみる ジェネリック関数（上記例では print_debug ）を用いた場合、コンパイル時点で引数の型が全て明らかになっている( u8, &str, Point )ため、それぞれの型専用の関数が作成されます。 実行時に型から関数への割当関係を解決する動的ディスパッチを行う場合は実行時にその分のコストが掛かりますが、Rustはコンパイル時に解決してしまう静的ディスパッチを使用するため、実行時にはゼロオーバーヘッドで関数を対応する呼び出す事ができます。 開発効率 また、開発効率の面も考慮事項でした。Rustは新しい言語ではあるものの、他の言語以上に効率良く開発できる環境が整っています。標準的なツールセットがあることや、テストが標準ライブラリに含まれていることはC++よりも好ましい部分です。 rustupによる簡単な環境構築 Rustは環境構築が驚くほどに簡単です。 rustup.rs にアクセスし、表示されたコマンドを実行するだけでRustを使い始めることが出来ます。 RustのパッケージマネージャであるCargoですが、パッケージ管理だけでなく、プロジェクトの作成からテスト、ビルド時の設定まで一貫して管理してしてくれるため、いろいろなツールを使い分ける必要がありません。もちろんrustupでインストールされます。 コーディング時のサポート Rust Language Server (RLS) が開発されており、コーディング面で補完などのサポートが受けられます rustfmt で統一的なコード整形が可能です 上記のツール群も日々アップデートされており、不便なくツール群の恩恵に預かっています。 エラーメッセージが親切 Rustのコンパイラの特徴として、非常に親切なメッセージが挙げられるます。所有権やライフタイムといった馴染みの薄い概念があるため、完璧なコードを一撃で書くことはまだ難しいのですが、基本的に「どこを」「どう」修正すれば適切なアノテーションができるかを、コンパイラがエラーメッセージとして表示してくれます。コンパイラのサポートを受けながらコードを書いていくことが出来ます。 言語標準のテスト Rustは 言語の標準機能 としてテストが用意されており、cargo testのコマンドで実行することが出来ます。テスト用のライブラリ群をインストールして......といった作業が無いのは嬉しいことです。cargo new --libした際に作られるスケルトンには、テストケースのスケルトンが含まれています。すぐにテストを書かないとという気分にさせてくれますし、実装とテストが同じファイルに書けるため、テストが仕様の役割を果たしやすくなります。docコメント中のテストも実行されるので、実装とコメントが乖離することも防ぎやすくなっています。 また、テストはファイルごとに並列で処理されるため、プロジェクト全体のテストを行う際も高速にテストが可能です。 学習コスト Rustのデメリットとして、初期の学習コストの高さが挙げられます。 実際、借用（・所有権）・ライフタイムの概念は馴染みが薄く、ドキュメントを読みコンパイラと格闘しながら学習していくことになりました。確かに馴染みの薄い概念ではなるものの、ユーザーとして使う分には難しい概念ではないため、職業プログラマが仕事として向き合ってしまえばコンパイラのサポート化で問題なく利用できるレベルだと考えています。 文法に関して「変数の型はアノテーション風に書く※」「ブロックの末尾の式が返り値になる」と念じれば、他の手続き型言語と大きな違いはありません。先日の勉強会で「Rustは関数型風の文法が書ける手続き型言語」とおっしゃっていた方がいらっしゃいました。実際手続き型言語に馴染みのある人間からすると、パターンマッチなど関数型言語に特徴的な機能を使うことができる手続き型言語という風に見え、文法部分の学習コストは大きくありません。 フォルシアでは概念と基本文法を理解するためのハンズオンを社内で行い、Rustが書けるエンジニアを増やそうと試みています。 ※JavaScriptのFlowやPythonでアノテーションを書いたことがある人であれば、いつもの位置に書くだけです。 さいごに 以上の理由から、フォルシアでインメモリデータベースを作る際に、速度と開発効率の面でRustは良い選択肢になりました。 2019年1月16日に予定している Shinjuku.rs #2 ではデモをお見せできそうです。

技術本部の相澤です。日頃はSQLかSQLを出力するプログラムばかり書いています。 先日、PostgreSQL9.6系の検索アプリをチューニングする機会があり、pg_prewarmと複合indexを用いることで、劇的な改善を図ることができました。今回はそのときに使ったその2つの技術についてご紹介します。 チューニングしたアプリの概要 はじめに、今回私がチューニングしたアプリの概要をご説明します。 PostgreSQL9.6系で動作している。 アプリケーションのみフォルシアにて管理、OSは顧客が管理している。 約27000件のホテルとこれに紐づく約500万件の宿泊プランから特定の条件の

FORCIAアドベントカレンダー2018 3日目の記事です。 技術本部の相澤です。日頃はSQLかSQLを出力するプログラムばかり書いています。 先日、PostgreSQL9.6系の検索アプリをチューニングする機会があり、pg_prewarmと複合indexを用いることで、劇的な改善を図ることができました。今回はそのときに使ったその2つの技術についてご紹介します。 チューニングしたアプリの概要 はじめに、今回私がチューニングしたアプリの概要をご説明します。 PostgreSQL9.6系で動作している。 アプリケーションのみフォルシアにて管理、OSは顧客が管理している。 約27000件のホテルとこれに紐づく約500万件の宿泊プランから特定の条件のホテル・プランを検索する。 件数増加等によりDBが肥大化し、 postgres再起動時の検索 と 大量のプランがヒットする場合の施設検索 が遅くなっていた。 postgresのキャッシュのヒット率は良くないが、仕様の都合上改善できないので対象外とした。 データ構造と検索時のSQL 次に、データ構造の概要をご説明します。施設にはuniq にhotel_id、プランにはplan_idが割り振られています。 以下、テーブル構造です。 hotel：hotel_idをprimary keyにしたホテルマスタ。施設の全情報を持つ。（施設並び順keyも然り） plan：plan_idをprimary keyにしたホテルマスタ。プランの全情報持つ。またjoin keyとしてhotel_idをもつ。 プラン情報から施設検索の際に発行されるSQLは次のとおりです。 SELECT {Hテーブル上のカラム} FROM ( SELECT hotel_id FROM plan P WHERE {検索条件から発行されるWHERE句} GROUP BY P.hotel_id )s INNER JOIN hotel H USING(hotel_id) ORDER BY H.hotelorderkey1, H.hotelorderkey2, H.hotelorderkey3.... OFFSET.... LIMIT.... {一回に必要なのは10件程度} チューニング方法 postgres再起動時のチューニングには PostgreSQL9.4から実装されているEXTENSIONの pg_prewarm を適切に設定することで対応します。 大量のプランがヒットする場合の施設検索に関しては適切にindexを貼り、GROUP BY を速くすれば良いだろうということが実行計画から読み取れたので、 複合index を採用しチューニングしました。 方法１ pg_prewarmの設定によるチューニング pg_prewarmとは？ SELECT pg_prewarm('hotel', 'buffer', 'main'); のようにテーブル名を指定して、特定のリレーションをキャッシュするモジュールです。postgresサーバーを再起動すると、テーブルがメモリから落ちてしまいます。テーブルがメモリに載っていない状態のままオンラインに出してしまうと、最初に一気にテーブルを読み込み、大量のI/Oが発生してしまい高負荷となりますが、pg_prewarmを用いて予めキャッシュしておけば高負荷を避けることができます。 また、キャッシュに乗り切らないテーブルサイズがある場合でも、キャッシュに乗る範囲でテーブルをキャッシュしておくだけで高負荷を避けることができます。 ＜pg_prewarm 公式ドキュメント＞ https://www.postgresql.jp/document/9.6/html/pgprewarm.html 3つのモードはどれを使うべきか pg_prewarmには3つのモードがあります。 buffer : posgresのバッファキャッシュに載せます。 prefetch : OSに非同期のプレフェッチをリクエストします。もしOSやビルド時にプレフェッチをサポートしていない場合はエラーとなります。 read : ブロックの要求された範囲を読み込みます。プレフェッチとは違って、すべてのプラットフォームにサポートするようにビルドされていますが、速度が遅くなります。 以下の理由から、bufferを採用しました。 理由1：サービスに関してフォルシアでOSの管理をしておらず、権限や設定に関して変更ができないため。 理由2：pg_buffercacheを使えば、バッファキャッシュにどのテーブルがどれだけ乗っているか確認できるため（具体的な確認のSQLは下に記載があります）。 4つのテーブルをメモリに乗せるには、どの書き方が良いか pg_prewarmを呼び出すクエリの書き方は、大きく2通り考えることが出来ます。今回は双方を検証しました。 パターン1：一つのSELECT文として呼び出す。 SELECT pg_prewarm('table1', 'buffer', 'main') ,pg_prewarm('table2', 'buffer', 'main') ,pg_prewarm('table3', 'buffer', 'main') ,pg_prewarm('table4', 'buffer', 'main') ; パターン2：それぞれ別のSELECT文として呼び出す。 SELECT pg_prewarm('table1', 'buffer', 'main'); SELECT pg_prewarm('table2', 'buffer', 'main'); SELECT pg_prewarm('table3', 'buffer', 'main'); SELECT pg_prewarm('table4', 'buffer', 'main'); パターン1は、テーブルサイズを大きくしていくとクエリが長時間になりすぎて異常を検知してしまいました。パターン2では一つずつSQLが実行され、キャッシュしきれない場合は前から順に落ちていくだけでした。このため、パターン2の書き方で重要性の高い(I/Oにつながりやすい)テーブルを後ろで呼び出すように温めてやるのがよいと考えました。 テーブルがキャッシュから落ちているかどうかはEXTENSIONのpg_buffercacheを使うことで調査可能です。 CREATE EXTENSION pg_buffercache; SELECT C.relname ,count(*) AS buffers FROM pg_buffercache B INNER JOIN pg_class C ON b.relfilenode = pg_relation_filenode(c.oid) AND b.reldatabase IN ( 0 ,( SELECT oid FROM pg_database WHERE datname = current_database() ) ) GROUP BY C.relname ORDER BY 2 DESC ; relname | buffers ----------------------------------------+--------- plan | 167927 hotel | 3418 ＜参考にしたブログ＞ PostgreSQL Deep Dive ＜pg_buffercache 公式ドキュメント＞ https://www.postgresql.jp/document/9.6/html/pgprewarm.html I/Oの高い時間を避ける pg_prewarmはそれなりに時間が掛かるクエリで、実行中はI/Oが高いです。postgres再起動時に、pg_prewarmの終了を待って検索が行われるように設定をいれたところ、postgres再起動後の初期検索におけるI/Oが激減しました。 結果 元の状態ではpostgres再起動後はじめてのオンライン投入時に、高負荷な状態が5～10分程度続いていましたが、prewarmを採用した場合は オフライン状態2～5分程でI/Oが落ち着くようになりました 。 方法２ 複合indexによるチューニング 検索ロジックについては、プラン情報から施設検索の際に発行されるSQLは以下のとおりです（再掲載）。 SELECT {Hテーブル上のカラム} FROM ( SELECT hotel_id FROM plan P WHERE {検索条件から発行されるWHERE句} GROUP BY P.hotel_id )s INNER JOIN hotel H USING(hotel_id) ORDER BY H.hotelorderkey1, H.hotelorderkey2, H.hotelorderkey3.... OFFSET.... LIMIT.... {一回に必要なのは10件程度} 検索テーブルやjoinキーには基本的にindexが張ってありますが、複合indexはありませんでした。そのためWHERE句で十分にplanが絞れなかった場合に、GROUP BYの処理に時間がかかってしまっていました。 hotel_orderに関して、当然ながらhotel_idによって一意に定まります。ならばplanテーブルにあらかじめ持たせることで、以下のようなSQLに変更しても同じ意味になります。 カラムの定義 ROW_NUMBER () OVER (ORDER BY H.hotelorderkey1, H.hotelorderkey2, H.hotelorderkey3....) AS hotel_order SELECT {Hテーブル上のカラム} FROM ( SELECT P.hotel_order, P.hotel_id FROM plan P WHERE {検索条件から発行されるWHERE句} GROUP BY P.hotel_order, P.hotel_id -- hotel_idだけのときと同じです ORDER BY P.hotel_order, P.hotel_id -- hotel_orderだけのときの同じです )s INNER JOIN hotel H USING(hotel_id) ORDER BY s.hotel_order -- inner joinの前後で施設並び順は維持されないので、再度並べ直しが必要です OFFSET.... LIMIT.... {一回に必要なのは10件程度} SELECT, GROUP BY,ORDER のキーが一致しましたので以下の複合indexを用意すれば、indexを用いて高速でサブクエリを終えることができます。 CREATE INDEX hotel_order_index_on_plan ON plan (hotel_order, hotel_id); 多様なORDERパターンがありますが、このようなhotel_orderを何種類か準備すればいいだけ。DB構築も検索ロジックもそう難しくなるものではありません。 結果 もともと2秒以上かかっていた検索クエリが、 約1/700の3ms で終了するようになりました。余談ですがこれをサービス反映したところ、検索が早くなるだけではなく、前半で問題にしていたI/Oも更に下がりました。 さいごに 上記2つの改修は、実際のサービスを使う際にも体感できるレベルの改善になりました。遅いクエリに着目した高速化は、ユーザーの最も悪い経験を向上させるため、コスパが良いと感じています。ご参考になれば幸いです。

FORCIAアドベントカレンダー2018 1日目の記事です。 技術本部の龍島です。アドベントカレンダーの最初の記事ということで何を書こうかと考えていたんですが、以前記事を書いたAlexa、スマートスピーカーについて書こうと思います。いくつかのAlexaスキル開発に携わり、スマートスピーカー、VUIの特性、弱みやその補い方が見えてきました。 以前の記事は こちら 人気スキルの傾向 はじめにAlexaスキルの人気傾向からどのようなスキルが使われるのか考えてみたいと思います。少し前のデータになりますが、 Amazonランキング大賞2018上半期 を見ると、人気のスキルは大きく以下に分類できるでしょう。 情報提供系 野村證券の株式市場の情報提供スキル、JR東日本の運行情報提供スキル、Yahoo!ニュースのように一般的な情報を提供するスキルです。特徴としてユーザごとの情報の出し分けは基本的に無く、あってもよく使う路線を登録する（例：JR東日本列車運行情報案内）などで、ユーザ毎に得られる情報は大きく変わりません。 キャラクター系 ピカチュウトーク、豆しばをはじめとしたキャラクターとの会話を楽しむものです。特徴としてユーザは会話の内容よりキャラクターの声を重視していると言えるでしょう。 ゲーム系 駅しりとり powered by 駅すぱあと、アルクの英語クイズのようにゲームを楽しむスキルです。しりとりのようにユーザが発話すべき単語が少ないものや、英語のリスニングのように問題文が流れてユーザは選択肢から答えるといったものが多いようです。 音楽系 radiko.jp、カラオケJOYSOUNDのように音楽を流すタイプのスキルです。スピーカーから流れる音自体に価値があるのでスマートスピーカーとの相性はよく、人気なことはうなずけます。 スキルの苦手なところ 人気のスキルから見て取れることは、インプットの情報量（ユーザ→スキル）が少なく、アウトプットの情報（スキル→ユーザ）は量の多寡はあるものの種類が少ないということかと思います。これにはスマートスピーカー、VUIの特徴である「音声で操作する」という性質が影響しています。ユーザの発話は、長くなればなるほど複雑さや聞き取りの難易度が上がります。そのため、単体のユーザ発話はできるだけ短くしたいところですが、細かく何度も質問するとユーザを疲れさせてしまいます。 インプットの情報が少ないということはそれに応じて返却するアウトプットの情報の種類も少なくなってしまうということであり、ユーザに多くの情報を入力させ最適な情報を提供するようなサービスは設計が難しくなります。 苦手を克服するには？ インプットの量が必要なサービス、例えばユーザの好みに応じた商品を提供するECサイトや、旅行商品を検索するようなサービスはスキルで実現できないのでしょうか？ そんなことはないと考えています。 アメリカのスターバックスのスキル はこの問題の解決のヒントになるでしょう。 アメリカのスターバックスのスキルはAlexaからコーヒーを注文して店舗で受取ることができるのですが、それに必要なユーザの発話は「Alexa, order my Starbucks」のみです。どういう仕組みになっているかと言うと、オンラインオーダーが可能なスターバックスアプリ上で「デフォルト注文」が設定されており、Alexaからはスキルを呼び出すだけでその注文が行われるというわけです。スタバの注文のためには「コーヒの種類」「サイズ」「ミルクの量」などのインプットが必要ですが、それには適したツールのスマホアプリをユーザに利用させ、注文の機能のみをより手軽に使えるAlexa上からも行えるようになっているのです。発想としては Amazon Dash Button に近いですね。 さいごに インプットの情報量が少ないことはAlexaに限らず、スマートスピーカーに共通した弱点と言えます。情報のインプット部分はより適したデバイス（スマホ、PC）を利用し、強みである「手軽さ」を生かして実行部分のみをスマートスピーカー上から行えるようにしたスターバックスの例は一つの解だと思います。インプット情報を補完する点はユーザに別端末で入力させる以外にも、ユーザのwebサイトでの行動履歴を利用する、似たユーザの情報を使うなどが考えられるでしょう。スマートスピーカー、VUIの特性を理解し、得意な部分を任せ、苦手とする部分は他の方法で取得するといったことがスキルの設計では重要だと考えられます。

技術本部の光山です。今夏、フォルシアでは初の試みとなる「FORCIA Summer Internship 2018」を開催しました。 前回の記事 では、インターンチームからの視点で、サマーインターンを実現するまでの道のりをご紹介しました。今回はメンター視点で、具体的にインターン生に取り組んでもらった課題について、前編・後編の2回に分けてご紹介します。サマーインターンに参加されなかった学生の皆さんにも、フォルシアの取り組みやフィロソフィーを多少でも知っていただけたら幸いです。 私はメンターとして、下記2つのコースを担当しました。 検索高速化コース（第1ターム・第3ターム） ECサイトのオンラインのSQLを徹底的にチューニングするコースです。 データクレンジングコース（第2ターム・第3ターム） 「検索改善のための、ECサイト用データのクレンジング」に取り組むコースです。 記事は こちら 前編では、「検索高速化コース」について、詳しく説明していきます。 検索高速化コース 高速化はなぜ重要か フォルシアは創業時から、一貫して「速さ」にこだわり、検索の高速化に取り組んできました。なぜ高速化が重要なのでしょうか。私の考える代表的な理由は次のとおりです。 ユーザにとって、ストレスの無いサービスとなる 速ければその分、複雑な処理をさせることができる 複雑な処理とは、例えばユーザごとに検索結果の並び順を最適化したり、料金などの表示内容を変えたりすることです。フォルシアの検索速度へのこだわりについては こちら の記事にもまとめられていますので、ぜひご覧ください。 この検索高速化コースはまさにフォルシアの コア技術 、そしてコアバリューを体感していただく絶好の場となるはずだと思い、私も気合いを入れて課題作成を行いました。 課題の概要 今回は、とあるECサイトの検索で実際に使用されているSQLを、課題用に多少簡略化した状態で、インターンシップの最初に提示しました。このSQLは、商品の基本情報を保持する「商品マスタ」、商品が属するカテゴリの情報を保持した「カテゴリマスタ」など、10種類程度のマスタ群から、ECサイトの商品一覧の表示に使用する10項目程度を返却するSQLになります。 このSQLは、インデックスも作成されていませんし、NULLも含まれていますし、オンラインで複数テーブルとのJOINも行われています（課題とは言え、なかなかひどいSQLでした）。そのまま実行した場合の実行時間は10秒以上です。 オンラインのレスポンスが毎回10秒以上となると、ユーザに与えるストレスは多大なものとなってしまいます。そのようなサービスがあったとしたら、まともに使われることはないでしょう。そこで、 「実行時間が10秒以上のこのSQLを高速化せよ！目標性能は300ミリ秒以内」 を検索高速化コースのお題としました。 インターン生の取り組み 第1タームのインターン生は、Webアプリケーションの開発経験はあるものの、SQLはORMの使用が中心で、SQLのチューニングをしたり、複雑なSQLを書いたりした経験は無い、というバックグラウンドの方でした。ご自身もその点に課題意識があり、弱点克服のためにこのインターンシップに応募してくださいました。実際、ORMであっても、どのようなSQLが実行されているのか理解しておくことはとても重要になります。その意味で、課題意識がとても素晴らしい方だなと思いました。 第3タームのインターン生は、データ分析用のSQLの経験がある方でした。ただし、データ分析を行っていたときは、一晩かけて実行して翌日結果を確認する、といったことが多かったようです。1秒でも「遅い」と言われるオンラインでのパフォーマンスの世界に最初は戸惑いつつも、果敢に課題にチャレンジされていました。 インターンシップ期間中は、インデックスの作成（闇雲に作成すればよいというものではありません）や、検索に最適なデータの保持方、PostgreSQLのユーザ定義関数の実装など、様々な角度から高速化を検討していただきました。 特に印象的だったのは、ただ高速化を図るだけではなく、お二方とも、 不必要にリッチな提供はしない（速度面を考慮して料金は離散値で保持、など） 精度も考慮した機能の提供（キーワード検索において、合致したカラムに応じて並び順を変更するロジックの実装、など） のように、 機能面でも積極的に工夫をされている点でした。 さらには、最終日に振り返りをしていたとき、第1タームのインターン生が 「何のための高速化であるのか、という観点がとても重要であることが分かりました。そのために、高速化以外にも、UI/UXの設計やデータクレンジングも併せて考慮する必要があるのだと実感しました」 とおっしゃっていました。こちらは正にそのとおりで、この発言には私も思わず膝を打ちました。実際、今回のインターンシップではUI/UXコースもデータクレンジングコースもあります。顧客に価値を提供するためにも、これらは密に関連しているからです。たった5日間でこの発言に至る彼の成長速度に大変感動し、本当にトップレベルの優秀な学生の方に来て頂いたんだなと実感した次第です。 おまけ おすすめ本 達人に学ぶ SQL徹底指南書 著者：ミック 出版社：翔泳社 (2008/2/7) SQLの基礎固め用に、事前課題として「達人に学ぶ SQL徹底指南書」という本を読んでもらいました。 SQLは集合指向の言語であるということが（しつこいくらい？）書いてあり、手続き型言語と根本思想が異なることがよく分かります。応用編と併せてとてもおすすめなので、SQL入門者の方にぜひ読んでいただきたい本です。 次回予告 次回は、「サマーインターンメンターが語るインターン生の取り組み【後編】」として、データクレンジングコースの取り組みをご紹介します。お楽しみに！

2017年新卒入社エンジニアの新谷です。フォルシアでは、検索エンジニア 兼 ダイナミックプライシングの構想企画/研究開発/事業開発を担当しています。学生時代は数理工学の研究をしていました。 今回は、 先日ご紹介した京都大学との共同記者会見 で発表した研究テーマ「ダイナミックプライシング」について、具体的な構想をご説明します。 ダイナミックプライシングとは 先日、 USJ が入場券に変動価格性を導入することを発表 し、話題となっているダイナミックプライシング。一言で言うと、ダイナミックプライシングとは、需要と供給に応じて価格を調整し、 売り手と買い手の適切なマッチングを実現する手段 です。航空券やホテル、イベントチケットなどで広がる売り手も買い手もハッピーなこの仕組みを、より多くの商材に適用して世の中に広めていこう、というのがこの研究/事業の趣旨です。 経済産業省のレポート でも、2030年代に確実に起こる未来としてダイナミックプライシングが取り上げられており、今後どんどん広がっていくことが予想されています。 従来ダイナミックプライシングには適性がある まず、従来のダイナミックプライシングについて、航空券を例にご説明します。購入可能な座席数が多い売り始め期、先の予定が決まっている買い手は少なく需要が小さいために、航空券は比較的安価で購入することができます。一方、フライト直前期は、購入可能な座席数が少なく需要が大きくなるために、高額になるといった仕組みで導入されています。 この方法が適するのは、「この日じゃないといけない」という性質の強い商材であり（他にもいろいろ理由はありますがここでは割愛）、ゆえに航空券やホテル、イベントチケットなどには先行して導入されています。逆に、「この日じゃなくてもいいな」という性質が比較的強いサービス（映画館などのレジャー、医療サービス、美容院など）には、 なかなか適用されにくい現状 があります。 ダイナミックプライシングが広がっていく時流を踏まえると、この適性の有無の問題は避けて通れない道です。 フォルシアの扱うダイナミックプライシングとは 「期間」×「利用頻度」の観点を設け、全体最適を求める 着目したのは、 売買における共通構造。 在庫の概念を伴うあらゆる商品の売買には、「提供可能な枠を埋めていく」という共通した性質があり、枠の埋まり具合のバラツキが、機会損失であるとされています。我々は、航空券や映画館、引いてはサービスに限らずモノに至るまで共通する、この「枠を埋める」構造に着目し、あらゆる商材の枠を 効率的に埋めていくには というアプローチでダイナミックプライシングを捉えています。 これをベースとした以下の考え方が、フォルシアのやろうとしているアプローチです。 一回一日という単位ではなく、一定期間での「枠」と考える 個人の利用頻度/利用額と空き状況を元にし、人ごとに適切な価格とタイミングを提示する これを毎日、全ての利用者に対して実施することで、全体として効率的に枠を埋め、機会損失を解消する この考え方はつまり、「この商品をいくらで売ると、その枠の何％が埋まるのか」といったような、商品一体を一つとした価格設定ではなく、「人にいついくらで利用してもらうか」といった、 個人単位でのダイナミックプライシング として見ることができます。 ダイナミックプライシングの汎用理論創出へ 利用頻度と空き状況を元に機会損失を解消していくこのアプローチは、数理的構造として商材間に差はありません。ゆえに、広く適用できる汎用理論を作ることができると考えています。今はまだないダイナミックプライシングに関する汎用的な数理モデルを、こういったアプローチで構築していこうとしています。 まとめ これからスタートするこの研究/事業は、さまざまな業界で機会損失が解消されることを目指しており、道のりとしては、 パートナー企業と共にさまざまな業界データを使って実証実験を繰り返し、少しずつ形になっていくものだと思っています。 また、記者会見でも多数質問のあった、「個人ごとに価格が変わる、という文化は根付くのか？」という問題についても、人々の納得感が得られるかどうかが鍵となると考えています。公明正大でフェアな理論としての研究開発を進め、世の中に浸透するダイナミックプライシングの基盤作りを目指していきます。