Writing a damn fast hash table with tiny memory footprints - Carpe diem (Felix's blog)
Hash table is probably the most commonly used data structure in software industry. Most implementations focus on its speed instead of memory usage, yet small memory footprint has significant impact on large in-memory tables and database hash indexes. In this post, I”ll provide a step by step guide for writing a modern hash table that optimize for both speed and memory efficiency. I’ll also give so
Rustでグラフを表現するにはTyped Arenaが便利 - 簡潔なQ
概要: Rustでグラフのように相互参照を含むデータ構造を表現するには、Typed Arenaという方法が適している。これについて説明する 整数による表現 グラフの表現方法で、最も簡単なのは、ノードを整数で表し、グラフのデータを別に持つ方法である。 fn main() { let mut edges = vec![vec![]]; edges[0].push(0); edges.push(vec![]); edges[1].push(0); } これは大抵どんな言語でも同じように使えるし、場合によってはこちらで済ませてしまったほうが簡単かもしれない。特に競技プログラミングではノードに付与されている情報が少なかったり、ノードに明示的に整数が付番されていたりするため、ほとんどの場合整数で表現するほうが扱いやすい。 しかしこの方法では、整数とグラフデータとの対応関係を見失いやすいと考えられる。整
chokudaiサーチ(ビームサーチ亜種)の利点の話 - chokudaiのブログ
たまには技術ネタを。やたら要望が多いので。 最後の「多様性って何？」が本番です。ここの説明さえできればいいなって思ってました。実装の話まで行こうかと思ったけど、長くなるから要望があれば、って感じで。 貪欲法とは？ 多分分かる人しか読まないのでざっくり。 現在の状態から、１手先だけを探索し、もっとも評価が上がる１手を選んで状態を更新する、というアルゴリズムです。 ビームサーチとは？ ビームサーチでは、「１手先のみ」という条件は変わりません。変わるのは、保持する状態の数です。 ビーム幅Kのビームサーチは、現在持っているK個以下の状態から、１手先だけを探索し、評価値で上からK個の状態を、次の状態として保持する、という感じです。 当然、K＝１の時は、貪欲法と同じ結果になります。 貪欲法である程度良い解が出せるが、最適な解が出せない、というような問題に対し、手軽により良い解を見つけることが出来ます。
I Wrote The Fastest Hashtable
I had to get there eventually. I had a blog post called “I Wrote a Fast Hashtable” and another blog post called “I Wrote a Faster Hashtable.” Now I finally wrote the fastest hashtable. And by that I mean that I have the fastest lookups of any hashtable I could find, while my inserts and erases are also really fast. (but not the fastest) The trick is to use Robin Hood hashing with an upper limit on
The Algorithms Behind Probabilistic Programming
We recently introduced our report on probabilistic programming. The accompanying prototype allows you to explore the past and future of the New York residential real estate market. This post gives a feel for the content in our report by introducing the algorithms and technology that make probabilistic programming possible. We’ll dive even deeper into these algorithms in conversation with the Stan
競技プログラミングにおけるゲーム木探索の面白さ - Qiita
フューチャーアーキテクト Advent Calendar 2016の21日目1の記事です。 競技プログラミングにおける、所謂ゲームAI系の長期コンテストについて書きます。 また、巷でよく聞く「競技プログラミングって仕事で役に立つんですか？」について、最後に少し触れます。 ゲームAIは面白そうだけど敷居が高いと感じるあなたへ 本記事は、ゲームAIコンテストがどんなものかなんとなく知っている、けどちゃんと取り組んだことが無いという人に向けた記事です。「初耳なんですが…」という方は、下記の素晴らしい記事を一読下さい。 強くなるためのプログラミング -様々なプログラミングコンテストとそのはじめ方- by ぴよぴよ.py ゲームAIコンテストのすすめ by iwashi31’s diary なお、本記事ではサンプルコードをjava2で記載します。忙しいあなたも本記事のコードをコピー&ペースト、自分な
Push-Relabel による最大フローアルゴリズム - 宇宙ツイッタラーXの憂鬱
はじめに この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの23日目の記事として書かれました。 最初に、一般的なフローネットワークについて触れてます。これは始点と終点を除く頂点について、入ってくるフローと出ていくフローが常に等しい状態であるもので、Ford-Fulkerson 法などを理解するために必要です。最小カット最大フローの定理についても触れます。 次に、条件を緩和して過剰フローを許したプリフローについて考えます。高さ関数制約を導入してプッシュ操作と再ラベル操作を定め、Generic-Push-Relabel のアルゴリズムを考えます。プリフローネットワークに対して処理をしていくと最終的に最大フローが得られることを確認し、再ラベル操作、飽和プッシュ操作、非飽和プッシュ操作の回数の上界を調べます。 さら
K問題：Black and White Boxes - tshitaの備忘録Ⅱ
1. 概要 これは Competitive Programming （その2） Advent Calendar 2016 - Adventar の22日目の記事です． 今年のACM-ICPC 2016アジア地区つくば大会のK問題で組合せゲーム理論に関する問題が出題されました．この問題を通して組合せゲーム理論の紹介をします (考察が中途半端になってしまいました)． 2017年1月5日に追記・修正しました． 解説等は公開されています． 問題 ： Problem K : Black and White Boxes 判定データ ： http://icpc.iisf.or.jp/past-icpc/regional2016/judge-data/K/ 講評 ： http://icpc.iisf.or.jp/past-icpc/comments/2016.pdf#page=5 講評スライド ： htt
桁DP入門 - ペケンペイのブログ
$A$ 以下の非負整数のうち「3の倍数または3の付く」かつ「8の倍数でない」数がいくつあるか求めてみよう。でもいきなりこの問題を解くのは難しいと思うので、 $A$ 以下の非負整数の総数を求める $A$ 以下の非負整数のうち、3の付く数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」の数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める という4つの問題を順に解くことにしよう。 A以下の非負整数の総数を求める 左から順に数字を決めていこう。 左から 4175 と決めたあとの状況を考えてみる。 ? に入りうる数字は何だろう。これは 0 から 9 のどれでもいい。上から 2 桁目が $A$ より小さいので ? に何を選んでも $A$ 以上にはならないからだ。次の場合はどうだろう。 この場合 ? に入りうるのは 0
高速なキューを作る話（後編） - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 前編の続きです。前編ではChan.Unagiには以下の欠点があることを解説しました。 読み出しを行うスレッドに対する非同期例外の扱いが面倒 データがすぐにGCされない 後編では、Chan.Unagiの欠点を克服したキューを作るやり方について解説します。 不要になったデータをGCできるようにする まずは簡単な方から解決していきましょう。 Chan.Unagiで読み出し終わったデータをMutableArrayから削除できないのは、Chan.Unagiがチャネル（書き込まれた値を複数のキューに書き込まれたかのように読み出す機能を持つ）であるた
Skip Lists: Done Right ·
Warning: This is the blog I wrote as a kid. Most of what is written here is probably wrong. Sat, Sep 17, 2016 What is a skip list? In short, skip lists are a linked-list-like structure which allows for fast search. It consists of a base list holding the elements, together with a tower of lists maintaining a linked hierarchy of subsequences, each skipping over fewer elements. Skip list is a wonderf
高速なキューを作る話（前編） - Qiita
私が以前Haskellで作成した（割と自己満足な）kazura-queueという比較的高速なキューのライブラリがあります。 このライブラリを作るときに考えたアレコレを書いてみたいと思います。 前提 ここでいうキューって何？ データ構造としてのキュー（Sequenceみたいな）や分散処理用のキュー？（RabbitMQみたいな）ではなく、並行処理のためにスレッド間の部品として使うようなキュー（Chan（やTQueueやTChan）みたいな）を意図しています。 ここではChanが持っているキューとしての性質をざっと書き出してみましょう。 キューに入るデータの型は任意 Chan aという型で表現できる範囲で好きなデータを入れることができる。 FIFO キューなのだから当たり前といえば当たり前かもしれませんが一応。 スレッドセーフ 複数のスレッドが同時に書き込もうとしても問題が起きない。1 複数のス
セグメント木をあきらめた人のための平方分割 - くじらにっき++
この記事はCompetitive Programming Advent Calendar 2016（その2）の12月15日の記事です。 www.adventar.org はじめに 基本事項 1点に対する変更クエリ・区間に対する質問クエリ Range Sum Query Range Minimum Query 区間に対する変更クエリ・1点に対する質問クエリ Range Add Query Range Update Query 区間に対する変更クエリ・区間に対する質問クエリ RSQ and RAQ RMQ and RUQ 応用例 Flipping Parentheses セグメントツリーにチャレンジしたくなったら 謝辞 はじめに 私はRMQのような典型的なセグメント木までは比較的容易に実装できるのですが，それよりも難しいクエリに対応したセグメント木を書くのは難しく感じています。とはいえ「区間に
データ構造と代数構造 - koba-e964の日記
この記事は、Competitive Programming Advent Calendar 2016 - Adventarの15日目の記事です。 この記事について 去年(2015年)の12月ごろ、「セグメント木が任意のモノイドに対して使えるという(当たり前のことが)明示的に書かれた日本語の記事がないなぁ」と思い、「(当時)来年のAdvent Calendarあたりに書こうか」と思ったので書きました。その後調べてみましたが、どうやらこの1年(2015年12月-2016年12月)で割と書かれたようでした。(この記事の意味とは…) 前述のように多数の記事がこの1年間で出たので、この記事は主にそれらへのリンクを貼り、場合によってコードを紹介することにします。 データ構造と代数構造 セグメント木 <=> モノイド 集合M、Mの要素eとその上の二項演算*があり、*が e * x = x * e = x
データ構造と代数(後編)
この記事はIS17er Advent Calendar 2016の13日目の記事です． 前日の記事データ構造と代数(前編)に対応した後編となっています． Segment tree(つづき) 区間更新，区間畳み込み 最後は区間更新と区間での演算の畳み込みの両方をサポートするタイプです． 例としては，区間に一様に一次関数の作用ができて，かつ区間での最小値も求めたいなどです． 区間での畳み込み単体，区間での更新単体は既に扱ったので，あとはそれらをどううまく組み合わせるかを考えます． 畳み込みを計算するための内部二分木，作用を記録する内部二分木の両方は当然必要で，その2つをうまく同期させなければなりません． 考えねばならないのは，作用を記録する木から畳み込み用の木への影響で， つまり作用クエリが来た時には畳み込み用の木もよしなに(高速に)変更できなければなりません． 例えば，あるノードが対応づいて
データ構造と代数(前編)
この記事はIS17er Advent Calendar 2016の12日目の記事です． この記事では，データ列の連続部分列に対するクエリを扱う基本的なデータ構造についての代数的なお話をします． 具体的には， Segment tree Fenwick tree(Binary indexd tree) Sparse table の3つについて扱います． この並びでお気づきの方もいらっしゃるかもしれませんが，自分がプログラミングコンテストチャンレジブックを読み進めながら思ったことを整理して書き下したものとなっています． 記事の半分以上はこの記事の充実のために新規に学んだものが占めており，素人の学習日記のような側面もあり簡潔さに欠けるので，ぜひデータ構造と代数構造 - koba-e964の日記も読まれることをおすすめします． はじめに 扱うトピックの関係上データ構造はわかるが代数には馴染みがないと
I've been writing ring buffers wrong all these years
So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure. It was just surprisingly annoying to write, due to reasons we'll get to in a bit. After giving it a bit of thought, I realized I'd always been writing ring buffers "wrong", and there was a better way. Array + two indices There are two common ways of implementing a queue w
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
100 days of algorithms – Medium
An Analysis of Skip Lists
Implement a faster sort algorithm · Pull Request #38192 · rust-lang/rust
