Taming Floating-Point Sums | orlp.net
Suppose you have an array of floating-point numbers, and wish to sum them. You might naively think you can simply add them, e.g. in Rust: fn naive_sum(arr: &[f32]) -> f32 { let mut out = 0.0; for x in arr { out += *x; } out } This however can easily result in an arbitrarily large accumulated error. Let’s try it out: naive_sum(&vec![1.0; 1_000_000]) = 1000000.0 naive_sum(&vec![1.0; 10_000_000]) = 1
Zed Decoded: Rope & SumTree - Zed Blog
For this second post in Zed Decoded, our blog & video series in which we're taking a closer look at how Zed is built, I've talked to Zed's three co-founders — Nathan, Max, Antonio — about the data structure at the heart of Zed: the rope. Companion Video: Rope & SumTree This post comes with a 1hr companion video, in which Thorsten, Nathan, Antonio, and Max use Zed to look at how Zed uses the Rope a
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 batch. But I've spent the past month or so doing research and writing code, and it turns out that you can build a lot with just a few simple things! In this series, we'll learn what a CRDT is. Then we'll w
アルファ・ベータ法 - Wikipedia
アルファ・ベータ法（アルファ・ベータほう、alpha-beta pruning）は完全情報ゲームにおける探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部分を枝刈りしている。 擬似コード[編集] アルファ・ベータ法の擬似コードを以下に示す。alphabeta関数がアルゴリズムの実装であり、minimax関数はミニマックス法とインタフェースを揃えるためのラッパーである。 function minimax(node, depth) return alphabeta(node, depth, -∞, +∞) function alphabeta(node, depth, α, β) if node が終端ノード or depth = 0 return node の評価値 if node が自分のノード
Trying to invent a better substring search algorithm - moao's blog
To start, calculate the sum of the first window naively: First sum is 15. For the rest, reuse the previous sum, subtract the removed element and add the new one: Second = First + 6 - 0 = 21. Third = Second + 7 - 1 = 27. Fourth = Third + 8 - 2 = 33. Fifth = Fourth + 9 - 3 = 39. And so on... That's O(N) for all windows, and addition is, of course, fast as hell. The algorithm Let's preprocess the sum
Binary Trees To Hash Array Mapped Tries, Step by Step - Vaibhav Sagar
Binary Trees To Hash Array Mapped Tries, Step by Step Hash Array Mapped Tries (HAMTs) are a persistent data structure used to implement hashmaps. They’re heavily used in Clojure and used to be the backbone of Haskell’s aeson library until relatively recently. I’ve written about HAMTs before but wanted to try a different approach: starting with a binary tree (or something close to it) and then maki
1€ Filter
1€ Filter Géry Casiez1,2,3 Nicolas Roussel3 and Daniel Vogel4 1LIFL, 2University of Lille, 3Inria Lille and 4Cheriton School of Computer Science, University of Waterloo This page implements the "1€ Filter" in different languages. See our CHI 2012 paper (PDF). The name "1€" is an homage to the $1 recognizer. Algorithm1€ Links and Downloads Our CHI 2012 1€ paper (PDF) Data corresponding to figure 1
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
AlphaDev discovers faster sorting algorithms
Impact AlphaDev discovers faster sorting algorithms Published 7 June 2023 Authors Daniel J. Mankowitz and Andrea Michi New algorithms will transform the foundations of computing Digital society is driving increasing demand for computation, and energy use. For the last five decades, we relied on improvements in hardware to keep pace. But as microchips approach their physical limits, it’s critical t
Twitter's Recommendation Algorithm
Twitter aims to deliver you the best of what’s happening in the world right now. This requires a recommendation algorithm to distill the roughly 500 million Tweets posted daily down to a handful of top Tweets that ultimately show up on your device’s For You timeline. This blog is an introduction to how the algorithm selects Tweets for your timeline. Our recommendation system is composed of many in
Building a Fibonacci Heap — Kurt Lawrence
A Fibonacci heap is a heap data structure which leverages laziness to obtain a few favourable time complexities. A Fibonacci heap is used as a priority queue, usually used in graph algorithms to find the shortest path, such as A* or Dijkstra's algorithm. Compared to a binary heap, a Fibonacci heap has an amortised time complexity for inserts and key decreases of O(1) versus a binary heap's O(log n
The World's Smallest Hash Table | orlp.net
This December I once again did the Advent of Code, in Rust. If you are interested, my solutions are on Github. I wanted to highlight one particular solution to the day 2 problem as it is both optimized completely beyond the point of reason yet contains a useful technique. For simplicity we’re only going to do part 1 of the day 2 problem here, but the exact same techniques apply to part 2. We’re go
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Knuth–Morris–Pratt illustrated | Journal of Functional Programming | Cambridge Core
PentominoをBitboardを使って解く - すぎゃーんメモ
A Lock-Free Vector
What is HyperLogLog and how to build yours in Rust
Fast(er) binary search in Rust
Build your own CountMinSketch in Rust
Build your own Counting Bloom Filter in Rust
Surprising Weak-Ref Implementations: Swift, Obj-C, C++, Rust, and Vale