第130回【Python】先頭の要素の削除、先頭の要素の削除(query)
現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
Python をゼロから勉強してみよう、のコーナー 130 回目です。
最近は、VBA の方の調査で時間がかかっています。長いこと VBA を利用してきましたが、知らないことはまだまだあるものです。大変勉強になっています。しかし、Python をゼロから勉強するコーナーなので、もっと Python で突っ込んだ調査をした方がいいかもしれない？
それでは、今日も頑張ってみようと思います。
先頭の要素の削除
https://paiza.jp/works/mondai/query_primer/query_primer__sin...数列 A が与えられるので、A の先頭の要素を削除した後の A を出力してください。
N
A_1
...
A_N・1 行目では、配列 A の要素数 N が与えられます。
・続く N 行では、配列 A の要素が先頭から順に与えられます。
すべてのテストケースにおいて、以下の条件をみたします。
・2 ≦ N ≦ 100,000
・0 ≦ A_i ≦ 10,000 (1 ≦ i ≦ N)
入力例
10
5980
1569
5756
9335
9680
4571
5309
8696
9680
8963出力例
1569
5756
9335
9680
4571
5309
8696
9680
89632 つめの要素から順番に出力すればいいんじゃね？ って思ったけれど、問題の趣旨に合ってなさそうなのでやめました。
Python
N = int(input())
A = [int(input()) for _ in range(N)]
del A[0]
for a in A:
print(a)del の計算量は O(N) で、効率的というわけではない。
VBA
Sub query_primer__single_pop()
N = Cells(1, 1)
Dim A() As Long
ReDim A(N - 1)
For i = 0 To N - 1
A(i) = Cells(i + 2, 1)
Next
For i = 0 To N - 2
A(i) = A(i + 1)
Next
ReDim Preserve A(UBound(A) - 1)
For Each v In A
Debug.Print v
Next
End Sub先頭の要素の削除(query)
https://paiza.jp/works/mondai/query_primer/query_primer__mul...数列 A と入力の回数 K が与えられるので、K 回の入力に応じて次のような処理をしてください。
・pop
A の先頭の要素を削除する。既に A に要素が存在しない場合何もしない。
・show
A の要素を先頭から順に改行区切りで出力する。A に要素が存在しない場合何も出力しない。
N K
A_1
...
A_N
S_1
...
S_K・1 行目では、配列 A の要素数 N と与えられる入力の数 K が与えられます。
・続く N 行では、配列 A の要素が先頭から順に与えられます。
・続く K 行では、"pop" または “show" が与えられます。
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ K ≦ N ≦ 100,000
・0 ≦ A_i ≦ 10,000 (1 ≦ i ≦ N)
・S_i (1 ≦ i ≦ K) は “pop" , “show" のいずれか
・S_i のうち、"show" であるものは 10 個以下であることが保証されている。
入力例
5 3
7564
4860
2410
9178
7252
pop
pop
show出力例
2410
9178
7252キューの出番です。あまり使ったことはないけれど、以前、AWS Lambda でどうしてもタイムアウトするときに使ってみたらうまくいったことがあります。
Python
from collections import deque
N,Q = map(int,input().split())
A = deque([int(input()) for _ in range(N)])
for _ in range(Q):
query = input()
if query == 'pop':
A.popleft()
else:
for a in A:
print(a)VBA
## クラスモジュール（query）
Private c As Collection
Private dataSizeIndex As Long
Private headerIndex As Long
Private Sub Class_Initialize()
Set c = New Collection
dataSizeIndex = 0
headerIndex = 0
End Sub
Public Sub enqueue(v As Variant)
c.add v, CStr(dataSizeIndex)
dataSizeIndex = dataSizeIndex + 1
End Sub
Public Function dequeue() As Variant
If c.count = 0 Then
Exit Function
End If
Dim vType As Long
vType = VarType(c.item(CStr(headerIndex)))
Select Case vType
Case vbObject
Set dequeue = c.item(CStr(headerIndex))
Case vbDataObject
Set dequeue = c.item(CStr(headerIndex))
Case vbUserDefinedType
Set dequeue = c.item(CStr(headerIndex))
Case Else
dequeue = c.item(CStr(headerIndex))
End Select
Call c.Remove(CStr(headerIndex))
headerIndex = headerIndex + 1
End Function
Public Function count() As Long
count = c.count
End Function
Public Function result_print()
For Each v In c
Debug.Print v
Next
End Function
Private Sub Class_Terminate()
Set c = Nothing
End Sub## 標準モジュール
Sub query_primer__multi_pop()
t = Timer
NQ = Split(Cells(1, 1), " ")
N = Val(NQ(0))
Q = Val(NQ(1))
Dim que As queue
Set que = New queue
For i = 1 To N
que.enqueue Cells(i + 1, 1)
Next
For i = 1 To Q
s = Cells(i + N + 1, 1)
If s = "pop" Then
que.dequeue
Else
que.result_print
End If
Next
Debug.Print Timer - t
End Sub疑似的にキューを作ったもの。参考にさせていただいたネットの皆様、ありがとうございます。
前問と同じ方針で書いたコード。
Sub query_primer__multi_pop_OLD()
t = Timer
NQ = Split(Cells(1, 1), " ")
N = Val(NQ(0))
Q = Val(NQ(1))
Dim A() As Long
ReDim A(N - 1)
For i = 0 To N - 1
A(i) = Cells(i + 2, 1)
Next
For i = 1 To Q
s = Cells(i + N + 1, 1)
If s = "pop" Then
For j = 0 To UBound(A) - 1
A(j) = A(j + 1)
Next
ReDim Preserve A(UBound(A) - 1)
Else
For Each v In A
Debug.Print v
Next
End If
Next
Debug.Print Timer - t
End Sub前者は 172 秒、後者は 250 秒と、1 分以上の開きが出ました。（paiza が用意してくれている境界値データでのテスト結果）
最後に
Python での実装は簡単ですが（import するだけ！）、VBA で実装すると、なかなか大変なことになりました。まぁ、ほとんどが出力している時間だったので、悪くはないスピード短縮だったのではないかと思います。
最近は、もっといい方法はないか、もっといい方法はないか、とそればかり考えていて、調べているうちにかなりの時間を盗まれています。まぁ、そういうのも楽しいのですが。
引き続き、よろしくお願いいたします！