第129回【Python】指定要素の検索、指定要素の検索 (query)

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

はじめに

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

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

キャンプ場の夜の過ごし方は Amazon Prime で適当な番組を見て過ごす、です。重宝しているのは、ダイソーの Bluetooth スピーカー（レトロタイプ）。以前はタブ PC からの音量の調整に苦労していました。今は手元で自分たちだけに聞こえるよう音量調節できるので楽ちんです。

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

指定要素の検索

長さ N の重複した要素の無い数列 A と整数 K が与えられるので、
A に K が含まれていれば “YES" を、そうでなければ “NO" を出力してください。

N K
A_1
...
A_N

・1 行目では、配列 A の要素数 N と検索する値 K が半角スペース区切りで与えられます。
・続く N 行では、配列 A の要素が先頭から順に与えられます。

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 100,000
・0 ≦ A_i , K ≦ 1,000,000 (1 ≦ i ≦ N)

入力例

3 5
1
3
5

出力例

YES

最大値が 100,000 となっている。境界値のテストケースで一つずつ検索をかけるとちょっと時間がかかりそう。

Python
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
print("YES" if K in A else "NO")

in 演算子の計算量は O(N) で、効率的というわけではない。

VBA
Sub query_primer__single_search()

    s = Split(Cells(1, 1), " ")
    N = Val(s(0))
    K = Val(s(1))
    
    Dim A() As Long
    ReDim A(N - 1)
    
    For i = 0 To N - 1
        A(i) = Cells(i + 2, 1)
    Next
    
    Do
        For i = LBound(A) To UBound(A)
            If A(i) = K Then
                Debug.Print "YES"
                Exit Do
            End If
        Next

        Debug.Print "NO"

    Loop While False
    
End Sub

最近お気に入りの Do Loop 1 回抜け。Python の For else 文の真似事のつもりです。フラグ管理とかより、わかりやすい気がしています。

指定要素の検索 (query)

長さ N の重複した要素の無い数列 A と Q 個の整数 K_1 … K_Q が与えられるので、
各 K_i について、 A に K_i が含まれていれば “YES" を、そうでなければ “NO" を出力してください。

N Q
A_1
...
A_N
K_1
...
K_Q

・1 行目では、配列 A の要素数 N と検索する値の個数 Q が半角スペース区切りで与えられます。
・続く N 行では、配列 A の要素が先頭から順に与えられます。
・続く Q 行では、検索する値 K_1 .. K_Q が順に与えられます

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N , Q ≦ 100,000
・0 ≦ A_i ≦ 1,000,000 (1 ≦ i ≦ N)
・0 ≦ K_i ≦ 1,000,000 (1 ≦ i ≦ Q)

入力例

5 5
1
2
3
4
5
1
3
5
7
9

出力例

YES
YES
YES
NO
NO

10 万件と 10 万件の検索だと、最大で 100 億回の検索が必要。それはさすがに時間がかかりすぎる。

Python
N,Q = map(int,input().split())
A = { int(input()) for _ in range(N) }
for _ in range(Q):
    K = int(input())
    if K in A:
        print('YES')
    else:
        print('NO')

set を利用する。set はハッシュ法を利用しているため、in 演算子の計算量が平均で O(1) で実行できる。

VBA
Sub query_primer__multi_search()

    NQ = Split(Cells(1, 1), " ")
    N = Val(NQ(0))
    Q = Val(NQ(1))

    Dim dic As Object
    Set dic = CreateObject("Scripting.Dictionary")

    For i = 1 To N
        A = Cells(i + 1, 1)
        If Not dic.exists(A) Then
            dic.Add A, A
        End If
    Next

    For i = 1 To Q
        K = Cells(N + i + 1, 1)
        If dic.exists(K) Then
            Debug.Print "YES"
        Else
            Debug.Print "NO"
        End If
    Next
    
End Sub

VBA のハッシュは連想配列らしい。

最後に

Python は、ほとんど一瞬で動きます。さて、VBA の方は・・・。paiza が用意してくれている境界値データを用いた場合で 1 分ちょっとくらいかかりました。早いっちゃ早い？

他の方法もいろいろと調べてみたのですが、VBA のハッシュは連想配列くらいしか見当たらなかったので、もっと早くできる方法があれば教えてください。ちなみに、100 で割った余りを key としてデータを分割、親連想配列とし、その中に子連想配列を入れ子にしてみたのですが、ちょっとかかる時間が大きくなりました。

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

Python学習,Python,paiza

Posted by LeoSaki