Help us understand the problem. What is going on with this article?

Pythonでループ内の最大値を求める場合の速度比較[if, max, list, set, numpy]

はじめに

Project Eulerの問題を解いていると、ある条件下で答えが最大となるものを解答することが多いと感じました。
大体forやwhileのループで回した中で最大を出すのですが、毎ループごとにifで比較するのとlistなどに追加して最後にmax()で最大値を取得するのどっちが早いのだろうと疑問に思ったので試してみました。

試したもの

  • ループごとにifで判定する
  • ループごとにmax()で判定する
  • listに追加していき、ループ後にmax()
  • setに追加していき、ループ後にmax()
  • numpy.ndarrayにnumpy.appendで追加していき、ループ後にmax()

追記:numpy.appendはこれまでlist.appendと同じように使ってしまっていた自分への戒めとして計測してみました。

条件

for i in range(10 ** 8):で1億回ループを行い、最も大きいiを判定(答えは9999999)

def testA():
    # ループごとにifで大小比較
    max_num = 0
    for i in range(10 ** 8):
        if max_num < i:
            max_num = i
    #print(max_num)

def testB():
    # ループごとにmaxで大小比較
    max_num = 0
    for i in range(10 ** 8):
        max_num = max(max_num, i)
    #print(max_num)

def testC():
    # listにappendその後max判定
    ls = []
    for i in range(10 ** 8):
        ls.append(i)
    max(ls)

def testD():
    # numpy.ndarrayにappendその後max判定
    # このやり方は非常に問題のあるやり方なので普通は使わない
    arr = np.empty((0,))
    for i in range(10 ** 5):
        arr = np.append(arr, i)
    np.max(arr)
    #print(np.max(arr))

def testE():
    # setにaddその後max判定
    st = set()
    for i in range(10 ** 8):
        st.add(i)
    max(st)
    #print(max(st))

setやnumpy.ndarrayも同様に。
numpy.appendを使ったtestDは不適切な例として作成しました。

結果

結果としてループごとにif文で判定が最速、次点でlistとなりました。

条件 実行時間
ifで判定 7.894秒
maxで判定 19.869秒
list 12.700秒
set 23.937秒
numpy.ndarray 10**6でも600秒以上

考察

個人的に、今回の結果で少し意外だった点はifの代わりにmaxで判定を行うとlist.append()より遅いということです。
理由としては、maxは引数に配列を与えても最大値を取り出せますが、その分単純な2値の比較では無駄が多いということが考えられます。
また、setがlistの倍近く遅いということもわかりました。これはlistへの要素追加が末尾に追加するだけであるのに対し、setでは重複しないように処理する必要があるからなのではないかと考えます。
よく言われていることですが、numpy.append()は他の方法とは比較にならないほど遅いということが改めてわかりました。長さが変わる配列を扱う場合には一度listに変換したほうが良いでしょう。

結語

  • ループ内での最大値を求めるにはifが早い。
  • 2値の比較ではmax()は使わない。
  • numpy.appendは使わない。appendするならlistに変換。

以前のコードでは対して気にせずnumpy.append()を多用していましたが、今後は気をつけていこうと思います。
もしifより早い方法があればご教授願います。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away