処理時間はデータ量に比例するとは限らない

処理時間(計算量)はデータ量に比例するとは限りません。
例えば、データ量が10倍になったからと言って、処理時間も10倍になるとは限りません。

処理時間が何倍になるかは、アルゴリズムにより決まります。
アルゴリズム次第では、データ量が10倍になった時に処理時間が100倍になることも有り得ます。

今回は、試しに、Java作成したソート処理の実行時間を測ってみます。
アルゴリズムはバブルソートです。


【サンプルコード】

・BubbleSort.java

【実行時間】

・データ量が10000レコードの場合

・データ量が100000レコードの場合


以上のように、データ量が10倍になった場合に、実行時間も100倍(実測ではそれ以上)になりました。

なぜ実行時間がデータ量に比例しないのかと言うと、このアルゴリズムでは二重ループが発生するからです。
二重ループの中の処理が行われる回数は、10000レコードの場合は「1万 * 1万」(正確には「1万 * 9999」)回ですが、100000レコードの場合は「10万 * 10万」(正確には「10万 * 99999」)回となり、100倍の差となります。
この差が、実行時間にも反映されます。

専門用語で言うと、このような概念は「O(オーダ)」と呼ばれます。
(詳しくは、以前の記事で紹介しています)

実務でも、大量のデータを処理する必要がある場合は、「O(オーダ)」の概念や、最適なアルゴリズムを意識する必要があります。
基礎的なアルゴリズムは、情報処理技術者試験で学ぶことができます。
また、競技プログラミングでは最適なアルゴリズムを考えさせる問題が頻出なので、詳しく学びたい方は手を出してみると面白いと思います。


いかがでしたでしょうか。

「処理時間はデータ量に比例するとは限らない」というのは、アルゴリズムや性能問題を学んだことがない人にとっては意外なことだと思います。
システムには性能問題(Webページの動作が遅い、夜間バッチが決められた時刻までに終わらずにサービス開始時刻になってもシステムを利用できない、等)がつきものです。
そうした性能問題は、データ量の増加に対して処理時間が指数関数的に増えることで引き起こされていることも少なくありません。

この記事を通して、アルゴリズムや性能問題への興味を持つ人が一人でも増えれば幸いです。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA