OJS内のデータを利用したユーザへの効率的なアルゴリズム要否の提示

奈良先端科学技術大学院大学
柴田 敦也, 須藤 克仁, 畑 秀明, 中村 哲

1

目次
1.
2.
3.
4.
5.
6.

背景
目的
関連研究
実験
まとめ
今後の課題

2

背景
ソフトウェア開発では時としてアルゴリズムに関する知識が必要
ネットワークシステムにおけるルーティングでは最短経路問題の解決が必要
実際, アルゴリズムを利用するシステムはGitHub上に多数存在

3

背景
ソフトウェア開発では時としてアルゴリズムに関する知識が必要
ネットワークシステムにおけるルーティングでは最短経路問題の解決が必要
実際, アルゴリズムを利用するシステムはGitHub上に多数存在
実装者の技術不足・納期の優先 により非効率的なアルゴリズムが採用される場合も4

背景 アルゴリズムの効率ある問題を解決するアルゴリズムが複数存在するケースもあり、必要な知識は膨大
Suffix-Array 作成 アルゴリズム
遅① O(|S|2 log|S|) version② O(|S| log2|S|) version

速③ O(|S|) version※|S| は文字列Sの文字列長5

背景 アルゴリズムの効率ある問題を解決するアルゴリズムが複数存在するケースもあり、必要な知識は膨大
Suffix-Array 作成 アルゴリズム
遅① O(|S|2 log|S|) version② O(|S| log2|S|) version

速③ O(|S|) version

効率的だが実装が複雑

6

背景 アルゴリズムの効率ある問題を解決するアルゴリズムが複数存在するケースもあり、必要な知識は膨大
Suffix-Array 作成 アルゴリズム
遅① O(|S|2 log|S|) version② O(|S| log2|S|) version

速③ O(|S|) version

効率的だが実装が複雑

効率的なアルゴリズムの推薦により質の高いソフトウェアを開発可能

7

目的 対象とするタスク&解決する問題
対象とするタスクの具体化①非効率的なアルゴリズムを検出②効率的な等価アルゴリズムを選択③ユーザのコードに近い形式で提示

8

目的 対象とするタスク&解決する問題
対象とするタスクの具体化①非効率的なアルゴリズムを検出

本タスクの最終的な目標②効率的な等価アルゴリズムを選択③ユーザのコードに近い形式で提示

9

目的 対象とするタスク&解決する問題
本タスクの困難さ
2つのプログラムは等価？
任意の入力で両プログラムの出力が同じプログラムの効率性は？
複数の値を入力して評価
時にプログラムへの入力の組み合わせは膨大（完全なソフトウェアテストの困難性）
10

目的 対象とするタスク&解決する問題
非効率的/効率的 なアルゴリズムのデータ収集①非効率的なアルゴリズムを検出②効率的な等価アルゴリズムを選択③ユーザのコードに近い形式で提示
本研究では①に注目

動的な実行無しにソースコードの構造などの特徴を抽出
非効率的/効率的の2値分類問題として機械学習で解決
また、教師データとしてOJS内のデータを利用
11

目的 オンラインジャッジシステム
非効率的/効率的 なアルゴリズムのデータ収集
OJS( Online Judge System )• プログラミング学習のための既存のwebサービス• 提出されたソースコードの機能・性能を自動的に検証

12

目的 オンラインジャッジシステム
非効率的/効率的なアルゴリズムのデータ収集

13

目的 オンラインジャッジシステム非効率的/効率的なアルゴリズムのデータ収集
OJSの正誤判定結果の例
Status

意味Accepted

提出されたプログラムは正しい

Wrong Answer

提出されたプログラムは正しくない

Time Limit Exceed

提出されたプログラムの出力は正しいが実行時間が長く非効率的14

目的 オンラインジャッジシステム
非効率的/効率的なアルゴリズムのデータ収集: 4 case
入出力
規定実行時間 : 5,000[ms]以内

ジャッジ結果はTLE(Time Limit Exceeded)15

目的 対象とするタスク&解決する問題
非効率的/効率的 なアルゴリズムのデータ収集
教師データとしてのOJSのメリット•

汎用的なアルゴリズムを実装したコードが多数存在•

全てのソースコードが動的なソフトウェアテストによって機能・性能が検証済み
ソフトウェアの動的な検証が困難という問題を解決可能

16

関連研究
• コード補完※1
入力された宣言済みの変数名の一部に対して該当変数名を提示 タイピング数を削減
本研究はユーザの知識以上のコードを提示• プログラミング学習者向けソースコード提示※2
OJS上の問題を解く際にヒントとなるソースコードを段階的に提示し、学習を支援
本研究の適用対象はOJSに限らない※1: Hindle, Abram et al. 2012. “On the Naturalness of Software.” 2012 34th International
Conference on Software Engineering.
※2:中川 尊雄, 藤原 新, 畑 秀明, and 松本 健一. 2016. “プログラミング学習者向けソースコード提示システムTAMBA.” ソフトウェアエンジニアリングシンポジウム2016論文集: 34--41.

17

実験 OJS 実験
OJS内ソースコードからの非効率的な処理検出
1. OJS内の最短経路問題を解くソースコードを用意
2. 非効率的/効率的を分類する識別器を設計
特徴量

単語N-gramによる文字列的特徴
for/while/if 構文による構造的特徴

3. 5-fold 交差検証により識別器の性能を検証
18

実験 OJS 実験設定
OJS内ソースコードからの非効率的な処理検出
1. OJS内の最短経路問題を解くソースコードを用意
2. 非効率的/効率的を分類する識別器を設計
特徴量

単語N-gramによる文字列的特徴
for/while/if 構文による構造的特徴

3. 5-fold 交差検証により識別器の性能を検証
19

実験 OJS 実験設定
OJSによる正誤判定結果の例
Status

意味Accepted

提出されたプログラムは正しい

Wrong Answer

提出されたプログラムは正しくない

Time Limit Exceed

提出されたプログラムの出力は正しいが実行時間が長く非効率的

Accepted: 効率的なアルゴリズム

Time Limit Exceed : 非効率的なアルゴリズム
20

実験 OJS 実験設定
OJS内ソースコードからの非効率的な処理検出
データセットの詳細(最短経路問題の例)

効率的なアルゴリズム(C++): 501 (75.1%)•O(|E| log|V|) Dijkstra(priority-queueを使用)•O(|E| log|V|) Dijkstra(radix-heapを使用)

非効率的なアルゴリズム(C++)•O(|V|2) Dijkstra•O(|E| |V|) Bellman-ford•

O(|V|3) Floyd-Warshall: 166 (24.9%)21

実験 OJS 実験設定
OJS内ソースコードからの非効率的な処理検出
1. OJS内の最短経路問題を解くソースコードを用意
2. 非効率的/効率的を分類する識別器を設計
特徴量

単語N-gram等による文字列的特徴
for/while/if 構文等による構造的特徴

3. 5-fold 交差検証により識別器の性能を検証
22

実験 OJS 実験設定
OJS内ソースコードからの非効率的な処理検出
ソースコードから素性をプログラムで抽出
これを特徴量として各提出の特徴ベクトルを作成
ロジスティック回帰で分類（正規化はL2）

23

実験 OJS 実験設定
OJS内ソースコードからの非効率的な処理検出提案手法 特徴量一覧
word̲Ngram

コード中に含まれる単語 N-gramdeclared̲variable̲type

コード中で宣言されている変数の型

max̲depth̲of̲nest

コード中の制御構文によるネストの最大値#̲of̲nest

コード中の深さ1以上の独立なネストの数#̲of̲for

コード中のforループの数#̲of̲while

コード中のwhileループの数#̲of̲if

コード中のIf文の数

24

実験 OJS 実験設定
OJS内ソースコードからの非効率的な処理検出
float x=0.3;
int i, j;x = x*2
queue<float> que;for(i=0;i<5;i++){for(j=0;j<5;j++){que.push(i*j*x);}}

特徴量word̲Ngram
float xfloat x =etc…
declared̲variable̲type
int: 2
float: 1
queue<float>: 1

25

実験 OJS 実験設定
OJS内ソースコードからの非効率的な処理検出
float x=0.3;
int i, j;x = x*2
queue<float> que;for(i=0;i<5;i++){for(j=0;j<5;j++){que.push(i*j*x);}}

特徴量max̲depth̲of̲nest2#̲of̲nest1#̲of̲for2#̲of̲while0#̲of̲if0

識別器はロジスティック回帰26

実験 OJS 評価実験
OJS内ソースコードからの非効率的な処理検出
1. OJS内の最短経路問題を解くソースコードを用意
2. 非効率的/効率的を分類する識別器を設計
特徴量

単語N-gramによる文字列的特徴
for/while/if 構文による構造的特徴

3. 5-fold 交差検証により識別器の性能を検証
27

実験 OJS 評価実験
OJS内ソースコードからの非効率的な処理検出• 関連研究で述べた中川らの研究※ を参考に
N-gramの特徴量のみを用いた分類をベースライン手法• 前述の特徴量全てを用いた分類を提案手法※:中川 尊雄, 藤原 新, 畑 秀明, and 松本 健一. 2016. “プログラミング学習者向けソースコード提示
システムTAMBA.” ソフトウェアエンジニアリングシンポジウム2016論文集: 34--41.

28

実験 OJS 評価実験
OJS内ソースコードからの非効率的な処理検出分類精度（classification accuracy）と適合率（precision）に基づいて分類結果を評価

TP + TN
classif ication accuracy =TP + FP + FN + TNTP
precision =TP + FP29

実験 OJS 評価実験
非効率的な処理検出 結果（10回の試行の平均）• ベースライン手法（N-gram特徴量のみ）
平均分類精度 : 81.72%: 69.75%
平均適合率• 提案手法（複数の特徴量）
平均分類精度 : 82.01%: 69.80%
平均適合率
提案手法はわずかに高い 分類精度・適合率 を示すが有意差は無し
30

実験 OJS 実験結果の分析
有効な特徴量上位10件
ベースライン手法

提案手法

31

実験 OJS 実験結果の分析
有効な特徴量上位10件
ベースライン手法

提案手法

Dijkstraであってもpriority̲queue（ヒープ）を使わない場合非効率的となりうることを学習

32

実験 OJS 実験結果の分析
混同行列
ベースライン手法

提案手法

33

実験 OJS 実験結果の分析
混同行列
ベースライン手法

提案手法

34

実験 OJS 実験結果の分析
混同行列
提案手法のみ誤分類したソースコードの一部
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi& a) { for(int i = 0; i < (int)(a).size(); ++i) printf("%d%c",a[i],i==(int)(a).size()-1?'¥n':' ');}
const int MX = 100005, INF = 1000010000;

型名指定子（typedef）や 関数指定子（inline）に脆弱でありこれらの実質的な置換をソースコードに適用する必要性

35

実験 OSS 実験
GitHub上のコードを用いた有効性判定
1. GitHub上の最短経路問題を解くソースコードを用意
2. 前述の識別器を用いて非効率的なソースコードを検出
3. 非効率的であるとされたソースコードが実際に非効率的である割合（Precision）を評価
36

実験 OSS 実験設定
GitHub上のコードを用いた有効性判定
1. GitHub上の最短経路問題を解くソースコードを用意
2. 前述の識別器を用いて非効率的なソースコードを検出
3. 非効率的であるとされたソースコードが実際に非効率的である割合（Precision）を評価
37

実験 OSS 実験設定
GitHub上のコードを用いた有効性判定
データセットの詳細

ソースコード中で最短経路問題を解く
53件
GitHub上のC++のソースコード•非効率的/効率的 のラベルなし•

平均108行（30行~272行）

38

実験 OSS 実験設定
GitHub上のコードを用いた有効性判定
評価方法

適合率（precision）に基づいて分類結果を評価

TP
precision =TP + FP39

実験 OSS 実験設定
GitHub上のコードを用いた有効性判定
1. GitHub上の最短経路問題を解くソースコードを用意
2. 前述の識別器を用いて非効率的なソースコードを検出
3. 非効率的であるとされたソースコードが実際に非効率的である割合（Precision）を評価
40

実験 OSS 評価実験
GitHub上のコードを用いた有効性判定
1. GitHub上の最短経路問題を解くソースコードを用意
2. 前述の識別器を用いて非効率的なソースコードを検出
3. 非効率的であるとされたソースコードが実際に非効率的である割合（Precision）を評価
41

実験 OSS 評価実験
GitHub上のコードを用いた有効性判定
ベースライン手法

非効率的: 14件, 効率的: 39件
平均適合率: 57.14% (8/14)

提案手法

非効率的: 11件, 効率的: 42件
平均適合率: 63.64% (7/11)

42

実験 OSS 評価実験
GitHub上のコードを用いた有効性判定
ベースライン手法

非効率的: 14件, 効率的: 39件
平均適合率: 57.14% (8/14)

提案手法

非効率的: 11件, 効率的: 42件
平均適合率: 63.64% (7/11)

提案手法では宣言された変数を考慮しており一般のソースコードでもより効率的に分類が可能

43

まとめ•

非効率的なアルゴリズム検出のため
N-gram以外の構造的・構文的素性を追加
現状ではN-gramのみと比較して有意差なし• GitHub上のコードを用いた評価
一般のソースコードに対しても提案手法が有効
44

今後の課題•

非効率的なアルゴリズム検出の精度向上•以下の課題②, ③の解決（本研究では①を解決）①非効率的なアルゴリズムを検出②効率的な等価アルゴリズムを選択③ユーザのコードに近い形式で提示• 最短経路問題以外の問題への拡張45

目的 対象とするタスク&解決する問題
本タスクの困難さ
例: 入力された値が素数かを判定するプログラム• 入力は無限に存在（任意の自然数）• 入力が2など小さい値で割れる場合高速だが素数の場合時間がかかる

YesX（or） isPrime?

No46