情報処理学会研究報告
IPSJ SIG Technical ReportOJS 内のデータを利用したユーザへの効率的なアルゴリズム
要否の提示
柴田 敦也1,a)

須藤 克仁1

畑 秀明1

中村 哲1

概要：ソフトウェア開発において効率的に動作するアルゴリズムの選択が重要となる場面が存在するが，全てのソフトウェアに効率的なアルゴリズムが採用されているとは限らない．そこで本稿では，ユーザのプログラム記述に対して，より効率的なアルゴリズムが存在する場合に自動的に実装の推薦を行うために必要な技術/手法について検討する．本研究では効率的なアルゴリズム実装の推薦を，1. ユーザのソース
コード中の非効率的なアルゴリズムの有無の検出，2. 検出した非効率的なアルゴリズムに対応する，効率的なアルゴリズムの選択，3. 効率的なアルゴリズムをユーザの元のソースコードに近い形に整形して提示の 3 つの課題に大別した．本稿では 1 の課題をプログラムの非効率的/効率的分類問題として定式化し，オンラインジャッジシステム（OJS）上に提出されたソースコードに基づく機械学習手法について検討した．
キーワード：オンラインジャッジシステム, ソースコード推薦, プログラミング言語処理, 機械学習

Suggesting the Necessity of an Eﬀective Algorithm using Data on
Online Judge System
Abstract: The use of eﬃcient algorithms is important in software development. However, it is not necessarily true in practice. In this paper, we pursue a method that automatically suggests an eﬃcient algorithm
for user’s source code when such an algorithm is available. In this work, we divide the problem into three
sub-problems: 1. Detecting ineﬃcient algorithms in user’s source code; 2. Choosing an appropriate algorithm
for detected ineﬃcient algorithm; 3. Suggesting an eﬃcient source code that can be adapted to user’s sourcecode easily. In this paper, we formulate this problem as a binary classification problem of the eﬃciency andtackle it with a machine learning method based on submitted source code on an online judge system.
Keywords: Online Judge System, Code recommendation, Programming language processing, Machinelearning

1. はじめに1.1 背景重要性が増している．例えば，ネットワークシステムにおけるルーティング処理はアルゴリズムの知識が必要となる
身近な例である．しかし，全てのプログラマが多種多様な仮想化技術実現のためのサーバ集約によるシステムの大アルゴリズムに精通し，それぞれの問題に対して適切なア

規模化や，ハードウェアの複雑化が進んでおり，高難易度

ルゴリズムを適用・実装することは決して容易ではない．

化するソフトウェア開発を支援するシステムの需要が高ツールによりプログラミングを支援する既存技術の一つとまっている．また，人工知能・IoT 技術への期待の高まり

してコード補完があるが，これはすでにユーザに入力されによって，ソフトウェア開発に複雑なアルゴリズムを要求た内容の文脈に沿ったコードを補完することで効率化を図

される場面が増加しており，アルゴリズムに関する知識のるものであり，ユーザの知識以上に高度なプログラムを作成することはできない．そこで本研究では，処理速度が高1a)

奈良先端科学技術大学院大学 情報科学研究科
Nara Institute of Science and Technology, Information science , Ikoma , Nara, 630-0192, Japan
shibata.atsuya.ry3@is.naist.jp

c 2018 Information Processing Society of Japan⃝

速である，あるいはメモリをはじめとする計算資源の使用量が少ない処理を効率的な処理と定義する．そして，ユーザの作成したプログラムに対して，より効率的なアルゴリ

1情報処理学会研究報告
IPSJ SIG Technical Report

ズムが存在するかを判定し，存在するならばより効率の良

ソフトウェア内に非効率的な処理がある場合，具体的

い実装例の推薦を行うことを最終的な目的とし，そのためにどういったアルゴリズムであるかを判定（図 1 のの課題解決を目指す．

2）．

ここで，非効率的なアルゴリズムがソフトウェアに採用( 3 ) 効率的なアルゴリズムをユーザの元のソースコードにされる原因について考える．プログラマが解決すべき問題

近い形に整形して提示に直面した場合，プログラマは書籍や Web 上に存在するリ

効率的なアルゴリズムに該当するオンラインジャッジ

ファレンスを参照して最も効率的なアルゴリズムの実装をシステム内のソースコードに対して，ソフトウェア内行えばよい．しかし，実装者の技量の不足や，効率性といのソースコードと対応する処理単位の切り出しや，ソう観点の欠如，開発期間に制限があり実装するソースコー

フトウェア内のコードとの変数名の統一（図 1 の 3）．

ド量の増加を避けたいといった場合等に，非効率的なアルゴリズムが採用されうる．
次に，同じ問題を解決するが処理時間などの観点で効率の異なるアルゴリズムの具体例を挙げる．例として，文字列検索などに応用される Suﬃx Array（接尾辞配列）を作成するためのアルゴリズムについて考える．この問題を解く最も効率的な方法として，SA-IS と呼ばれる時間計算量
が O(|S|) となるアルゴリズム（|S| は対象文字列の文字列長）[1] が知られている．しかし実装が非常に複雑であるこ図 1 本研究で対象とする問題とを理由に，計算量の観点で非効率的なアルゴリズム（ナイーブな O(|S|2 log |S|) アルゴリズムや O(|S| log2 |S|) ア

効率性の評価とプログラムの等価性の評価を行うことがルゴリズム [2]）が代替として用いられているケースが存在

できればこれらの問題は比較的容易に解決可能だが，これする．このように，ソフトウェアに非効率的なアルゴリズ

らは非常に困難な問題である．例えば，2 つのプログラム

ムが含まれる場合，ソフトウェア開発を行うユーザに対しが等価であるためには，任意の入力において両プログラムて，より効率的なアルゴリズムとその実装を推薦できれば，の出力が同じでなければならない．またプログラムの効率

効率の良いソフトウェアを容易に作成することができる．

性を比較するためには，一部の値だけでなく多種多様な値

本研究では上記のような効率的なアルゴリズムの推薦を入力とし，実行速度などの評価を行う必要がある．しかを，1. ユーザのソースコード中の非効率的なアルゴリズム

し，プログラムへの入力の組み合わせは膨大であるため，の有無の検出，2. 検出した非効率的なアルゴリズムに対応

ソースコードの情報のみからプログラムの等価性や効率性

する，効率的なアルゴリズムの選択，3. 効率的なアルゴリを厳密に評価することは困難である．また，一般にソフト

ズムをユーザの元のソースコードに近い形に整形して提示

ウェアは複数のプログラムからなり，ソフトウェアごとにの 3 つの課題に大別した．本稿では，ソースコード中のア

ビルド・実行を適切な手順で行う必要がある．このため，ルゴリズムの効率性の評価は困難であるが，ユーザへの効

様々なソフトウェアを機械的にビルド・実行し，動作を動率的なアルゴリズムの推薦には欠かせない課題であること的に検証することは非常に困難である．

から，1 の課題について検討を行った．

この技術の実現のため，本稿では 1 の課題に注目し，ユー
ザのソースコード中に非効率的な処理が含まれているかを

1.2 本研究で対象とする問題

判定し，含まれていれば効率性改善の余地があることを通本研究では，ソフトウェア内に含まれるソースコード中

知可能とする．これにより，実際のソフトウェア開発におの非効率な処理を，動的なソフトウェアの実行・ビルドないてプロダクト内のソースコード中から，非効率な処理をしに検出し，同様の処理を実現する効率的なソースコード

行っている可能性のあるソースコードを発見することがで提示によるユーザ支援を目的とする．この問題は，大きくきる．本稿ではこれらの問題を解決するにあたり，オンラ

分けて以下の 3 つの課題からなる．

インジャッジシステムに提出されたソースコード群を利用( 1 ) ソフトウェア内から非効率的な処理を行うソースコー

した．オンラインジャッジシステムを利用するメリットとドの検出して，汎用的なアルゴリズムを実装したコードが多数存在

ソフトウェア内で非効率的な処理が利用されているかすること，提出された全てのソースコードが動的なソフトを判定することで，効率的なアルゴリズムの推薦が必ウェアテストにより機能・性能を検証済みであることなど

要であるか不要であるかを確認（図 1 の 1）．

が挙げられる．このメリットは，一般にソフトウェアの動( 2 ) 非効率的なアルゴリズムに対応する，効率的なアルゴ
リズムの選択c 2018 Information Processing Society of Japan⃝

的な検証は困難であるという問題を解決可能であり，本稿でオンラインジャッジシステム上のソースコードをデータ

2

情報処理学会研究報告
IPSJ SIG Technical Reportとして利用する最大の理由である．

2. 関連研究2.1 コード補完
ユーザの入力したソースコードに対してソースコードを提示する試みの一つとして，コード補完が挙げられる．これは，同じコーパス内ですでに宣言されている変数名をタイプする際に，その一部をタイプするだけで該当変数名の提示を行ったり，入力したクラスのもつメンバ関数の一覧の提示を行う技術である．この技術は，ユーザのミスタイ
プの発見・訂正や，タイピング数の削減を支援することでプログラミングに必要な時間を短縮することができる．実
現のためには，N-gram に基づいた言語モデル [3], [4] が多く利用されている．また，近年では深層学習を用いて言語モデルを作成する研究 [5] も存在する．コード補完は，ユー
ザに入力された文脈に沿ったコードを提示することで効率化を図るものであるが，ユーザの知識以上に高度なプログ
ラムを作成することはできない．一方，本研究はユーザーの知識以上の効率的なアルゴリズムを提示する点でコード補完とは異なる．

2.2 プログラミング学習者向けソースコード提示
オンラインジャッジシステムでプログラミング学習を行うユーザ（以下学習者）の不正解であるソースコードに対して，正解したソースコードのうち類似のアルゴリズムを用いたものを提示することで，学習を支援する研究が存在する [6]．オンラインジャッジシステムには過去に提出されたソースコードが保管されており，学習者は他の学習者の正解したソースコードを閲覧できる．しかし，上級者による理解の困難なソースコードを閲覧しても，自力で理解し解答までたどり着くことは困難である．また，同じ問題を解くソースコードであっても実装方法は多彩であり，学習者と同じアルゴリズムを用いて正答しているソースコー
ドを参考にすることが重要である．そこで，不正解となった他の学習者が正解となるまでに辿った道筋を分析する．
そして，学習者のソースコードと同様のアルゴリズムが用いられたソースコードを，正解への道筋に従って漸進的に提示する．
学習者と同じアルゴリズムを用いているソースコード判
別のため，この研究では N-gram IDF[7] を指標とした階層クラスタリングによる分類を行っている．N-gram IDF
では任意の長さの単語列に重み付けすることができ，テキスト内の特徴的な単語 N-gram を抽出できる．正解への道
筋は，オンラインジャッジシステムに保管されている提出履歴を用いて抽出する．この研究の適用対象はオンライン
ジャッジシステムを利用する学習者であり，一般のソフト
ウェアへの適用でない点が本研究とは異なる．

c 2018 Information Processing Society of Japan⃝

3. 非効率的なアルゴリズムと効率的なアルゴリズム
3.1 アルゴリズムの効率性の評価
アルゴリズムの汎用的な評価方法の代表的なものとして，オーダー記法による時間計算量および空間計算量を用いた評価が挙げられる．本研究ではこの時間計算量および空間計算量を軸として，ソースコードおよびアルゴリズムの効率性を評価する．

3.2 同一問題を解く効率の異なる複数のアルゴリズム
同一，あるいは類似の問題を解くアルゴリズムが複数存在し，かつ時間計算量や空間計算量が異なる場合が多数存在する．ここでは例として 最短経路問題を解くアルゴリズ
ムを考える．最短経路問題を解くアルゴリズムにも様々な種類がある．dijkstra 法，bellman-ford 法， floyd-warshall法などがその例である．頂点数を |V |，辺の数を |E| としたときの各アルゴリズムの時間計算量は，dijkstra 法はO(|V |2 ) の計算量，dijkstra 法に二分ヒープを用いることでO(|E| · log |V |) の計算量，bellman-ford 法は O(|E| · |V |) の計算量，floyd-warshall 法は O(|V |3 ) の計算量となる．計
算量の観点では頂点数および辺の数の条件によらず，常に二分ヒープを用いた dijkstra 法を利用すべきである．しかし，必ずしも bellman-ford 法や floyd-warshall 法が劣っているとは言えない．何故ならば表 1 に示すように，dijkstra
法はコストが負の辺があるグラフに対して正しく最短経路を求めることができないからである．つまり，負の辺を含むグラフでの最短経路問題に対して bellman-ford 法を使用しているソースコードを検出しても，時間計算量の優れる dijkstra 法への置き換えは不可である．なお，負の辺を含まないグラフに対して bellman-ford 法を使用している
場合は，もちろん dijkstra 法へ置き換え可能である．このように，時間計算量が優れていても置き換え不可である場
合が存在するが，本研究では適用不可能である場合は提示後にユーザが棄却することを期待し，考慮から外すものとする．

4. オンラインジャッジシステムの性質
本稿では非効率的なソースコードであるかそうでないかを判定するため，オンラインジャッジシステム上のソース
コードを利用する．本節では，オンラインジャッジシステ
ムの特徴と利用する場合のメリットについて述べる．

4.1 オンラインジャッジシステムとはプログラミング教育の一環として，プログラミングに競争の要素を導入することで意欲の向上を目的とした，プロ
グラミングコンテストが多く開かれている．プログラミン
グコンテストには種類があり，自然言語によって記述され3

情報処理学会研究報告
IPSJ SIG Technical Report
表 1 最短経路問題を解くアルゴリズムの比較
アルゴリズム

時間計算量

コストが負の辺

dijkstra 法（二分ヒープ不使用）

O(|V | )非対応

dijkstra 法（二分ヒープ使用）

O(|E| · log |V |)非対応

2bellman-ford 法

O(|E| · |V |)対応

floyd-warshall 法

O(|V |3 )対応た問題文が仕様として与えられ，その問題の解答プログラとなった具体的な入出力については報告されない．

ムをいかに正確かつ短時間で作成することができるかを競うコンテスト [8] や，いかに実行速度の高速な解答プログ
ラムを作成することができるかを競うコンテスト [9]，いかに少ない文字数の解答プログラムを作成することができるかを競うコンテスト [10] 等がある．有名なプログラミングコンテストとして，計算機科学分野の学会である ACM の主催する大学対抗コンテストである ACM-ICPC（1979〜）
や，国際科学オリンピックの一つである情報オリンピック（1989〜）等がある．
プログラミングコンテスト環境のうち重要な要素の一つとして，参加者によって提出されたソースコードの正確さを自動的に検証するシステムが挙げられる．このシステム
は，事前に決められた入力を用いて実行を行い，その結果に基づいて提出された解答の正確性を評価する．また，提出されたソースコードが規定リソース使用量（実行時間や使用メモリなど）を超えていないことも確認する．行われた評価に基づいて，全参加者のランキングが計算され，コンテスト実施中にリアルタイムで表示される．この，ユーザのソースコードをコンパイル・実行することで，プログ

図 2 オンラインジャッジシステムの仕組み

例として，提出したソースコードが正誤判定によって実行時間超過と判定されるまでの流れを述べる．ここでは，

4 つの入出力ケースに対して正しい答えを 5,000ms（5 秒）以内の実行時間で解答することが求められる場合として，
図 3 の状況を考える．オンラインジャッジシステムは 1

ラムの正確性の評価を自動的かつリアルタイムに行うシス
テムがオンラインジャッジシステムである．

4.2 オンラインジャッジシステムの仕組み
オンラインジャッジシステムは，ネットワーク上のサー
バプログラムとして用意される図 2 のようなシステムで，コンテスト参加者から提出されたプログラムに対して正誤判定を自動で行う．システムは正誤判定のために入力デー
タとその入力データに対する正解出力を入出力ケースと図 3 正誤判定の流れして用意し，システム上に保管しておく．コンテスト参加
者はプログラムを完成させると，ソースコードをシステム

つ目の入出力ケースから順に正誤判定を行う．その入出力に提出する．システムはユーザのソースコードをコンパイ

ケースにおいて出力および規定リソース使用量に問題がな

ル・実行し，用意された入力データを入力として与える．

ければ OK と判定し，同様に 2 つ目，3 つ目の入出力ケー

このときの出力を正解出力と比較することで，システム

スへと進む．3 つ目の入出力ケースのように出力は正しい

は正誤を判定する．正誤判定では，出力結果の正しさの評が規定実行時間を超過している場合や，そもそも出力が正価のみならず，コンパイルエラー，実行時エラー，規定リしくない場合などはその場で不正解となり，それ以降の入ソース使用量超過の有無（非効率的なアルゴリズム使用に出力ケースは実行されない．今回の例では規定実行時間超

よる実行時間超過・メモリ使用量超過など）についても評過により TLE（Time Limit Exceeded）と判定されている．

価し，全ての項目において問題がない場合にのみ正解と評全ての入出力ケースにおいて OK と判定された場合は価する．なお，オンラインジャッジシステムは主にコンテ

Accepted に，図 3 のように判定中に不正解となった場合はストでの使用を目的としているため，誤りの詳細や不正解

不正解と判定される．不正解にも種類が複数あり，出力が正しくないことを示す Wrong Answer，出力は正しいがメc 2018 Information Processing Society of Japan⃝4

情報処理学会研究報告
IPSJ SIG Technical Report

モリの規定使用量を超過したことを示すは Memory Limit

グ言語の構文を満たす一つのソースコードであり，出力はExceeded，出力は正しいが規定実行時間を超過したことを「非効率的なアルゴリズム」あるいは「効率的なアルゴリズ

示す Time Limit Exceeded などがある．

ム」であるという判定結果である．分類にはロジスティッ

オンラインジャッジシステムにおいてどのような入出力

ク回帰を用い，教師データとしてオンラインジャッジシス

ケースを用いてソースコードの正誤判定を行うかというの

テム内のソースコードを用いる（詳細は 6.1.1 項に後述）．

も非常に重要な問題である．例えば，足し算の繰り上がり

本稿では 5.2 節に示すように，ソースコードを構成する文にバグのあるプログラムを誤答と見抜くためには、繰り上字列から得られる様々な特徴量を用いた分類を行う．分類

がりの発生する入出力ケースが含まれている必要がある．

問題の評価には分類精度（classification accuracy），再現また，非効率的で規定実行時間を超過しうるプログラムを率（recall），適合率（precision）などの指標があるが，本研誤答と見抜くためには、効率性によって大きな差が生まれ

究では分類精度と適合率に注目して評価を行う．本研究でる巨大な入出力ケースが含まれている必要がある．この問は特に，非効率的なソースコードが正しく非効率的だと判

題は処理可能な値の全ての組み合わせを入力として試すこ別される（True Positive の値が大きい）こと，また効率的とで回避可能だが，この組み合わせは膨大である．しかし、なソースコードが誤って非効率的だと判別されない（False

オンラインジャッジシステム内の各問題には問題作成者にPositive の値が小さい）ことが重要であるため，適合率がよって用意された誤りのあるプログラムを正解としないた

高いことがより重要である．表 2 のように分類結果を定義

めの多様な入出力が用意されており，信頼性の高い正誤判

すると，分類精度は式 1 で，適合率は式 2 で表される．
TP + TN
classif ication accuracy =(1)
TP + FP + FN + TNTP
precision =(2)
TP + FP定が行われている．

4.3 オンラインジャッジシステムに保管されるソースコー
ドの特徴
本稿では，ソフトウェア内から非効率的な処理を行う

5.2 特徴量

ソースコードの検出を行うためにオンラインジャッジシ

ソースコードが効率的か否かを判断するため，各ソース

ステム内のデータを利用する．オンラインジャッジシステ

コードの文字列的特徴および構造的特徴を特徴量として利ムに提出されている全てのソースコードは，検証用入出力

用する．表 3 に，利用する特徴量の一覧を示す．なお，分ケースや検証器を用いて正確さと性能がすでに検証されて類の際に各特徴量の値は 0〜1 の値に正規化して利用している．今回利用する AOJ（Aizu Online Judge）[11] にはいる．

1000 問以上の問題が収録されており，300 万以上のソー5.2.1 N-gram IDF 特徴量

スコードが提出されている．これだけの量の動作や性能が2.2 節に示した関連研究でも使用されていた，N-gram

検証されたソースコードが存在することは，オンライン

IDF を特徴量として用いる．この特徴量により，ソース

ジャッジシステム特有の大きなメリットである．また，多コード中のトークン N-gram による表層的な特徴を分類にくのオンラインジャッジシステムはアルゴリズムの習得を利用可能とする．ソースコード全体から N-gram IDF 値の目的としたものであり，さまざまなアルゴリズムを要求す

高い，特徴的な単語 N-gram（N ≤ 5）のリストを作成し，る問題が揃っている [12], [13]．そのため，本研究の目的で各ソースコードでの各単語 N-gram の出現回数を特徴量とある，非効率的なアルゴリズムによる処理の検出を行うたして用いる．N-gram IDF 値の計算には，N-gram IDF にめのデータとして利用する上で適切であると考えられる．

関する論文 [7] の著者である Shirakawa らが開発している

5. 機械学習による非効率的な処理の検出
本節では，5.1 節で分類問題の定義について，5.2 節で各
特徴量の詳細とソースコードからの抽出方法について述
べる．

ツール，N-Gram Weighting Scheme[14] を用いる．なお，
前処理として各ソースコード中の大文字を全て小文字に変換する．

5.2.2 コード中で宣言された変数の型特徴量
ソースコード中で宣言された変数，およびデータ構造を特徴量として用いる．この特徴量により，アルゴリズムの効率

5.1 非効率的/効率的なアルゴリズム分類問題の定義性を分ける要因の一つである，データ構造の情報を分類に利1.2 節で述べたように，本稿ではユーザのソースコード

用可能とする．この特徴量は，ANTLR（ANother Tool for

中の非効率的なアルゴリズムの有無を検出する課題を解決

Language Recognition）[15] を用いて作成した C++パー

する．そのためのアプローチとしてこの課題を，特定のアサによって変数の宣言部を検出することで抽出する．

ルゴリズムを含むソースコードに対して「非効率的なアル5.2.3 制御構文によるネスト特徴量

ゴリズム」を含むか「効率的なアルゴリズム」を含むかを

ソースコード中の最も深いネストの深さ，および制御構判定する 2 値分類問題と定義する．入力はプログラミン

文によるネストからなるスコープの個数を特徴量として用

c 2018 Information Processing Society of Japan⃝5

情報処理学会研究報告
IPSJ SIG Technical Report
表 2 混同行列の例
Label
非効率的

Predict

非効率的True Positive(TP)False Positive(FP)

効率的

False Negative(FN)

True Negative(TN)表 3 使用する特徴量
特徴量

効率的

概要

おり（正誤判定については 4.2 節参照），なおかつ規定実行時間を超過しているソースコードを非効率的なアルゴリ

Ngram IDF

各単語 N-gram-IDF の出現回数

variable type

コード中で宣言された変数の型

depth of max nest

制御構文による最も深いネストの深さ# of nest

深さ 1 以上の独立なネストの数として採用する際に正解率の条件を考慮するのは，単に無# of for

コード中の for ループの数

限ループなどを含みそもそも最短経路問題を解けていない# of while

コード中の while ループの数

ソースコードを教師データに含めないためである．なお，# of if

コード中の if 文の数

ここでは提出数の多さを理由として C++で記述されていズム，正解率が 100%であるようなソースコードを効率的なアルゴリズムとし，作成した．非効率的なアルゴリズム

るソースコードのみを対象とした．結果として得られた教いる．この特徴量により，計算量のボトルネックとなることの多い，処理の中心となるループを検出し，分類に利用可能とする．この特徴量は，自作の簡易的な構文解析器により for 文・while 文・if 文 などの制御構文を検出することで抽出する．

5.2.4 制御構文特徴量
ソースコード中の for 文・while 文・if 文といった制御構文の出現頻度を，特徴量として用いる．この特徴量により，アルゴリズムの概形を表現する制御構文が，それぞれどれほど使用されているかを検出し，分類に利用可能とす
る．この特徴量は，N-Gram Weighting Scheme[14] の機能を用いてソースコードをトークナイズし，各制御構文の出
現回数をカウントすることで抽出する．

6. 評価実験
本節では，オンラインジャッジシステムのデータを用いてソースコードの非効率的/効率的を判定する手法の評価を行う．評価には，オンラインジャッジシステム上のソー
スコードを対象とした実験を用いた．

6.1 オンラインジャッジシステム内ソースコードからの非効率的な処理の検出

6.1.1 実験設定
ソースコード中の非効率的なアルゴリズムを検出する手法の評価のため，オンラインジャッジシステム上のソース
コードを対象とした実験を行った．オンラインジャッジシ
ステム上のソースコードは，実行時間や正確さが評価されている．本実験では対象とする問題を最短経路問題に限定し，非効率的/効率的 のラベルのついたソースコードを教師データとした，効率的/非効率的 をロジスティック回帰により判定する 2 値分類器を設計した．
次に，教師データの詳細について述べる．オンライン
ジャッジシステム上の最短経路問題を解くソースコードの
うち，少なくとも前半 50%のケースで OK と判定されてc 2018 Information Processing Society of Japan⃝

師データの情報を表 4 に示す．
本節では，2.2 節の関連研究を参考に N-gram IDF のみ
を特徴量としてロジスティック回帰で分類を行ったもの
をベースライン手法，表 3 に示す特徴量を用いてロジス
ティック回帰で分類を行ったものを提案手法とし，それぞれ 5-fold の交差検証で性能を評価した．また，ロジス
ティック回帰の正則化には L2 正則化を用い，正則化パラ
メータ λ = 0.5 とした．利用するソースコードに対し前処理として，コメントアウト部分の除去・#include 文の除
去・#define マクロの置換 を行った．

6.1.2 実験結果と考察
本項では，6.1.1 項で述べた設定で実験を行った結果を示す．結果は 30 回試行の平均の形で，表 5 に示す．ベー
スライン手法に対して提案手法がわずかに高い平均適合率と平均分類精度を示しているが，有意差は認められなかった．いずれの実験も学習データにおける分類精度は100%であったことから，学習データへのオーバーフィッ
ティングとみなせる．
ここで，実験プログラムにおける乱数のシード値を固定したときの，それぞれの手法において重みの絶対値の大きい素性を表 6，表 7 に示す． ベースライン手法においても提案手法においても，分類において N-gram IDF 特徴量が非常に有効に作用していることがわかる．特筆すべき
は，ベースライン手法では「dijkstra r」という 2-gram が分類に有効であるが，一方提案手法では上位 10 件に登場していない点である．この 2-gram は，ソースコード中の「dijkstra( r )」という，問題文中で始点となる頂点を表す
変数 r を引数とした dijkstra 関数の呼び出しに相当する．
一見これは効率的なアルゴリズムを判別する有効な特徴量
であるが，表 1 に示すように dijkstra 法には 2 つの種類が存在し，二分ヒープを使用しない dijkstra 法の場合は効率的なアルゴリズムと言うことはできない．その点二分ヒー
プ（C++では priority queue コンテナ変数）の存在を考慮

6

情報処理学会研究報告
IPSJ SIG Technical Report
表 4

教師データの情報

件数

割合

備考

非効率的なアルゴリズム

166 件

24.9%

TLE かつ正解率 50%以上

効率的なアルゴリズム

501 件

75.1%

Accepted

表 5

実験結果

手法

平均適合率

平均分類精度

最低 - 最高分類精度

標準偏差

ベースライン

69.75%

81.72%

80.30% - 83.46%

0.0073

提案手法

69.80%

82.01%

80.45% - 83.31%

0.0078

ケースを，提案手法では非効率的であると分類しているこ

表 6 ベースライン手法において分類に有効な特徴量上位 10 件
特徴量のタイプ値

係数とがわかる．以下に，該当するソースコードの一部を添付する．

N-gramif update-0.936

N-gram1 break

0.631

N-gram

min c

0.609

1

u s i n g namespace s t d ;N-grami push back

0.516

2

typedef long long int

N-gramcs-0.5123t y p e d e f p a i r <i n t , i n t > P ;N-gramr scanf d d d

0.483

4

t y p e d e f v e c t o r <i n t > v i ;N-gramdijkstra r-0.4335

i n l i n e i n t i n ( ) { i n t x ; s c a n f ( ”%d” ,&x ) ;N-gramque empty-0.430N-gramedge e g v-0.411N-grampush r

-0.407ll ;return x ;}6

i n l i n e v o i d p r i v ( v i& a ) { f o r ( i n t i = 0 ; i < (i n t ) ( a ) . s i z e ( ) ; ++i ) p r i n t f ( ”%d%c ” , a [ i ] , i==( i n t ) ( a ) . s i z e ( ) −1? ’ \n ’ : ’ ’ ) ; }表 7

提案手法において分類に有効な特徴量上位 10 件

特徴量のタイプ

N-gram7

c o n s t i n t MX = 1 0 0 0 0 5 , INF = 1 0 0 0 0 1 0 0 0 0 ;8

c o n s t l l LINF = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 l l ;値

係数

if update-0.9009c o n s t d o u b l e e p s = 1 e −10;

10

const i n t di [ ] = { −1 ,0 ,1 ,0} , dj [ ] =s t r u c t Dijk {N-gram1 break

0.618

N-gram

min c

0.606

{0 , −1 ,0 ,1};N-gramcs-0.515

11

N-grami push back

0.501

12

t y p e d e f i n t TT;

variablepriority queue p

0.494

13

s t r u c t dat {

0.463

14

-0.40815

N-gramN-gramr scanf d d dque empty

N-gram

top pq-0.393N-grampush r

-0.390

表 8

ベースライン手法における混同行列
Label
非効率的

Predict

表 9

Predict

非効率的
効率的

効率的

19

5

16

93

提案手法における混同行列
Label
非効率的

効率的

非効率的

19

6

効率的

16

92

TT d ; i n t v ;b o o l o p e r a t o r <( c o n s t dat& a ) c o n s t { r e t u r n d>a . d ; }

16

};

17

int n;

18v e c t o r < v e c t o r <dat> > t o ;19

D i j k ( i n t n ) : n ( n ) , t o ( n ) {}20

v o i d add ( i n t a , i n t b , TT c ) {t o [ a ] . p u s h b a c k ( ( dat ) { c , b } ) ;

21
22

}

23

v e c t o r <TT> d i s t ; v i p r e ;24

v o i d s o l v e ( i n t sv ) {25

d i s t = v e c t o r <TT>(n , INF ) ; p r e = v i ( n , −1) ;26

p r i o r i t y q u e u e <dat> q ;27

d i s t [ sv ] = 0 ;28

q . push ( ( dat ) { 0 , sv } ) ;注目すべきは 2〜13 行目に見られる，型名指定子（typedef
可能な提案手法においては「dijkstra r」という 2-gram がマクロ）や，関数指定子（inline マクロ）や，const 修飾子

上位 10 件に登場しないことは妥当な結果と言える．

である．この指定子の役割は，例えば 2 行目の「typedef

次に，実験プログラムにおける乱数のシード値を固定したときの，混同行列を表 8， 表 9 に示す．

ling long int ll;」であれば long long int 型の変数を宣言する際に long long int と入力する代わりに ll と入力すること

これらの混同行列は概ね同じ結果となっているが，ベーで同様の機能を実現することが可能となる．この実質的なスライン手法では正しく効率的であると分類できていた 1

置換機能により，特徴量として本来 long long int という型

c 2018 Information Processing Society of Japan⃝7

情報処理学会研究報告
IPSJ SIG Technical Report

が情報として取得できるはずが ll という未知の型が得られてしまう．このことから，本ソースコードのような置換機
能が多く用いられたものが入力として与えられた場合，提案手法において追加された特徴量が正しく働いていない可能性が考えられる．本実験では，define マクロについては対応済みであるが，typedef などの置換については未対応である．これは，置換の実現のためには C++ソースコー

謝辞
オンラインジャッジシステムのデータを提供して下さった，会津大学 渡部 有隆 上級准教授に感謝致します．
参考文献
[1]

ドに対する複雑な構文解析処理が必要となるためである．

7. おわりに[2]

本稿では，効率的なアルゴリズム実装の推薦という問題
を，達成に必要な課題に分割し，その第一歩である入力ソー[3]

スコード中の非効率的なアルゴリズムの有無の検出を行った．オンラインジャッジシステム内のソースコードを教師
データ，入力ソースコードの文字列的特徴および構造的特[4]徴を特徴量としたロジスティック回帰により分類を行った
結果，約 82%の分類精度で非効率的なアルゴリズムの有無を判別できた．また，非効率的であると判定されたソース
コードのうち約 70%は，実際に非効率的なアルゴリズムを用いたソースコードであると正しく判定された．一方残り[5]

約 30%のソースコードでは，効率的なアルゴリズムを用いているにも関わらず非効率的であると誤って判定された．
表 6，表 7 に示した有効な特徴量一覧の比較により，提案手法で採用した，宣言された変数の型に関する特徴量が有[6]効であることが確認できた．さらなる精度向上には，型名指定子（typedef マクロ）や関数指定子（inline マクロ）な
どによる置換に対応すべく，特徴量の抽出方法のさらなる[7]

工夫が必要であると考えられる．
一方，本研究の最終的な目的である，ユーザへの効率的なアルゴリズム実装推薦のためには，検出した非効率的な[8]に近い形に整形して提示という 2 つの課題が残されており，

[9]
[10]
[11]
[12]

本稿を端緒として引き続き課題に取り組む必要がある．よ[13]

アルゴリズムに対応する，効率的なアルゴリズムの選択，および効率的なアルゴリズムをユーザの元のソースコード

り効率的なアルゴリズムの選択のためには，非効率的であると判定されたソースコードがどのようなアルゴリズムを使用しているのかを判別するという点が重要であると考えられる．また，効率的なアルゴリズムを整形して提示する

[14]
[15]

Nong，Ge，Sen Zhang，and Wai Hong Chan. 2009. Linear Suﬃx Array Construction by Almost Pure InducedSorting. In 2009 Data Compression Conference，IEEE，193202. http://ieeexplore.ieee.org/document/4976463/.
Manber，Udi，and Gene Myers. 1993.
Suffix Arrays:
A New Method for On-Line String
Searches. SIAM Journal on Computing 22(5): 93548.
http://epubs.siam.org/doi/10.1137/0222058.
Hindle，Abram et al. 2012. On the Naturalness of Software. 2012 34th International Conference on Software
Engineering.
Nguyen，Tung Thanh，Anh Tuan Nguyen，Hoan Anh
Nguyen，and Tien N. Nguyen. 2013.
A Statistical Semantic Language Model for Source Code.
In Proceedings of the 2013 9th Joint Meeting on
Foundations of Software Engineering - ESEC/FSE
2013，New York，New York，USA: ACM Press，532.
http://dl.acm.org/citation.cfm?doid=2491411.2491458.
Nguyen，Anh Tuan，Trong Duc Nguyen，Hung Dang
Phan，and Tien N. Nguyen. 2018. A Deep Neural Network Language Model with Contexts for Source Code.
In 2018 IEEE 25th International Conference on Software
Analysis，Evolution and Reengineering (SANER)，IEEE，
32334. http://ieeexplore.ieee.org/document/8330220/.
中川 尊雄，藤原 新，畑 秀明，and 松本 健一. 2016. プログ
ラミング学習者向けソースコード提示システム TAMBA.
ソフトウェアエンジニアリングシンポジウム 2016 論文集: 34–41.
白川 真澄，原 隆浩，西尾 章治郎. 2015. コルモゴロフ複雑性に基づく IDF の単語 N-Gram への適用. データ工学と情報マネジメントに関するフォーラム (DEIM 2015).
ACM: The ACM-ICPC International Collegiate Programming Contest Web Site sponsored by IBM.
http://sortbenchmark.org/
http://codegolf.com/
http://judge.u-aizu.ac.jp/onlinejudge/
渡部 有隆. 2015. オンラインジャッジの開発と運用 ─
Aizu Online Judge ─. 56(10): 9981005.
WASIK，SZYMON et al. 2018. A Survey on Online
Judge Systems and Their Applications. Lakartidningen 108(3): 9091.
N-GramWeighting
Scheme.
https://github.com/iwnsew/ngweight.
ANTLR. https://www.antlr.org/.

ためには，非効率的であると判定されたソースコード中の変数名や構文的構成など，より複雑な情報について分析を行う必要があると考えられる．加えて，本稿で取り組んだ
入力ソースコード中の非効率的なアルゴリズムの有無の検出に関しては，dijkstra 法以外のアルゴリズムへの適用対象拡張が今後の課題となる．また，さらなる特徴量の追加
や，入力ソースコード中の typedef マクロなどによる置換処理の適用による分類精度・適合率の向上が課題である．

c 2018 Information Processing Society of Japan⃝

8