Pythonのリスト（list）は変更可能な構造であり、タプル（tuple）は変更不可能です。

list: 新しい要素を追加する（append、extend、insert）際、Pythonは配列の成長時に割り当て回数を最小限に抑えるために"余裕を持って"メモリブロックを確保します（"over-allocation strategy"）。要素の削除（pop、remove）は迅速に行われますが、時にはメモリの再配分を引き起こすことがあります。
tuple: タプルのサイズは固定であり、要素は変更または追加できません。これにより、大量の不変データを保持する際に、リストに比べて読み取り操作の速さとメモリの消費が減少します。

リストとタプルの変更を示す例:

lst = [1, 2, 3]
lst.append(4)    # OK
lst[1] = 20      # OK

tup = (1, 2, 3)
tup[1] = 20      # TypeError

パフォーマンス:

質問: なぜリストへの要素追加操作は通常迅速に実行されるか（O(1)）、配列の観点からはメモリの再配分を引き起こすはずなのに？

答え:

Pythonは"数個の要素のために余分にメモリを割り当てる"動的配列を実装しています。したがって、appendは通常O(1)であり、メモリの再配分は実際の予約ブロックの枯渇時にのみ発生します。

例:

import sys
lst = []
for i in range(10):
    lst.append(i)
    print(len(lst), sys.getsizeof(lst))  # メモリサイズは厳密に線形には増加しない

歴史

あるプロジェクトでは辞書のキーにlistが使用されました。開発者はリストがハッシュ化されないこと（可変性）を知らず、"TypeError: unhashable type: 'list'"というエラーを引き起こしました。

開発者はよく長いリストを+を使って連結していました。これにより配列の追加コピーが発生し、高いメモリと時間のオーバーヘッドがかかりました。サイクル内でappendを使用するか、ジェネレーターを使用する方が効率的でした。

ロギングシステムでは、タイムスタンプを保持するためにタプルを選択しましたが、不変性のおかげで速くなると思っていました。しかし、時折変更の必要が生じ、新しいタプル（コピーオンライト）を常に作成する必要があり、リストを使用する場合に比べて動作が遅くなりました。

Pythonにおけるリストとタプルのメモリ管理者の動作原理を説明してください。リストとタプルの要素を変更/追加することの違いは何ですか、そして、それがパフォーマンスにどのように影響しますか？