リストとPythonでゼロを格納する辞書

Question

私はゼロのリストが必要な問題を解決しています。その後、リスト内のいくつかの値を更新する必要があります。今私は私の心の中で2つの選択肢があります。これはまず最初にゼロのリストを作成して値を更新するか、辞書を作成して値を更新することです。

リスト方式：

l=[0]*n 

辞書法：今すぐ

d={} 
for i in range(n): 
    d[i]=0 

複雑に辞書を構築するためには、O(n)あるし、キーを更新するとO(1)です。しかし、私はPythonが上記の方法を使ってゼロのリストを構築する方法を知らない。

ここで、nが大きな値であるとしましょう。上記の方法は、このタスクに適していますか？リストメソッドはどのようにPythonで実装されていますか？ 。また、なぜ上記のリストメソッドはリストの理解の方法よりもゼロのリストを作成するより速いのですか？

Answer 1

シーケンスをあらかじめ割り当てておけば、アクセスと更新はほぼ同じになります。

アプリケーションに適したデータ構造を選択します。この場合、より自然に「整数でインデックス付けされたシーケンス」に適合するため、リストを提案します。

理由は[0] * nが速いのは、常に拡大するのではなく、正しいサイズのリストを1回で作成できるからですより多くの要素が追加されたリスト。

Answer 2

timeitを使用してテストを実行した後：

import timeit 
timeit.repeat("[0]*1000", number=1000000) 
#[4.489016328923801, 4.459866205812087, 4.477892545204176] 

timeit.repeat("""d={} 
for i in range(1000): 
d[i]=0""", number=1000000) 
#[77.77789647192793, 77.88324065372811, 77.7300221235187] 

timeit.repeat("""x={};x.fromkeys(range(1000),0)""", number=1000000) 
#[53.62738158027423, 53.87422525293914, 53.50821399216625] 

あなたが見ることができるようにこれらの2つの方法と三番目が優れている間ではなく、リストのような大きな違いがあります！その理由は、サイズが指定されたlistを作成することは、反復でそれを拡張してdictionaryを作成するよりも速すぎます。

Answer 3

インデックスを使用せずに一部のデータにアクセスしたい場合を除き、このような状況ではリストを使用してください。

Pythonリストは配列です。これは、特定のサイズで初期化されます。サイズを保持できるよりも多くのアイテムを格納する必要がある場合は、すべてを新しい配列にコピーし、コピーはO（k）です。ここで、kはリストのサイズです。このプロセスは、リストがn以上のサイズになるまで何度も発生する可能性があります。ただし、[0] * nは適切なサイズ（n）の配列を作成するだけなので、リストを最初から正しいサイズに更新するよりも高速です。

リストの理解で作成する場合、[0 for i in range(n)]のようなものなら、リストサイズを更新するのが苦労し、遅くなると思います。

Python辞書はハッシュテーブルの実装であり、新しいキーと値のペアを挿入するときにハッシュ関数を使用してキーのハッシュ値を計算します。ハッシュ関数そのものの実行自体は比較的高価であり、辞書は衝突のような他の状況も処理するため、辞書はさらに遅くなります。したがって、辞書による作成0は、理論的には最も遅くなければならない。

Answer 4

collections.defaultdictは、初期値を保持している更新中に多くの要素が変更されないようにしたい場合（そして何らかの形でKeyErrorに依存しない場合）、より良い解決策になる可能性があります。ちょうど

import collections 
d = collections.defaultdict(int) 

assert d[42] == 0 
d[43] = 1 
# ... 

もう一つ考慮すべきことはarray.arrayです。 1つのタイプの要素（数）だけを保存する場合に使用できます。

import array 
l = array.array('L', [0]) * n 
# use as list