質問編集履歴

様々な頂点数で時間を測った結果を追記

2019/07/22 01:53

投稿

gottadiveintopy

スコア736

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -141,3 +141,223 @@
 になると思います。
+### 追記
+私が書いた上二つの方法と`hayataka2049`さんの物と`bamboo-nova`さんの物を、頂点数を色々変えて実行時間を測ってみたので載せておきます。
+```python3
+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))
+```
+```text
+頂点数: 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()`の順に速いとなりました。

コードのbugを修正

2019/07/22 01:53

投稿

gottadiveintopy

スコア736

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -93,3 +93,51 @@
 - Python: 3.7.1
+### 追記
+`method_1()`がそもそも正しく動いていませんでした。正しくは
+```python3
+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)
+```
+になると思います。