pythonのリスト操作が強力すぎる

まず、下のソースを見てください。

def checkio(data):
    if len(data) == 1:
        return data[0][0]
    else:
        r = range(len(data))
        exp = [data[i][0] * checkio([data[x][1:] for x in r if x != i]) for i in r]
        return sum(exp[::2]) - sum(exp[1::2])

これ、checkioの課題で書いたコードなんでcheckioって名前ついてますが、dataで与えられる大きさNの正方行列の行列式を返します。例えば

data = [[1, 2], [2, 3]]
assert checkio(data) == -1

なんていう感じです。checkio(data)って計算させると、-1とか正解してくれちゃうんですよ。

それで、何がいいたいかというと、たった7行なんですよ。7行で行列式が計算できちゃう。今はどうだか知りませんが、ある行列の行列式を計算するっていうのは高校の数学の演習問題程度にはなっちゃう課題なんですよね。それが7行で記述できちゃう。今時の高校生は、たった7行のプログラムをpythonで書いてしまえば、その日の授業の演習問題の正解が計算できちゃう。余った時間で部活をするも良し、テレビを見るのもよし、デートにいくのも良し。青春を満喫できるわけですよ。

それで、たった7行で行列式を計算するためには、いちいち細かい計算の仕方を手取り足取りプログラムしていちゃだめナンですよ。今時そんなヤリ方は時代遅れ。プログラムには定義だけを記述します。実際に今回のソースには、len(data)==1の場合と、それ以外の場合に、何を返すかの定義を行なっているにすぎません。

ところで、定義を簡明に記述するためには、それなりの道具が必要です。今回の課題でいえば、正方行列dataの部分行列を簡単に記述できる必要があります。具体的には、6行目のcheckio再帰呼出で引数として使われている部分ですね。

[data[x][1:] for x in r if x != i]

これが、dataの部分行列data'を定義しているンです。ここで使われているのが、リスト内包表記と、スライスで、いずれもpythonでとても強力だと評価されている機能です。

まずはスライスの説明から。
一般的には、list[n]でlistのn番目の要素にアクセスできますが、pythonではlist[n:]でlistのn番目以降の部分リストを取得できます。list[n:m]でlistのn番目からm-1番目までの部分リストを取得できます。list[-n:]でリストの後ろからn番目から最期までの部分リストが取得できます。さらにlist[::2]で、リストの(先頭を0番目と数えた場合の)偶数番目の要素をあつめた部分リストを取得できます。list[1::2]だったらリストの奇数番目の部分リストってことですね。今回の例でいえば、data[x][1:]と書くと、dataのx行目の1列目から最期までの部分リストが取得できる訳ですね。これってスゴいと思いませんか？

スライスを使えば、dataの任意の行の部分行列が取得できるのはわかりましたが、それだけでは不十分です。今回の例でいえば、dataの0行目からN-1行目までのうち、i行目を除く全ての行をリストアップしなければなりません。そこで活躍するのがリスト内包表記です。それで、リスト内包表記について丁寧に説明しようと思いましたが、すっかり酔いも回ってきて面倒くさいので止めます。っていうかもう説明書いたような気がする。どーしても知りたい人はググってください。それじゃ。

(追記)
N=10の浮動小数点を要素にもつ正則行列の行列式を計算させた所、15秒ちょっとでした。AMD Athlon II 640プロセッサでlinux上で走らせてみました。N==2の場合の計算式を与えてやると(たった2行の追加)、計算時間は半分になります。
実行するコード

def checkio(data):
    if len(data) == 1:
        return data[0][0]
    elif len(data) == 2:
        return data[0][0] * data[1][1] - data[0][1] * data[1][0]
    else:
        r = range(len(data))
        exp = [data[i][0] * checkio([data[x][1:]
                                     for x in r if x != i]) for i in r]
        return sum(exp[::2]) - sum(exp[1::2])

if __name__ == '__main__':
    data = [[1.2, 2, 3, 4, 5, 6, 7, 8, 9, 10],
            [2, 3, 3, 5, 6, 7, 8, 9, 10, 1],
            [3, 4, 5, 6, 7, 8, 9, 10, 1, 2],
            [4, 5, 6, 7, 8, 9, 10, 1, 2, 3],
            [5, 6, 7, 8, 9, 10, 1, 2, 3, 4],
            [6, 7, 8, 9, 10, 1, 2, 3, 4, 5],
            [7, 8, 9, 10, 1, 2, 3, 4, 5, 6],
            [8, 9, 10, 1, 2, 3, 4, 5, 6, 7],
            [9, 10, 1, 2, 3, 4, 5, 6, -7.4, 8],
            [10, 1, 2, 3, 4, 5, 6, 7, 8, 9],
            ]
    print(checkio(data))

実行結果

dwarfjay $ python -m cProfile determinant.py                                                               
-6017528000.0
         12802310 function calls (10195810 primitive calls) in 7.952 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   11.742   11.742 determinant.py:1(<module>)
2606501/1    4.508    0.000   11.742   11.742 determinant.py:1(checkio)
  2606500    2.411    0.000    2.411    0.000 determinant.py:8(<listcomp>)
        1    0.000    0.000   11.742   11.742 {built-in method exec}
  6005103    0.554    0.000    0.554    0.000 {built-in method len}
        1    0.000    0.000    0.000    0.000 {built-in method print}
  1584202    0.479    0.000    0.479    0.000 {built-in method sum}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}