teratail
回答率
85.48%
質問するログイン新規登録
トップソートに関する質問pythonで、先頭、最後、先頭から2番目、最後から2番目、・・・のように順番に並べる方法が分かりません

編集履歴

回答編集履歴

5

Edit

2018/05/15 22:51

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -20,6 +20,10 @@
20
20
 
21
21
  #------LouiS0616さん回答
22
22
 
23
+ #後ろ半分を逆に並べて、前半分と交互に差し込む方法。
24
+
25
+ #成分が奇数個の場合の処理に大半のテクニックが使われている。
26
+
23
27
  from itertools import chain, zip_longest
24
28
 
25
29
  n = 10000
@@ -46,6 +50,10 @@
46
50
 
47
51
  #------list.pop
48
52
 
53
+ #リストのpopで成分取り出し。
54
+
55
+ #pop(0)がO(N)
56
+
49
57
  n = 10000
50
58
 
51
59
  a = list(range(n))
@@ -72,6 +80,10 @@
72
80
 
73
81
  #------deque.pop
74
82
 
83
+ #dequeのpopで成分取り出し。
84
+
85
+ #両端共にO(1)
86
+
75
87
  from collections import deque
76
88
 
77
89
 
@@ -104,6 +116,10 @@
104
116
 
105
117
  #------list.slice
106
118
 
119
+ #リストのsliceで成分取り出し。
120
+
121
+ #inplaceではなくコピーで時間がかかっているはず。
122
+
107
123
  n = 10000
108
124
 
109
125
  a = list(range(n))
@@ -134,6 +150,10 @@
134
150
 
135
151
  #------reverse.pop
136
152
 
153
+ #後ろからしかpopしないと心に決める方法。
154
+
155
+ #取り出すごとにリストを逆順にならべかえる。
156
+
137
157
  n = 10000
138
158
 
139
159
  a = list(range(n))
@@ -162,6 +182,12 @@
162
182
 
163
183
  #------index
164
184
 
185
+ #popみたいな操作が遅いと疑ってみる方法。
186
+
187
+ #appendが遅いのがどうにもならないっぽい。
188
+
189
+ #dequeより遅いのはif文のせいか？（根拠なし）
190
+
165
191
  n = 10000
166
192
 
167
193
  a = list(range(n))
@@ -198,78 +224,36 @@
198
224
 
199
225
 
200
226
 
227
+ ※最初の回答
228
+
201
229
  dequeに入れて、両端から交互にpopすればできます。
202
230
 
203
231
 
204
232
 
205
- リスト版
206
-
207
- ```python
208
-
209
- a = list(range(10))
210
-
211
-
212
-
213
- ans = []
214
-
215
-
216
-
217
- while True:
218
-
219
- try:
220
-
221
- ans.append(a[0])
222
-
223
- a = a[1:]
224
-
225
- ans.append(a[-1])
226
-
227
- a = a[:-1]
228
-
229
- except IndexError:
230
-
231
- break
232
-
233
-
234
-
235
- print(ans)
236
-
237
- ```
233
+ ---
238
-
239
-
240
-
241
- deque版
234
+
242
-
243
- ```python
235
+
244
-
236
+
245
- from collections import deque
237
+ 数字の0を含む場合のfilterの処理が気になる方が万が一いらっしゃれば、
246
-
247
-
248
-
249
- a = list(range(10))
238
+
250
-
251
- a = deque(a)
252
-
253
-
254
-
255
- ans = []
256
-
257
-
258
-
259
- while True:
260
-
261
- try:
262
-
263
- ans.append(a.popleft())
239
+ https://stackoverflow.com/questions/16096754/remove-none-value-from-a-list-without-removing-the-0-value
264
-
265
- ans.append(a.pop())
240
+
266
-
267
- except IndexError:
241
+
268
-
269
- break
242
+
270
-
271
-
272
-
273
- print(ans)
274
-
275
- ```
243
+ ---
244
+
245
+
246
+
247
+ 結局LouiS0616さん回答やdequeの方法あたりまでくると、リストの生成に一番時間がかかっているので、直接lambda式で処理するのが速いようですね。
248
+
249
+ dequeの場合、一度dequeに入れなおす必要があって、その処理時間を削減できないので結果としてLouiS0616さん回答の約倍の時間がかかるようです。
250
+
251
+
252
+
253
+ 個人的にはsliceの方がpopよりだいぶ遅いのは意外でした。（小並感）
254
+
255
+
256
+
257
+ それぞれの構造体の各処理速度が気になる方は、
258
+
259
+ https://wiki.python.org/moin/TimeComplexity

4

edit

2018/05/15 22:51

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -18,6 +18,34 @@
18
18
 
19
19
  ```python
20
20
 
21
+ #------LouiS0616さん回答
22
+
23
+ from itertools import chain, zip_longest
24
+
25
+ n = 10000
26
+
27
+ A = list(range(1, n+1))
28
+
29
+ ans = list((lambda elems:
30
+
31
+ (lambda es, m: list(filter(None,
32
+
33
+ chain(*zip_longest(es[:m],
34
+
35
+ es[m:][::-1]))))
36
+
37
+ )(elems, len(elems) // 2)
38
+
39
+ )(A)
40
+
41
+ )
42
+
43
+ #454 µs ± 4.94 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
44
+
45
+
46
+
47
+ #------list.pop
48
+
21
49
  n = 10000
22
50
 
23
51
  a = list(range(n))
@@ -42,6 +70,8 @@
42
70
 
43
71
 
44
72
 
73
+ #------deque.pop
74
+
45
75
  from collections import deque
46
76
 
47
77
 
@@ -72,6 +102,8 @@
72
102
 
73
103
 
74
104
 
105
+ #------list.slice
106
+
75
107
  n = 10000
76
108
 
77
109
  a = list(range(n))
@@ -100,6 +132,8 @@
100
132
 
101
133
 
102
134
 
135
+ #------reverse.pop
136
+
103
137
  n = 10000
104
138
 
105
139
  a = list(range(n))
@@ -118,10 +152,6 @@
118
152
 
119
153
  a = a[::-1]
120
154
 
121
- ans.append(a.pop())
122
-
123
- a = a[::-1]
124
-
125
155
  except IndexError:
126
156
 
127
157
  break
@@ -130,6 +160,8 @@
130
160
 
131
161
 
132
162
 
163
+ #------index
164
+
133
165
  n = 10000
134
166
 
135
167
  a = list(range(n))

3

edit

2018/05/15 10:52

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -12,6 +12,160 @@
12
12
 
13
13
 
14
14
 
15
+ スピードはこんな感じ。
16
+
17
+
18
+
19
+ ```python
20
+
21
+ n = 10000
22
+
23
+ a = list(range(n))
24
+
25
+
26
+
27
+ ans = []
28
+
29
+ while True:
30
+
31
+ try:
32
+
33
+ ans.append(a.pop(0))
34
+
35
+ ans.append(a.pop())
36
+
37
+ except IndexError:
38
+
39
+ break
40
+
41
+ #3.46 ms ± 4.17 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
42
+
43
+
44
+
45
+ from collections import deque
46
+
47
+
48
+
49
+ n = 10000
50
+
51
+ a = list(range(n))
52
+
53
+ a = deque(a)
54
+
55
+
56
+
57
+ ans = []
58
+
59
+ while True:
60
+
61
+ try:
62
+
63
+ ans.append(a.popleft())
64
+
65
+ ans.append(a.pop())
66
+
67
+ except IndexError:
68
+
69
+ break
70
+
71
+ #942 µs ± 821 ns per loop (mean ± std. dev. of 7 runs, 100 loops each)
72
+
73
+
74
+
75
+ n = 10000
76
+
77
+ a = list(range(n))
78
+
79
+
80
+
81
+ ans = []
82
+
83
+ while True:
84
+
85
+ try:
86
+
87
+ ans.append(a[0])
88
+
89
+ a = a[1:]
90
+
91
+ ans.append(a[-1])
92
+
93
+ a = a[:-1]
94
+
95
+ except IndexError:
96
+
97
+ break
98
+
99
+ #89 ms ± 278 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
100
+
101
+
102
+
103
+ n = 10000
104
+
105
+ a = list(range(n))
106
+
107
+ a = a[::-1]
108
+
109
+
110
+
111
+ ans = []
112
+
113
+ while True:
114
+
115
+ try:
116
+
117
+ ans.append(a.pop())
118
+
119
+ a = a[::-1]
120
+
121
+ ans.append(a.pop())
122
+
123
+ a = a[::-1]
124
+
125
+ except IndexError:
126
+
127
+ break
128
+
129
+ #94.4 ms ± 425 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
130
+
131
+
132
+
133
+ n = 10000
134
+
135
+ a = list(range(n))
136
+
137
+
138
+
139
+ ans = []
140
+
141
+ i = 0
142
+
143
+ while True:
144
+
145
+ ans.append(a[i])
146
+
147
+ if len(ans)==n:
148
+
149
+ break
150
+
151
+ i += 1
152
+
153
+ ans.append(a[-i])
154
+
155
+ if len(ans)==n:
156
+
157
+ break
158
+
159
+ #1.35 ms ± 2.62 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
160
+
161
+ ```
162
+
163
+
164
+
165
+ ---
166
+
167
+
168
+
15
169
  dequeに入れて、両端から交互にpopすればできます。
16
170
 
17
171
 

2

Edit

2018/05/15 10:04

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -1,3 +1,17 @@
1
+ 注：研修の問題でしたか。
2
+
3
+ 答えを載せちゃうのはまずかったかも。
4
+
5
+ ちゃんと理解することをお勧めします。
6
+
7
+ あとで困るのは自分自身なので。
8
+
9
+
10
+
11
+ ---
12
+
13
+
14
+
1
15
  dequeに入れて、両端から交互にpopすればできます。
2
16
 
3
17
 
@@ -35,3 +49,41 @@
35
49
  print(ans)
36
50
 
37
51
  ```
52
+
53
+
54
+
55
+ deque版
56
+
57
+ ```python
58
+
59
+ from collections import deque
60
+
61
+
62
+
63
+ a = list(range(10))
64
+
65
+ a = deque(a)
66
+
67
+
68
+
69
+ ans = []
70
+
71
+
72
+
73
+ while True:
74
+
75
+ try:
76
+
77
+ ans.append(a.popleft())
78
+
79
+ ans.append(a.pop())
80
+
81
+ except IndexError:
82
+
83
+ break
84
+
85
+
86
+
87
+ print(ans)
88
+
89
+ ```

1

Edit

2018/05/15 09:33

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -1 +1,37 @@
1
1
  dequeに入れて、両端から交互にpopすればできます。
2
+
3
+
4
+
5
+ リスト版
6
+
7
+ ```python
8
+
9
+ a = list(range(10))
10
+
11
+
12
+
13
+ ans = []
14
+
15
+
16
+
17
+ while True:
18
+
19
+ try:
20
+
21
+ ans.append(a[0])
22
+
23
+ a = a[1:]
24
+
25
+ ans.append(a[-1])
26
+
27
+ a = a[:-1]
28
+
29
+ except IndexError:
30
+
31
+ break
32
+
33
+
34
+
35
+ print(ans)
36
+
37
+ ```