pythonの関数の引数としてlistを渡すときに、何が起こっているかを正しく説明できるだろうか？intやstringを渡すときは特に何も考えることなく渡すことができ、特にエラーを発生させることもないだろう。しかし、listを引数とするときには挙動を正しく理解して細心の注意を払わなければ意図しない挙動を簡単に起こしうる。今回は、アルゴリズムの問題の解答の例を交えながら配列を引数とする時の挙動について説明していく。

要点

関数の引数としてlistが渡される時それは参照渡しである
参照渡しとは同じ実態を操作対象とすることである

問題文

Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

解答1

pythonの関数の引数にlistを渡すと、それは値わたしではなく参照わたしとなる。そのため、current_combinationをそのまま渡すと意図しない値の変化が関数によって起こされてしまう可能性がある。この問題を防ぐために新しい配列(メモリの場所が異なる)を作成する必要がある。

current_combination + [candidates[index]]はlistの結合であり、current_combinationに要素を一つ追加する。ただしこれはlistのappendと異なり、新しい配列を作成するという点がポイントである。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def _combination_helper(current_combination, current_sum, idx):
            if current_sum == target:
                res.append(current_combination)
                return
            
            if current_sum < target:
                for index in range(idx, len(candidates)):
                    _combination_helper(current_combination + [candidates[index]], current_sum + candidates[index], index)
        
        res = []
        _combination_helper([], 0, 0)
        return res

解答2

これはバックトラッキングと言われる手法である。先ほどと解き方の考え方自体は似ているが、再帰関数に新しい配列ではなく参照だけを渡している点に注意されたい。

イメージとしては解答1は存在する組み合わせの可能性ごとに異なる個別の箱を用意していたのに対して、解答2は1つの箱に対して中身を入れ替え続けているイメージである。つまり、再帰関数を呼び出す前後で値をappendして、popするという操作を行なっている。

この回答の注意点は、res.append(current_combination[:])の部分である。res.append(current_combination)と書いてしまった場合を考えよう。全ての再帰関数でcurrent_combinationという同じ配列を参照しているため、resに加えたのちに、他の再帰関数から変更が加えられると既に格納しているものの値も変わってしまうのである。

そのため、コピーを作成してからresにappendしているのである。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def _combination_helper(current_combination, current_sum, idx):
            if current_sum == target:
                res.append(current_combination[:])
                return
            
            if current_sum < target:
                for index in range(idx, len(candidates)):
                    current_combination.append(candidates[index])
                    _combination_helper(current_combination, current_sum+candidates[index], index)
                    current_combination.pop()
                    
        res = []
        _combination_helper([], 0, 0)
        return res

比較：どちらがはやい？

解答1のほうが一般的には挙動がわかりやすいのではないだろうか？しかしながら、関数の呼び出し時に毎回配列のコピーを作成するため、配列が長くなるほどコピーのオーバーヘッドが増加していく。よって、通常は解答2の方法の方が早いことが多いだろう。

自分のmacの環境で簡単な実験を行ってみた。以下のコードを参照してほしい。コピーを作成する方法と、同じ参照でappendとpopを使う方法を比較したところ、それぞれの実行時間は以下のようになった。後者の方法の方が実行時間が1/5程度であることがわかった。

解答1の方法: 0.00017094
解答2の方法: 0.0000319

import time

# コピーを作成する方法
def with_copy(n):
    def helper(path, idx):
        if idx == n:
            result.append(path[:])  # コピーを保存
            return
        helper(path + [idx], idx + 1)  # 新しいリストを作成
    result = []
    helper([], 0)
    return result

# バックトラッキングの方法
def with_backtracking(n):
    def helper(path, idx):
        if idx == n:
            result.append(path[:])  # コピーを保存
            return
        path.append(idx)
        helper(path, idx + 1)  # リストを直接変更
        path.pop()  # 戻す
    result = []
    helper([], 0)
    return result

n = 100  # 再帰の深さ
start = time.time()
with_copy(n)
print("With copy:", time.time() - start)

start = time.time()
with_backtracking(n)
print("With backtracking:", time.time() - start)