回答編集履歴
2
誤字の修正
answer
CHANGED
|
@@ -47,7 +47,7 @@
|
|
|
47
47
|
|100000|10|10|0.00100026|0.00080609|0.00132823|
|
|
48
48
|
|1000000|10|10|0.01386561|0.01161385|0.01659012|
|
|
49
49
|
|
|
50
|
-
[TimeComplexity - Python Wiki](https://wiki.python.org/moin/TimeComplexity)によるとlistの削除はO(n)らしく、`pop(0)`もO(n)と思われます。なお、deque版も作りましたが、資料でO(1)とある通りに一定サイズ以上はほぼ同じ速度になります。Ruby 2.4.0のArray#
|
|
50
|
+
[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)のようで、一定サイズ以上はほぼ同じ速度です。
|
|
51
51
|
|
|
52
52
|
このことから、一定サイズ以上のlistをキューに使用するとかなり遅くなる場合があり得ます。キューにはdequeを使って回避するのが良いでしょう。
|
|
53
53
|
|
|
@@ -55,7 +55,7 @@
|
|
|
55
55
|
|
|
56
56
|
【蛇足】
|
|
57
57
|
|
|
58
|
-
なぜ、RubyのArray#
|
|
58
|
+
なぜ、RubyのArray#shiftは速いのか？
|
|
59
59
|
|
|
60
|
-
RubyのArray#
|
|
60
|
+
RubyのArray#shiftは、配列が一定サイズ以上の場合、メモリ上の配列はそのままで先頭のポインタをずらすという手法を採っています。メモリ的には不利ですが、速度的には有利になります。サイズの大きさで処理を変えることで、同じ書き方でもなるべく高速に動作させるという戦略のようです。
|
|
61
61
|
[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
追記
answer
CHANGED
|
@@ -13,4 +13,49 @@
|
|
|
13
13
|
|
|
14
14
|
(作り方がRuby脳なのかな…全く同じアルゴリズムの筈だけどPythonだと遅すぎるし、PyPy3だと逆にTLEとか、なぜだ…)
|
|
15
15
|
|
|
16
|
-
問題によるかもしれませんが、私の実装では誤差程度しか出ませんでした。
|
|
16
|
+
問題によるかもしれませんが、私の実装では誤差程度しか出ませんでした。
|
|
17
|
+
|
|
18
|
+
---
|
|
19
|
+
|
|
20
|
+
以下のようなプログラムを作り、配列のサイズによってpop()がどうなるかを試しました。
|
|
21
|
+
|
|
22
|
+
```Python
|
|
23
|
+
import random
|
|
24
|
+
import time
|
|
25
|
+
|
|
26
|
+
while True:
|
|
27
|
+
n, m = [int(i) for i in input().split()]
|
|
28
|
+
if n <= 0:
|
|
29
|
+
break
|
|
30
|
+
list = [random.randrange(n) for _ in range(n)]
|
|
31
|
+
|
|
32
|
+
start_time = time.time()
|
|
33
|
+
for _ in range(m):
|
|
34
|
+
list.pop(0)
|
|
35
|
+
end_time = time.time()
|
|
36
|
+
|
|
37
|
+
print("%.8f" % (end_time - start_time))
|
|
38
|
+
```
|
|
39
|
+
|
|
40
|
+
Python3 3.6.0 macOS Siera
|
|
41
|
+
|配列サイズ|取出数|試行回数|平均|最小|最大|
|
|
42
|
+
|---|---|---|---|---|
|
|
43
|
+
|10|10|10|0.00000560|0.00000286|0.00002098|
|
|
44
|
+
|100|10|10|0.00000367|0.00000262|0.00000405|
|
|
45
|
+
|1000|10|10|0.00000801|0.00000477|0.00001383|
|
|
46
|
+
|10000|10|10|0.00004036|0.00003099|0.00005794|
|
|
47
|
+
|100000|10|10|0.00100026|0.00080609|0.00132823|
|
|
48
|
+
|1000000|10|10|0.01386561|0.01161385|0.01659012|
|
|
49
|
+
|
|
50
|
+
[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)のようで、一定サイズ以上はほぼ同じ速度です。
|
|
51
|
+
|
|
52
|
+
このことから、一定サイズ以上のlistをキューに使用するとかなり遅くなる場合があり得ます。キューにはdequeを使って回避するのが良いでしょう。
|
|
53
|
+
|
|
54
|
+
---
|
|
55
|
+
|
|
56
|
+
【蛇足】
|
|
57
|
+
|
|
58
|
+
なぜ、RubyのArray#shfitは速いのか？
|
|
59
|
+
|
|
60
|
+
RubyのArray#shfitは、配列が一定サイズ以上の場合、メモリ上の配列はそのままで先頭のポインタをずらすという手法を採っています。メモリ的には不利ですが、速度的には有利になります。サイズの大きさで処理を変えることで、同じ書き方でもなるべく高速に動作させるという戦略のようです。
|
|
61
|
+
[https://github.com/ruby/ruby/blob/ruby_2_4/array.c#L1000](https://github.com/ruby/ruby/blob/ruby_2_4/array.c#L1000)
|