■概要
再帰処理とループ処理を使用して、0〜99までの任意の数字を10万個用意し、配列要素の合計値を取得する。
その際、処理時間を測定し、どちらが速いか調べる。
・配列要素に0〜99までの任意の数字を10万個用意
・再帰処理とループ処理の処理時間を測定
■フローチャート
「再帰処理：配列要素の合計値を求める」、「ループ処理：配列要素の合計値を求める」、「メイン処理」のフローチャートを以下に示す。
▼再帰処理：配列要素の合計値を求める
「再起処理：配列の合計値を求める」処理について、フローチャートを以下に示す。
▼ループ処理：配列要素の合計値を求める
「ループ処理：配列の合計値を求める」処理について、フローチャートを以下に示す。
▼メイン処理
「メイン処理」について、フローチャートを以下に示す。
■プログラム仕様
「再帰処理：配列要素の合計値を求める」、「ループ処理：配列要素の合計値を求める」、「メイン処理」のプログラム仕様を以下に示す。
▼再帰処理：配列要素の合計値を求める
「再帰処理：配列要素の合計値を求める」について、＜引数と戻り値＞および＜処理内容＞を下表に示す。
＜引数と戻り値＞
| 項目 | 型 | 項目内容 |
|---|---|---|
| 第1引数 | int型 | 左側のインデックス番号 |
| 第2引数 | int型 | 右側のインデックス番号 |
| 第3引数 | list型 | 0〜99の任意の数字を10万個格納した配列 |
| 戻り値 | int型 | 「左側と中間」および「中間と右側」の合算値 |
＜処理内容＞
| 入力 | 処理内容 | 出力 |
|---|---|---|
| – | ▼条件分岐：左右の数字の差分 【1の場合】 ｜左側の配列要素を返す。 ▲ | – |
| – | 左右のインデックス番号の中間を取得する。 | – |
| – | 再帰処理呼び出し ・第1引数：左側のインデックス番号 ・第2引数：中間のインデックス番号 ・第3引数：0〜99の任意の数字を10万個格納した配列 | – |
| – | 再帰処理呼び出し ・第1引数：中間のインデックス番号 ・第2引数：右側のインデックス番号 ・第3引数：0〜99の任意の数字を10万個格納した配列 | – |
| – | 戻り値：「左側と中間」および「中間と右側」の合算値を返す。 | – |
▼ループ処理：配列要素の合計値を求める
「ループ処理：配列要素の合計値を求める」について、＜引数と戻り値＞および＜処理内容＞を下表に示す。
＜引数と戻り値＞
| 項目 | 型 | 項目内容 |
|---|---|---|
| 第1引数 | list型 | 0〜99の任意の数字を10万個格納した配列 |
| 戻り値 | int型 | 配列要素の合計値 |
＜処理内容＞
| 入力 | 処理内容 | 出力 |
|---|---|---|
| – | 合計値の初期値セット 初期値：0 | – |
| – | ■ループ処理：配列の要素数分繰り返し ｜合計値を計算する。 ■ | – |
| – | 戻り値：合計値を返す。 | – |
▼メイン処理
「メイン処理」について、＜引数と戻り値＞および＜処理内容＞を下表に示す。
＜引数と戻り値＞
| 項目 | 型 | 項目内容 |
|---|---|---|
| 引数 | – | なし |
| 戻り値 | – | なし |
＜処理内容＞
| 入力 | 処理内容 | 出力 |
|---|---|---|
| – | 左側のインデックス番号の初期値セットする。 初期値：0 | – |
| – | 0〜99の任意の数字を10万個用意する。 | – |
| – | 右側の初期値をセットする。 初期値：配列の要素数 | – |
| – | 再帰処理：処理開始時間を設定する。 | – |
| – | 再帰処理呼び出し ・第1引数：左側のインデックス番号 ・第2引数：右側のインデックス番号 ・第3引数：0〜99の任意の数字を10万個格納した配列 | 【コンソール】 再帰処理：合計値 |
| – | 再帰処理：処理終了時間を設定する。 | – |
| – | 再帰処理：処理時間を出力する。 | 【コンソール】 再帰処理：処理時間 |
| – | ループ処理：処理開始時間を設定する。 | – |
| – | ループ処理呼び出し ・第1引数：0〜99の任意の数字を10万個格納した配列 | 【コンソール】 ループ処理：合計値 |
| – | ループ処理：処理終了時間を設定する。 | – |
| – | ループ処理：処理時間を出力する。 | 【コンソール】 ループ処理：処理時間 |
■サンプルコード
import random
import time
# 再帰処理：配列要素の合計値を求める
def bunkatsu_tochi(left_num: int, right_num: int, list_data: list) -> int:
# 左右の数字の差分が1の場合
if right_num - left_num == 1:
# 左側の配列要素を返す
return list_data[left_num]
# 左右の中間を取得する
middle_num = (left_num + right_num) // 2
# 再帰処理呼び出し：左側と中間
left_middle_num = bunkatsu_tochi(left_num, middle_num, list_data)
# 再帰処理呼び出し：中間と右側
middle_right_num = bunkatsu_tochi(middle_num, right_num, list_data)
# 「左側と中間」および「中間と右側」の合算値を返す
return left_middle_num + middle_right_num
# ループ処理：配列要素の合計値を求める
def for_loop_sum(list_data: list) -> int:
# 合計値の初期値セット
result_sum = 0
# ループ処理：配列の要素数分繰り返し
for i in range(len(list_data)):
# 合計値を計算
result_sum = result_sum + list_data[i]
# 合計値を返す
return result_sum
# メイン処理
if __name__ == '__main__':
# 左側の初期値セット
first_left_num = 0
# 0〜99の任意の数字を10万個用意
list_data = [random.randint(0, 99) for _ in range(100000)]
# 右側の初期値をセット
first_right_num = len(list_data)
# 再帰処理：開始時間
start_time = time.time()
# 再帰処理：呼び出し
print('再帰処理：', bunkatsu_tochi(first_left_num, first_right_num, list_data))
# 再帰処理：終了時間
end_time = time.time()
# 再帰処理：処理時間
print('処理時間：', end_time - start_time)
# ループ処理：開始時間
start_time = time.time()
# ループ処理：呼び出し
print('ループ処理：', for_loop_sum(list_data))
# ループ処理：終了時間
end_time = time.time()
# ループ処理：処理時間
print('処理時間：', end_time - start_time)
■実行結果
再帰処理： 4960900
処理時間： 0.03483915328979492
ループ処理： 4960900
処理時間： 0.0066988468170166016この2つの処理については、ループ処理の方が速いことがわかる。
コメント