Python3 のデフォルトのデータ構造 (リスト、辞書、タプルなど) の計算上の複雑さはどれくらいですか?
(メモリの複雑さの問題も興味深いです。)
私が見つけたもの: http://wiki.python.org/moin/TimeComplexity - 残念ながら、それは python 2 に関するものですよね?
質問する
344 次
2 に答える
2
The wiki entry apply to CPython for Python 2 and 3. これらのクラスは変更されていません。他の実装は異なる可能性がありますが、コードを CPython から xpython に移植したい場合は、似ている必要があります。たとえば、リスト タイプにリンク リストを使用する Python では、うまく機能させるために、かなり異なるプログラミング スタイルとコードの再配置が必要になります ;-)。
3.3 では、dict クラスが変更され、1 つのクラスの複数のインスタンスの_dict _s に共通する一部の情報が複製される代わりに共有されるようになりました。これは主に、あるクラスの数百または数千のインスタンスを持つ人々に影響し、dict スペースの約 1/3 を節約します (私が思うに)。これは、スペースの複雑さのクラスを変更しない一定の要因です。
さらに重要なことは、(unicode) str クラスが完全に書き直され、必要なバイト数/文字数だけを使用するようになったことです。その結果、通常はスペースと時間が少なくなりますが、やはり主な効果は、O(xxx) 表記によって無視される乗数にあるはずです。
于 2012-05-28T23:00:01.750 に答える
1
計算の複雑さは、 の解き方に関係しています。Python 3 の方が速いかどうかに関係なく、原理が異なるアルゴリズムを使用して問題が解決されない限り、複雑さは同じになります。
場合によっては、同じ名前の抽象データ構造が異なる場合があります (たとえば、Python 2 文字列と Python 3 文字列、または Python 2 の int、long と Python 3 の一般化された int など)。
私はそれをチェックしませんでしたが、私の推測では、Python 2 と Python 3 はこの意味で違いはありません。
于 2012-05-24T07:48:00.417 に答える