やるだけPython競プロ日誌

競プロの解説をPythonでやっていきます。できるだけ初心者に分かりやすいように『やるだけ』とかは言わないようにします。コメントについては必ず読んでいます。どんなに細かいことでもいいのでコメントくださればうれしいです。

国会でも話に上がった "HASH" をPythonで -- hash()じゃないよ! --

以前、”国会にhash関数の話が出たwww”といって、そっちの界隈の人でちょっとした話題になっていました。

では、hashとはなんなのか?分からない人もいると思います。

それがわかっても、Pythonでの実装がわからない方もいらっしゃると思いますので、この記事を書いた次第です。

hashって?

wikipediaを参照すると

データから算出した小さな値。各データを区別・表現する目的に用いる。

となっています。

つまり、あるデータから、それ固有の値を取り出して(計算から導き出す)、データの区別に使うための値。です

この計算というのが大事で、たとえば、長さが400ページ以上もある本を文字に落とし込んで所得したhashと、

その文字列の句点と読点を一個だけ入れ替えた文字列のhashは異なります

そこから、文書の改ざん対策などにも用いられるんですね。

また、その『元からhashを求めるのは用意である』が『hashから元を求めるのは非常に困難である』という性質を利用して、暗号・セキュリティにも用いられています。

Pythonで実装

Pythonにはhash関数が元からありますので、それを利用してみましょう。

>>> hash("1")  # "ハッシュ不可能"(listやset, dictなど)は用いないでください
4940519975841726253

求められましたね。

しかし、これではだめです

このhashが信頼できるのは、このインタープリタを閉じるまでだからです。

一度閉じて、もう一度実行してみましょう。

>>> hash("1")
2261270426266027010

おなじ文字列のhashを取り出したにもかかわらず、違う値が出ていますよね。

このように、正当性を確かめるには、標準のhashは不向きであるとわかります。

そこで使うのが、hashlibです

>>> import hashlib
>>> hashlib.md5(b"1").digest()  # bytesにしましょう
b'\xc4\xcaB8\xa0\xb9#\x82\r\xccP\x9aou\x84\x9b'
  # 一度閉じます
>>> import hashlib
>>> hashlib.md5(b"1").digest()
b'\xc4\xcaB8\xa0\xb9#\x82\r\xccP\x9aou\x84\x9b'  # 同じ値が返ってきます

みなさんが同じコードを打っても、同じ値が返ってくるはずです。

これが、一意性を保っているということです。

MD5(hash化の方法の種類です)のほかに、SHA1、SHA224、SHA256、SHA384、SHA512が対応しているようです。

ユーザーのパスワードをhash化して持っておき、ログインしようとしたときに、そのhashと入力された文字列のhashを比べる、なんてこともできますよね。
MD5に関しては、衝突(別のデータが同じhash値を持つ)ことが他のものと比べて多いようなので、注意です


しかし、まだまだパスワードは軟弱で、Brute-Force-Attack(総当たり攻撃)に対抗するだけの力がありません。

なので、Salt(パスワードと関係のない値)と反復を繰り返すのがhashlib.pbkdf2_hmac()です。

より高度な使用

>>> import os, hashlib, binascii
>>> salt = os.urandom(64)  # osの提供する64文字長の信頼できるrandomなbytes
>>> salt
b'\xc0<U\xdc5\xea\x8d+y\xe6W\x882U\xdaG\xbe\xd5\x19\xc0\xb2l\xf5\xd5/~W2\xa9\x92z\x8b\xff\xba\x8bs\x95t)I\xd1s\xfa.\x85R\xff\xd6\x89\x10n\xb7\xc3<\x84\x87\xea\xe6X\x8a\xdb,\xc3\x1c'
>>> dk= hashlib.pbkdf2_hmac("sha256", b"PaSsWoRd", salt, 100000)  # sha256でb"PaSsWoRd"とsaltを使って100000回hmacの反復
>>> binascii.hexlify(dk)  # 得られたhash
b'53ce88a1559e955b7b68794225365af09261f0a411629cef554de208e33e8da7'

といった感じです。

最低反復は 10,000回以上回すことが推奨されています。

それでは皆さん、よいPythonLifeを!!

AtCoder に登録したら解くべき精選過去問 10 問 をPythonで解いてみた

全く違うサイトにはなりますが、 drken 氏がQiitaで投稿された
AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ - Qiita

Pythonで解いてみました。

ある程度難しい問題があるので、説明を端折ることもあると思いますが、できるだけわかりやすく説明します。

2022/5/22
記事執筆時は未熟だったもので、十分にPythonicであるといえない解答も多く解説も不十分でしたので、改訂いたしました。

0問目 PracticeA - はじめてのあっとこーだー(Welcome to AtCoder

https://language-test-201603.contest.atcoder.jp/tasks/practice_1

問題文
高橋君はデータの加工が行いたいです。
整数 a,b,cと、文字列 s が与えられます。
整数 a+b+c と、文字列 s を並べて表示しなさい。

入力
入力は以下の形式で与えられる。

a
b c
s
1 行目は、整数 a (1≦a≦1,000) が与えられる。
2 行目は、整数 b,c (1≦b,c≦1,000) が与えられる。
3 行目は、文字列 s が与えられる。この文字列の長さは 1 文字以上 100 文字以下である。
出力
a+b+c と s を空白区切りで 1 行に出力せよ。

また、出力の末尾には改行を入れること。

要は、与えられる文字列と数字を出力しろということですね。

a = int(input())
b, c = map(int, input().split())
print(a + b + c, input())

1問目 ABC086A - Product

A - Product

問題文
シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。

制約
1 ≤ a,b ≤ 10000
a,b は整数
入力
入力は以下の形式で標準入力から与えられる。

a b
出力
積が奇数なら Odd と、 偶数なら Even と出力せよ。

非常に簡単な問題ですね

a, b = map(int, input().split())
if (a * b) % 2:
    print("Odd")
else:
    print("Even")

この問題はa, bともに10000未満と制約が緩いので問題ありませんが、C++などの整数を扱える型に最大値の制限がある言語では、a, bともに奇数であるかどうかを判定したり、文字列として受け取ったのちに1の位のみを判定したりする必要があります。

しかしPython多倍長整数を使えるので、かけ合わせたものを純粋に割った方が早いです。

2問目 ABC081A - Placing Marbles

A - Placing Marbles

問題文
すぬけ君は 1,2,3 の番号がついた 3 つのマスからなるマス目を持っています。 各マスには 0 か 1 が書かれており、マス i には si が書かれています。

すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。

制約
s1,s2,s3 は 1 あるいは 0
入力
入力は以下の形式で標準入力から与えられる。

s1s2s3
出力
答えを出力せよ。

つまり、1の個数を数えればいいわけですね。

print(input().count("1"))

与えられるのは文字列ですので、そのままcountでよいと思います

3問目 ABC081B - Shift only

B - Shift only

問題文
黒板に N 個の正の整数 A1,…,AN が書かれています.

すぬけ君は,黒板に書かれている整数がすべて偶数であるとき,次の操作を行うことができます.

黒板に書かれている整数すべてを,2 で割ったものに置き換える.
すぬけ君は最大で何回操作を行うことができるかを求めてください.

制約
1≤N≤200
1≤Ai≤109
入力
入力は以下の形式で標準入力から与えられる。

N
A1 A2 ... AN
出力
すぬけ君は最大で何回操作を行うことができるかを出力せよ.

つまり、与えられた数字を一気に並列で2で割るとしたとき、何回まで整数のままで割れますか。ということです。

n = input()
a = list(map(int, input().split()))

ans = float("inf")
for v in a:
    ans = min(ans, list(reversed(bin(v))).index('1'))
    
print(ans)

binを用いて2進数に変換すると、右に続く0の数=何回2で割れるか、というものになっています。そして、その最小の値をとるという流れです。
1つでも奇数のものがあれば無条件に0になります。
愚直にやった場合、計算量的には O(200 * log2109 ≒6000 ) と普通に通ってしまうのですが、スマートではないので2進数にしています。何回もfor分を回すのはめんどくさいですしね。
Pythonは面白い言語で、"無限"を表現しようとすると、float("inf") としなければいけません。

4問目 ABC087B - Coins

B - Coins

問題文
あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。

同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約
0≤A,B,C≤50
A+B+C≥1
50≤X≤20,000
A,B,C は整数である
X は 50 の倍数である
入力
入力は以下の形式で標準入力から与えられる。

A
B
C
X
出力
硬貨を選ぶ方法の個数を出力せよ。

制約が大きいとforの回し方を工夫する必要がありますが、今回は小さいので、普通に回しましょう。

a, b, c, x = map(int, [input() for _ in range(4)])
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i * 500 + j * 100 + k * 50 == x:
                ans += 1
print(ans)

rangeの引数には+1を忘れないで入れておきましょう。

5問目 ABC083B - Some Sums

B - Some Sums

問題文
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

制約
1≤N≤104
1≤A≤B≤36
入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。

N A B
出力
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を出力せよ。

文字列変換→sumとすればよいでしょう。制約も小さいので。

n, a, b = map(int, input().split())
ans = 0
for i in range(n+1):
    if a <= sum(map(int, str(i))) <= b:
        ans += i
print(ans)

そのままですね。

6問目 ABC088B - Card Game for Two

B - Card Game for Two

問題文
N 枚のカードがあります. i 枚目のカードには, ai という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

制約
N は 1 以上 100 以下の整数
ai (1≤i≤N) は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.

N
a1 a2 a3 … aN
出力
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.

パっと見ても、sliceを使いそうですよね。

n = int(input())
a = sorted(map(int, input().split()), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))

これでよいと思います。sliceでは2つ区切りで取り出して、sumを求めるということをしています。

7問目 ABC085B - Kagami Mochi

B - Kagami Mochi

問題文
X 段重ねの鏡餅 (X≥1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい(一番下の餅を除く)もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。

ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は di センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約
1≤N≤100
1≤di≤100
入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。

N
d1
:
dN
出力
作ることのできる鏡餅の最大の段数を出力せよ。

何やら難しそうなことを言ってますが、要は、ユニークな要素はいくつありますか。ということです。ですので、setがうまく使えそうですね。

n = int(input())
print(len(set(map(int, [input() for i in range(n)]))))

非常に簡単ですね。

8問目 ABC085C - Otoshidama

C - Otoshidama

問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約
1≤N≤2000
1000≤Y≤2×107
N は整数である。
Y は 1000 の倍数である。
入力
入力は以下の形式で標準入力から与えられる。

N Y
出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。

N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。


これに関しては、よーくfor文の条件を考えないとTLE(時間オーバー)してしまいます

n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")

はい。実は、for文二回でいけるんですね。それも当然で、2種類の枚数が定まれば、自然ともう一種類も定まるからですね。
競プロは、時間がきちきちになることはありますが、(ほとんどの言語で)必ず解けます
あと、exit()を忘れないように…(1敗)

9問目 ABC049C - 白昼夢 / Daydream

C - Daydream

問題文
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。

T の末尾に dream dreamer erase eraser のいずれかを追加する。
制約
1≦|S|≦105
S は英小文字からなる。
入力
入力は以下の形式で標準入力から与えられる。

S
出力
S=T とすることができる場合 YES を、そうでない場合 NO を出力せよ。

つまり、与えられる文字列は、すべて、["eraser", "erase", "dream", "dreamer"]でなっていますか。という問題です。

s = input()

while s:
    for query in ("erase", "eraser", "dream", "dreamer"):
        if s.endswith(query):
            s = s[:-len(query)]
            break
    else:  # breakされなかったとき、つまり、合致する文字列がなかった場合
        print('NO')
        exit()

print('YES')

この問題の面倒なところは、頭から順番に見ていくと"dreamer..."という文字列が"dream"+"eraser?"なのか、"dreamer"なのか分からないという部分です。

この問題の簡単な解法がぱっと思いつくだけで2通りあります。
1つが、「先頭が"dreamera" の時は"dreamer"ではなく"dream"を削除する」というものです。"a"から始まるクエリは存在しないので、"dream"というクエリが与えられていると確定します。
2つ目が、先頭から見ていくのではなく最後尾から見ていくというものです。頭のerで困っているのなら、後ろから削ってしまえば問題ありません。この方法では、"dream"と"dreamer"の優先順位など気にしなくてもよいので、とても楽です。
今回は後者を採用しました。

10問目 ABC086C - Traveling

C - Traveling

問題文
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 ti に 点 (xi,yi) を訪れる予定です。

AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約
1 ≤ N ≤ 105
0 ≤ xi ≤ 105
0 ≤ yi ≤ 105
1 ≤ ti ≤ 105
ti < ti+1 (1 ≤ i ≤ N−1)
入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。

N
t1 x1 y1
t2 x2 y2
:
tN xN yN
出力
旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

これも考えてみると実に簡単です。

n = int(input())

plans = []
for _ in range(n):
    plans.append(map(int, input().split()))

st = sx = sy = 0
for t, x, y in plans:
    dt, dx, dy = t - st, abs(x - sx), abs(y - sy)
    if t % 2 != (x + y) % 2 or dx + dy > dt:
        print('No')
        exit()
    st, sx, sy = t, x, y
print('Yes')

それぞれの t, x, y について
x + y と t の偶奇が違っていればダメ
x + y が t より大きければダメ。
この二つのコードを書けば終わりです。
その場にとどまることはできないので、tが1増えるとx+yの偶奇が入れ替わります。つまり、tの偶奇とx+yの偶奇は必ず同じになります。
また、前回からの移動距離であるabs(dx)+abs(dy)はdt以下でなければなりません。絶対値を取らなければ、例えば

0 0 0
1 -100 100

といった値が通ってしまうので注意が必要です。

終わりに

未だPythonは日本ではあまり主流とまではいっていません。それが競技プログラミングともなれば、ほとんどがC++などといった高速な言語ばかりです。
我々Pythonistaは、それによる速度の遅さのせいでしばしばPythonistaにしかわからない苦悩を味わうときさえあります。
しかし、少なくとも私はPythonに対する愛で乗り越えてきましたし、これからもそうでしょう。
特にfunctools, itertools, bisect, 等といった標準ライブラリには感服せざるを得ません。
豊富なライブラリに幾度となく助けられてきました。それは競技プログラミングでも同じです。
あなたも、この素晴らしい言語に対する愛が深まるように応援しています。

2022/5/22 追記

近年機械学習や深層学習の流れを受け、主にアカデミーの分野からPythonの波が来ています。
Web系においても十分選択肢として挙げられるものとなり、喜びを隠せません

Pythonでenumerateを賢く使う。

enumerateって?

英語で『数え上げる』という意味です。この関数の引数にイテレータを与えると、何回そのイテレータを呼び出したかを数える数と、そのイテレータ自身を返します。
例えば

for i, j in enumerate(range(5, 0, -1)):
    print(i, j)
"""
0 5
1 4
2 3
3 2
4 1
"""

rangeの特異な使い方については、こちらをご覧ください
delta114514.hatenablog.jp


となります。 i には 呼び出し回数が、j にはイテレータ(今回は、特にジェネレータです)の値が入っています。

ちなみに、enumerateは引数を二つ取ります。二つ目は、1番初めの番号を決めます。

for i, j in enumerate(range(5, 0, -1), start=5):
    print(i, j)
"""
5 5
6 4
7 3
8 2
9 1
"""

これを使うと、AtCoderのこのC問題なら2行で解くことができます。
C - 背の順

問題文

高橋学級には N 人の生徒がいます。 生徒は 1 から N まで出席番号が振られています。 i 番目の生徒の身長は a_i です。 a_i はすべて相異なります。
高橋先生は N 人の生徒を背の高い方から順に並べました。 N 人の生徒の出席番号を背の高い方から順に出力してください。

制約

2≦N≦10^5
ai は整数である。
1≦a_i≦10^9
a_i はすべて相異なる。

部分点

30 点分のテストケースでは、N≦1000 を満たす。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 … a_N

出力

N 行出力せよ。 i 行目には、i 番目に背の高い生徒の出席番号を出力せよ。

はい。
愚直にやると

n = int(input())
individuals = list(map(int, input().split()))
for i in range(n):
    tallest = max(individuals)
    number = individuals.index(tallest)  # tallestを直に入れても良いです
    print(number + 1)
    individuals[number] = 0

背の高い人を毎回割り出して、その番号を返し、身長をブラックホール圧縮することでカウントしないようにしています。


ですが、こちら、TLEしてしまいました。


悲しいなぁ…

ですが、このenumerateを使う方法ならTLEせずに解けます。

n=int(input())
for i in sorted(enumerate(list(map(int, input().split())), start=1), key = lambda x :x[1], reverse = True):
    print(i[0])

lambdaについては 
delta114514.hatenablog.jp
をご覧ください
わかりやすくすると

def getsecond(n):  # lambdaの明示化
    return n[1]
 
n = int(input())
individuals = list(map(int, input().split()))  # 入力
enumerated_individuals = list(enumerate(individuals, start=1))  # enumerateされたlistを作る
enumerated_individuals.sort(key=getsecond, reverse=True)  # 身長でsortする
for i in enumerated_individuals:
    print(i[0])

です。つまり、身長と、入力された順番で対応したlistを作り、身長でsort(番号はくっついたまま)することにより、上から取り出すことで、番号のみを取り出すことができます。

各実行ごとでは

def getsecond(n):  # lambdaの明示化
    return n[1]
 
n = int(input())
individuals = list(map(int, input().split()))  # 入力
# individuals == [[160, 120, 150, 170]]

enumerated_individuals = list(enumerate(individuals, start=1))  # enumerateされたlistを作る
#enumerated_individuals == [(1, 160), (2, 120), (3, 150), (4, 170)]

enumerated_individuals.sort(key=getsecond, reverse=True)  # 身長でsortする
#enumerated_individuals == [(4, 170), (1, 160), (3, 150), (2, 120)]

for i in enumerated_individuals:
    print(i[0])

となります。

いいでしょ~、enumerate!!

それではみなさん、よいPythonLifeを!

宣伝…

Pythonの無名関数=(lambda)について

lambda

分かりにくいですよね笑

私も理解するために少し時間がかかりました。

簡単に言うと

””
def せずに関数を定義する
””

ものです。

もし、あるイテレータ・構造の二番目を取り出す関数を作るには

def getsecond(n):
    return n[1]

とできますが、もっと短く

getsecond = lambda x: x[1]
getsecond([1, 2])
  # 2

とできます。

lambda の文法について

lambda の文法は
"""
lambda 引数: 返り値
"""

となっています。なので、

先ほどのlambdaでいうと

x を引数としたときに、x[1]を返り値にする。

ということです。

なので、keyを引数に取るようなsortで、絶対値を基準にソートしたいとき

a = [1, 3, 5, 7, -2, -4, -6]
print(sorted(a))
  # [-6, -4, -2, 1, 3, 5, 7]
print(sorted(a, key=lambda x: abs(x)))
  # [1, -2, 3, -4, 5, -6, 7]

とできます。

どうですか?分かりやすかったですか?
質問があれば気軽にどうぞ!

宣伝…

ただの回数繰り返しだけじゃない! range()の賢い使用法

rangeって?

英語で範囲 を現します。Pythonでは、第一引数から第二引数まで、第三引数区切りで値を作ります。


え?引数を3つも取れるの?


そう思った方のための記事となりますので、すでに知っていた方はブラウザバックしていただいても大丈夫です…。

引数について

公式のリファレンスでは

class range(start, stop[, step])
range コンストラクタの引数は整数 (組み込みの int または __index__ 特殊メソッドを実装するオブジェクト) でなければなりません。step 引数が省略された場合のデフォルト値は 1 です。start 引数が省略された場合のデフォルト値は 0 です。 step が 0 の場合、ValueError が送出されます。

step が正の場合、range r の内容は式 r[i] = start + step*i で決定されます。ここで、 i >= 0 かつ r[i] < stop です。

step が負の場合も、range r の内容は式 r[i] = start + step*i で決定されます。ただし、制約条件は i >= 0 かつ r[i] > stop です。

r[0] が値の制約を満たさない場合、range オブジェクトは空になります。range は負のインデックスをサポートしますが、これらは正のインデックスにより決定されるシーケンスの末尾からのインデックス指定として解釈されます。

となっています。

簡単に言うと、
『全ての引数は整数で、step=0だけはやめてね』
ということです。

つまり、日ごろ皆さんが使っている
range(n)

range(0, n, 1)
同義です

トリッキー(?)な使い方

もしstep < -1 且つ stop < start の時、返すイテレータは、徐々に数が小さくなっていきます。

ただ、上記のどちらかのみが成り立つとき、イテレータは何も返しません。

以下対話型シェルでの実行です。

>>> list(range(0, 5, 1))
[0, 1, 2, 3, 4]
>>> list(range(5, 0, -1))  # 負のstepになっても、stopの値は含まないことに注意してください
[5, 4, 3, 2, 1]
>>> list(range(5, 0, 1)) == list(range(0, 5, -1))  # 両方とも空のリストを返します。
True
>>> list(range(5, 0, 1))
[]
>>> list(range(100, -1, -2))
[100, 98, 96, 94, 92, 90, 88, 86, 84, 82, 80, 78, 76, 74, 72, 70, 68, 66, 64, 62, 60, 58, 56, 54, 52, 50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 0]
  # このようにすることで、1行で”100から0まで、偶数を降順でリストアップする”が実装できます

いかがでしょうか?使いやすいでしょう?

それでは、みなさん!頑張ってくださいね!

宣伝…

数え上げに使えるcollections の Counter のお話

"collections" ライブラリの "Counter"。文字通り、数えるためにあります。

『数え上げ?普通にfor文回せばいいじゃんアゼルバイジャン

という方もいらっしゃるでしょう。

お前それ競プロの前でも言えんの?

))

では、for + リストでの数え上げがどの程度の愚行なのか実験していきましょう。

for + リストでの数え上げ

import time  # @1
summ = 0
for j in range(1, 11):  #@2
    start = time.time()
    for i in range(int(1e4)):  #@3
        count = [0 for m in range(200)]
        for i in """
        Beautiful is better than ugly.
        Explicit is better than implicit.
        Simple is better than complex.
        Complex is better than complicated.
        Flat is better than nested.
        Sparse is better than dense.
        Readability counts.
        Special cases aren't special enough to break the rules.
        Although practicality beats purity.
        Errors should never pass silently.
        Unless explicitly silenced.
        In the face of ambiguity, refuse the temptation to guess.
        There should be one-- and preferably only one --obvious way to do it.
        Although that way may not be obvious at first unless you're Dutch.
        Now is better than never.
        Although never is often better than *right* now.
        If the implementation is hard to explain, it's a bad idea.
        If the implementation is easy to explain, it may be a good idea.
        Namespaces are one honking great idea -- let's do more of those!
        """:  #@4
            count[ord(i)] += 1  #@5
    end = time.time()
    print("{}: {}  (sec)".format(j, end - start))  #@6
    summ += end - start
for i in range(len(count)):
    if count[i]:
        print("{!r}: {}, ".format(chr(i), count[i]), end="")  #@7
print("")
print("average: {}  (sec)".format(summ / 10))  #@8
  • @1: 時間を計りたいので、timeをimportします
  • @2 10回回して、平均を出そうと思います
  • @3 10000回計算します
  • @4 Pythonインタープリタで >>>import this と入力してみてください。同じものが出ます。これは、Pythonのエッセンスです
  • @5 それぞれの番号を決めるのは面倒なので、文字ごとの文字番号をインデックスにしています
  • @6 10000回計算するごとに、その回の計算時間を出力します
  • @7 改行を改行として出力してしまうので、{!r}を使うことにより、エスケープシーケンスをつけて出力できます
  • @8 10回の平均を出します

出力がこちらになります

1: 1.5162262916564941  (sec)
2: 1.5041000843048096  (sec)
3: 1.5104267597198486  (sec)
4: 1.574958086013794  (sec)
5: 1.4988515377044678  (sec)
6: 1.488734483718872  (sec)
7: 1.499678611755371  (sec)
8: 1.5089690685272217  (sec)
9: 1.5006461143493652  (sec)
10: 1.4950613975524902  (sec)
'\n': 20, ' ': 278, '!': 1, "'": 4, '*': 2, ',': 3, '-': 6, '.': 18, 'A': 3, 'B': 1, 'C': 1, 'D': 1, 'E': 2, 'F': 1, 'I': 3, 'N': 2, 'R': 1, 'S': 3, 'T': 1, 'U': 1, 'a': 50, 'b': 19, 'c': 16, 'd': 16, 'e': 86, 'f': 10, 'g': 11, 'h': 29, 'i': 49, 'k': 2, 'l': 33, 'm': 15, 'n': 38, 'o': 41, 'p': 20, 'r': 31, 's': 42, 't': 74, 'u': 20, 'v': 5, 'w': 4, 'x': 6, 'y': 15, 
average: 1.5097652435302735  (sec)

1.5秒ですか~…。

う~ん、遅い!w

つぎに、ディクショナリを使ってみましょう。

defaultdict をつかう数え上げ

defaultdictを使えば、存在しない要素(key)を指定したときに、勝手に初期化してくれます。

import time
import collections
summ = 0
for j in range(1, 11):
    start = time.time()
    for i in range(int(1e4)):
        count = collections.defaultdict(int)
        for i in """
        Beautiful is better than ugly.
        Explicit is better than implicit.
        Simple is better than complex.
        Complex is better than complicated.
        Flat is better than nested.
        Sparse is better than dense.
        Readability counts.
        Special cases aren't special enough to break the rules.
        Although practicality beats purity.
        Errors should never pass silently.
        Unless explicitly silenced.
        In the face of ambiguity, refuse the temptation to guess.
        There should be one-- and preferably only one --obvious way to do it.
        Although that way may not be obvious at first unless you're Dutch.
        Now is better than never.
        Although never is often better than *right* now.
        If the implementation is hard to explain, it's a bad idea.
        If the implementation is easy to explain, it may be a good idea.
        Namespaces are one honking great idea -- let's do more of those!
        """:
            count[i] += 1
    end = time.time()
    print("{}: {}  (sec)".format(j, end - start))
    summ += end - start
print(count)
print("average: {}  (sec)".format(summ / 10))

こちらの出力はこうなります

1: 1.0501744747161865  (sec)
2: 1.0498456954956055  (sec)
3: 1.0457956790924072  (sec)
4: 1.050318956375122  (sec)
5: 1.0362188816070557  (sec)
6: 1.044149398803711  (sec)
7: 1.0807437896728516  (sec)
8: 1.0319969654083252  (sec)
9: 1.0468177795410156  (sec)
10: 1.0291187763214111  (sec)
defaultdict(<class 'int'>, {'\n': 20, ' ': 278, 'B': 1, 'e': 86, 'a': 50, 'u': 20, 't': 74, 'i': 49, 'f': 10, 'l': 33, 's': 42, 'b': 19, 'r': 31, 'h': 29, 'n': 38, 'g': 11, 'y': 15, '.': 18, 'E': 2, 'x': 6, 'p': 20, 'c': 16, 'm': 15, 'S': 3, 'o': 41, 'C': 1, 'd': 16, 'F': 1, 'R': 1, "'": 4, 'k': 2, 'A': 3, 'v': 5, 'U': 1, 'I': 3, ',': 3, 'T': 1, '-': 6, 'w': 4, 'D': 1, 'N': 2, '*': 2, '!': 1})
average: 1.046518039703369  (sec)

1秒ですか…そこそこですね…
まだまだいけそうですね()

では、大本命、Counterを使ってみましょう

Counter での数え上げ

import time
from collections import Counter
summ = 0
for j in range(1, 11):
    start = time.time()
    for i in range(int(1e4)):
        count = Counter("""
        Beautiful is better than ugly.
        Explicit is better than implicit.
        Simple is better than complex.
        Complex is better than complicated.
        Flat is better than nested.
        Sparse is better than dense.
        Readability counts.
        Special cases aren't special enough to break the rules.
        Although practicality beats purity.
        Errors should never pass silently.
        Unless explicitly silenced.
        In the face of ambiguity, refuse the temptation to guess.
        There should be one-- and preferably only one --obvious way to do it.
        Although that way may not be obvious at first unless you're Dutch.
        Now is better than never.
        Although never is often better than *right* now.
        If the implementation is hard to explain, it's a bad idea.
        If the implementation is easy to explain, it may be a good idea.
        Namespaces are one honking great idea -- let's do more of those!
        """)
    end = time.time()
    print("{}: {}  (sec)".format(j, end - start))
    summ += end - start
print(count)
print("average: {}  (sec)".format(summ / 10))

そして気になる実行時間ですが

1: 0.4078483581542969  (sec)
2: 0.41309595108032227  (sec)
3: 0.4018237590789795  (sec)
4: 0.40430498123168945  (sec)
5: 0.4073166847229004  (sec)
6: 0.424285888671875  (sec)
7: 0.4343554973602295  (sec)
8: 0.42177391052246094  (sec)
9: 0.43581199645996094  (sec)
10: 0.4025719165802002  (sec)
Counter({' ': 278, 'e': 86, 't': 74, 'a': 50, 'i': 49, 's': 42, 'o': 41, 'n': 38, 'l': 33, 'r': 31, 'h': 29, '\n': 20, 'u': 20, 'p': 20, 'b': 19, '.': 18, 'c': 16, 'd': 16, 'y': 15, 'm': 15, 'g': 11, 'f': 10, 'x': 6, '-': 6, 'v': 5, "'": 4, 'w': 4, 'S': 3, 'A': 3, 'I': 3, ',': 3, 'E': 2, 'k': 2, 'N': 2, '*': 2, 'B': 1, 'C': 1, 'F': 1, 'R': 1, 'U': 1, 'T': 1, 'D': 1, '!': 1})
average: 0.4153188943862915  (sec)

Yeah!! Pythonic!!

0.4秒ですって。

リストに比べて約1/4程になりましたね…

このように、非常に高速な演算が可能です。

ちなみに、Counterはdict型を返します。

Counterの便利な使い方

Counterには多くの便利な機能があります。

Counter.elements()

それぞれのkeyを、value個入れたリストを返してくれます。

from collections import Counter
let = Counter("abraham lincoln said\"abracadabra\"")
print(let)
print("".join(sorted(let.elements())))

とすれば、

Counter({'a': 9, 'b': 3, 'r': 3, ' ': 2, 'l': 2, 'i': 2, 'n': 2, 'c': 2, 'd': 2, '"': 2, 'h': 1, 'm': 1, 'o': 1, 's': 1})
  ""aaaaaaaaabbbccddhiillmnnorrrs

となります。

Counter.most_common()

出現回数の多い(valueの多い)ものを、上から引数個分だけ取り出してくれます。引数が無ければ、全て取り出してくれます。

sorted(list(let.items()), key=lambda x: x[1], reverse = True)[:引数]

と同じですね。

from collections import Counter
let = Counter("abraham lincoln said\"abracadabra\"")
print(let.most_common(3))

とすれば

[('a', 9), ('b', 3), ('r', 3)]

が返ってきます。

Counter.substract(another Counter)

Counterから、another Counterの値を引きます。破壊的な関数です。

from collections import Counter
leta = Counter("abraham lincoln said\"abracadabra\"")
letb = Counter("baby array and bad bully")
leta.subtract(letb)
print(leta)

答えがマイナスなどになることも十二分にあり得ます。

Counter({'a': 4, 'i': 2, 'c': 2, '"': 2, 'r': 1, 'h': 1, 'm': 1, 'n': 1, 'o': 1, 's': 1, 'l': 0, 'd': 0, 'b': -1, 'u': -1, ' ': -2, 'y': -3})

どうでしょうか?

非常に使いやすいと思います。

Pythonボトルネックは速度なので、それさえ乗り越えられれば愛せるようになりますよ。すでに愛している方は、さらに愛せるように…

いいお話

あ、そうだ(唐突)

Pythonパーカーを作ろうと思っています。興味の湧いた方はどうぞご一報ください。

かう人が多ければ多いほど安くできるので、募集中です(宣伝)

ちなみに、私に利益な一切来ないようにします…(純粋な愛ゆえのパーカーなので、それで金儲けしようとは考えていません。)
なので、思われているより安いと思いますよ笑

では皆さん、よいPythonライフを!!

Python における list の本質と 二次元配列 ( 多次元配列 ) のお話。

こんなページを見てくださっているような方々は分かり切っていることかもしれませんが、わたくしなりに考えてみたことです。

ネットで、私の疑問に直接回答しているサイトは見当たりませんでしたので、ここに記します。

茶番開始です()

配列の宣言

Pythonでリストを宣言するときは、

list = [1, 1, 1, 1, 1]  # あるいは
list = [1] * 5

のようにするのが一般的かと思います。
そして中身を変更する際は

list[0] = 9
print(list)  # [9, 1, 1, 1, 1]

とするものだと思います。

基本中の基本ですよね。


二次元配列

知らない方のために一応説明しておきますが、二次元配列とは、"要素として配列を使用した配列"です。

つまり、

[[1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [3, 3, 3, 3, 3]]

こういったものです。今のリストは、

list = [[i] * 5 for i in range(1, 4)]

で作成できます。

range(1, 4) つまり i = 1, 2, 3の時の [i] * 5 を要素とするリスト。という意味になります。



ふむふむ。分かりやすい。


では、すべて0で初期化した二次元目の要素数5、一次元目の要素数3のリストを作ってみましょう。

list = [[0] * 5] * 3
print(list)  # [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

できました。では、要素の変換をしてみましょう。

それぞれの要素ごとに対応したインデックスを付けたします。

list[一次元目のインデックス][二次元目のインデックス]

といった感じです。

list[1][2] では、一次元目が2番目の、二次元目が3番目の要素を指定できます。

list = [[0] * 5] * 3
list[1][2] = 1
print(list)  # [[0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0]]

あれ!? 丘people!? なんでこうなるの!?





茶番でした()


はい。よく聞くお話ですよね。


上の宣言では、[0] * 5 というリストを3つ並べているだけなので、1つの要素を変えると、ほかの要素まで変わってしまう。という話です。


もう少し細かくいうと、


[0] * 5 という1つしか無いリストをそれぞれlist[0]からlist[2]で参照しているだけなので、list[1][2]というたった1つの要素を変えたつもりでも、参照元[0] * 5 というリストそのものを書き換えてしまっているので、list[0], list[2]の要素も変わってしまう(様に見える) ということです。
(様に見える)、というのは、もともとlist[0]list[2]も固有の要素を持っているわけではないという意味です※ここ重要です。

なので

list = [[0] * 5] * 3
if id(list[0]) == id(list[1]):
    print("same id")  # same id

となります(id は固有に与えられたものなので、違うものであれば同じidであることはありません。)


ちなみに、先ほどの二次元配列を正しく初期化しようとすると、

list = [[0] * 5 for i in range(3)]
if id(list[0]) != id(list[1]):
    print("different id")  # different id

[0] * 5 というリストを3回作っているので、別のものとしてカウントされます。

となります。

これは私も理解できます。ところで

何故二次元の要素は同じだとカウントされないのだろう

ということを疑問に思いました。

先ほどの物は例として悪いので、新しいものを挙げます。

number = 0
list = [[number] * 5] * 3
print(list)  # [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
list[0][0] = 1
print(list)  # [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]
print(number)  # 0

こういった場合に関する疑問です。

上の宣言から、listの各要素はすべてが number であることがわかります。

そして代入時に

list[0][0] = 1

つまり

number = 1

よって、すべてのnumberを参照している値(list[0][0] から list[2][4])すべてが1に代わるのではないかと思ったのです。


私のどの部分が間違っているのでしょうか?


先ほど使ったid()関数を用いて考えます。

要素すべてがnumber を参照しているわけではない説

確かめてみましょう

number = 0
list = [[number] * 5] * 3
print(id(number))  # 1952997504
print(id(list[0][0]))  # 1952997504
print(id(list[0][1]))  # 1952997504
print(id(list[2][4]))  # 1952997504

全て同じですね。

この説は野獣先輩たまご説ていどの信ぴょう性しかなさそうです。


ということは

代入時に参照が解かれている説

number = 0
list = [[number] * 5] * 3
print(id(number))  # 1952997504
print(id(list[0][0]))  # 1952997504
list[0][0] = 1
print(id(number))  # 1952997504
print(id(list[0][0]))  # 1952997536
print(id(list[0][1]))  # 1952997504

らしいですね。

なぜこんなことが起こるのでしょうか?


実は、Pythonという言語の変数( リスト )の仕様に答えがあります。

答え

勘違いしがちなのですが、実際に変数やリストに値が代入されているわけではないのです。

実のところ、"値をメモリに記憶し、その参照先( アドレス )を保管している"のです。

つまり、list[0][0]が初めに参照してたのは、numberの参照先データです。

そのうえからlist[0][0] には、1 というデータを保管したアドレスを上書きされたので、numberには直接影響は出ません

しかし、list[1][0]list[2][0]list[0][0]のアドレスを参照しているので、こういった事態になるのです。


これは野獣先輩女の子説と同じくらいはっきりわかんだね…

あー、すっきりした。

というわけで、今回は私のバカな疑問でした。

それではPythonistaの皆さん、よいPython Life を!!

宣伝…