JOI夏季セミナー2023 全体講演会1の講演資料です。 【講義題目】 メタヒューリスティクスで広がる「解けた！」の世界 【講義概要】 世の中には，まだ効率的に解く方法が見つかっていない難しい問題がたくさんあります．こうした問題に立ち向かうときに頼りになるのが，メタヒューリスティクスと呼…
メタヒューリスティクスで広がる「解けた！」の世界
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
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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Merkle trees and build systems [LWN.net]
グラフアルゴリズム実践活用術
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
