python - len() 関数のコスト

Question

len()Python 組み込み関数のコストはいくらですか? (リスト/タプル/文字列/辞書)

Answer 1

それは、あなたが言及したすべてのタイプ、setおよびarray.array.

Answer 2

これらのデータ型で len() を呼び出すことは、Python 言語の最も一般的な実装であるCPythonの O(1) です。CPython のさまざまな関数のアルゴリズムの複雑さを示す表へのリンクを次に示します。

TimeComplexity Python Wiki ページ

Answer 3

これらのオブジェクトはすべて、独自の長さを追跡します。長さを抽出する時間は短く (big-O 表記の O(1))、ほとんど [大まかな説明、C 用語ではなく Python 用語で記述] で構成されます: 辞書で「len」を検索し、それをオブジェクトの__len__メソッドを検索してそれを呼び出す built_in len 関数... 必要なのは、return self.length

Answer 4

len()以下の測定値は、頻繁に使用されるデータ構造に対して O(1) で あるという証拠を提供します。

に関する注意timeit:-sフラグが使用され、2 つの文字列が最初の文字列に渡されるとtimeit、1 回だけ実行され、タイミングが設定されません。

リスト：

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop

タプル:

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop

弦：

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop

辞書 (辞書の理解は 2.7+ で利用可能):

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop

配列：

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop

セット (セット内包表記は 2.7 以降で使用可能):

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

デキュー:

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

Answer 5

len は O(1) です。これは、RAM ではリストがテーブル(一連の連続したアドレス) として格納されるためです。テーブルがいつ停止するかを知るには、長さと開始点の 2 つが必要です。これが len() が O(1) である理由です。コンピューターは値を格納するため、検索するだけで済みます。