Fastest Branchless Binary Search | mhdm.dev
You’re a busy person so I’ll first jump right to it. Here it is, the fastest general (and simple) binary search C++ implementation: template <class ForwardIt, class T, class Compare> constexpr ForwardIt sb_lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp) { auto length = last - first; while (length > 0) { auto rem = length % 2; length /= 2; if (comp(first[length], value))
Pike VMとEarley法の関係についてRubyで実装して考えてみる | makenowjust-labs/blog
正規表現マッチングの実装手法の1つとしてPike VMと呼ばれるものがあります。 これはGo言語の正規表現実装やRustのregex crateで使われている手法であり、正規表現rrrと入力文字列wwwに対してO(∣r∣×∣w∣)O(|r| \times |w|)O(∣r∣×∣w∣)の計算量でマッチングができるのが特徴です。 Earley法はJay Earleyの提案した文脈自由文法 (CFG) の構文解析手法の1つです。 すべてのCFGを構文解析できる手法で最悪計算量はO(∣w∣3)O({|w|}^3)O(∣w∣3)ですが、無曖昧であればO(∣w∣2)O({|w|}^2)O(∣w∣2)で、決定的であればO(∣w∣)O({|w|})O(∣w∣)で構文解析ができます。 実装してみると分かりますが、Pike VMとEarley法には類似している点があり、Earley法をPike VMの発展系の
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
The e-graph data structure
Note: Forcing dark mode via a plugin will make some pictures ugly (ironic because I do this). Sorry. E-graphs are a cool data structure, but I think that what makes them cool also has the side effect of making them a little inscrutable. This is an e-graph. Does it confuse you? It certainly took me a long time before I understood one. My goal with this post is to Motivate two distinguishing feature
Hashing
This page makes heavy use of JavaScript to visualise the concepts discussed. Viewing it without JavaScript will be a strange experience, as the text talks about the visualisations. I strongly recommend either enabling JavaScript, or not wasting your time. As a programmer, you use hash functions every day. They're used in databases to optimise queries, they're used in data structures to make things
m2scorerを(100倍位)高速化してみた - 英語帝国を打倒しよう
まとめ 単語数をVとして、V^3からV^2ぐらいへ高速化した。 バグを見つけるなどして、定数倍の高速化にも努めた。 m2scorer_python3_fastで公開している。 m2scorerとは Grammalyのような、文法的に誤った文を文法的に正しい文に直すタスクがあり、文法誤り訂正(GEC)と呼ばれています。 M2(MaxMatch)とは文法誤り訂正の評価手法の一つです。提案されたのは少し古いのですが、CoNLL-2014と呼ばれるコンペの評価指標として採用されたこともあって、過去の実験と比較する時などには必ず用いられています。 M2はm2scorerというレポジトリでgithubに公開されています。 https://github.com/nusnlp/m2scorer 事の発端 国際学会への投稿を目指していたのですが、それにあたって大規模な実験を行う必要がありました。しかし、その
Text Editor Data Structures
Text editors can be an interesting challenge to program. The types of problems that text editors need to solve can range from trivial to mind-bogglingly difficult. Recently, I have been on something of a spiritual journey to rework some internal data structures in an editor I have been building, specifically the most fundamental data structure to any text editor: the text. Table of Contents Resour
Leo Robinovitch @ The Leo Zone
I implemented a simple hash table in C when solving a problem in CS Primer. Solving it helped me gain better intuition around hash functions, pointers, and memory segments like the stack and the heap. BasicsYou have probably encountered a hash table in the wild, like a dict in Python, map in Go, or Map in JavaScript. Hash tables associate a key with a value. Setting, looking up, and deleting value
Faster sorting algorithms discovered using deep reinforcement learning - Nature
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.
High-performance tidy trees visualization
NaiveTidyThis article introduces the algorithm to draw non-layered trees in linear time and re-layout partially when some nodes change in O(d) time, where d is the maximum depth of the changed node. The source code is available at zxch3n/tidy. It only takes a few milliseconds to finish the layout of a tree with tens of thousands of nodes within the web browser. IntroductionLayered and non-layeredA
Beautiful Branchless Binary Search
I read a blog post by Alex Muscar, “Beautiful Binary Search in D“. It describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search? So I did the work to translate it into a algorithm for C++ iterators, no longer requir
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
monics.tex
A minimal version of Yannakakis's algorithm for mostly plain Python
bfs 3.0: the fastest find yet! - tavianator.com
The Most Elegant Search Structure | (a,b)-trees
Can a Rubik's Cube be brute-forced?
GitHub - clibraries/array-algorithms: Unintrusive algorithms for C arrays OR a C implementation of <algorithm> from C++
【Rustで実装】Reed-Solomonをkurenaif先生が教えてくれるらしい #ch789
Exploring DeepMind's AlphaDev Breakthrough in Optimizing Sorting Algorithms
Modern perfect hashing for strings