数独のアルゴリズムを考える ― 各種法の改善と高速化
数独を解くプログラムは多数ある中で、全ての問題を解けるアルゴリズムは意外と少ない。 そこで、どんなアルゴリズムが完全に解け、計算量が妥当なのかを考えてみることにしました。
For Algorithms, a Little Memory Outweighs a Lot of Time | Quanta Magazine
One July afternoon in 2024, Ryan Williams set out to prove himself wrong. Two months had passed since he’d hit upon a startling discovery about the relationship between time and memory in computing. It was a rough sketch of a mathematical proof that memory was more powerful than computer scientists believed: A small amount would be as helpful as a lot of time in all conceivable computations. That
A leap year check in three instructions
With the following code, we can check whether a year 0 ≤ y ≤ 102499 is a leap year with only about 3 CPU instructions: bool is_leap_year_fast(uint32_t y) { return ((y * 1073750999) & 3221352463) <= 126976; } How does this work? The answer is surprisingly complex. This article explains it, mostly to have some fun with bit-twiddling; at the end, I'll briefly discuss the practical use. This is how a
Reservoir Sampling
Reservoir sampling is a technique for selecting a fair random sample when you don't know the size of the set you're sampling from. By the end of this essay you will know: When you would need reservoir sampling. The mathematics behind how it works, using only basic operations: subtraction, multiplication, and division. No math notation, I promise. A simple way to implement reservoir sampling if you
Bloom filters - Eli Bendersky's website
The original motivation for the creation of Bloom filters is efficient set membership, using a probabilistic approach to significantly reduce the time and space required to reject items that are not members in a certain set. The data structure was proposed by Burton Bloom in a 1970 paper titled "Space/Time Trade-offs in Hash Coding with Allowable Errors". It's a good paper that's worth reading. Wh
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
p-fast trie: lexically ordered hash map – Tony Finch
Compressing Icelandic name declension patterns into a 3.27 kB trie
Algorithms for Modern Processor Architectures
Stepanov’s biggest blunder
People Keep Inventing Prolly Trees
The Interactive Handbook on Data Structures and Algorithms
https://codeforces.com/blog/entry/143279
oils.vim/doc/algorithms.md at main
Mixed Boolean-Arithmetic (Part 1): Introduction
Monte Carlo Tree Search - Computerphile
The radix 2^51 trick
Async from scratch 3: Pinned against the wall | natkr's ramblings
Functional hash tables explained — Spritely Institute
GitHub - Nicoshev/rapidhash: Very fast, high quality, platform-independent hashing algorithm.
#9 - Pathfinding - Deep Space Exploitation by JuhrJuhr