listの要素を偶数番目と奇数番目に分けて同じ処理を行いたい時の効率的な方法は？

Question

以下のように2次元の頂点の座標が入ったlistがあるのですが

[x1, y1, x2, y2, x3, y3, ...]

ここからxの最小値, yの最小値, xの最大値, yの最大値を求める方法、言い換えるなら全ての頂点を包括する最小の長方形(回転はさせない)を効率よく求める方法を教えて欲しいです。自分で思いついたコードは以下の二つなのですが

def method_1(points):
    max_x, min_x, max_y, min_y = 0, 0, 0, 0
    try:
        it = iter(points)
        while True:
            x = next(it)
            max_x = max(max_x, x)
            min_x = min(min_x, x)
            y = next(it)
            max_y = max(max_y, y)
            min_y = min(min_y, y)
    except StopIteration:
        pass
    return (min_x, min_y, max_x, max_y)


def method_2(points):
    half_length = len(points) // 2
    x_list = [None] * half_length
    y_list = [None] * half_length
    x_index = 0
    y_index = 0
    try:
        it = iter(points)
        while True:
            x_list[x_index] = next(it)
            y_list[y_index] = next(it)
            x_index += 1
            y_index += 1
    except StopIteration:
        pass
    return (min(x_list), min(y_list), max(x_list), max(y_list))

もっと良い方法はあるでしょうか？

(頂点数は100未満で、非標準moduleを使わないという条件での効率的な方法を探しています、)

環境

• Python: 3.7.1

追記

method_1()がそもそも正しく動いていませんでした。正しくは

def method_1(points):
    try:
        it = iter(points)
        max_x = min_x = next(it)
        max_y = min_y = next(it)
        while True:
            x = next(it)
            max_x = max(max_x, x)
            min_x = min(min_x, x)
            y = next(it)
            max_y = max(max_y, y)
            min_y = min(min_y, y)
    except StopIteration:
        pass
    return (min_x, min_y, max_x, max_y)

になると思います。

追記

私が書いた上二つの方法とhayataka2049さんの物とbamboo-novaさんの物を、頂点数を色々変えて実行時間を測ってみたので載せておきます。

def method_1(points):
    try:
        it = iter(points)
        max_x = min_x = next(it)
        max_y = min_y = next(it)
        while True:
            x = next(it)
            max_x = max(max_x, x)
            min_x = min(min_x, x)
            y = next(it)
            max_y = max(max_y, y)
            min_y = min(min_y, y)
    except StopIteration:
        pass
    return (min_x, min_y, max_x, max_y)


def method_2(points):
    half_length = len(points) // 2
    x_list = [None] * half_length
    y_list = [None] * half_length
    x_index = 0
    y_index = 0
    try:
        it = iter(points)
        while True:
            x_list[x_index] = next(it)
            y_list[y_index] = next(it)
            x_index += 1
            y_index += 1
    except StopIteration:
        pass
    return (min(x_list), min(y_list), max(x_list), max(y_list))


def method_hayataka(points):
    even = points[::2]
    odd = points[1::2]
    return min(even), min(odd), max(even), max(odd)


def method_bamboo(points):
    x_list = []
    y_list = []
    it = iter(points)
    for v in it:
        x_list.append(v)
        y_list.append(next(it))
    return (min(x_list), min(y_list), max(x_list), max(y_list))


import random
import timeit

for num_points in (10, 50, 100, 150, 200, 5000):
    print(f'\n頂点数: {num_points // 2}')
    points = [random.randrange(1000)%100 for _ in range(num_points)]
    print('method_1():', timeit.timeit(lambda :method_1(points), number=1000))
    print('method_2():', timeit.timeit(lambda :method_2(points), number=1000))
    print('method_hayataka():', timeit.timeit(lambda :method_hayataka(points), number=1000))
    print('method_bamboo():', timeit.timeit(lambda :method_bamboo(points), number=1000))

頂点数: 5
method_1(): 0.027533224085345864
method_2(): 0.025170729029923677
method_hayataka(): 0.013926777057349682
method_bamboo(): 0.01895964704453945

頂点数: 25
method_1(): 0.08861580200027674
method_2(): 0.0367969439830631
method_hayataka(): 0.00978929502889514
method_bamboo(): 0.03307596605736762

頂点数: 50
method_1(): 0.11920186190400273
method_2(): 0.05401027004700154
method_hayataka(): 0.015701663098298013
method_bamboo(): 0.0533315270440653

頂点数: 75
method_1(): 0.1530481429072097
method_2(): 0.07044070307165384
method_hayataka(): 0.018882130039855838
method_bamboo(): 0.058508455054834485

頂点数: 100
method_1(): 0.22204544604755938
method_2(): 0.08647163794375956
method_hayataka(): 0.02639697107952088
method_bamboo(): 0.06969467597082257

頂点数: 2500
method_1(): 4.2770471959374845
method_2(): 1.7805748030077666
method_hayataka(): 0.2754193090368062
method_bamboo(): 1.3511152860010043

というわけで結果はすべての場合において

method_hayataka() > method_bamboo() > method_2() > method_1()の順に速いとなりました。

Answer 1

一般論としてpythonでループを書くと遅いので、非効率だと思っても安直にやった方が良い結果を生んだりします。

import random
import timeit

def method_1(points):
    max_x, min_x, max_y, min_y = 0, 0, 0, 0
    try:
        it = iter(points)
        while True:
            x = next(it)
            max_x = max(max_x, x)
            min_x = min(min_x, x)
            y = next(it)
            max_y = max(max_y, y)
            min_y = min(min_y, y)
    except StopIteration:
        pass
    return (min_x, min_y, max_x, max_y)


def method_2(points):
    half_length = len(points) // 2
    x_list = [None] * half_length
    y_list = [None] * half_length
    x_index = 0
    y_index = 0
    try:
        it = iter(points)
        while True:
            x_list[x_index] = next(it)
            y_list[y_index] = next(it)
            x_index += 1
            y_index += 1
    except StopIteration:
        pass
    return (min(x_list), min(y_list), max(x_list), max(y_list))

def method_3(points):
    even = points[::2]
    odd = points[1::2]
    return min(even), min(odd), max(even), max(odd)

points = [random.randrange(100) for _ in range(150)]

print(timeit.timeit(lambda :method_1(points), number=1000))
print(timeit.timeit(lambda :method_2(points), number=1000))
print(timeit.timeit(lambda :method_3(points), number=1000))

""" =>
0.06728547700913623
0.029172458976972848
0.010517314949538559
"""

あとmethod_1とmethod_2は結果が一致しないので、チェックする必要がありそう。

Comments

[gottadiveintopy]

回答ありがとうございます、おかげでbugに気づきました(^_^;)。 実行速度ばかり気にしていて他の事がおろそかになってしまったようです。

method_3()が読みやすさも実行速度も最高のようなので、これを使おうと思います。
(そもそもこの構文([::2])を忘れていました。)

[hayataka2049]

これが計算コスト的に効率が悪いのは事実で、本来は1回のループで済むと言えば済みます（このコードだとmin,maxを4回呼ぶのでそれだけで4倍＋スライスで余計なオブジェクトを生成するのでそのオーバーヘッドが乗る）。
ただ、pythonレイヤでそれをやると組み込みの実装の方が速いので、勝ち目はありません。
最速を追求するならC拡張で書く？　みたいな話になってしまいます（一応標準でできるはずだけど、私もやったことないし・・・）。

[gottadiveintopy]

> これが計算コスト的に効率が悪いのは事実で...

言われてみるとそうですね。実は頂点数しだいではmethod_1()が最も速くなるんじゃないかと期待していたのですが、そんなことありませんでした。(計測結果を追記しました)。なのでやはりmethod_3()が良い気がします。

Answer 2

イテレータにして二つずつ取り出した方が綺麗にかけると思います。よかったら参考にして見てください。

inp = [2, 3, 1, 4, 5, 1]
res1 = []
res2 = []
it = iter(inp)

for i in it:
    res1.append(i)
    res2.append(next(it))
    
print(min(res1))
print(max(res1))
print(min(res2))
print(max(res2))

Comments

[gottadiveintopy]

回答ありがとうございます(^_^) こちらのコードの方が簡潔で読みやすいですね。ただlistに一つずつ加える事が、実行効率を落とさないか気になりました。私がmethod_2()のように一気にlistの領域を確保する方法に至ったのもそのためです。

[gottadiveintopy]

今 実際に時間を測ってみた所、bamboo-novaさんの方法はmethod_3()に次いで二番目に早いことが分かりました。よく調べもせずに効率がどうのこうの言ってすいません。後ですがfor文を使いながらも二つずつ要素を取り出せるのは盲点でした。