09 · 容器、哈希与顺序

# order.py —— 同一批元素，dict 和 set 的迭代顺序
items = ["banana", "apple", "cherry", "date", "elderberry"]

d = dict.fromkeys(items)          # 只借它的键
s = set(items)

print("放进去的顺序：", items)
print("dict 迭代出来：", list(d))
print("set  迭代出来：", list(s))
print()
print("dict 和插入序一致吗：", list(d) == items)
print("set  和插入序一致吗：", list(s) == items)

# crossproc.py —— 同一行代码，连跑 5 个进程，看 set 的迭代顺序变不变
import os
import subprocess
import sys

CODE = "print(list({'a', 'b', 'c', 'd'}))"

print("① 默认（哈希随机化开着）：")
for i in range(5):
    r = subprocess.run([sys.executable, "-c", CODE],
                       capture_output=True, text=True, encoding="utf-8")
    print("   ", r.stdout.strip())

print("\n② 钉死 PYTHONHASHSEED=0：")
env = dict(os.environ, PYTHONHASHSEED="0")
for i in range(5):
    r = subprocess.run([sys.executable, "-c", CODE], env=env,
                       capture_output=True, text=True, encoding="utf-8")
    print("   ", r.stdout.strip())

print("\n③ 换成整数元素（默认环境）：")
CODE_INT = "print(list({1, 2, 3, 4}))"
for i in range(5):
    r = subprocess.run([sys.executable, "-c", CODE_INT],
                       capture_output=True, text=True, encoding="utf-8")
    print("   ", r.stdout.strip())

print("\n④ 同一个进程里建 5 次（默认环境）：")
CODE_SAME = "print([list({'a','b','c','d'}) for _ in range(5)])"
r = subprocess.run([sys.executable, "-c", CODE_SAME],
                   capture_output=True, text=True, encoding="utf-8")
print("   ", r.stdout.strip())

print("\n⑤ hash('a') 在 5 个进程里：")
for i in range(5):
    r = subprocess.run([sys.executable, "-c", "print(hash('a'))"],
                       capture_output=True, text=True, encoding="utf-8")
    print("   ", r.stdout.strip())

# hashseed_late.py —— 在脚本里设 PYTHONHASHSEED，太晚了
import os
import subprocess
import sys

LATE = "import os; os.environ['PYTHONHASHSEED'] = '0'; print(hash('a'))"

print("① 脚本里 os.environ['PYTHONHASHSEED']='0' 之后 hash('a')：")
for _ in range(3):
    r = subprocess.run([sys.executable, "-c", LATE],
                       capture_output=True, text=True, encoding="utf-8")
    print("   ", r.stdout.strip())

print("② 解释器启动前就设好：")
env = dict(os.environ, PYTHONHASHSEED="0")        # ⭐ 传给子进程，启动时就在
for _ in range(3):
    r = subprocess.run([sys.executable, "-c", "print(hash('a'))"], env=env,
                       capture_output=True, text=True, encoding="utf-8")
    print("   ", r.stdout.strip())

# repro.py —— 种子全固定了，结果照样每次不同：因为中间遍历了一个 set
import os
import subprocess
import sys
import tempfile

SCRIPT = '''
import random

random.seed(42)                                   # 种子固定死了

feats = {"age", "income", "city", "clicks", "device", "tenure"}   # 一个 set
top3_bad  = [f for f in feats][:3]                # 直接遍历 set —— 不稳
top3_good = sorted(feats)[:3]                     # 先排序再取 —— 稳

print(round(random.random(), 6), "|", top3_bad, "|", top3_good)
'''

d = tempfile.mkdtemp()
path = os.path.join(d, "train.py")
with open(path, "w", encoding="utf-8") as fh:
    fh.write(SCRIPT)

print("random.random() | 直接遍历 set 取前3 | 先 sorted 再取前3")
for i in range(4):
    r = subprocess.run([sys.executable, path],
                       capture_output=True, text=True, encoding="utf-8")
    print(f"第 {i + 1} 次： {r.stdout.strip()}")

# setfix.py —— 集合运算的结果落地成「一串东西」时，三种写法
a = ["zeta", "yak", "xray", "wolf"]
b = ["yak"]

bad = list(set(a) - set(b))                # ❌ 顺序跨进程漂
ok = sorted(set(a) - set(b))               # ✅ 首选：确定、可读，一次 O(n log n)
keep = [x for x in a if x not in set(b)]   # ✅ 次选：想保留 a 的原始顺序时用

print("❌ list(set)  →", bad)
print("✅ sorted     →", ok)
print("✅ 保留原顺序 →", keep)

# key.py —— 什么能当 key，以及改了 key 之后会发生什么
class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __repr__(self):
        return f"Point({self.x}, {self.y})"

    def __eq__(self, other):
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        return hash((self.x, self.y))       # ⭐ 和 __eq__ 用同一批字段


# ① 列表不能当 key
try:
    {[1, 2]: "x"}
except TypeError as e:
    print("① 列表当 key：TypeError:", e)

# ② 元组可以 —— 但只在它内部全是不可变的时候
print("② 元组当 key：", {(1, 2): "ok"})
try:
    {(1, [2]): "x"}
except TypeError as e:
    print("   里面塞个列表：TypeError:", e)

# ③ 只定义 __eq__ 不定义 __hash__ → 类当场变成不可哈希
class OnlyEq:
    def __eq__(self, other):
        return True

try:
    {OnlyEq(): 1}
except TypeError as e:
    print("③ 只写 __eq__：TypeError:", e)

# ④ 改了 key 之后：东西还在，但找不回来了
p = Point(1, 2)
d = {p: "原点附近"}
print("\n④ 改 key 之前 d[p] =", d[p], "| hash =", hash(p) % 10007)

p.x = 99                                    # ⭐ 就改这一行
print("   改完 p =", p, "| hash =", hash(p) % 10007)
print("   p in d          →", p in d)
print("   Point(99,2) in d→", Point(99, 2) in d)
print("   Point(1,2)  in d→", Point(1, 2) in d)
print("   但它还在字典里 ：", list(d.items()))
print("   len(d) =", len(d))

# numkey.py —— hash 相等 + == 相等 ⇒ 字典认为是同一个 key
print("hash(1) == hash(1.0) == hash(True) →", hash(1) == hash(1.0) == hash(True))
print("1 == 1.0 == True                   →", 1 == 1.0 == True)

d = {1: "int", 1.0: "float", True: "bool"}
print("\n写下 {1:'int', 1.0:'float', True:'bool'}  实际得到 →", d)
print("len =", len(d), "| 留下来那个 key 的类型 =", type(list(d)[0]).__name__)

counts = {}
for x in [1, True, 1.0, 2, 2.0]:
    counts[x] = counts.get(x, 0) + 1
print("\n拿这 5 个值计数 →", counts)

# dictorder.py —— dict 的「插入序」保证到什么程度
from collections import OrderedDict

d = {"a": 1, "b": 2, "c": 3}

d["b"] = 99                                   # 改已有 key 的值
print("① 改值       →", list(d))

del d["a"]
d["a"] = 1                                    # 删掉再加回来
print("② 删了再加回 →", list(d))

print("③ dict 的 ==        不看顺序 →",
      {"x": 1, "y": 2} == {"y": 2, "x": 1})
print("④ OrderedDict 的 == 看  顺序 →",
      OrderedDict(x=1, y=2) == OrderedDict(y=2, x=1))

print("\n⑤ frozenset 能当 key：", {frozenset({1, 2}): "ok"})
try:
    {{1, 2}: "x"}
except TypeError as e:
    print("   set 不能当 key：TypeError:", e)

# perf.py —— 复杂度不是理论：把「x in 容器」和「往头部插」量出来
import random
import timeit
from collections import deque

for n in (1_000, 10_000, 100_000):
    data = list(range(n))
    random.shuffle(data)
    lst, st = data, set(data)
    target = -1                                   # ⭐ 不存在 → 逼 list 走完全程

    t_list = timeit.timeit(lambda: target in lst, number=200) / 200
    t_set = timeit.timeit(lambda: target in st, number=200) / 200
    print(f"n={n:>7,}  x in list = {t_list * 1e6:9.2f} us   "
          f"x in set = {t_set * 1e6:6.3f} us   "
          f"倍数 = {t_list / t_set:8.0f}x")

print()
for n in (10_000, 50_000):
    t_list = timeit.timeit("l.insert(0, 1)",
                           setup=f"l = list(range({n}))", number=20_000) / 20_000
    t_deq = timeit.timeit("d.appendleft(1)",
                          setup="from collections import deque; "
                                f"d = deque(range({n}))", number=20_000) / 20_000
    print(f"n={n:>7,}  list.insert(0,x) = {t_list * 1e6:7.2f} us   "
          f"deque.appendleft(x) = {t_deq * 1e6:5.3f} us   "
          f"倍数 = {t_list / t_deq:6.0f}x")

print("\n（deque 只是为了对比才 import 的：", deque([1, 2]), "）")

# lookup.py —— 把「被查的那一侧」先转成 set
import time

big = list(range(20_000))
other = list(range(10_000, 30_000))

t0 = time.perf_counter()
bad = [x for x in big if x in other]              # ❌ 每个 x 都扫一遍 other
t1 = time.perf_counter()

lookup = set(other)                               # ⭐ 提到循环外面，只转一次
good = [x for x in big if x in lookup]            # ✅
t2 = time.perf_counter()

print("结果一样吗：", bad == good, "| 命中", len(good), "个")
print(f"❌ x in list ： {t1 - t0:7.4f} s")
print(f"✅ x in set  ： {t2 - t1:7.4f} s   快 {(t1 - t0) / (t2 - t1):.0f}x")

# coll.py —— defaultdict / Counter / deque 各替掉了哪几行样板代码
from collections import Counter, defaultdict, deque

rows = [("cat", 3), ("dog", 1), ("cat", 5), ("bird", 2), ("dog", 4), ("cat", 1)]

# ① 分组：手写 vs defaultdict
plain = {}
for k, v in rows:
    if k not in plain:                            # ⭐ 这两行就是 defaultdict 干掉的
        plain[k] = []
    plain[k].append(v)

dd = defaultdict(list)
for k, v in rows:
    dd[k].append(v)                               # ⭐ 一行

print("① 手写      ：", plain)
print("   defaultdict：", dict(dd), "| 一样吗：", plain == dict(dd))

# ⚠️ defaultdict 的坑：只是"读"一下也会把 key 建出来
print("   len 之前 =", len(dd), "| 读一个不存在的 key:", dd["fish"],
      "→ len 之后 =", len(dd))
print("   稳的读法 dd.get('snake') =", dd.get("snake"), "| len =", len(dd))

# ② 计数
c = Counter(k for k, _ in rows)
print("\n② Counter   ：", c)
print("   most_common(2) =", c.most_common(2))
print("   不存在的 key   =", c["fish"], "| 查完 len =", len(c), "（不新建）")
print("   相加 =", c + Counter({"cat": 10}))
print("   相减 =", c - Counter({"cat": 10}))      # ⚠️ 负数和零会被丢掉

# ③ deque：定长滑动窗口
print("\n③ deque(maxlen=3) 当滑动窗口：")
window = deque(maxlen=3)
for loss in [0.9, 0.7, 0.55, 0.51, 0.50]:
    window.append(loss)                           # ⭐ 满了自动挤掉最老的
    print(f"   加入 {loss} → 窗口 {list(window)}  近3步均值 "
          f"{sum(window) / len(window):.4f}")

d = deque([1, 2, 3])
d.appendleft(0)
d.rotate(1)
print("   appendleft + rotate(1) →", list(d))