回答編集履歴
2
誤字の修正
test
CHANGED
|
@@ -96,7 +96,7 @@
|
|
|
96
96
|
|
|
97
97
|
|
|
98
98
|
|
|
99
|
-
[TimeComplexity - Python Wiki](https://wiki.python.org/moin/TimeComplexity)によるとlistの削除はO(n)らしく、`pop(0)`もO(n)と思われます。なお、deque版も作りましたが、資料でO(1)とある通りに一定サイズ以上はほぼ同じ速度になります。Ruby 2.4.0のArray#shf
|
|
99
|
+
[TimeComplexity - Python Wiki](https://wiki.python.org/moin/TimeComplexity)によるとlistの削除はO(n)らしく、`pop(0)`もO(n)と思われます。なお、deque版も作りましたが、資料でO(1)とある通りに一定サイズ以上はほぼ同じ速度になります。Ruby 2.4.0のArray#shiftについても同様にO(1)のようで、一定サイズ以上はほぼ同じ速度です。
|
|
100
100
|
|
|
101
101
|
|
|
102
102
|
|
|
@@ -112,10 +112,10 @@
|
|
|
112
112
|
|
|
113
113
|
|
|
114
114
|
|
|
115
|
-
なぜ、RubyのArray#shf
|
|
115
|
+
なぜ、RubyのArray#shiftは速いのか？
|
|
116
116
|
|
|
117
117
|
|
|
118
118
|
|
|
119
|
-
RubyのArray#shf
|
|
119
|
+
RubyのArray#shiftは、配列が一定サイズ以上の場合、メモリ上の配列はそのままで先頭のポインタをずらすという手法を採っています。メモリ的には不利ですが、速度的には有利になります。サイズの大きさで処理を変えることで、同じ書き方でもなるべく高速に動作させるという戦略のようです。
|
|
120
120
|
|
|
121
121
|
[https://github.com/ruby/ruby/blob/ruby_2_4/array.c#L1000](https://github.com/ruby/ruby/blob/ruby_2_4/array.c#L1000)
|
1
追記
test
CHANGED
|
@@ -29,3 +29,93 @@
|
|
|
29
29
|
|
|
30
30
|
|
|
31
31
|
問題によるかもしれませんが、私の実装では誤差程度しか出ませんでした。
|
|
32
|
+
|
|
33
|
+
|
|
34
|
+
|
|
35
|
+
---
|
|
36
|
+
|
|
37
|
+
|
|
38
|
+
|
|
39
|
+
以下のようなプログラムを作り、配列のサイズによってpop()がどうなるかを試しました。
|
|
40
|
+
|
|
41
|
+
|
|
42
|
+
|
|
43
|
+
```Python
|
|
44
|
+
|
|
45
|
+
import random
|
|
46
|
+
|
|
47
|
+
import time
|
|
48
|
+
|
|
49
|
+
|
|
50
|
+
|
|
51
|
+
while True:
|
|
52
|
+
|
|
53
|
+
n, m = [int(i) for i in input().split()]
|
|
54
|
+
|
|
55
|
+
if n <= 0:
|
|
56
|
+
|
|
57
|
+
break
|
|
58
|
+
|
|
59
|
+
list = [random.randrange(n) for _ in range(n)]
|
|
60
|
+
|
|
61
|
+
|
|
62
|
+
|
|
63
|
+
start_time = time.time()
|
|
64
|
+
|
|
65
|
+
for _ in range(m):
|
|
66
|
+
|
|
67
|
+
list.pop(0)
|
|
68
|
+
|
|
69
|
+
end_time = time.time()
|
|
70
|
+
|
|
71
|
+
|
|
72
|
+
|
|
73
|
+
print("%.8f" % (end_time - start_time))
|
|
74
|
+
|
|
75
|
+
```
|
|
76
|
+
|
|
77
|
+
|
|
78
|
+
|
|
79
|
+
Python3 3.6.0 macOS Siera
|
|
80
|
+
|
|
81
|
+
|配列サイズ|取出数|試行回数|平均|最小|最大|
|
|
82
|
+
|
|
83
|
+
|---|---|---|---|---|
|
|
84
|
+
|
|
85
|
+
|10|10|10|0.00000560|0.00000286|0.00002098|
|
|
86
|
+
|
|
87
|
+
|100|10|10|0.00000367|0.00000262|0.00000405|
|
|
88
|
+
|
|
89
|
+
|1000|10|10|0.00000801|0.00000477|0.00001383|
|
|
90
|
+
|
|
91
|
+
|10000|10|10|0.00004036|0.00003099|0.00005794|
|
|
92
|
+
|
|
93
|
+
|100000|10|10|0.00100026|0.00080609|0.00132823|
|
|
94
|
+
|
|
95
|
+
|1000000|10|10|0.01386561|0.01161385|0.01659012|
|
|
96
|
+
|
|
97
|
+
|
|
98
|
+
|
|
99
|
+
[TimeComplexity - Python Wiki](https://wiki.python.org/moin/TimeComplexity)によるとlistの削除はO(n)らしく、`pop(0)`もO(n)と思われます。なお、deque版も作りましたが、資料でO(1)とある通りに一定サイズ以上はほぼ同じ速度になります。Ruby 2.4.0のArray#shfitについても同様にO(1)のようで、一定サイズ以上はほぼ同じ速度です。
|
|
100
|
+
|
|
101
|
+
|
|
102
|
+
|
|
103
|
+
このことから、一定サイズ以上のlistをキューに使用するとかなり遅くなる場合があり得ます。キューにはdequeを使って回避するのが良いでしょう。
|
|
104
|
+
|
|
105
|
+
|
|
106
|
+
|
|
107
|
+
---
|
|
108
|
+
|
|
109
|
+
|
|
110
|
+
|
|
111
|
+
【蛇足】
|
|
112
|
+
|
|
113
|
+
|
|
114
|
+
|
|
115
|
+
なぜ、RubyのArray#shfitは速いのか？
|
|
116
|
+
|
|
117
|
+
|
|
118
|
+
|
|
119
|
+
RubyのArray#shfitは、配列が一定サイズ以上の場合、メモリ上の配列はそのままで先頭のポインタをずらすという手法を採っています。メモリ的には不利ですが、速度的には有利になります。サイズの大きさで処理を変えることで、同じ書き方でもなるべく高速に動作させるという戦略のようです。
|
|
120
|
+
|
|
121
|
+
[https://github.com/ruby/ruby/blob/ruby_2_4/array.c#L1000](https://github.com/ruby/ruby/blob/ruby_2_4/array.c#L1000)
|