AtCoder Pythonの新環境についてまとめていく-1- 組み込み関数&モジュール

AtCoder

いよいよAtCoderのジャッジシステムが更新されますね！

しっかり環境構築しつつ、新しく使えるようになった便利なものは積極的に使っていきたいものです。

ということでドキュメントを流し読みしながら気をつけたほうがよさそうなことや、便利そうなものをまとめていくことにしました。(Pythonです)

記事作成日　2020.04.05

新環境のVersion

まずメインどころは以下のバージョンに変わったようです。

  • Python 3.4.3　->　3.8.2
  • NumPy 1.8.2　->　1.18.2
  • SciPy 0.13.3　->　1.4.1

一応以下のように確認したので間違ってはいないはずです。

ほんとはNumPy, SciPyもまとめたかったんですが、色々みていたら思ったより長くなってしまったので、今回は組み込み関数と組み込みモジュールのみです。

Pythonのバージョンによる違い

collections.deque　（モジュール）

それほど大きな変化ではありませんが、以下の機能が追加されています。(3.5 document)

  • copy()
  • insert()
  • index()

insertは用事がないかもしれませんが、index(), copy()は使う機会があるかもしれませんね。

copyは割愛しますが、IndexはIndex(探したい値, 探索開始位置, 探索終了位置)で使えるようです。値がない場合はValueErrorになるので注意です。

from collections import deque

A = deque([1, 2, 4, 8, 4])
print(A.index(4))
# 2

print(A.index(4, 3))
# 4

print(A.index(4, 1, 3))
# 2

print(A.index(4, 1, 2))
# ValueError 4 is not in deque

dictの改良　省メモリ&順序保持

dictのメモリ消費が20~25%小さくなったようです。メモリがコンパクトになれば処理速度も速くなると思うので、制限時間が厳しい問題が解きやすくなるかもしれませんね！

また、keyの挿入順序を保持してくれるようになりました。for key in dict:　で挿入した順にkeyが取り出せますし、reversed(dict.items())のように逆順の取り出しも可能です。

しかもif key in dictもしっかりO(1)で動きます。すごいですね！！！（どうやって実装してるのか気になるので今度ソースコードをみて勉強してみます）

collections.OrderedDict　（モジュール）

辞書のキーの挿入順序を保持してくれるデータ構造です。以前から使えた機能ですが、C言語で再実装されたようで、4~100倍早くなったそうです。(document)

ただし、前述した通り通常のdictもkeyの挿入順序を保持してくれるようになっています。

OrderedDictにしかない機能としてはめぼしいところでは以下のようなものがあります。

  • dictはpopitem()でLIFOでしか要素を取りだせないが、OrderedDictはpopitem(last=False)にすればFIFOで要素を取り出せる。（dequeみたいですね）
  • move_to_end(key, last=bool)で特定の要素の順序を最初 or 最後に移動できる。しかもO(1)っぽいです。

要素の順序も欲しいし、LIFOとFIFOを切り替えたり、時には真ん中らへんの要素も欲しいなんていう欲張りな問題で使えたりするかもしれませんね。

速度の比較については、vs dictでは簡単な処理だとどちらもそれほど変わらない（普通のdictの方がややはやい？）ようです。

import time
from collections import OrderedDict

start = time.time()
ordered = OrderedDict()
for i in range(5 * 10 ** 6):
    ordered[i] = i
for key in ordered:
    ordered[key] += 1
print(time.time() - start)
# 2.177706003189087

start = time.time()
normal = dict()
for i in range(5 * 10 ** 6):
    normal[i] = i
for key in normal:
    normal[key] += 1
print(time.time() - start)
# 1.9143791198730469

またdequeの代わりに使えるかどうかも確認してみましたがさすがにdequeの方が速そうです。（そもそもkeyの重複不可なので使いづらいとは思いますが）

import time
from collections import OrderedDict
from collections import deque

start = time.time()
dic = OrderedDict()
for i in range(5 * 10**6):
    dic[i] = i

for _ in range(5 * 10**6):
    dic.popitem(last=False)

print(time.time() - start)
# 2.5691630840301514

start = time.time()
deq = deque([])
for i in range(5 * 10**6):
    deq.append(i)

for _ in range(5 * 10**6):
    deq.popleft()

print(time.time() - start)
# 1.0689191818237305

typing　（モジュール）

興味がない人が多い気がしますが、Pythonでも変数の型宣言に近いことができるようになっていて（あくまで型のヒントを明示するだけ）、そのためのモジュールの機能がかなり整備されています。

ライブラリの構築でコードをわかりやすくするために使ってみるといいかもです。

f-strings（構文）

個人的にはこれが結構嬉しいです。（役立つ機会少ないですが・・・）str.format()とよく似ていますが、f-stringsの方が書きやすく感じています。

これまで'{}’.format(変数名)としていたところを、f'{変数名}’と書けるようになります。

細かい仕様はdocumentを参照していただきたいですが、結構直感的なので使いやすいですよね？？

その他formatでできること（0埋めや小数点桁数揃えなど）もformatと同じ指定方法で実現できます。

Google Code Jamででてきたアウトプットの様式なんかに使いたくなります！（ちなみにGCJのPythonのバージョン3.5では使えなくて、しばらくハマってました・・・）

test_number = 10
ans = 999

print('Case #{} {}'.format(test_number, ans))
# Case #10 999

print(f'Case #{test_number} {ans}')
# Case #10 999

1_000_000_007（構文）

数値の桁が多い時に_で区切れるようになりました。

これでmodが書きやすくなりますね。私は10**9 + 7と書きます

print(10**9 + 7)
print(1_000_000_007)

async/await（構文）

ごめんなさい。よくわかってません。非同期処理に関する機能が色々とサポートされたようです。またこれに伴って予約語として登録されたため、変数名に上記2種は使用できなくなりました。

うまいこと使えば高速化できるんでしょうか？？？うーむ・・・・・

Decimal.as_integer_ratio()（モジュール）

Decimal型の関数にas_integer_ratio()が追加されました。高精度で少数から分数に変換したい時に使えます。（いままでこの変換をやりたいと思ったことはないんですが一応）

from decimal import Decimal

num = Decimal(0.5)
print(num.as_integer_ratio())
# (1, 2)

math.gcd（モジュール）

これは有名ですね。今までの環境だとfraction.gcdで使っていたと思いますが、新環境からmathモジュールの中に入ります。気をつけましょう！！

あとmath.comb（組み合わせの計算）も追加されているので、近いうちにscipyとの比較もやってみたいと思います。

queue.SimpleQueue（モジュール）

queueモジュールにSimpleQueueクラスが追加されました。Queueからタスク管理の機能などを取り払ったクラスとのことです。

がしかし、普通のQueueと比べて特別速いわけではないようなので、collections.dequeを使っておけば良いと思います。

import time
from queue import SimpleQueue, Queue
from collections import deque

# ------Queue-------
start = time.time()
que = Queue()
for i in range(10**6):
    que.put(i)
for _ in range(10**6):
    que.get()

time_que = time.time() - start
print(time_que)
# 3.783491849899292

# ------SimpleQueue-------
start = time.time()
s_que = SimpleQueue()

for i in range(10**6):
    que.put(i)
for _ in range(10**6):
    que.get()
# 3.6932871341705322

time_sque = time.time() - start
print(time_sque)

# ------deque-------
start = time.time()
deq = deque([])
for i in range(10**6):
    deq.append(i)
for _ in range(10**6):
    deq.popleft()
time_deq = time.time() - start
print(time_deq)
# 0.21197223663330078

:=　セイウチ演算子（構文）

名前がユニークでハイセンスですよね。私はあんまり積極的に使おうとは思っていないんですが、これから使う人が増えるかもしれないので、他人のコードをよく読む人は知っておいた方が良さそうです。

変数に代入しながらいろいろ処理ができるようです。導入にあたっては結構Python界隈でももめたみたいですね。

A = [1, 2, 3, 4]

if (n := len(A)) < 5:
    print(n)  # 4

if len(A) < 5:
    print(len(A))  # 4

n = len(A)
if n < 5:
    print(n)  # 4

### これ注意です ###
if n := len(A) < 5:
    print(n)  # True

まとめ

  • dictがkeyの挿入順序を反映します。
  • 多機能なOrederdDictが速くなったらしい。
  • f-stringsいいよ！
  • math.gcd !!!!!!!
  • :=

長くなってしまったので、とりあえずここまで。NumPy, SciPyはまた時間のある時に調査したいと思います。

コメント

タイトルとURLをコピーしました