【Python】どちらが速い？再帰処理とループ処理で配列要素の合計値を取得

■概要

再帰処理とループ処理を使用して、0〜99までの任意の数字を10万個用意し、配列要素の合計値を取得する。
その際、処理時間を測定し、どちらが速いか調べる。

・配列要素に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つの処理については、ループ処理の方が速いことがわかる。