https://learning.oreilly.com/library/view/high-performance-python/9781492055013/
List와 tuple은 array와 유사하다. 사실 list는 mutable한 array이고, tuple은 immutable한 array라고 볼 수 있다.
실제 데이터는 int-ptr로 되어있기 때문에 vectorizing이 필요하면 numpy등을 이용해야함.
tuple은 데이터가 immutable하다. 그래서 복사할 때 reference만을 가져간다. 짜피 값이 바뀔 일이 없으니까. 하지만 list는 값이 바뀔 수 있기 때문에 매번 전체를 복사한다.
사실상 Hashmap. InsertID = hash값 & bitmask (사이즈 땜에)
__hash__로 1차 검증을 하고__cmp__ 또는 __eq__ 로 값이 맞는지 더블체크. 만약 값이 있다면 probing을 해야하는데, 이 경우 higher-order bit (가능한 비트열에서 최상위 비트)을 +1 하는 방식으로 진행 (최대한 안겹치게 하기 위하여 ⇒ 사실 의미 있는지 모르겠음... 해시 자체가 충분히 random할텐데 최상위 비트나 최하단 비트나 다를게 있을까?)
삭제를 한다면 arr의 값을 null로 표기하는 대신 "deleted" 등의 특수 플레그로 설정함 (cpython→dictobject에 구현되어 있는거 봤는데,,, 이름이 기억안나서 deleted라고 일단 붙임) 바로 null을 넣으면 probing시에 "여기까지 왔는데 없으니 끝내야지" 할 수도 있기 때문. deleted 칸은 추후 재사용 가능함.
resize는 insert시에만 발생함. 크기는 커질 수 도 있고, 작아질 수도 있음.
import math
from math import sin
def test1(x):
"""
>>> %timeit test1(123_456)
162 µs ± 3.82 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
"""
res = 1
for _ in range(1000):
res += math.sin(x)
return res
def test2(x):
"""
>>> %timeit test2(123_456)
124 µs ± 6.77 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
"""
res = 1
for _ in range(1000):
res += sin(x)
return res
def test3(x, sin=math.sin):
"""
>>> %timeit test3(123_456)
105 µs ± 3.35 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
"""
res = 1
for _ in range(1000):
res += sin(x)
return res
<aside> 1️⃣ global 조회 → math 조회 → sin 발견후 호출
</aside>
<aside> 2️⃣ global조회 → sin 발견후 호출
</aside>
<aside> 3️⃣ local namespace에 sin이 있어서 바로 호출
</aside>
trie 와 DAWGs 찾아볼것. trie는 tree를 이용해서 텍스트를 저장하는것 같고 DAWGs는 DFA(결정적 유한 오토마타)를 만들어서 입력값이 있는지 검증하는 시스템 같음.
