第134回【Python】歴史を作る時間
現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
Python をゼロから勉強してみよう、のコーナー 134 回目です。
時間がかかりすぎて困るんです、と見せられた VBA が、ちょうど、最近やっている配列を用いた処理の部分でした。鼻高々で修正してどや顔をしておきました。まぁ、めったにあることではないので、たまにはいいじゃないですか。
それでは、今日も頑張ってみようと思います。
歴史を作る時間
https://paiza.jp/works/mondai/query_primer/query_primer__his...西暦 1,000,000,000 年に行われた歴史の授業のグループワークで、歴史上のいくつかの出来事についての記事を年代順に並べて歴史年表を作成することになりました。
ところが、歴史年表は 1 枚の紙にまとめる必要があるため、古い出来事を担当する人から順番に歴史年表を書くことにしました。
グループの人数 N とそのメンバー S_1 … S_N が与えられます。
続けて、歴史年表に載せる出来事の数 K , 各出来事の起こった年 Y_i , その出来事の記事を担当する生徒の名前 C_i が与えられるので、歴史年表を書く担当者の順番を出力してください。
なお、 1 人の生徒が複数の出来事の記事を担当することがある点に注意してください。
N K
S_1
...
S_N
Y_1 C_1
...
Y_K C_K・1 行目では、グループの人数 N と歴史年表に載せる出来事の数 K が与えられます。
・続く N 行のうち i 行目では、 i 人目のメンバーの名前 S_i が与えられます。
・続く K 行のうち i 行目では、 i 個目の出来事の起こった年 Y_i と、その記事を担当する生徒の名前 C_i が先頭から順に与えられます。
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 1,000
・1 ≦ K ≦ 100,000
・S_i は 20 文字以下の英数字列 (1 ≦ i ≦ N)
・S_i ≠ S_j (i ≠ j)
・1 ≦ Y_i ≦ 1,000,000,000 (1 ≦ i ≦ K)
・C_i は S_j のいずれか (1 ≦ i ≦ K , 1 ≦ j ≦ N)
入力例
3 5
nao
hiro
yuki
645 nao
593 hiro
2058 yuki
29484 nao
374759 nao出力例
hiro
nao
yuki
nao
nao地球は 10 億年後も人間が営みを続けているのだろうか。10 億年後に作る歴史年表に大化の改新なんて書いてもしょうがない気がする。もっと重要なことがたくさん起きているだろう・・・。
Python
N,K = map(int,input().split())
S = [input() for _ in range(N)]
histories = [None] * K
for i in range(K):
Y,C = input().split()
histories[i] = (int(Y),C)
for y,n in sorted(histories):
print(n)VBA
Sub query_primer__history()
ti = Timer
NK = Split(Cells(1, 1), " ")
N = Val(NK(0))
k = Val(NK(1))
Dim A() As Variant
ReDim A(k - 1)
For i = 0 To k - 1
s = Split(Cells(i + N + 2, 1), " ")
year_ = Val(s(0))
name_ = s(1)
A(i) = Format(year_, "0000000000") & name_
Next
Call QuickSort(A, LBound(A), UBound(A))
For Each v In A
Debug.Print Mid(v, 11)
Next
Debug.Print Timer - ti
End Sub
Private Sub QuickSort(ByRef argAry() As Variant, ByVal lngMin As Long, ByVal lngMax As Long)
Dim i As Long
Dim j As Long
Dim vBase As Variant
Dim vSwap As Variant
vBase = argAry(Int((lngMin + lngMax) / 2))
i = lngMin
j = lngMax
Do
Do While argAry(i) < vBase
i = i + 1
Loop
Do While argAry(j) > vBase
j = j - 1
Loop
If i >= j Then Exit Do
vSwap = argAry(i)
argAry(i) = argAry(j)
argAry(j) = vSwap
i = i + 1
j = j - 1
Loop
If (lngMin < i - 1) Then
Call QuickSort(argAry, lngMin, i - 1)
End If
If (lngMax > j + 1) Then
Call QuickSort(argAry, j + 1, lngMax)
End If
End Subいつもの境界値データで約 30 秒でした。
最後に
VBA で Debug.Print をしない場合、10 万件データを約 0.7 秒で処理しました。VBA にも夢があるね。
Python はわかりやすいコードが書けて素敵です。最近、配列を初期化するのに、[None]*N を用いているのですが、これが一番早いらしい、です。VBA でやろうとすると、初期化の時点では配列のサイズを変数で指定することができないので ReDim をする必要があり、ちょっと面倒くさい。
あと、ご指摘いただきましたが、Option Explicit は、普段はつける派です。ないと不安になる派です。Python との比較なので書いていないだけです。
引き続き、よろしくお願いいたします！