第130回【Python】先頭の要素の削除、先頭の要素の削除(query)

現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 130 回目です。

最近は、VBA の方の調査で時間がかかっています。長いこと VBA を利用してきましたが、知らないことはまだまだあるものです。大変勉強になっています。しかし、Python をゼロから勉強するコーナーなので、もっと Python で突っ込んだ調査をした方がいいかもしれない？

それでは、今日も頑張ってみようと思います。

先頭の要素の削除

数列 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
8963

2 つめの要素から順番に出力すればいいんじゃね？ って思ったけれど、問題の趣旨に合ってなさそうなのでやめました。

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)

数列 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 で実装すると、なかなか大変なことになりました。まぁ、ほとんどが出力している時間だったので、悪くはないスピード短縮だったのではないかと思います。

最近は、もっといい方法はないか、もっといい方法はないか、とそればかり考えていて、調べているうちにかなりの時間を盗まれています。まぁ、そういうのも楽しいのですが。

引き続き、よろしくお願いいたします！

Python学習,Python,paiza

Posted by LeoSaki