回答編集履歴
3
追記
test
CHANGED
@@ -151,3 +151,23 @@
|
|
151
151
|
257 µs ± 19.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
|
152
152
|
|
153
153
|
```
|
154
|
+
|
155
|
+
|
156
|
+
|
157
|
+
追記
|
158
|
+
|
159
|
+
**長い**dequeから、**長い**部分要素を取り出すならisliceの方が有利です。(popを繰り返す操作がネックになりますから)
|
160
|
+
|
161
|
+
```plain
|
162
|
+
|
163
|
+
In : %timeit y = list(islice(x, 700000, 100000))
|
164
|
+
|
165
|
+
2.21 ms ± 24.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
|
166
|
+
|
167
|
+
|
168
|
+
|
169
|
+
In : %timeit slice_deque(x, 700000, 100000)
|
170
|
+
|
171
|
+
9.72 ms ± 48.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
|
172
|
+
|
173
|
+
```
|
2
スライスに関して
test
CHANGED
@@ -87,3 +87,67 @@
|
|
87
87
|
5.93 µs ± 636 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
|
88
88
|
|
89
89
|
```
|
90
|
+
|
91
|
+
|
92
|
+
|
93
|
+
----
|
94
|
+
|
95
|
+
追記
|
96
|
+
|
97
|
+
|
98
|
+
|
99
|
+
[https://docs.python.org/ja/3/library/collections.html#deque-recipes](https://docs.python.org/ja/3/library/collections.html#deque-recipes)
|
100
|
+
|
101
|
+
> To implement deque slicing, use a similar approach applying rotate() to bring a target element to the left side of the deque. Remove old entries with popleft(), add new entries with extend(), and then reverse the rotation. With minor variations on that approach, it is easy to implement Forth style stack manipulations such as dup, drop, swap, over, pick, rot, and roll.
|
102
|
+
|
103
|
+
|
104
|
+
|
105
|
+
```python
|
106
|
+
|
107
|
+
def slice_deque(d, i, n):
|
108
|
+
|
109
|
+
d.rotate(-i)
|
110
|
+
|
111
|
+
t = [d.popleft() for _i in range(n)]
|
112
|
+
|
113
|
+
d.extend(t)
|
114
|
+
|
115
|
+
d.rotate(i+n)
|
116
|
+
|
117
|
+
return t
|
118
|
+
|
119
|
+
```
|
120
|
+
|
121
|
+
|
122
|
+
|
123
|
+
|
124
|
+
|
125
|
+
```plain
|
126
|
+
|
127
|
+
In : x = deque(range(1000000), 1000000)
|
128
|
+
|
129
|
+
|
130
|
+
|
131
|
+
In : %timeit y = list(islice(x, 100, 10))
|
132
|
+
|
133
|
+
808 ns ± 12.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
|
134
|
+
|
135
|
+
|
136
|
+
|
137
|
+
In : %timeit slice_deque(x, 100,10)
|
138
|
+
|
139
|
+
1.99 µs ± 52.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
|
140
|
+
|
141
|
+
|
142
|
+
|
143
|
+
In %timeit y = list(islice(x, 700000, 10))
|
144
|
+
|
145
|
+
2.31 ms ± 44.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
|
146
|
+
|
147
|
+
|
148
|
+
|
149
|
+
In : %timeit slice_deque(x, 700000,10)
|
150
|
+
|
151
|
+
257 µs ± 19.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
|
152
|
+
|
153
|
+
```
|
1
追求
test
CHANGED
@@ -1,6 +1,8 @@
|
|
1
1
|
一般的にこれが最良という方法はありません。
|
2
2
|
|
3
3
|
dequeはどういうアルゴリズムで動いているかを中までわかった上でないと**速くならない**し、実際にどのぐらいのデータをどのように扱うかを前提にしないと使うべきなのか判断できない、かなり低水準なライブラリなのです。
|
4
|
+
|
5
|
+
(だからこそスライス実装を提供していないように思えます)
|
4
6
|
|
5
7
|
|
6
8
|
|