プログラミング歴1年の新人です
pythonにはリストと言うものが存在しますが、この中身はどういった物なのでしょうか
私の認識ではlistと言うと連結リスト等の事を表してると思ったのですが、多くの入門サイトにおいては他の言語における配列と同じ物だと書かれているものもあります
しかし、もしpythonのリストの中身が一般的にリストと呼ばれている(と私が誤認しているだけかもしれないが)物だとしたら、配列と同じ物と呼んでしまうと明らかに語弊があるのではないかと思います
pythonのリストの中身はどういった物なのか、ご存知の方いらっしゃったらお願いします
4 件の回答
本家の Fred Foo さんの回答によれば、CPython の実装には「ポインタの配列」が使われている様子です。
typedef struct {
PyObject_HEAD
Py_ssize_t ob_size;
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
*/
Py_ssize_t allocated;
} PyListObject;
なので、配列と同じようなものと考えても問題ありません。
(他の言語でいうと、 C++ ならば vector, Java ならば ArrayList でしょうか。)
-
Python のリストはヘテロなので、C++ の vector を普通に使うとちょっと違うかもしれないな、と思いました(
boost::any
もあるので直ちには言えないのですが……)。– nekketsuuu ♦Commented 2017年7月27日 12:45
Python の リファレンス・マニュアル (日本語版はこちら) を読む限りでは、マニュアルのレベルでは Python の「リスト」がどのような実装になっているべきかは書かれていないようです。(ただし Python FAQ には書かれていました。)
そこでこの投稿では、Python 処理系の実際の実装においてリストがどのように実現されているかに注目して回答します。
Python の処理系はいくつかありますが、ここでは標準的な実装である CPython を取り上げます。
CPython における実装
CPython は、C 言語によって実装された Python 処理系で、最も一般的に使われている処理系です。普段 python
コマンドを実行したときに立ち上がっているものと考えて頂いて差し支えありません。
この処理系の実装では、「リスト」はいわゆる連結リストのことではありません。多くのサイトに書かれている通り、C 言語の配列とほぼ同じものだと考えてよいでしょう。正確にいうと、可変長かつ heterogeneous な配列になっています。
以下、もっと詳しく解説してみます。
CPython の実装では、リスト型の値を表す PyListObject
構造体が Include/listobject.h で定義されています (Python version 3.7.1 alpha 1 時点)。
今回大事な部分だけ抜き出してコードから引用すると、以下の通りです。
typedef struct {
/* 中略 */
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* 中略 */
} PyListObject;
// CPython のコードより引用したものを加工しました。
つまり、 CPython のリストは「"各要素が置いてあるアドレス"の配列」の形で実装されています。
このように実装されていると、リストの n
番目の要素 list[n]
へのアクセスが O(1) 時間で可能になります。(連結リストだと O(n) 時間かかります。)
この意味で、CPython のリストの 中身 は C 言語における配列とほぼ同じと言えるでしょう。
ただし Python のリストをプログラムから触るときには、可変長であったり、違う型のオブジェクトを同じリストに入れられたりする (heterogeneous) ので、この意味では C 言語における生の配列とは少し違って感じられるかもしれません。
たとえば以下は CPython 3.6.0 で試してみた例です。id(x)
で x
のアドレスが分かります。
>>> str = 'abc'
>>> mylist = [1, 2, 3, 'one', str, str]
>>> id(mylist)
140278170168200
>>> for item in mylist:
... print(id(item))
...
140278195378432
140278195378464
140278195378496
140278167680088
140278196758432
140278196758432
>>>
リストの各要素が実際に置かれているアドレスは連続しておらず、まただんだん増えていっているわけでもないことが分かると思います。
TimeComplexity - Python WikiによればCPythonのリストは配列で実装されています。さらに重要なのはGet Item
, Set Item
がC等の配列と同じくO(1)で行える=ランダムアクセスができるという点です。この特徴を以って「他の言語における配列と同じ物」と言っているのだと思います。
(プログラマからの観点)Pythonのリストの構造は、リニア リストですから、配列とほぼ同義です。
(内部構造)Pythonはリスト、配列、タプルなど様々な構造を持っていますので、その内部表現ではリンク(ポインター)が活用されているだろうと推測します。連結リストも使われているのではないでしょうか。