matsu7874のブログ

和歌山出身プログラマmatsu7874が書いています。Python3と時々C++11を書きます。

スペース区切りの文字列をリストに格納する方法の比較

競技プログラミングの入力では、一行にいくつかの数字がスペース区切りで並んでいるケースをよくみる。

例えば、No.16 累乗の加算 - yukicodera_1,a_2,...,a_N

Python3でこれらを一つのリストに格納したい時、一番早い方法はなんだろうか。

  1. map関数を使ってからlistにする
  2. リスト内包表記でmap関数
  3. ジェネレータ式からリストにする
  4. リスト内包表記でfor

それぞれに必要な時間を計測した。

import time
import random

A = [str(random.randint(0, 10000)) for i in range(5000)]
S = ' '.join(A)
times = 10000

print('method|elapsed[s]|type(A[0])')
print('---|---|---')
time_start_map = time.time()
for i in range(times):
    A = list(map(int, S.split()))
time_elapsed_map = time.time() - time_start_map
print('list(map)|', time_elapsed_map,'|',type(A[0]))

time_start_map = time.time()
for i in range(times):
    A = [map(int, S.split())]
time_elapsed_map = time.time() - time_start_map
print('[map]|', time_elapsed_map,'|',type(A[0]))


time_start_for = time.time()
for i in range(times):
    A = list(int(x) for x in S.split())
time_elapsed_for = time.time() - time_start_for
print('list(generator)|', time_elapsed_for,'|',type(A[0]))

time_start_for = time.time()
for i in range(times):
    A = [int(x) for x in S.split()]
time_elapsed_for = time.time() - time_start_for
print('[]|', time_elapsed_for,'|',type(A[0]))

結果

method elapsed[s] type(A[0])
list(map) 11.86867880821228 class 'int'
[map] 2.891165256500244 class 'map'
list(generater) 18.646066665649414 class 'int'
[] 17.813018798828125 class 'int'

結論

リスト内包表記でmap関数を使うのが爆速だけどmap形式だと意味が無いよ…… mapからlistに渡すのが早いと思っていたら4倍ほど遅かったのでびっくりしています。 びっくりはするもののこれがlist(map)が最速ですかね。