Monoxer Intern Report #13_大量のコンテンツの描画処理最適化

自己紹介

筑波大学大学院修士1年の山﨑昂輔です。大学ではRDFデータを分散処理で効率的に問合せするためのデータ分割手法について研究しています。 モノグサで7月から9月までの3ヶ月間夏季インターンシップに参加していました。

参加を決めた理由

Scalaという言語をより実践的に学びたいということと、実務経験を積みたいということが主な理由です。 私は研究でこのScalaを使用しているのですが、学習のための資料が少ない状況でした。5年以上前のwebページの資料等を参考になんとか学習し、使えるようにはなりましたが、この使い方が本当に正しいのかを知りたいと考えていました。 そこで様々なインターン応募サイトを探していたところ、AtCoder JobでScalaを使用している企業としてモノグサがヒットし、参加を決めました。

取り組んだこと

細かいタスク

Monoxerの業務は様々ですが、私はその中でもマーケットプレイスという領域のタスクに取り組みました。マーケットプレイスは出版社が商品を販売・管理する機能や、利用組織の管理者である学校の先生などが商品を購入・管理する機能があります。詳しくはマーケットプレイス概論を読んでみてください。 マーケットプレイスでの開発は、フロントエンドとバックエンドを触ることになるのですが、私は今回のインターンシップが実務初体験であり、TypeScriptの使い方どころかGitHubの使い方すらわかっていませんでした。そこで初めは軽めのタスクを割り当ててもらいながらどのようなものかを理解していきました。 詳細は省きますが、小さめのタスクは

  • ページネーションの導入
  • ダイアログをトーストに変更
  • 表示のバグの修正

などです。これらのタスクを通して基本的なGitHubの使い方やReactの仕組み、バックエンド処理などについて教わったのち、今回のインターンシップのメインタスクに取り組み始めました。

メインタスク

概要

私のメインタスクは、「マーケットプレイスのコンテンツを大量に購入しているとブラウザが停止してしまう」という問題の解決でした。上述の通り、マーケットプレイスの商品は学校の先生などが購入して利用しますが、先生方が利用するPCのスペックはあまり高くないことも多いです。そしてその場合、購入したコンテンツが増えると一覧表示時等においてそれらを処理することができなくなってしまいます。そこで今回のメインタスクによって、PCのスペックを問わずスムーズな操作の実現を目指しました。

Bookとその統合

今回の問題はBookの統合を行う際に生じていました。 Bookとは、モノグサの商品に含まれているいわゆる問題集のようなものであり、組織は商品を購入し、その問題を児童生徒らに解かせることができます。このBookは単元ごとに分割されていることもあり、組織が商品一覧から複数のBookを選択し統合することで、指導内容に合わせた新たなBookを作成することも可能です。今回の問題は、この統合操作の際に生じていました。

従来の処理

そもそもなぜブラウザが停止してしまうことがあったのかを理解するために、元々どのような処理になっていたのかを説明します。 学校の先生などが購入した商品の一覧を開く際、従来はすべての商品とその商品に含まれるBookの情報を一括で受信し表示していました。さらに、この時デフォルトではアコーディオンが開いており、購入している商品だけでなくその中のBookが全て表示される(図1参照)ことから、商品数の増加に伴い描画コストも増加し、結果としてブラウザが処理しきれずに停止してしまっていたのです。また、商品検索も同様で、大量の商品内での検索は処理コストが高くブラウザ上での処理が困難となってしまっていました。

図1.「Bookの統合」を開いた時の従来の画面

処理の改善

上記の問題に対して、受信・描画するデータ量を削減することによる改善を試みました。 具体的には、

  1. ページネーションを導入し、1ページあたりの商品数を30件に制限
  2. デフォルトではアコーディオンを閉じ、商品名のみの表示(図2参照)
  3. 商品検索をサーバーサイドでの処理に変更

の3つのアプローチを取りました。1と2のアプローチは、描画量の大幅な削減を目的としており、従来は総商品数+総Book数だけ必要だった描画を30件以下に抑制できます。3のアプローチは検索コストの削減を目的としており、サーバー側での処理によって組織のPCのスペックに依存しないスムーズな検索を実現できます。 リリース後には、「挙動が軽くスムーズになった」との声もいただきました。

図2.「Bookの統合」を開いた時の変更後の画面

インターンの感想

実務を行う経験

本インターンシップはインターンシップ専用のプログラムではなく、実際に実務としての開発を行い、会議や社内chat等の閲覧も可能な環境でした。今後就活を控えている身として、どのような人たちがどのようにして働いているのかを知ることができたのはとても良い経験であり、社会での働き方の例として大変参考になりました。プログラミングの面では、そもそもの一般的なコーディングの作法から必須スキルまで、多くのことを経験できたと感じています。特に、命名や責任範囲などは普段の研究でも自分のコードを読むために重要なことであるため、意識して活かしていきたいと思います。

誰かのためにプログラムを書く経験

これまで自身のためのプログラムしか書いたことがなかった私にとって、私がコードを書くことで他の誰かのユーザー体験が改善したという実感はとても新鮮であり、かつ嬉しいものでした。実際に「挙動が軽くなって助かった」という声をいただくことができたのも印象的です。

社内の環境や働き方

先にも書いた通り社内のやり取りの閲覧や自分の意見の発信もできるという中で、社員の方々がモノグサという会社とサービスに誇りを持ち、より良くしていこうと考えていることを感じられました。また、多くのやり取りの中で「ありがとうございます」という言葉が頻繁に出てくるのも印象的でした。私自身、特にインターン開始直後などは自分の考えを発信する際に「こんな初歩的なこと聞いても良いのだろうか」や、「素人意見で大丈夫だろうか」などとドキドキすることもありましたが、「ありがとうございます」と言っていただけることで発言のハードルが下がり、より気楽に発信しやすくなったと感じました。 働き方の面では、勤務時間・勤務形態ともに柔軟であり、授業や課題、研究等とのバランスを取りながら不自由なく勤務できました。また、会社にはフリードリンクや軽いおやつ、ボードゲームなど仕事以外も充実しており出社も楽しかったです。

自身の成長

授業や研究でのプログラミング経験はあったものの実務での経験は0からのスタートだったので最初は不安もありましたが、日を重ねるごとに徐々にいろいろなことを理解していくことができたと感じました。特に、9月に2週間他社のインターンシップにて学生7人でチームを組んでReactを用いたAgile開発を行なった際には、モノグサでインプットしてきた経験や知識を適切にアウトプットでき、これまで自身が教わってきたことが自分のものになっていることを実感しました。とはいえ何度もメンターの加藤さん含めいろいろな方に質問しており、レビューでもたくさんの指摘をいただいているので、まだまだこれからも様々なことを吸収していきたいと考えています。 今後は通年インターンに切り替えて引き続きモノグサで働かせていただけるので、より良いサービス作りに貢献できればと思います。

Monoxer Intern Report #12_タスクの検索性改善

自己紹介

モノグサのソフトウェアエンジニアインターンに参加した山田です。現在は東京大学農学部でイネの研究をおこなう傍ら、ut.code();というプログラミングサークルでWeb開発をしています。

参加を決めた理由

私が今夏のインターンで達成したかった目標は以下の2つです。

  1. 個人開発やサークルでの開発からステップアップし、本格的な開発を学ぶ
  2. ソフトウェアエンジニアとして働くイメージをつけ、今後のキャリアを具体的に決める

モノグサのインターンでは、実際のプロダクト開発に関わる中でこれらの目標を達成し、自身の成長に繋げられると考え、参加することにしました。

取り組んだこと

記憶アプリMonoxerでは、学習者はタスク(課題)を使って学習しています。組織によっては大量のタスクを据え置き型で配信しており、多い場合には学習者あたり1,000件以上のタスクを抱えています。そのため、学習者が特定のタスクを探すには、タスク一覧画面で大量にスクロールをする必要がありました。

そこで本インターンでは、「Deep Link」と「タグ検索」という2つのアプローチでこの問題に取り組みました。

Deep Linkとは、ユーザを特定のアプリに遷移させ、指定したアプリ内コンテンツに誘導するリンクのことです。従来のMonoxerでは、Deep Linkを使ってアプリを直接開くことはできましたが、アプリ内の特定のコンテンツに誘導する機能はありませんでした。

そこで、アプリ側(iOS/Android)で、

という形式のリンクを踏むとアプリが開き、タスク画面に遷移する機能を実装しました。 管理者がDeep Linkを使って学習指示を行う方法としては、以下の2通りを想定しています。

1つは、Web管理画面上で生成したリンクを塾や学校等で用いている外部サービスで共有し、学習者にリンクをタップしてもらう方法です。 もう1つは、Web管理画面上で生成した二次元コードを印刷し、学習者に端末のカメラアプリから読み取ってもらう方法です。二次元コードは、node-qrcodeを使ってフロントエンド側で生成しています。

以前より、URLから直接タスクを開きたいという要望は複数寄せられており、確かなニーズがありました。本機能により、管理者はより簡単に学習指示を行えるようになり、学習者はスクロールせずに特定のタスクにアクセスできるようになりました。

タグ検索

もう1つのアプローチは、管理者がタスクにつけたタグ(例: #8/31日分宿題)を使って絞り込みを行う機能です。従来のMonoxerでは、Web管理画面上ではタグを使ってタスクを管理していましたが、アプリ側ではタグを活用できていませんでした。

そこで、アプリ側(iOS/Android)でもタスクについたタグを使って検索する機能を実装しました。具体的には、検索窓の横にある絞り込みアイコンを押すと、タグで絞り込むための画面が表示され、複数選択でタグを絞り込むことができます。 選択可能なタグ一覧を取得するにあたっては、2つの方法を検討しました。

1つは、APIサーバーにタグを取得するためのAPIエンドポイントを追加する方法です。 もう1つは、APIサーバーからタスク一覧を取得する際に、すべてのタスクからタグを重複なく抽出する方法です。

この判断は悩みましたが、APIエンドポイントをむやみに増やすべきではないこと、学習者あたりのタスク数が最大1,700程度でありパフォーマンスに影響しづらいことなどから、最終的には後者を採用しました。

本記事の執筆時はまだレビュー段階ですが、タグによる絞り込み機能についても根強いニーズがあり、もしリリースされれば、管理者による学習指示のやり方を大きく変えることになるのではないかと考えていて、楽しみにしています。

インターンの感想

本インターンでは、SwiftとKotlinを使う機会が多かったです。どちらもはじめて触れる言語でしたが、既存のコードや公式ドキュメントを読み、詰まったら積極的に質問していたため、思いの外、詰まることはほとんどありませんでした。そのため、未経験の開発言語の募集であっても、恐れずに突っ込んでもよいという学びがありました。

一方で、ソフトウェア開発全般の知識面では困ることがあり、開発効率という点でも、人より手戻りが多かったように思います。この部分に関しては、実務経験というより基本的な理解が不足していることが問題だと認識しています。コードを書けるようになるだけではなく、どうして動くのか、どうしてそう書くのかといった仕組みや原理に近い部分も理解する必要があると感じました。

また、取り組んだテーマの難易度やインパクトの大きさなどから、インターン生ながら責任感とやりがいを感じながら働くことができました。そのおかげで、期間中は終始楽しく開発ができ、あらかじめ設定していた目標も達成でき、非常に充実したインターンとなりました。 貴重な経験をさせていただき、ありがとうございました。

Monoxerに限らず、世の中には解決したい記憶にまつわる苦しみがまだまだたくさんあります。記憶の苦しみを一緒に解決したいという方は、ぜひ採用サイトをご覧ください! モノグサでは職種問わず一緒に働ける方を募集しています! careers.monoxer.com

モノグサキーボードの苦しみを解決した話

ソフトウェアエンジニアの狩野です。 Monoxerでは記憶を定着させるために、様々な形式での学習を提供しています。例えば、いくつかの選択肢の中から正解を選ぶような選択肢形式、問題に対してキーボードから回答を入力するような形式、手書きで漢字を回答するような形式などがあります。今回はその中から、キーボードを使って回答を入力する形式に関するお話です。

Monoxerで提供するキーボード

Monoxerでは回答を入力するために専用のキーボードを用意し提供しています。例えば英単語を入力するような問題では、次のスクリーンショットのようなキーボードが学習者に提供されます。

qwerty配列による英語キーボード
また日本語で回答するような問題に対しては、限定されたキーから回答を入力するようなキーボードが提供されます。
日本語を入力するキーボード
このキーボードは社内では「Monoxerキーボード」や「自由入力キーボード」「日本語入力キーボード」といった名称で呼ばれています。以降、本記事ではこのキーボードを「日本語入力キーボード」と表現します。 「OS標準のキーボードを使わないのか」と疑問に思う方もいるかもしれません。これは利用者の端末や環境に依存せず同じ学習体験を与えるためというのが大きな理由になります。Monoxerでは記憶をするために必要な体験を最適な形で提供しようと試みています。

日本語入力キーボードの苦しみ

日本語入力キーボードでは、正解を構成する文字の他に誤答候補となる単語の文字を配置しています。例えば「りんご」が正解となる問題の時には「りんご」の他に「ぶどう」や「みかん」の文字がキーボードに表示されます。こちらの誤答単語の生成についても非常に深い領域であり、インターン生に取り組んでいただくなどして機能の向上を図っております。詳しくはこちらの記事をご覧ください。 ここで次のスクリーンショットをご覧ください。

今現在は本画面のようにはなりません
同じ形の文字が複数表示されています。それぞれ伸ばし棒の「ー」と漢字の「一(いち)」なのですが、違いが分かるでしょうか? 仕様に詳しい人であれば「カタカナの後ろにあるやつは伸ばし棒のー」「漢字のキーの前にあるやつは漢字の一」だと予測することができるのですが、初見で遭遇した人は混乱してしまいます。もちろん入力するキーを間違えれば不正解となります。結果だけ見るとどこが間違っているか分からなく、納得感がありません。
どこが間違っているのか分からない
余談ですが、ここで取り上げたような似た文字に関する話題はMonoxer以外でも度々見かけられ、頭を悩ませる原因になる事も多いようです。
こんなにある

似た形の文字同士をペアにする

似た形の文字を考えてみると、実はそんなに種類が多くないことが分かります。

  • 伸ばし棒の「ー」と漢字の「一」と全角ハイフン「-」
  • カタカナの「ニ」と漢字の「二」
  • カタカナの「エ」と漢字の「工」
  • カタカナの「カ」と漢字の「力」
  • カタカナの「ト」と漢字の「卜」
  • カタカナの「ロ」と漢字の「口」

そこでMonoxerでは上記問題に対処するために、似た形の文字同士をあらかじめペアとして持つことにしました。その文字が解答に使われる際には、ペアのもう片方の文字をキーボードに採用しないキーのセットに追加します。そうすることで、似た形の文字は同じキーボードに表示されなくなるようになります。 今回は日本語に限定した対処としましたが、将来的に他言語での文字にも対応できるよう拡張しやすいコードを書くことなども行っています。既存のコードもとても拡張しやすいように書かれており、最小限の変更で機能を追加することができました。

これなら間違えようもありません
また余談にはなりますが、似た形の英語には既に対処されていたりします。大文字の「I(アイ)」と小文字の「l(エル)」は見た目上同じ形ですが、Monoxerでは大文字のI(アイ)の表示を変えることで見分けがつくようになっています。
大文字のI(アイ)と小文字のl(エル)の違い

学習の苦しみを解決する

以上のアップデートにより、学習で生じる苦しみが解決されました。モノグサでは、記憶にまつわる本質的な苦しみを100件解決することを2023年度の目標として掲げています。そして本件はその中の1つの事例となりました。 そしてMonoxerではキーボード以外にも、日々様々な領域で記憶にまつわる苦しみの解決が試みられています。そのすべてをこのような形で公開することは難しいですが、Monoxer アップデートブログを見ていただけるとある程度雰囲気が分かるかもしれません。

Monoxerに限らず、世の中には解決したい記憶にまつわる苦しみがまだまだたくさんあります。記憶の苦しみを一緒に解決したいという方は、ぜひ採用サイトをご覧ください! モノグサでは職種問わず一緒に働ける方を募集しています!

https://careers.monoxer.com/

競プロ部で第1回LT会を開催しました

SWEの@tobisatisより、競技プログラミング部の活動報告をお届けします。 部内で、初めてのLT会を開催しました。LTはlightning talkの略で、短い時間のプレゼンテーションを行うことをいいます。 今回は、4名の部員にひとり約10分で発表をしてもらいました。それぞれの発表について、簡単に紹介します。

競プロに特化したIDE

競プロに特化した自作IDEについて発表してもらいました。こちらに公開されています。

https://github.com/fukatani/rujaion

外観はこのようになっており、画面を切り替えず使える並列のレイアウトが印象的です。 発表では、例えば次のような機能について実演してもらいました。

  • サンプルケースの自動実行。手動で入力して目視で出力をチェックする、といった手間が省けます。問題数が多いAtCoder Beginner Contestなどでは特に便利に見えました。
  • 問題文の入力ケースからグラフを可視化する機能。数クリックで頂点とその番号、辺とその重みを描画できます。

上のリンクから、ぜひ他の機能もチェックしてみてください!

開発者fukataniからのメッセージ:

「現在、コード補完に使用しているracer-rustがdeprecatedになったことより、ビルド不能となっておりまして、代わりの補完ライブラリを導入にチャレンジしてくださる方、PRウェルカムです!」

C言語コンパイラ自作に取り組んでいます

C言語のコンパイルについて発表してもらいました。自作したコンパイラの話を通して、コンパイルの仕組みや言語によるパースの難しさの比較などがわかりやすく説明されていました。社内の他の部活の話やChatGPTの話も聞くことができました。

https://docs.google.com/presentation/d/1QK2N86194IaF855MTtSbLb6bdjxUsxszPceyZleOR5U/edit?usp=sharing

1万倍高速化

競プロにおける高速化について発表してもらいました。普段Rubyでコンテストに出られているプレイヤーならではの定数倍高速化の知見が、競プロ典型90問の1問を例に紹介されていました。タイトルは「1万倍高速化」。モノグサではRubyを1万倍高速化できる技術を習得できるかもしれません!

https://docs.google.com/presentation/d/1Oy6jQrn1mle_0iYOIJbpFp8-IU0WZYt76Lzf8B-b4o8/edit?usp=sharing

競プロ作問を支える技術

競プロの作問で活躍されているtsutajさんに、その難しさや便利なツールについて発表してもらいました。コンテストに出場しているだけだとわからない運営の作業を知る貴重な機会でした。

スライドはこちら↓

発表の様子

普段の活動としては、引き続きコンテスト後の感想や解法の共有を行っています。少しずつ部員数も増えていき、より活発になっています。

競プロ部の活動に興味を持たれた方、ぜひ一度採用サイトをご覧くださいませ!

https://careers.monoxer.com/

モノグサQAチームの立ち上げについて

こんにちは!やまもと@テスト番長です。今はモノグサでQAマネージャーをしています。 モノグサに参画してから10ヶ月ほど経ちましたので、これまでのチーム立ち上げについて振り返ってみたいと思います。

モノグサは「記憶を日常に。」をミッションとして掲げ、AI学習アプリを提供している会社です。 EdtechのQA事情については、先日公開したエントリをご覧いただけますと幸いです。

モノグサのQAチーム

モノグサのQAチームは2022年に発足しました。最初のQAEが入社したのが1年ほど前のことになります。 それ以前はSWEが実装からリリースまで全ての責任を負っておりましたが、プロダクトが巨大化・複雑化し開発チームの人数も増え、品質を保ち続けるためにQAEの採用が開始されました。 モノグサではQuality Management という部署の中にQAとE2E Test Automationがあり、QAは現在社員3名と業務委託スタッフ2名の体制で稼働しております。

モノグサにjoinして取り組んだこと

さて、モノグサに入ってまず取り組んだことは実情調査でした。Web開発の現場は色々経験してきておりますが、それぞれの現場の状況を知る事なくして正しいアプローチ戦略は立てられません。

最初の1ヶ月はオンボーディングメニュー(会社のルール説明を聞いたり開発環境を作ったり)を受けつつ、ステークホルダーを芋づる式に教えてもらい1on1を設定してペインポイントのヒアリングを実施しました。先に入社していたQAEメンバーからも色々と情報を教えてもらい、その結果、寄せられたお悩みを集約すると概ね以下のようになりました。

  • 開発者の不具合対応工数を減らしたい
  • QAは開発者個々の裁量に任されており、必ずテストされる仕組みがなく不安
  • ビジネスサイドからは開発の進行状況が分かりにくい

それらを受けて当面の方針案を作成することとしました。

  • リリース作業の巻き取り

開発者の作業負担を減らすためにリリース作業の巻き取りプロジェクトを始めました。Android/iOSアプリは2022年7月時点で巻き取り済みで、WEBとAPIのリリースが新たに対象となりました。システム上の制限とサービスポリシーの観点など調整事項が多かったため、こちらは現在も進行中です。

  • 開発プロセスにQAフェイズを明記する&実施する

開発プロセスのドキュメントにQAフェイズを段階的に追加していきました。

  1. リリース前リグレッションの明記

  2. 影響の大きな変更では着手前に召集してもらうように記載

  3. インテグレーションテストの実施を明記

結果、以前に比べ大きなトラブルは減ってきたようです。(古参スタッフ談) 現在のQAEの人数でカバーできる範囲は自ずと限られているため、体制を整えながら段階的にQAフェイズを拡充していく方針です。 今後は開発者テストとQAテストのレベル感合わせなど細かいところも詰めていくことにしています。

  • リリース情報の伝達フローを整理する

モノグサではリリース内容を事前に確約することはせず、リリースが終わってから周知するスタイルでずっと運営されています。 リリース内容はQAに回ってきた段階でほぼ確定しているので、可能な範囲でなるべく早くビジネスサイドに通知する運用フローを整備しました。 これによって、以前は散発的に発生していたビジネスサイドからのリリースについての問い合わせは減ってきました。

方針案ではエンジニアの負荷軽減を最大のフォーカスポイントと考えました。モノグサには優秀な開発メンバーが多く、工数的な余裕が生まれれば他の様々な問題も連鎖的に解決しそうだったからです。まだまだ十分には軽減出来ていませんが、今後も継続して推進して行きたいところです。

最終的に2023年内までの体制案とロードマップの形に落とし込み、立ち上がりの対応としてはひと段落しました。

新設されたQAチームがやるべきこととは?

既にサービス展開中のプロダクトチームに後からQAが入った場合どう動くべきか? 当たり前のことが多いですが、今回改めて感じたことを整理してみます。

  • リグレッションテストから入ると仕様理解が進む

リグレッションテストがあれば本番環境を最低限正常に動作するようキープすることが出来ます。入社して日が浅くプロダクトの仕様に不慣れなQAチームがシステムの全体像を掴んでいくためにも有効でした。 現在モノグサではリグレッションテストをNotion上で管理しています。かなりライトな管理方法ですが、将来的にE2E自動テスト中心への移行を見越してテスト管理システムなどはあえて入れずにやっています。

  • 負荷軽減を意識する

QAが新設されたということは品質に何らかの懸念があるわけで、その状況下では開発メンバーに相当負荷がかかっているケースが多いように思います。 不具合対応に費やす工数割合が多いと新規開発はなかなか思ったように進みません。市場不具合を減らしていく努力が必要です。 かといって単純にテストの工程を増やすと更に負担を増やしてしまいかねないので、工数を増やさず手戻りを減らせるように意識してプランニングしました。

また、BtoBのビジネスモデルにおいてリリース時期を予告しないスタイルは、顧客対応の難易度が高くなります。可能な限りの事前共有を行うことで、スムーズなサポートが可能になり開発・ビジネスサイド双方の業務負荷が軽減出来るのではと思っています。

  • プロダクトや会社の文化を理解しながらQA文化をデザインする

参画直後はどうしても会社の独自ルールが目につくものです。すぐに色々変えたくなりますが、しかしそれはそれなりの過去の経緯が存在するものなので、改善は慌てずに進めるべきです。 過去の時点の組織においてはそれがベストソリューションだったはず。たとえ標準と乖離していても非難されるべきではないのです。

  • 当たり前の水準を上げる

専任のQAが居なかった頃は検証周りの整備にリソースが割けないため、十分にチェックできる状況が整っていませんでした。 2022年7月時点では、対象OSの幅の広さに対して検証端末の数が少なく、主にエミュレーター上でデバッグすることが多かったようです。 とりあえず最初の3ヶ月で検証端末の台数を倍にしてもらいました。 検証環境のダミーデータも少なく、十分にチェックを行えない状況だったのでQAチームでどんどん作成していきました。 日々の備えがあってこそ、守れる品質の水準が上がります。

モノグサQAは最高に楽しい

モノグサのQAチーム立ち上げ話はいかがだったでしょうか?ここ数年、QAチーム立ち上げや一人QAの情報が多く発信されているようですね。QAの重要性に対する認識が広がってきて活躍の場が増えているのだとしたら、とても良いことだと思います。

モノグサは社員たちのオーナーシップが強く互いにリスペクトする文化があり、働き者が多いです。Valueに「いつでもボードゲームを遊ぶ余裕を持つ」とあるように、いつも誰かしらゲームで遊んでいる人がいる稀有で素敵な会社です。 QAチームの環境だけ見ても、どんなアプローチで品質向上に取り組むかは自由に考えられますし、アプリのリリースタイミングがQA主導であったり、開発者が協力的で検証に困ることがなかったり、かなり働きやすい環境だと思います。

モノグサにおけるQAの取り組みはまだまだこれからですが、今後は更に体制を強化して事業に貢献できるチームになっていきたいと思っています。 QAE絶賛募集中ですので、ご興味のある方はぜひご応募ください!

このブログ記事が何かのご参考になりましたら幸いです。

最後に:

記事は状況説明のために一人視点で書いてありますが、これら立ち上げのあれこれはモノグサのQMチーム全員で実現してきたことですので、メンバーのみなさまにも感謝を述べさせていただきたいと思います。 いつも一緒に働いてくれてありがとうございます!

EdtechアプリのQA事情

こんにちは!やまもと@テスト番長です。2022年の7月からモノグサでQAマネージャーをしています。 僕はこれまで20年弱くらいWeb系の会社でQAのお仕事をしてきているのですが、Edtechと呼ばれる教育系のジャンルはモノグサが初めてです。普通のスマートフォンアプリと結構違うところがあって、毎日面白いなと関心しながら仕事をしています。

折角ですので今回はEdtechならではのQA事情をご紹介してみたいと思います。

続きを読む

AHC019 に参加してみた

ソフトウェアエンジニアの杉江(AtCoder ID: tsutaj)です。

2 年ほど前から、プログラミングコンテストサイト「AtCoder」でヒューリスティックコンテスト(通称:AHC)が開催されています。どんなコンテストなのか簡単に説明すると、最適解を出すことが難しい問題に対して、できるだけ良い解を出すプログラムを期間内に作成するコンテストです。

先日 MC Digital プログラミングコンテスト2023(AtCoder Heuristic Contest 019) に参加して、結果は 89 位(正の得点を得た 737 人中)でした。どんな解法になったのか書いていきます。

この記事を読んでヒューリスティックコンテストに興味が出ましたら、ぜひコンテストにも参加してみてください!

問題概要

atcoder.jp

三次元物体を正面から見たシルエット・右から見たシルエットが 2 組与えられます。 1 \times 1 \times 1 の立方体を面同士でくっつけてできるポリキューブ状のブロックの集合をひとつ決め、それらのブロックを使って正面・右シルエットが完全一致するようなポリキューブの配置を求めてください。同じブロックの集合を使って 2 組のシルエット両方について完全一致できる必要があります。

(ざっくり言うと)できるだけ大きく、できるだけ少ない数のブロックの組み合わせで実現できると高い評価が得られます。片方のシルエットの組でしか使われず、もう片方では使われないブロックが存在しても良いですが、そうするとスコアが減点されてしまいます。

自分の解法

一言で言うと「力まかせに答えを見つける」という解法で、条件を満たすまでランダムにポリキューブを決めて配置することを繰り返します。ですが、闇雲に探索をしても良いスコアにはならないため、いろいろ工夫しました。

配置するポリキューブのサイズを制限する

 N 個の立方体からなるポリキューブは何種類あるか考えてみます。以下の表は Wikipedia の記事 から引用したものですが、 N が大きくなると爆発的に増えるようです。(今回は鏡像を区別するので左側の列が参考になります)

このことから、サイズ 5 までのポリキューブに限定して探索することにしました。適当にはめていくだけで本当に解が作れるの?と思われるかもしれませんが、意外と作れます。

しかしこれに限定して探索しただけだと、当然ですが得られる解にはサイズ 5 までのポリキューブしか登場しません。より大きなポリキューブも欲しいので、シルエットの条件をある程度満たしたらポリキューブをマージしたり伸ばしたりすることで、より大きなポリキューブになるようにしました。その操作をしたあとに、解として正当な状態になっていれば OK です。

ちなみに、上位陣の解法を見ていると、ポリキューブの形状と位置を決めてから配置できるか試すのではなく、各シルエットについて適当に始点を決めて、始点から伸ばせるだけ伸ばしている方がちらほらいました。私は「この方針だったらブロックの大きさのバランスが取れないだろう」と思って捨ててしまいましたが、うまくやるとできるんですね。。。

条件を満たしたら、解を部分的に破壊する

最終日の前日まで、私の解法は「正当な解を求めることを繰り返す」ものでしたが、正当な解がひとつ得られたあと、それを完全に忘れてまっさらな状態でもう一度探索を始めていました。解が得られるまでに割と時間がかかることもあってこれでは非効率的です。

そこで、正当な解が得られたあとは部分的に破壊して、途中から再度探索するようにしました。ポリキューブのサイズが最も小さいもの(複数ある場合はどれか 1 つ)を選んで、それ自身とその周囲にあるものを消すことで部分的破壊をしました。サイズの小さいポリキューブを除去した状態からまた探索できるので、これを実装するだけで順位表上のスコアが約 1.25 倍になりました。

解を部分的に破壊しているため、状態の近傍(少し変化させた状態)を取っています。上位の解法を見ていると、ざっと見ただけでも他に以下のような近傍のとり方があるようです。とても勉強になりました。

  • ポリキューブの平行移動
  • セルの譲渡(一方で使用していた領域を、隣接している他方のポリキューブに譲る)
  • 取り除いても解の条件を満たすようなセルの削除

高速化

探索がどれくらい回るのかは解法の性能に直結します。多く回れば回るほど良いです。そのため、どのコンテストでも高速化は重要になります。今回もたびたび高速化に迫られました。

私は Rust でコンテストに参加していますが、flamegraph でボトルネックを見つけるのをよくやります。処理時間全体に対して各処理がどれくらいの割合で行われているかがわかるので、幅の大きい部分を重点的に直していきました。

高速化にたびたび効いたのは Zobrist Hashing でした。各座標に乱数を事前に割り振っておき、ポリキューブ(の位置を正規化したもの)が占める座標に対応する乱数の XOR を取ることで、ポリキューブ同士が同型かどうか判定しました。Zobrist Hashing については以下の記事を参考にしました。

trap.jp

同型なポリキューブのペアについて、座標と回転方向のマッピングができればハッシュを使わなくても処理が出来るかとは思いますが、複数の方向で同型になる場合があったり、ペアの入れ替えをしたくなったりしてどうも納得いくものができず、結局ハッシュにずっと甘える形になりました。。。どこかで表現度を落としてでも高速化に振り切ってもよかったかもしれません。

解法まとめ

自分の解法を簡潔にまとめると次のようになります。やっていること自体はシンプルですが、実装はそこそこ大変でした。

最終提出へのリンク

焼きなまし法の適用

コンテスト後に「解を部分的破壊しているところは近傍選択っぽいし、焼きなまし法にできるのでは?」とふと思ったので、やってみました。

今までの解法は「常に解を採用し、それを部分的破壊して次の探索に進む」というもので、貪欲に解の生成を繰り返しているだけでした。これを次のように変えてみました。

  • 解が良くなったら常に、解が悪くなったら確率的に採用したのち、それを部分的破壊して再開する。採用しない場合は最後に部分的破壊を行った状態から再開する。
  • 不採用が一定回数続いた場合、何も置いていない状態から再度探索する。

こうすることで、手元で 1000 ケース回したときのスコア平均が 6% ほど改善しました。近傍を増やしたり、温度を調整したりするとさらに伸びるかもしれません。焼きなまし法にもっと慣れていきたいですね。

焼きなまし法を適用した提出へのリンク

さいごに

この問題の答えを人力で見つけるのはかなり大変だと思います(というか自分には無理です)。ですが、自分が書いたプログラムに任せればいい感じの答えが見つかります。自分の書いたプログラムで、自分には不可能なことが可能になる点が、ヒューリスティックコンテストの面白さのひとつだと感じています。

最終日の前日までスコアが思うように伸びず挫けそうにもなりましたが、粘り強く考えて最後にいい手法が思いつけてよかったです。とはいえまだまだ伸びしろは十分なので復習したいですね。

モノグサでは、記憶のプラットフォーム「Monoxer」を全人類に届けることを諦めない、粘り強いエンジニアを募集しています!!

careers.monoxer.com