Python のリストとセットの効率比較

プログラムの動作効率

プログラムの動作効率は、時間効率とスペース効率の2つに分けられます。時間効率は時間計算量と呼ばれ、空間効率は空間計算量と呼ばれます。時間計算量は主にプログラムの実行速度を測定し、空間計算量は主にプログラムに必要な追加の記憶域スペースを測定します。

理論的に言えば、プログラムの実行にかかる時間を計算することはできません。マシン上でプログラムを実行する場合にのみ、異なる時間に異なるマシンで得られる結果が異なる可能性があることを知ることができます。しかし、コンピュータ上のすべてのプログラムをテストする必要があるでしょうか?それは明らかに非現実的であるため、時間計算量の解析手法が開発されました。実際には, 時間計算量を計算するとき, 必ずしも正確な実行数を計算する必要はなく, おおよその実行数のみを計算する必要があります. 通常は Big O 漸近表現を使用します. 実行数が通常 1 の場合,時間計算量はO(1)と言えますが、n回かかると時間計算量はO(n)と言えます。

スペース複雑度は、アルゴリズムが動作中に一時的に占有するストレージスペースの量の尺度です。空間複雑度は、プログラムが占める空間のバイト数ではありません。実際の操作中に計算するのは難しいため、空間複雑度は変数の数をカウントします。空間計算量の計算ルールは基本的に時間計算量と同様であり、ビッグ O 漸近表記法も使用します。

最も一般的に使用される Python の結合データ型は、タプル、リスト、セット、辞書です。各データ型のさまざまな操作の時間計算量については、Python の公式リンクを参照してください。詳細な手順は Web ページにあります。 ,

• https://wiki.python.org/moin/TimeComplexity

タプルとリストはシーケンス型であり、それらの格納メカニズムは基本的に同じであり、セットとリストです。辞書も基本的には同じですが、唯一の違いは、コレクションの各要素に対応する値がないことです。次に、セットとリストを例として取り上げ、検索効率とストレージのオーバーヘッドを確認します。

データ検索効率

収集効率とリストデータ検索の効率にはどのくらいの差がありますか?まず一連の例を見てみましょう:

import time
import random
nums = [random.randint(0, 2000000) for i in range(1000)]
list_test = list(range(1000000))
set_test = set(list_test)
count_list, count_set = 0, 0
t1 = time.time()# 测试在列表中进行查找
for num in nums:
 if num in list_test:
 count_list += 1
t2 = time.time()
for num in nums:# 测试在集合中进行查找
 if num in set_test:
 count_set += 1
t3 = time.time()# 测试在集合中进行查找
print('找到个数，列表：{}，集合：{}'.format(count_list, count_set))
print('使用时间，列表：{:.4f}s'.format(t2 - t1))
print('使用时间，集合：{:.4f}s'.format(t3 - t2))

出力結果は次のとおりです:

找到个数，列表：515，集合：515
使用时间，列表：7.7953s
使用时间，集合：0.0010s

上記の例から、セットの検索効率がリストの検索効率よりもはるかに高いことが明確にわかります。したがって、さまざまなアプリケーション シナリオでは、必ず適切なデータ型を選択してください。少量のデータではパフォーマンスの違いはわかりません。大量のデータに切り替えると、その違いは大きく異なります。

データ ストレージのオーバーヘッド

セットの検索効率はリストの検索効率よりもはるかに高速です。主な理由は、ストレージの原則が異なるためです。セットは追加情報を保存するためにより多くのスペースを消費する必要があります。時間効率と引き換えにスペースを使用します。次に、getsizeof() 関数を使用してストレージ オーバーヘッドの違いを確認します。getiszeof() 関数は、Python の sys モジュールでオブジェクトのメモリ サイズを取得するために使用される関数です。返されるサイズはバイト単位です。

import sys
import random
list_test = list(range(1000000))
set_test = set(range(1000000))
print('列表占用大小：', sys.getsizeof(list_test))
print('集合占用大小：', sys.getsizeof(set_test))

出力結果は次のとおりです:

列表占用大小：9000112
集合占用大小：33554656

この結果から、同じデータ コンテンツの場合、コレクション ストレージのコストはリストのコストの数倍であることがわかります。

以上がPython のリストとセットの効率比較の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。