次のようなコードがよく発生します。
l = []
while foo:
# baz
l.append(bar)
# qux
リストに何千もの要素を追加しようとしている場合、新しい要素に合わせてリストのサイズを常に変更する必要があるため、これは非常に遅くなります。
Java では、初期容量を持つ ArrayList を作成できます。リストがどれだけ大きくなるかある程度わかっている場合、これははるかに効率的です。
このようなコードは、多くの場合、リスト内包表記にリファクタリングできることを理解しています。ただし、for / whileループが非常に複雑な場合、これは実行不可能です。私たち Python プログラマーに相当するものはありますか?
def doAppend( size=10000 ):
result = []
for i in range(size):
message= "some unique object %d" % ( i, )
result.append(message)
return result
def doAllocate( size=10000 ):
result=size*[None]
for i in range(size):
message= "some unique object %d" % ( i, )
result[i]= message
return result
結果。(各関数を 144 回評価し、期間を平均します)
simple append 0.0102
pre-allocate 0.0098
結論。それはほとんど問題ではありません。
時期尚早の最適化は諸悪の根源です。
Python リストには組み込みの事前割り当てがありません。本当にリストを作成する必要があり、追加のオーバーヘッドを回避する必要がある場合 (およびそのことを確認する必要があります)、次のようにできます。
l = [None] * 1000 # Make a list of 1000 None's
for i in xrange(1000):
# baz
l[i] = bar
# qux
おそらく、代わりにジェネレーターを使用してリストを回避できます。
def my_things():
while foo:
#baz
yield bar
#qux
for thing in my_things():
# do something with thing
このように、リストはすべてメモリに保存されるわけではなく、必要に応じて生成されるだけです。
ショートバージョン：使用
pre_allocated_list = [None] * size
リストを事前に割り当てる（つまり、追加してリストを徐々に形成するのではなく、リストの「サイズ」要素をアドレス指定できるようにする）。この操作は、大きなリストでも非常に高速です。後でリスト要素に割り当てられる新しいオブジェクトの割り当てには、はるかに時間がかかり、パフォーマンスの面でプログラムのボトルネックになります。
ロングバージョン：
初期化時間を考慮に入れるべきだと思います。
Pythonではすべてが参照であるため、各要素をNoneに設定するか、文字列に設定するかは関係ありません。どちらの場合も、それは単なる参照です。ただし、参照する要素ごとに新しいオブジェクトを作成する場合は、さらに時間がかかります。
Python 3.2の場合：
import time
import copy
def print_timing (func):
def wrapper (*arg):
t1 = time.time()
res = func (*arg)
t2 = time.time ()
print ("{} took {} ms".format (func.__name__, (t2 - t1) * 1000.0))
return res
return wrapper
@print_timing
def prealloc_array (size, init = None, cp = True, cpmethod = copy.deepcopy, cpargs = (), use_num = False):
result = [None] * size
if init is not None:
if cp:
for i in range (size):
result[i] = init
else:
if use_num:
for i in range (size):
result[i] = cpmethod (i)
else:
for i in range (size):
result[i] = cpmethod (cpargs)
return result
@print_timing
def prealloc_array_by_appending (size):
result = []
for i in range (size):
result.append (None)
return result
@print_timing
def prealloc_array_by_extending (size):
result = []
none_list = [None]
for i in range (size):
result.extend (none_list)
return result
def main ():
n = 1000000
x = prealloc_array_by_appending(n)
y = prealloc_array_by_extending(n)
a = prealloc_array(n, None)
b = prealloc_array(n, "content", True)
c = prealloc_array(n, "content", False, "some object {}".format, ("blah"), False)
d = prealloc_array(n, "content", False, "some object {}".format, None, True)
e = prealloc_array(n, "content", False, copy.deepcopy, "a", False)
f = prealloc_array(n, "content", False, copy.deepcopy, (), False)
g = prealloc_array(n, "content", False, copy.deepcopy, [], False)
print ("x[5] = {}".format (x[5]))
print ("y[5] = {}".format (y[5]))
print ("a[5] = {}".format (a[5]))
print ("b[5] = {}".format (b[5]))
print ("c[5] = {}".format (c[5]))
print ("d[5] = {}".format (d[5]))
print ("e[5] = {}".format (e[5]))
print ("f[5] = {}".format (f[5]))
print ("g[5] = {}".format (g[5]))
if __name__ == '__main__':
main()
評価：
prealloc_array_by_appending took 118.00003051757812 ms
prealloc_array_by_extending took 102.99992561340332 ms
prealloc_array took 3.000020980834961 ms
prealloc_array took 49.00002479553223 ms
prealloc_array took 316.9999122619629 ms
prealloc_array took 473.00004959106445 ms
prealloc_array took 1677.9999732971191 ms
prealloc_array took 2729.999780654907 ms
prealloc_array took 3001.999855041504 ms
x[5] = None
y[5] = None
a[5] = None
b[5] = content
c[5] = some object blah
d[5] = some object 5
e[5] = a
f[5] = []
g[5] = ()
ご覧のとおり、同じNoneオブジェクトへの参照の大きなリストを作成するのにかかる時間はごくわずかです。
プリペンディングまたは拡張には時間がかかります（平均化はしていませんが、これを数回実行した後、拡張と追加にほぼ同じ時間がかかることがわかります）。
要素ごとに新しいオブジェクトを割り当てる-これが最も時間がかかるものです。そして、S.Lottの答えはそれを行います-毎回新しい文字列をフォーマットします。これは厳密には必須ではありません。スペースを事前に割り当てたい場合は、Noneのリストを作成してから、リスト要素にデータを自由に割り当てます。いずれにせよ、リストの作成中に生成するか、その後に生成するかにかかわらず、リストを追加/拡張するよりもデータの生成に時間がかかります。ただし、人口がまばらなリストが必要な場合は、Noneのリストから始める方が間違いなく高速です。
S.Lott のコードを実行したところ、事前割り当てによって同じ 10% のパフォーマンス向上が得られました。ジェネレーターを使用して Ned Batchelder のアイデアを試してみたところ、ジェネレーターのパフォーマンスが doAllocate のパフォーマンスよりも優れていることがわかりました。私のプロジェクトでは 10% の改善が重要です。
def doAppend(size=10000):
result = []
for i in range(size):
message = "some unique object %d" % ( i, )
result.append(message)
return result
def doAllocate(size=10000):
result = size*[None]
for i in range(size):
message = "some unique object %d" % ( i, )
result[i] = message
return result
def doGen(size=10000):
return list("some unique object %d" % ( i, ) for i in xrange(size))
size = 1000
@print_timing
def testAppend():
for i in xrange(size):
doAppend()
@print_timing
def testAlloc():
for i in xrange(size):
doAllocate()
@print_timing
def testGen():
for i in xrange(size):
doGen()
testAppend()
testAlloc()
testGen()
testAppend took 14440.000ms
testAlloc took 13580.000ms
testGen took 13430.000ms
一部のアプリケーションでは、辞書が探しているものになる場合があります。たとえば、find_totient メソッドでは、インデックスがゼロではなかったので、辞書を使用する方が便利であることがわかりました。
def totient(n):
totient = 0
if n == 1:
totient = 1
else:
for i in range(1, n):
if math.gcd(i, n) == 1:
totient += 1
return totient
def find_totients(max):
totients = dict()
for i in range(1,max+1):
totients[i] = totient(i)
print('Totients:')
for i in range(1,max+1):
print(i,totients[i])
この問題は、事前に割り当てられたリストでも解決できます。
def find_totients(max):
totients = None*(max+1)
for i in range(1,max+1):
totients[i] = totient(i)
print('Totients:')
for i in range(1,max+1):
print(i,totients[i])
None を保存しているため、間違って使用すると例外がスローされる可能性があり、マップで回避できるエッジケースについて考える必要があるため、これはエレガントではなく、バグが発生しやすいと感じています。
確かに辞書はそれほど効率的ではありませんが、他の人がコメントしているように、速度のわずかな違いが常に重大なメンテナンスの危険に値するとは限りません。
私の理解では、Python のリストは既に ArrayLists と非常によく似ています。しかし、これらのパラメーターを微調整したい場合は、インターネットで興味深い投稿を見つけました (基本的には、独自のScalableList拡張機能を作成するだけです)。
http://mail.python.org/pipermail/python-list/2000-May/035082.html
