再帰的な構造のデータの同値性判定はどうしたらいいか - 貳佰伍拾陸夜日記
数日前にTwitterで, JavaScriptのオブジェクトに対する===の挙動が初心者には難しいみたいな話を見かけた. 発端や周辺の議論をちゃんと追いかけてないからとくに出典は貼らない. たぶん元々の話は「へぇ, こういう挙動なんだ, 簡単ではないね」くらいの話だったのかもしれない. 自分のタイムラインの観測範囲では「そうだそうだ, (参照の同一性ではなく)同値性にしとけばいいのに」と思っている人もそれなりにいそうに見えた. 個人的にも同値性が簡単に確認できるとよい気はするものの, 「なんでそうしないんだ, オブジェクトの中身を確認していくだけだろ!」みたいな簡単な話ではないことも知っているため, 以下のようなツイートをしたのだった. JavaScriptのオブジェクトの同値性、再帰的な構造とか作るとぜんぜん自明じゃないんだよなぁ。リンクの構造は違うけどプロパティを辿ったときのパスはど
The Beauty of Bézier Curves
Bézier curves - how do they do? They're used for animation, text rendering, and all sorts of curved shapes! But how do they actually work? well, like, that's what the video is about, so, watch it to find out etc!! • Lots of love to 💛 Jazz "queenjazz" Mickle for making the music ❱ https://queenjazz.bandcamp.com/ 💙 Grant "3Blue1Brown" Sanderson for pushing me to finally do this ❱ https://youtub
Speeding up `atan2f` by 50x
2021-08-16 Speeding up atan2f by 50x \mathrm{atan2} is an important but slow trigonometric function. However, if we’re working with batches of points and willing to live with tiny errors, we can produce an \mathrm{atan2} approximation which is 50 times faster than the standard version provided by glibc. Perhaps more impressively, the approximation produces a result every 2 clock cycles. This is ac
B-Trees: More Than I Thought I'd Want to Know
Recently, I’ve been reading through the excellent Database Internals (Alex Petrov, 2019). The first half of the book is dedicated to the implementation of database storage engines – the subsystem(s) of a DBMS that handles long-term persistence of data. A surprising amount of this section discusses the implementation and optimization of various B-Tree data structures. In my college Data Structures
Chronofold: a data structure for versioned text
Chronofold is a replicated data structure for versioned text. It is designed for use in collaborative editors and revision control systems. Past models of this kind either retrofitted local linear orders to a distributed system (the OT approach) or employed distributed data models locally (the CRDT approach). That caused either extreme fragility in a distributed setting or egregious overheads in l
CRDTs go brrr
5000x faster CRDTs: An Adventure in Optimization July 31 2021 A few years ago I was really bothered by an academic paper. Some researchers in France put together a comparison showing lots of ways you could implement realtime collaborative editing (like Google Docs). They implemented lots of algorithms - CRDTs and OT algorithms and stuff. And they benchmarked them all to see how they perform. (Cool
The patience diff algorithm – The If Works
If you enjoy this article, I have published a book explaining the internals of Git through implementation: Building Git. — Previously in this series, we explored the Myers diff algorithm, we learned a variation of it that uses linear space, then we saw how to use a diff algorithm to build three-way merge, and most recently we examined why merges fail and what can be done about it. In particular, w
Ribbon filter: practically smaller than Bloom and Xor
Filter data structures over-approximate a set of hashable keys, i.e. set membership queries may incorrectly come out positive. A filter with false positive rate $f \in (0,1]$ is known to require $\ge \log_2(1/f)$ bits per key. At least for larger $f \ge 2^{-4}$, existing practical filters require a space overhead of at least 20% with respect to this information-theoretic bound. We introduce the Ri
Introduction to Locality-Sensitive Hashing
Tyler Neylon — (Got a machine learning project? Email me: tyler@unboxresearch.com) [Formats: html | pdf | kindle pdf] Locality-sensitive hashing (LSH) is a set of techniques that dramatically speed up search-for-neighbors or near-duplication detection on data. These techniques can be used, for example, to filter out duplicates of scraped web pages at an impressive speed, or to perform near-constan
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
Binary search with modern processors
第16回 StringBeginners での発表資料
optimizing hashmaps even more
optimizing hashmaps even more — 2021-05-08 hashmaps and hashing algorithms enums as keys static strings as keys hybrid static + dynamic keys looking ahead conclusion In our last post we took a look at possible ways we could improve the ergonomics of Rust's refcounting APIs. In this post we'll be looking at Hashmap: how it's currently implemented, how we could optimize it further, and finally direc
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://dl.acm.org/doi/pdf/10.1145/3473596
Karatsuba's Multiplication Trick Summarised in 1 Minute
btree/PATH_HINT.md at master · tidwall/btree
GitHub - sweeneyde/multimerge: A faster multi-way merge algorithm interchangeable with heapq.merge
Shift-based DFAs
GitHub - hyperpape/needle: Compiling string matching algorithms and regular expressions to java bytecode
Verkle trees
Constant-Time Big Numbers: An Introduction - Cronokirby