cgiosy.dev

함수형 프로그래밍에서 반복문 대신 재귀를 쓸 때, 꼬리재귀 최적화가 없다면 메모리나 속도가 망하기 쉽다. 재귀 깊이 제한이 있다면 함수가 뻥뻥 터지기도 한다. 반복문으로 바꾸면 된다지만 썩 맘에 들지 않는 건 어쩔 수 없다. 함수형을 맛보기 좋은 걸로 알려진 JS에(정확히는 가장 널리 쓰이는 JS 엔진인 V8에) 이런 꼬리재귀 최적화가 없다는 건 상당히 이율배반적인 소리로 들린다. 때문에, 적절한 규격을 가진 재귀함수를 내부적으로 반복문처럼 처리하는 유틸리티 함수를 만들어볼 수 있다. 목표는 T(self => (n, acc = 0) => (n ? self(n - 1, acc + n) : acc))(100000000)을 했을 때 콜스택이 터지지 않고 잘 돌아가도록 T 함수를 만드는 것이다. const T ..

https://github.com/cgiosy/xxh32 JS 최적화 상식 정수 vs. 실수 JS는 기본적으로는 정수와 실수 구분이 없다. 사실상 모든 연산이 64비트 실수형 위에서 돌아간다고 보면 편하다. 그래도 비트 연산을 사용하면 32비트 정수라도 쓸 수 있게끔 되어 있다. 아래에서 두 번째가 첫 번째보다 두 배 가까이 빠르다. const N = 16384; const arr = new Uint32Array(N); for (let i = 0; i < N; i += 1) arr[i] = i; let s = 0; // Case #1 for (let i = 0; i < N; i += 1) s += arr[i] + 1; // Case #2 for (let i = 0; i < N; i = i + 1 | 0)..

작성자는 Recoil, Jotai, SolidJS, Preact 등 Signal과 비슷한 방식의 상태 관리 경험이 아주 적은 상태에서 본문을 작성하였음을 미리 알립니다. 상태들은 일반적으로 DAG 형태의 의존성으로 나타내지는데, 이를 명확하고 효율적으로 반응형답게 다루기 위한 패턴이다. Signal: 가장 기본적인 상태. Computed: 특정 Signal들에 기반해 계산되는 값. Effect: 특정 Signal들의 변화에 반응하는 함수. Wait: 특정 Effect들의 반응(실행) 시점을 미루는 기능. Batch: Wait에서 여러 Signal을 한꺼번에 바꾸기 편하게 약간 추상화된 형태. 여기에 비동기를 끼얹거나 DAG라는 점을 활용한 여러 응용이 있지만, 기본적인 상태와 연산들은 위와 같다. 런타임..

1000ms 주기로 count를 1씩 증가시키고 렌더링하면서, 그와 별개로 1200ms 주기로 count를 콘솔에 찍으려고 한다. 다음 코드를 보고 버그를 찾아보자. const useInterval = (fn, duration, deps = []) => { useEffect(() => { const timer = setInterval(fn, duration); return () => clearInterval(timer); }, deps); }; const Simple = () => { const [count, setCount] = useState(0); useInterval(() => { console.log(count); }, 1200, [count]); useInterval(() => { setCou..

최신 브라우저들에는 abort 메서드가 있는 AbortController와 상태를 전달받는 AbortSignal가 있으며, 이를 활용해 각종 객체에서 작업 중단 방식을 공통되게 작성 및 사용 가능하다. 예시로 알아보자. fetch 중단시키기 const controller = new AbortController(); setTimeout(() => controller.abort(), 100); try { await fetch("/api", { signal: controller.signal }); } catch (e) { console.log(e); } 꼬박꼬박 controller.를 붙여주는 이유는 abort 메서드가 this에 의존하기 때문이다. controller.를 생략하면 엉뚱한 값이 this가 되고..

처음으로 참가한 대학생 대회이자, 첫 팀 대회이자, 다른 PS러를 자의로(ㅋㅋ) 만난 첫 대회이다. 대회 직후에 바로 후기 써야지 했는데 힘들어서 다음 날로 미루고, 또 미루다가 이제서야 쓴다 ㅎㅎ; 기본적인 팀 설명 등은 지난 예선 후기에 작성했기 때문에 생략한다. 팀원인 주때의 후기도 함께 보면 좋을 듯. 팀노트 본선 대회를 하루 남겨둔 저녁, 위기감을 느낀 우리는 어떻게든 팀노트를 만들기 시작했다. 코드를 전부 우리가 다 짰으면 좋았겠지만, 팀노트는 한 페이지도 완성 안 돼있고 대회가 코앞인 상황에 그럴 시간은 없었다. 일단 예전에 짜둔 내 코드 30%, 주때의 작년 팀인 Longest path to WF의 팀노트, kactl에서 코드를 열심히 수혈받아왔다. 특히 출제자 목록을 보고 플로우는 꼭 넣..

아래에서 $N$은 테이블에 저장된 키 개수, $M$은 테이블 크기를 의미한다. $N$개의 키에 대한 해시값이 모두 $M$ 미만이고 distinct하다면, 즉 해시가 Perfect Hash Function이면 단순히 크기 $M$의 배열 각각에 키에 대한 값을 저장하면 된다. Perfect Hash Function을 사용하는 해시 테이블은 보통 FKS 해싱 기반인데, 이에 대해선 여기서 설명하지 않겠다. 그보단 대체로 xxHash나 wyhash처럼 매우 빠르며 충분히 랜덤함을 보장하는 해시 함수를 쓰게 된다. 문자열의 특정 부분만 뽑아 쓰는 해시도 있긴 한데, 이 글에선 해시 함수가 서로 다른 키에 대해 완전히 랜덤한 출력을 보장함을 가정한다. 생일 문제에 의해, $N = \sqrt{M}$ 정도만 돼도 테이..

어떤 집합에서 결합법칙을 만족하는 이항연산 $+$와 역연산 $-$가 있고, $f(x + y) = f(x) + f(y)$를 만족하는 함수 $f$가 있을 때, $f^n(x)$를 빠르게 계산할 수 있다면 길이 $N$의 문자열 $S$에 대해 $h = \sum_{k=1}^{N}{f^{N-k}(S[k])}$를 롤링 해시로 활용할 수 있다. $f(h) + S[N + 1]$로 뒤에 문자를 추가할 수 있고, $h - f^{N-1}(S[1])$로 앞에서 문자를 삭제할 수 있다. 당연히 중간에서 삭제 및 대체도 가능하지만, 앞뒤 추가 및 삭제에 비해 거의 안 쓰이는 편이다. 예시 위키피디아의 롤링 해시 문서에선 다음 두 가지 다항식 기반 롤링 해시를 소개한다. 다항식 롤링 해시 적당한 상수 $p$, $q$가 있을 때, mo..