【Python】リスト vs タプル vs セットの違い(速度とメモリ

# 可変(list)と不変(tuple)の違い
fruits_list = ["apple", "banana"]
fruits_list[0] = "grape"  # OK: リストは要素を更新できる
fruits_list.append("orange")  # OK: 要素の追加も可能

fruits_tuple = ("apple", "banana")
# fruits_tuple[0] = "grape"  # NG: タプルは不変なので更新不可 -> TypeError

# タプルは(要素がハッシュ可能なら)辞書キーにできる
coords = {(10, 20): "A", (30, 40): "B"}
print(coords[(10, 20)])  # => "A"

# リストはハッシュ不可能なのでキーにできない
try:
    bad = {[1, 2]: "NG"}  # TypeError
except TypeError as e:
    print("エラー:", e)

# タプルでも、中にリストが入るとハッシュ不可能になる
x = ([1, 2], 3)
try:
    s = {x}  # TypeError
except TypeError as e:
    print("エラー:", e)

# 重複排除とメンバーシップ判定はsetが有利
items = ["A", "B", "A", "C", "B"]
unique = set(items)  # {'A', 'B', 'C'}

print("B in items(list)?", "B" in items)  # O(n)
print("B in unique(set)?", "B" in unique)  # 平均O(1)

# 検索速度の比較: list vs set
import timeit

setup = """
data_list = list(range(200_000))
data_set = set(data_list)
target_hit = 199_999
target_miss = -1
"""

stmt_list_hit = "target_hit in data_list"
stmt_list_miss = "target_miss in data_list"
stmt_set_hit = "target_hit in data_set"
stmt_set_miss = "target_miss in data_set"

for label, stmt in [
    ("list hit", stmt_list_hit),
    ("list miss", stmt_list_miss),
    ("set  hit", stmt_set_hit),
    ("set  miss", stmt_set_miss),
]:
    t = timeit.timeit(stmt, setup=setup, number=5)
    print(f"{label:10s}: {t:.6f}s (5回合計)")

# 追加・削除のコスト比較
import timeit

setup = """
N = 200_000
lst = []
st = set()
"""

# append vs add
t_list_append = timeit.timeit("for i in range(N): lst.append(i)", setup=setup, number=1)
t_set_add = timeit.timeit("for i in range(N): st.add(i)", setup=setup, number=1)
print(f"list.append: {t_list_append:.4f}s, set.add: {t_set_add:.4f}s")

# pop vs remove
setup2 = """
N = 200_000
lst = list(range(N))
st = set(range(N))
"""
t_list_pop = timeit.timeit("while lst: lst.pop()", setup=setup2, number=1)
t_set_remove = timeit.timeit("for i in range(N): st.remove(i)", setup=setup2, number=1)  # 存在前提
print(f"list.pop (末尾): {t_list_pop:.4f}s, set.remove: {t_set_remove:.4f}s")

# 連結・拡張の違い
a_list = [1, 2]
b_list = [3, 4]
a_list.extend(b_list)  # a_listが[1,2,3,4]に拡張(破壊的)

a_tuple = (1, 2)
b_tuple = (3, 4)
c_tuple = a_tuple + b_tuple  # 新しいタプル(元は不変)

a_set = {1, 2}
b_set = {2, 3}
u1 = a_set | b_set          # 新しい集合{1,2,3}
a_set.update(b_set)         # a_setが{1,2,3}に(破壊的)

print(a_list, c_tuple, u1, a_set)

# イテレーション速度の目安
import timeit
setup = "lst = list(range(1_000_000)); tpl = tuple(lst); st = set(lst)"
for label, stmt in [
    ("list", "for x in lst: pass"),
    ("tuple", "for x in tpl: pass"),
    ("set", "for x in st: pass"),
]:
    t = timeit.timeit(stmt, setup=setup, number=1)
    print(f"{label:5s}: {t:.4f}s")

nums_set = {5, 1, 3}
# nums_set.sort()  # NG: setにsortはない
sorted_list = sorted(nums_set)       # 新しいリスト [1, 3, 5]
nums_list = [5, 1, 3]
nums_list.sort(reverse=True)         # 就地で降順 [5, 3, 1]
print(sorted_list, nums_list)

import sys

empty_sizes = {
    "list": sys.getsizeof([]),
    "tuple": sys.getsizeof(()),
    "set": sys.getsizeof(set()),
}
print(empty_sizes)

# 代表サイズ
lst = list(range(10_000))
tpl = tuple(lst)
st = set(lst)
print(sys.getsizeof(lst), sys.getsizeof(tpl), sys.getsizeof(st))

def unique_preserve_order(seq):
    # 見た要素をsetで記録し、結果はリストで並びを保持
    seen = set()
    out = []
    for x in seq:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out

data = ["A", "B", "A", "C", "B"]
print(unique_preserve_order(data))  # ['A', 'B', 'C']

data = ["A", "B", "A", "C", "B"]
print(list(dict.fromkeys(data)))  # ['A', 'B', 'C']

# list <-> tuple
lst = [1, 2, 3]
tpl = tuple(lst)
lst2 = list(tpl)

# list/set: 重複排除や集合演算の後に並びが必要ならlistへ
st = set(lst)         # {1, 2, 3}
lst_unique = list(st) # 並びは保証されない。必要ならsorted(st)やdict.fromkeysを使う

# 代表的な集合演算
a = {1, 2, 3}
b = {3, 4}
print(a | b)   # 和集合 {1, 2, 3, 4}
print(a & b)   # 積集合 {3}
print(a - b)   # 差集合 {1, 2}
print(a ^ b)   # 対称差 {1, 2, 4}

# timeitの典型パターン
import timeit

setup = "data = list(range(100_000)); s = set(data); target = -1"
stmt1 = "target in data"
stmt2 = "target in s"

t1 = min(timeit.repeat(stmt1, setup=setup, repeat=5, number=3))
t2 = min(timeit.repeat(stmt2, setup=setup, repeat=5, number=3))
print(f"list in: {t1:.6f}s (best of 5)")
print(f"set  in: {t2:.6f}s (best of 5)")