Pythonでリストや配列の計算速度を比較してみた

こんにちは、サイオステクノロジーの藤井です。

Pythonで数値計算するならnumpyが速いって聞くけど実際どれぐらい速いのか、また、他の書き方(リストの内包表記など)だとどのくらい時間がかかるのか比較してみました。

numpyとは

numpyとは、WikipediaによるとPythonにおいて数値計算を効率的に行うための拡張モジュールです。Pythonは動的型付け言語なので静的型付け言語(CやJavaなど)に比べて数値計算に時間がかかってしまいますが、numpyは内部がC言語で実装されているので高速に数値計算ができます。

実行速度の比較

今回は3つの計算についてそれぞれ、numpyを使う場合とそのほか考えられる計算方法で実行速度を比較しました。

計算が軽い順に、①単純な数値の加算、②リストや配列の要素同士の加算、③行列の積、です。

結果を簡単にまとめると、

  • ①はnumpyを使わない方が速い
  • ②はリストや配列のサイズによって変わる
  • ③はnumpyを使った方が速い

となりました。

実行環境

  • Windows 10
  • CPU: i5-8265U
  • メモリ:16GB
  • Anaconda3-2020.02
  • Python 3.7.6
  • numpy 1.18.1

実験① 数値の加算

まずはただの2つの数字の足し算です。

  1. +演算子
  2. 組み込み関数sum()
  3. numpyの+演算子
  4. numpyのsum()

の4つの方法を比較しました。

実験①の結果まとめ

方法 実行時間(ミリ秒)
+演算子 0.000166
リストに入れてsum() 0.000599
numpyの足し算 0.00176
numpyのsum()関数 0.00422

+演算子を使う方法が最も速く計算を行うことができました。

 

準備

aとbは0から1までの乱数です。この二つの合計を求める時間を競います。実行速度は30000回実行した平均を求めています。(有効数字3桁で四捨五入してます(が誤差が大きいので3桁目は参考にならないと思います))

import numpy as np
import time
import random
a=random.random()
b=random.random()

+演算子

足し算するなら、まあ普通こう書くと思います。

start=time.time()
c=a+b
t=time.time()-start

結果:0.000166ms

リストに入れてsum()

組み込み関数のsum()を使って合計を求めました。この実験では加算以外の処理(リストを作ったりだとか)は実行時間に含めていません。

l=[a,b]
start=time.time()
c=sum(l)
t=time.time()-start

結果:0.000599ms

numpyの足し算

numpyのarrayどうしを足すと要素ごとに加算されます。

a=np.array([random.random()])
b=np.array([random.random()])
start=time.time()
c=a+b
t=time.time()-start

結果:0.00176ms

numpyのsum()関数

numpyのsum関数を使うとarrayの要素の和が求まります。

n=np.array([a,b])
start=time.time()
c=np.sum(n)
t=time.time()-start

結果:0.00422ms

実験② リストや配列の要素どうしを加算

次は2つのリストの要素を足す計算です。

こんな計算です。

リストの要素数によって速い計算方法が変わりそうなので、要素数2,20,200の3パターンで比較しました。

  1. for文でリストの要素を1つずつ加算して新しいリストに追加
  2. 1.をリストの内包表記で記述
  3. 2.を組み込み関数zip()を使って改良
  4. 組み込み関数map()を使用
  5. numpyで加算
  6. numpyで加算+ndarray化とリスト化の型変換の時間

の6つの方法を比較しました。

実験②の結果まとめ

方法 実行時間(要素数2)(ms) 実行時間(要素数20)(ms) 実行時間(要素数200)(ms)
for文で1つずつ追加 0.00120 0.00325 0.0448
リストの内包表記 0.000800 0.00233 0.0315
zip()を使った内包表記 0.00104 0.00160 0.0191
map()を使用 0.000301 0.00146 0.0160
numpyで加算 0.000702 0.000731 0.00120
numpy+リスト化 0.00209 0.00416 0.0190

要素数2の場合の実行時間は

numpy+リスト化>for文>zip()>内包表記>numpy>map()

要素数20の場合の実行時間は

numpy+リスト化>for文>内包表記>zip()>map()>numpy

要素数200の場合の実行時間は

for文>内包表記>zip()≒numpy+リスト化>map>numpy

となりました。

リスト化は結構時間がかかるようです。

要素数が少ない場合はmap()を使うのが高速で、要素数が2桁になるあたりからnumpyの方が高速に計算できるようです。要素数が2桁になるようなリストの各要素を足すような計算する場合はnumpyを使った方が速くなりそうです。

さらに要素数を増やして実験してみましたが、numpy+リスト化では、mapより速くなることはなさそうです。リストの各要素を足すような計算する場合(かつ、プログラムのほかの部分との兼ね合いなどでデータをリスト型で保持しなければならない場合)、計算時だけnumpyに変換するのは逆に遅くなるようです。

準備

aとbは0から1までの乱数をn個含むリストです。a+bを求める時間を競います。実行速度は30000回実行した平均を求めています。(有効数字3桁で四捨五入してます)

import numpy as np
import time
import random
from operator import add

def randomList(n):
    out=[]
    for x in range(n):
        out.append(random.random())
    return out

a=randomList(n)
b=randomList(n)

for文でリストの中を1つずつ足していく

空のリストcにaとbの要素の和を追加していきます。

start=time.time()
c=[]
for x in range(len(a)):
    c.append(a[x]+b[x])
t=time.time()-start

結果はまとめて書きます。

リストの内包表記

pythonでは、リストの内包表記を使うと早くなります。(読みにくくなりますが)

start=time.time()
c=[a[i]+b[i] for i in range(len(a))]
t=time.time()-start

リストのzip()を使った内包表記

range(len(a))としたうえでa[i]と参照しているのが冗長だと感じたので組み込み関数のzip()を使って単純化します。zip()はイテラブルから要素を集めたイテレータを作る関数で、

[1,2,3], [4,5,6] → (1,4), (2,5), (3,6)

という変換を行ってくれます。

start=time.time()
c=[x+y for (x,y) in zip(a,b)]
t=time.time()-start

組み込み関数map()を使用

map()はmap(関数名 , イテラブルな引数 , ゙…)と書きます。イテラブルな引数はリストやタプルやrange()などです。イテラブルな引数 の要素を関数に適応させたイテレーターを出力します。(出力はリストではないのでlist()でリスト化させています。)

addは+演算子と同じ働きをする関数です。(from operator import add で使えるようになります。)

start=time.time()
c=list(map(add,a,b))
t=time.time()-start

numpyで加算

本題のnumpyです。numpyの配列は+演算子で要素ごとの加算を計算します。(リストに+演算子を使うとリストの結合が行われます。)

an=np.array(a)
bn=np.array(b)
start=time.time()
c3=an+bn
t=time.time()-start

numpyで加算後リスト化

上記の方法は、numpy.ndarray型の配列を計算しnumpy.ndarray型の配列を出力する時間になっています。ほかの方法は、リストを使っているので、”リストの要素どうしを加算したリスト”を計算する時間という意味では、

リスト → numpy.ndarray化 → numpyで計算 → リスト化

の時間で比較する方が平等かもしれません。

ndarrayをリスト化するときはndarray.tolist()を使っています。list(ndarray)でもリスト化できますが、tolist()の方が速かったです。

start=time.time()
an=np.array(a) 
bn=np.array(b)  
c=(an+bn).tolist()
t=time.time()-start

実験③ 行列の積

最後はnumpyの十八番、行列の演算で比較しました。numpyが速いのは当然としてほかの方法でもどこまで高速化できるか比較してみたいと思います。

今回は正方行列どうしの積を求めます。仮に2×2の正方行列ならこのような計算になります。

行列のサイズによって速い計算方法が変わりそうなので、2×2,10×10,100×100の3パターンで比較しました。

  1. for文で計算
  2. 1.をリストの内包表記で記述
  3. 2.を組み込み関数zip()を使って改良
  4. 3.を組み込み関数map()を使ってさらに高速化

実験③の結果まとめ

方法 2×2(ミリ秒) 10×10(ミリ秒) 100×100(ミリ秒)
for文 5.32 22.9 272
リストの内包表記 0.00332 0.233 171
zip()を使った内包表記 0.00000715 0.193 106
map()を使用 0.100 0.219 66.8
numpy 0.00295 0.00336 1.60

とても小さい行列でない限りnumpyを使う方法が最も速いです。

numpy以外ではmap()を使った内包表記が比較的速いですが、それでもnumpyの数十倍時間がかかってます。

準備

aとbはn×nの正方行列で各要素は0から1までの乱数です。abを求める時間を比較します。実行速度は300回実行した平均を求めています。(有効数字3桁で四捨五入してます)

import numpy as np
import time
import random
from operator import mul
from multiprocessing import Pool

def randomMatrix(n):
    out=[]
    for x in range(n):
        g=[]
        for y in range(n):
            g.append(random.random())
        out.append(g)
    return out

a=randomMatrix(n)
b=randomMatrix(n)

for文で計算

3重にfor文を回して計算しています。nの3乗回も掛け算してるので見るからに遅そうですね。

start=time.time()
c=[]
for x in range(len(a)):
    gyou=[]
    for y in range(len(b[0])):
        total=0
        for z in range(len(b)):
            total+=a[x][z]*b[z][y]
        gyou.append(total)
    c.append(gyou)
t=time.time()-start

結果は下にまとめて書きます。

リストの内包表記

上のfor文を内包表記に書き換えています。+の部分はsum()を使っています。

start=time.time()
c=[[sum([a[x][z]*b[z][y] for z in range(len(b))]) for y in range(len(b[0]))] for x in range(len(a))]
t=time.time()-start

zip()を使ったリストの内包表記

zip()などを使ってrange(len())の部分を単純化しました。

start=time.time()
c=[[sum([axz*byz for (axz,byz) in zip(ax,by)]) for by in zip(*b)] for ax in a]
t=time.time()-start

map()を使ったリストの内包表現

実験②でmap()を使うと高速という結果が出ていたので、掛け算とsum()の部分をmap()にさせて高速化しました。

start=time.time()
c=[list(map(sum,[map(mul,ax,by) for by in zip(*b)])) for ax in a]
t=time.time()-start

numpy

numpyで行列の積を計算するときはnumpy.dot()を使います。

an=np.array(a)
bn=np.array(b)
start=time.time()
c=np.dot(an,bn)
t=time.time()-start

マルチプロセス

高速化のほかの方法としてマルチプロセスを使ってみました。pythonでは通常、CPUを1つしか使用しませんが、マルチプロセスにすることで複数のCPUを使用することができます。以下のソースコードはmap()を使った内包表記にマルチプロセスを組み合わせています。

def f(ax,b):
    return list(map(sum,[map(mul,ax,by) for by in zip(*b)]))

if __name__ == "__main__":
    start=time.time()
    with Pool(8) as p:
        proc3=p.starmap(f,zip(a,[b]*len(a)))
    t=time.time()-start

マルチプロセスを使うときは、引数が1つの場合はPool.map(関数名,引数)を、複数ある場合はPool.starmap(関数名,引数)を使います。

注意する点としては、mainを明示的に書かなければなりません。書かないとエラーが無限に止まりませんでした。

結果としては、100×100の行列の積で約1400ミリ秒かかりました。(これは300回計測した平均ではなく1回しか計測していないのであまり正確な数値ではないです。)

他の方法よりも遅くなってしまいました。どうやらマルチプロセスでは、プロセス内の処理(このプログラムでいうf()のことです)がある程度重たくないとあまり速くならないようです。以下のように行列のサイズを大きくするとnumpy以外よりは速くなりました。

  100×100 300×300 1000×1000
map()を使用 0.0780秒 1.75秒 121秒
numpy 0.00504秒 0.0199秒 0.232秒
マルチプロセス 1.40秒 3.84秒 95.2秒

まとめ

この記事で書いたこと

  • numpyってなに
  • 簡単な計算ではnumpyは遅い
  • リストの加算では要素数10以上ならnumpyが速い、numpy以外ならmap()を使うのが速い
  • 行列の積ではnumpyが速いし読みやすい
  • マルチプロセスは1つのプロセスにそれなりに重たい処理がないと逆に遅くなる

numpyですが、pipでインストールしたものとcondaでインストールしたものではconda版のnumpyの方が速いという話を聞きました。pip版を使うとまた違った結果が出るかもしれません。

ご覧いただきありがとうございます! この投稿はお役に立ちましたか?

役に立った 役に立たなかった

1人がこの投稿は役に立ったと言っています。

コメントを残す

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