An Interactive Intro to CRDTs | jakelazaroff.com
Have you heard about CRDTs and wondered what they are? Maybe you’ve looked into them a bit, but ran into a wall of academic papers and math jargon? That was me before I started my Recurse Center The Recurse Center The Recurse Center is a self-directed, community-driven educational retreat for programmers in New York City. www.recurse.com/ batch. But I’ve spent the past month or so doing research a
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ | mond
MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ 端的に言うと性能が良いからです。 これを理解するにはバッファプールへの理解が必要です。ディスク指向のデータベースの上では有限のメモリを最大限活用することでメモリに入り切らない巨大なデータ群に対して良好な参照性能を出す必要があります。バッファプールとはディスク上のデータの羅列を固定サイズのページ（InnoDBの場合16KB）の羅列であるとして読み書きに必要な分だけをメモリに移し取り複数の書き込みをできる限りメモリ内で受け止めて後でまとめてディスクに書き戻すという、ライトバック型のキャッシュのような機構です。 この中においてバッファプールは有限のサイズしか無いので適宜プール内のデータを書き戻して入れ替えながら上手くやっていく必要があります。 さてB+treeとB-treeの最大の違いは木のリ
入門 B-link tree
概要 DBMS で広く利用されている B+ tree には様々な variant が存在するが、B-link tree もその1つ。 シンプルなラッチプロトコルで並行アクセスをさばけるよう、リーフノード以外のノードにも右の隣接ノードへのポインタを持たせた構造となっており、PostgreSQL で使われていることでも有名。 この記事では主にこの B-link tree に焦点を当てる。 B+ tree 全般やその他インデックス技術自体に興味がある場合は「最強DB講義 #10 いまどきのデータベース索引技術（石川佳治 教授）」の講義資料を読むのがおすすめ。 B-link tree 理解する上で必須な知識「ラッチ」 「ラッチ」というのはいわゆるロックのことだが、DB においては「ロック」というとトランザクション分離のための高価な(数千CPUサイクルを要する)処理を指すことが多く、「ラッチ」という
C++の高速なハッシュテーブルの実装を読んだ (ankerl::unordered_dense) - Qiita
m_bucketsがハッシュテーブルの管理データで、m_valuesが格納した要素の配列。 m_valuesは全要素が隙間なく詰められていて、イテレートする際はここを直接走査する。 dist_and_fingerprintは、名前の通り2つの値が一つの変数にパックされている。 この工夫で、いろいろと効率よく処理できる(後述) 上位3バイト: dist ハッシュ関数で求めた位置から、実際に要素が格納されている位置までの距離 基本アルゴリズムの解説でProbe Sequence Lengthと呼ばれているものと同じ 1から数えるので注意。つまりdist == 1ならハッシュ関数で求めた位置と実際に格納されている位置が等しい 下位1バイト: fingerprint ハッシュ値の下位1バイトを格納 dist_and_fingerprint == 0の場合はEmpty(その位置に要素が格納されていな
Why and How Does Python Use Bloom Filters in String Processing?
In our last discussion we learned all about bloom filters. It’s a unique data structure that provides membership queries in constant time while using a minimal quantity of memory. Primarily, you will find them being used in large scale and streaming applications where it is infeasible to keep all the data in memory. Examples include NoSQL databases, CDNs, load balancers, etc. However, it also has
Sparse sets
A sparse set is a simple data structure that has a few interesting properties: O(1) to add an item. O(1) to remove an item. O(1) to lookup an item. O(1) to clear the set. O(n) to iterate over the set. A set does not require its internal items storage to be initialised upon creation (!). Sparse sets are commonly used to implement Entity Component System architectural pattern. I plan to cover ECS in
Bitwise Binary Search: Elegant and Fast | orlp.net
I recently read the article Beautiful Branchless Binary Search by Malte Skarupke. In it they discuss the merits of the following snippet of C++ code implementing a binary search: template<typename It, typename T, typename Cmp> It lower_bound_skarupke(It begin, It end, const T& value, Cmp comp) { size_t length = end - begin; if (length == 0) return end; size_t step = bit_floor(length); if (step !=
メタヒューリスティクスで広がる「解けた！」の世界
JOI夏季セミナー2023 全体講演会1の講演資料です。 【講義題目】 メタヒューリスティクスで広がる「解けた！」の世界 【講義概要】 世の中には，まだ効率的に解く方法が見つかっていない難しい問題がたくさんあります．こうした問題に立ち向かうときに頼りになるのが，メタヒューリスティクスと呼…
GitHub - orlp/polymur-hash: The PolymurHash universal hash function.
PolymurHash is a 64-bit universal hash function designed for use in hash tables. It has a couple desirable properties: It is mathematically proven to have a statistically low collision rate. When initialized with an independently chosen random seed, for any distinct pair of inputs m and m' of up to n bytes the probability that h(m) = h(m') is at most n * 2^-60.2. This is known as an almost-univers
Fantastic Learning Resources
Fantastic Learning Resources Aug 6, 2023 People sometimes ask me: “Alex, how do I learn X?”. This article is a compilation of advice I usually give. This is “things that worked for me” rather than “the most awesome things on earth”. I do consider every item on the list to be fantastic though, and I am forever grateful to people putting these resources together. Learning to Code I don’t think I hav
Algorithm Repository
This page provides a comprehensive collection of algorithm implementations for seventy-five of the most fundamental problems in combinatorial algorithms. The problem taxonomy, implementations, and supporting material are all drawn from my book The Algorithm Design Manual. Since the practical person is more often looking for a program than an algorithm, we provide pointers to solid implementations
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
"New algorithms for collaborative text editing" by Martin Kleppmann (Strange Loop 2023)
https://nomad.foo/blog/cola
[0.0, 1.0) の乱数を得るための“本当の”方法
https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3172
グラフを用いた近似最近傍探索の理論と応用
dbs-028.dvi
Talks -Algorithmic ideas, engineering tricks, and trivia behind CPython's new sorting algorithm
Merkle trees and build systems
グラフアルゴリズム実践活用術
