「新人女子プログラマの書いたコードを直すだけの簡単なお仕事」にチャレンジしてみました

らくさん

2013.12.09

新人女子のらくさんです。最近、お昼は自分でお弁当を作ってます。

ソニックムーブ Advent Calendar 2013 9日目の記事になります。

先週頃からプログラマの間で流行っている「新人女子プログラマの書いたコードを直すだけの簡単なお仕事」に、ソニックムーブ新人女子の私もチャレンジしてみました。最初はとても遅かったんですが先輩に改善点を指摘していただいてがんばったところ、すっごく速くなりました！

結果はこちらになります。
rakusanさんの採点結果[100点 CTOに昇進しました！]

提出言語はJavaで、Test case 1,2,3 がそれぞれ 0.06, 0.07, 0.10秒でした。12月6日の時点で、Test case 3だけ最速実行時間の0.09秒にわずかに及びませんでした。
くやしい… 応募期間がまだ残り１ヶ月ほどあるので実際に書いたコードの掲載は控えますが、先輩に指摘していただいた改善点をまとめてみました。

O(D*N^2)
O(D*N*log(N))
枝刈り
O(D*N)
データ読み込みの高速化
まとめ

O(D*N^2)

一番簡単に思いつくのは、N個の商品中の2つの商品の組み合わせすべてを調べる方法ですね。

[sourcecode lang="java" highlight="9,12,13"] 
int N = readNumber(); // 商品の総数 
int D = readNumber(); // キャンペーンの日数
int[] prices = new int[N];
for (int i = 0; i &lt; N; ++i) {
 prices[i] = readNumber(); // 商品の価格
 }
for (int d = 0; d &lt; D; ++d) {
 int targetPrice = readNumber(); // キャンペーン設定金額 
int resultPrice = 0; 
for (int i = 0; i &lt; N; ++i) {
 for (int j = 0; j &lt; N; ++j) {
 if (i != j) { int sum = prices[i] + prices[j];
 if (sum &lt;= targetPrice &amp;&amp; sum &gt; resultPrice)
 { resultPrice = sum; } } } } System.out.println(resultPrice);
} [/sourcecode]

[sourcecode lang="java" highlight="9,12,13"]

int N = readNumber(); // 商品の総数

int D = readNumber(); // キャンペーンの日数

int[] prices = new int[N];

for (int i = 0; i < N; ++i) {

prices[i] = readNumber(); // 商品の価格

}

for (int d = 0; d < D; ++d) {

int targetPrice = readNumber(); // キャンペーン設定金額

int resultPrice = 0;

for (int i = 0; i < N; ++i) {

for (int j = 0; j < N; ++j) {

if (i != j) { int sum = prices[i] + prices[j];

if (sum <= targetPrice && sum > resultPrice)

{ resultPrice = sum; } } } } System.out.println(resultPrice);

} [/sourcecode]

9,12,13行目のループにがネストされて三重ループになっているため、一番内側の処理はD*N*N回実行されます。このような場合、「計算量が O(D*N^2) になる」と言います。商品数の二乗に比例して処理量が増えるので、商品数が増えると処理時間が急激に増えて行きます。新人女子の私がお婆ちゃんになってしまいます。

ここで、例えば i=5, j=20 の場合と i=20, j=5 の場合を考えてみます。これらの場合、N個の商品中から取り出した2つの商品の組は同じになります。取り出した順番が逆になっただけです。同じ組み合わせを二度計算するのは無駄ですので、これを一回で済むようにしてみます。

[sourcecode lang="java" highlight="12,13"] 
int N = readNumber(); // 商品の総数 
int D = readNumber(); // キャンペーンの日数

int[] prices = new int[N]; 
for (int i = 0; i &lt; N; ++i) {
 prices[i] = readNumber(); // 商品の価格 
}

for (int d = 0; d &lt; D; ++d) {
 int targetPrice = readNumber(); // キャンペーン設定金額 
 int resultPrice = 0; 
 for (int i = 0; i &lt; N-1; ++i) {
  for (int j = i + 1; j &lt; N; ++j) {
   int sum = prices[i] + prices[j];
   if (sum &lt;= targetPrice &amp;&amp; sum &gt; resultPrice) {
    resultPrice = sum;
  } 
 }
}
 System.out.println(resultPrice);
} [/sourcecode]

[sourcecode lang="java" highlight="12,13"]

int N = readNumber(); // 商品の総数

int D = readNumber(); // キャンペーンの日数

int[] prices = new int[N];

for (int i = 0; i < N; ++i) {

prices[i] = readNumber(); // 商品の価格

}

for (int d = 0; d < D; ++d) {

int targetPrice = readNumber(); // キャンペーン設定金額

int resultPrice = 0;

for (int i = 0; i < N-1; ++i) {

for (int j = i + 1; j < N; ++j) {

int sum = prices[i] + prices[j];

if (sum <= targetPrice && sum > resultPrice) {

resultPrice = sum;

}

System.out.println(resultPrice);

} [/sourcecode]

13行目のループが j=0 から開始していたところを j=i+1 から開始するようにしました。また12行目のループの終了条件も i<N から i<N-1 にしています。このようにすることで、同じ組み合わせを二度計算することがなくなります。

また、最初のコードでは14行目で if (i != j) として同一の商品の場合を除外していましたが、これも不要になりました。

さて、この場合の計算量ですが、一番内側のループの回る回数が最初はN-1回、次はN-2回、その次はN-3回…最後は1回となるので、一番内側の処理は D*((N-1) + (N-2) + … + 1) 回実行されることになります。

(N-1) + (N-2) + … + 1 のところは等差数列になっているので、等差数列の和の公式より N*(N-1)/2 = (N^2-N)/2 となります。(N^2-N)/2 には N^2 の項があるので「商品数の二乗に比例して処理量が増える」ことは変わっていません。

したがって、この場合の計算量は最初のコードと変わらず O(D*N^2) と表します。最初のコードよりは少し処理量は減っていますが、残念ながら計算量の大まかな「程度」は改善されていないのです。

O(DNlog(N))

計算量を減らすためによく用いられる方法に「二分探索」というものがあります。

ソート済みのリストや配列に入ったデータに対する検索を行うにあたって、中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

二分探索の計算量は O(log2(N)) です。つまり、1000000個のデータから目的の値を検索するのに必要な計算量は log2(1000000) で、これはおよそ20です。1000000個のデータの先頭から一つずつ調べてた場合、目的の値が見つかるまで平均で500000回調べる必要がありますが、二分探索では20回調べれば目的の値が見つかります。上の引用文に書かれているように、二分探索を行うには「ソート済みのリストや配列に入ったデータ」が必要なので、商品の値段が入っている配列をソートする必要があります。

Javaの場合、java.util.Arraysクラスのsortメソッドを使うことができます。二分探索は、同じArraysクラスのbinarySearchです。これらを使ってコードを書き換えると、次のようになります。

[sourcecode lang="java" highlight="9,15"] 
int N = readNumber(); // 商品の総数 
int D = readNumber(); // キャンペーンの日数

int[] prices = new int[N]; 
for (int i = 0; i &lt; N; ++i) { 
 prices[i] = readNumber(); // 商品の価格 
}

Arrays.sort(prices);

for (int d = 0; d &lt; D; ++d) {
 int targetPrice = readNumber(); // キャンペーン設定金額
 int resultPrice = 0;
 for (int i = 0; i &lt; N-1; ++i) {
  int j = Arrays.binarySearch(prices, i+1, N, targetPrice - prices[i]);
  if (j &gt;= i+1) { resultPrice = prices[i] + prices[j]; } else if (j == -i-2) { // 「挿入ポイント」が i+1 のときは該当なし
  continue;
 } else { // 「挿入ポイント」のひとつ手前
  j = -(j+1)-1; int sum = prices[i] + prices[j];
  if (sum &lt;= targetPrice &amp;&amp; sum &gt; resultPrice) { resultPrice = sum;
  }
 }
}
 System.out.println(resultPrice); 
} [/sourcecode]

[sourcecode lang="java" highlight="9,15"]

int N = readNumber(); // 商品の総数

int D = readNumber(); // キャンペーンの日数

int[] prices = new int[N];

for (int i = 0; i < N; ++i) {

prices[i] = readNumber(); // 商品の価格

}

Arrays.sort(prices);

for (int d = 0; d < D; ++d) {

int targetPrice = readNumber(); // キャンペーン設定金額

int resultPrice = 0;

for (int i = 0; i < N-1; ++i) {

int j = Arrays.binarySearch(prices, i+1, N, targetPrice - prices[i]);

if (j >= i+1) { resultPrice = prices[i] + prices[j]; } else if (j == -i-2) { // 「挿入ポイント」が i+1 のときは該当なし

continue;

} else { // 「挿入ポイント」のひとつ手前

j = -(j+1)-1; int sum = prices[i] + prices[j];

if (sum <= targetPrice && sum > resultPrice) { resultPrice = sum;

}

System.out.println(resultPrice);

} [/sourcecode]

この場合、binarySearchは D*(N-1) 回実行されるので計算量は O(D*(N-1)*log2(N)) となりますが、Nが十分大きい場合はNとN-1はほとんど同じなので、計算量を考える上で区別する意味はあまりありません。また対数は底によって定数倍変わるだけなので、やはり計算量を考える上で対数の底がいくつなのかも重要ではありません。したがって、この場合の計算量は、通常 O(D*N*log(N)) と表します。

また、最初に1回だけ行っているソートの計算量は O(N*log(N)) です。この分も考慮すると全体の計算量は O(N*log(N) + D*N*log(N)) = O((D+1)*N*log(N)) で、Dが十分大きければ O(D*N*log(N)) と見なせます。

今回の問題はDが最大で75なので十分大きいとは言えず、ソートの計算量が全体の計算量に影響する可能性がありますが、ここでは考えないことにします。なお、このコード中のコメントにある「挿入ポイント」について、ここでは触れません。挿入ポイントについてはbinarySearchのドキュメントに書かれていますのでそちらをご覧ください。

枝刈り

先ほどのコードの17行目は、binarySearchで探した値にちょうど一致する値が見つかった場合になります。つまり、この問題における「キャンペーン設定金額」にちょうど一致する商品の組み合わせが見つかった場合です。

したがって、これ以降も内側のループを続けるのは無駄です。ループを抜けてしまいましょう。このように明らかに無駄とわかる条件を見つけて処理を打ち切ってしまうことを「枝刈り」と言います。

[sourcecode lang="java" firstline="15" highlight="17,18"] 
int j = Arrays.binarySearch(prices, i+1, N, targetPrice - prices[i]); 
if (j &gt;= i+1) {
 resultPrice = prices[i] + prices[j];
 break;
 } else if (j == -i-2) { [/sourcecode]

[sourcecode lang="java" firstline="15" highlight="17,18"]

int j = Arrays.binarySearch(prices, i+1, N, targetPrice - prices[i]);

if (j >= i+1) {

resultPrice = prices[i] + prices[j];

break;

} else if (j == -i-2) { [/sourcecode]

ついでに、わざわざ足し算をする必要はなく、キャンペーン設定金額をそのまま代入してしまえば済みます。

 [sourcecode lang="java" firstline="15" highlight="17"] 
int j = Arrays.binarySearch(prices, i+1, N, targetPrice - prices[i]); 
if (j &gt;= i+1) {
 resultPrice = targetPrice;
 break; 
} else if (j == -i-2) { [/sourcecode]

[sourcecode lang="java" firstline="15" highlight="17"]

int j = Arrays.binarySearch(prices, i+1, N, targetPrice - prices[i]);

if (j >= i+1) {

resultPrice = targetPrice;

break;

} else if (j == -i-2) { [/sourcecode]

O(D*N)

二分探索を使って計算量を O(D*N*log(N)) まで減らすことができましたが、この問題の特性をよく考えると O(D*N) にすることができます。応募期間が終わっていないので具体的なコードを書くことは控えますが、考え方は次のようになります。

商品価格でソートされているので、i=1の商品の値段はi=0より少しだけ高い（もしくは同じ）
そのため、i=1の商品と組になるのは、i=0の商品と組になったものより少しだけ手前（もしくは同じ）
i=2以降も同様

データ読み込みの高速化

問題の条件をよく読むと、入力データは最大でも数MB程度なことがわかります。

一方、環境情報を見るとメモリ制限は256MBで、入力データのサイズに対して十分余裕があります。

このような場合は、1行ずつデータを読み込むよりはある程度まとめて（あるいは全部）メモリに読み込んでしまってから1行ずつのデータに分解した方が速くなる可能性があります。

まとめ

計算量が O(D*N*log(N)) でも結果が正しければ100点は取れるようですので、Test case 2, 3が時間切れになってしまった方も、あきらめずに再チャレンジしてみてください。また、Test case 2, 3をクリアできたら O(D*N) 化にもチャレンジし、さらにデータ読み込みの高速化も行って最速実行時間を目指してみてください。