240

それはリンクリストですか、配列ですか？周りを検索したところ、推測している人しか見つかりませんでした。私のCの知識は、ソースコードを見るのに十分ではありません。

4

9 に答える 9

288

実際、Cコードは非常に単純です。1つのマクロを展開し、いくつかの無関係なコメントを削除すると、基本構造はにlistobject.hあり、リストを次のように定義します。

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;

PyObject_HEAD参照カウントとタイプ識別子が含まれます。つまり、全体を割り当てるのはベクトル/配列です。いっぱいになったときにそのような配列のサイズを変更するためのコードはにありlistobject.cます。実際には配列が2倍になるわけではありませんが、割り当てることで大きくなります

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

毎回容量に合わせてnewsize、要求されたサイズはどこにありますか（必ずしも、要素を1つずつ作成するのではなく、任意の数の要素でallocated + 1実行できるためではありません）。extendappend

PythonFAQも参照してください。

于 2010-10-18T10:39:40.133 に答える
73

これは動的配列です。実用的な証明：インデックス作成には、インデックスに関係なく、同じ時間がかかります（もちろん、非常に小さな違い（0.0013 µsecs！））。

...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop

...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop

IronPythonまたはJythonがリンクリストを使用した場合、私は驚かれることでしょう。リストが動的配列であるという仮定に基づいて構築された、広く使用されている多くのライブラリのパフォーマンスを台無しにしてしまいます。

于 2010-10-12T18:04:10.837 に答える
54

LaurentLuceの記事「Pythonリストの実装」をお勧めします。著者がリストがCPythonでどのように実装されているかを説明し、この目的のために優れた図を使用しているので、私にとって本当に役に立ちました。

リストオブジェクトのC構造

CPythonのリストオブジェクトは、次のC構造体で表されます。ob_itemリスト要素へのポインタのリストです。割り当て済みは、メモリに割り当てられているスロットの数です。

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

割り当てられたスロットとリストのサイズの違いに注意することが重要です。リストのサイズはと同じlen(l)です。割り当てられたスロットの数は、メモリに割り当てられたものです。多くの場合、割り当てられたサイズよりも大きくなる可能性があります。reallocこれは、新しい要素がリストに追加されるたびに呼び出す必要がないようにするためです。

..。

追加する

リストに整数を追加します：l.append(1)。何が起こるのですか？
ここに画像の説明を入力してください

さらにもう1つの要素を追加します：l.append(2)。list_resizeはn+1 = 2で呼び出されますが、割り当てられたサイズが4であるため、これ以上メモリを割り当てる必要はありません。さらに2つの整数を追加しても同じことが起こります：l.append(3)、l.append(4)。次の図は、これまでの状況を示しています。

ここに画像の説明を入力してください

..。

入れる

位置1に新しい整数（5）を挿入して、l.insert(1,5)内部で何が起こるかを見てみましょう。ここに画像の説明を入力してください

..。

ポップ

最後の要素をポップすると：l.pop()、listpop()が呼び出されます。list_resize内部で呼び出されlistpop()、新しいサイズが割り当てられたサイズの半分未満の場合、リストは縮小されます。ここに画像の説明を入力してください

スロット4はまだ整数を指していることがわかりますが、重要なのはリストのサイズが4になっていることです。もう1つの要素をポップしましょう。ではlist_resize()、サイズ– 1 = 4 – 1 = 3は割り当てられたスロットの半分未満であるため、リストは6スロットに縮小され、リストの新しいサイズは3になります。

スロット3と4はまだいくつかの整数を指していることがわかりますが、重要なのはリストのサイズが3になっていることです。ここに画像の説明を入力してください

..。

Pythonリストオブジェクトの削除には、特定の要素を削除するメソッドがありますl.remove(5)。ここに画像の説明を入力してください

于 2017-07-20T10:50:05.363 に答える
45

これは実装に依存しますが、IIRC：

  • CPythonはポインターの配列を使用します
  • JythonはArrayList
  • IronPythonは明らかに配列も使用しています。ソースコードを参照して調べることができます。

したがって、それらはすべてO（1）ランダムアクセスを持っています。

于 2010-10-12T17:59:29.740 に答える
40

CPythonでは、リストはポインターの配列です。Pythonの他の実装では、さまざまな方法でそれらを保存することを選択できます。

于 2010-10-12T18:00:23.480 に答える
26

ドキュメントによると、

Pythonのリストは実際には可変長配列であり、Lispスタイルのリンクリストではありません。

于 2012-06-01T15:07:33.230 に答える
5

他の人が上で述べたように、リスト（かなり大きい場合）は、一定量のスペースを割り当て、そのスペースがいっぱいになる場合は、より多くのスペースを割り当てて要素をコピーすることによって実装されます。

この方法が一般性を失うことなくO（1）償却される理由を理解するために、a = 2 ^ n要素を挿入したと仮定し、テーブルを2 ^（n + 1）サイズに2倍にする必要があります。これは、現在2 ^（n + 1）回の操作を行っていることを意味します。最後のコピーでは、2^n回の操作を行いました。その前に、2 ^（n-1）...を8,4,2,1まで行いました。ここで、これらを合計すると、1 + 2 + 4 + 8 + ... + 2 ^（n + 1）= 2 ^（n + 2）-1 <4 * 2 ^ n = O（2 ^ n）= O（a）合計挿入数（つまり、O（1）償却時間）。また、テーブルで削除が許可されている場合は、テーブルの縮小を別の要素（3xなど）で実行する必要があることに注意してください。

于 2013-10-22T03:00:45.573 に答える
2

Pythonのリストは配列のようなもので、複数の値を格納できます。リストは変更可能です。つまり、リストを変更できます。あなたが知っておくべきもっと重要なことは、リストを作成するとき、Pythonはそのリスト変数のreference_idを自動的に作成します。他の変数を割り当てて変更すると、メインリストが変更されます。例を試してみましょう：

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

追加しますmy_listが、メインリストが変更されました。つまり、のリストは、参照として割り当てるコピーリストとして割り当てられませんでした。

于 2019-08-20T12:36:15.723 に答える
-2

CPythonでは、リストは動的配列として実装されているため、その時点で追加すると、マクロが1つ追加されるだけでなく、新しいスペースが追加されないように、さらにスペースが割り当てられます。

于 2020-03-19T14:31:24.407 に答える