2

私はcPythonリストのこれらのパフォーマンスノートを見つけました：

Pythonリストに必要な時間...。

  • ...個々のアイテムを取得または設定します：O（1）
  • ...リストに項目を追加します：最悪のO（n ^ 2）、ただし通常はO（1）
  • ...アイテムを挿入します：O（n）、ここでnは挿入された要素の後の要素の数です
  • ...アイテムを削除します：O（n）

ここで、cPythonセットの同じパフォーマンス特性を知りたいと思います。また、リスト/セットの反復がどれだけ速いかを知りたいです。私は特に大きなリスト/セットに興味があります。

4

1 に答える 1

1

AFAIK、Pythonの「仕様」は、リスト、辞書、またはセットの実装に特定のデータ構造を課していないため、これに「公式に」答えることはできません。CPython（リファレンス実装）のみに関心がある場合は、非公式の複雑さを取り入れることができます。特定のPython実装を対象とするように、質問を再定式化することをお勧めします。

いずれにせよ、あなたが言及した複雑さは正しくありえません。動的にサイズ変更された配列の実装を想定すると、アイテムの追加は償却されO(1)ます。ほとんどの場合、新しい値を単純にコピーし、最悪の場合、すべてのnアイテムと新しい値をコピーして再割り当てする必要があります。次に、挿入の最悪のシナリオはまったく同じであるため、複雑さの上限は同じですが、最良の場合、挿入する位置を超えたアイテムの数であるアイテムkのみが移動します。k

于 2011-03-06T23:08:36.443 に答える