Extremely Fast strstr-like Function: Home of Railgun_Quadruplet
Fastest strstr-like Function!? I've made a blend of the famous Karp-Rabin-Boyer-Moore-Horspool-Sunday algorithms named Railgun. When a needle is needed to be found in a haystack here comes the Railgun_Quadruplet - an extremely fast pattern searcher designed both for short(2bytes) and long(gigabytes) patterns/strings, to be replaced by Railgun_r8_Mimino_x64 hopefully this year. Until then the FASTE
最近点対問題の線形時間乱択アルゴリズム - うどん記
これは Competitive Programming Advent Calendar Div2013 の 20 日目の記事です．最近点対問題の話をします． 最近点対問題は，空間上に点の集合が与えられた時に，その中で最も距離が近いペアを探す問題です． 応用としては，何らかのオブジェクトを特徴ベクトルに写した後で，最も類似したペアを探したいときなどに役に立つのではないかと思います．競技プログラミング界では，今年のICPC会津大会で3次元上の最近点対問題が出題されました． 空間が平面のときは分割統治による $O(n\log{n})$ 時間アルゴリズムが有名かと思います．今回は一般の次元で，(ハッシュマップを用いて)線形時間で動く実装が楽そうな乱択アルゴリズムの紹介をします．参考にした文献は以下のサーベイです． Smid, Michiel. Closest point problems in c
Purely functional Dijkstra algorithm using priority search queue to find shortest paths
gistfile1.hs � � �� ��� �� -- % cabal install PSQueue -- % ghci Dijkstra.hs -- > dijkstra sample A -- [(A,0,A),(D,4,A),(E,7,D),(C,8,E),(B,9,E)] module Dijkstra where import Control.Applicative hiding (empty) import Data.List (unfoldr) import Data.Maybe (fromJust) import Data.PSQueue (PSQ, Binding(..)) import qualified Data.PSQueue as PSQ ------------------------------------------------------------
区間のk-th smallestが求められる謎データ構造 - 競技プログラミング+αなブログ
この記事は Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83) の16日目の記事です。 データ構造の話です。 地区予選の過去問を解いているときに、以下のような問題を見つけました。 【問題】 要素数Nの数列a(a[0],...,a[N-1])が与えられる。 以下の２種類からなるクエリがQ個与えられるので、それぞれ処理せよ。 ・Query1 l r k a[l],...,a[r-1]のk番目に小さい数は何か （1<=k<=r-l） ・Query2 l r x a[l],...,a[r-1]をソートしたとき、xは何番目か （x∈{a[l], ..., a[r]}） 【制約】 N<=10^5 Q<=10^5 0<=l 僕は解き方が
マニアック動的計画法特集 - めも帳
2013-12-12 マニアック動的計画法特集 この記事は Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83) の12日目の記事です。 マニアックな動的計画法(Dynamic Programming, 以下DPと表記)手法についての記事です。 「DP知ってるけど苦手だわ〜」って方は8日目の診断人さんの記事必見です！(http://d.hatena.ne.jp/shindannin/20131208/1386512864) 前書き DPとはなにか、一言でいうと「手法」だと思います。 二分探索や貪欲法と同じようにいろいろな問題に適用できる「手法」であり、 なにかひとつの「アルゴリズム」ではありません。 そういう訳
初心者の初心者による初心者のための典型segment tree - DEGwerのブログ
§0.はじめに この記事は、Competitive Programming Advent Calendar Div2013の11日目の記事として書かれたものです。この記事では、列に対して変な操作をして変なクエリがくる系の問題のsegment treeによる解法を説明します。 また、「初心者の初心者による初心者のための」と銘打っていますが、 segment treeとはどういうものか知っている 遅延更新のやり方が分かっている の2点を仮定します。前者が分からない人は蟻本、後者が分からない人はkyuridenamidaさんのこの記事(http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261)を見てください。 §1.segment treeとは何か まずsegment treeが何ができるデータ構造なのかを示します。segment treeと
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。 動的計画法(Dynamic Programming, DP)についての記事です。 12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました 12/11 前編の図２つを差し替えました。 はじめに まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
mrubyやKopiLuaにはなぜ文字連結用オペコードがあるの? ① (あるいはJavaの文字連結最適化について) - ほげほげにゃ
前置き 最近色々ありましてmrubyやKopiLua(C#によるLua実装)のソースコードを読んだりしております。 ちょうどVM部分を読んでいたら、面白い部分を見つけました。 mrubyのバイトコードにOP_STRCAT(文字連結)っていうのがあるのに驚いてたけど, LuaVM読んでたらOP_CONCATとかあったし文字連結系のオペコード用意するのって普通なんです…?— どみとり (@domitry) 2013, 12月 5 これまでx86のアセンブラしか読んだことがなかったので特殊かどうかよくわからない… そこでふとLL言語でない, 例えばJavaのVMはどうなってるんだろうなーと思い調べてみました。 昨日のお話、Javaのバイトコードを見てみたらstrcatやらconcatはなかった… キャストとかオブジェクト指向な要素(newとかclass method呼び出しとか)とかは含まれてた
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
Core algorithms deployed
Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashiona
Basic Data Structures and Algorithms in the Linux Kernel - The Phrygian Cap
Thanks to Vijay D'Silva's brilliant answer in cstheory.stackexchange.com I have been reading some of the famous data structures and algorithms used in the Linux Kernel. And so can you. Linked lists, doubly linked lists, lock-free linked lists.B+ Trees with comments telling you what you can't find in the textbooks.Priority sorted lists used for mutexes, drivers, etc.Red-Black trees are used are use
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
French Team Invents Faster Code-Breaking Algorithm – Communications of the ACM
Gagallium : Reconstructing the Knuth-Morris-Pratt algorithm
http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP01.pdf
http://ekmett.github.io/presentations/Cache-Oblivious%20Data%20Structures.pdf
Bandits and Stocks
jaspervdj - Picking a random element from a frequency list
http://whocouldthat.be/visualizing-string-matching/
http://www.siam.org/pdf/news/637.pdf
http://www.logos.ic.i.u-tokyo.ac.jp/~tau/lecture/software/