Rational を10進小数展開するアルゴリズムを実装した - mrkn 記
CRuby の Feature #8850 で提案されている Rational を10進小数展開する機能を実装してみた。 循環節の検出は、セルオートマトンの周期解を検出するときに使った手法を応用した。 この手法では、1桁ずつの展開 (標準展開) と2桁ずつの展開 (倍速展開) を同時に進め、両者の状態 (剰余) が等しくなったときに循環を見付けたことになる。 標準展開の末尾の位置と倍速展開の末尾の位置の差が循環節の長さに一致する。 循環節の先頭位置を見付けるには、標準展開と倍速展開のそれぞれの末尾から1桁ずつ前に戻りながら桁の値を比較していけば良い。 たとえば、循環を検出した時点で以下のような小数展開が得られたとしよう。 123.4567891357924680123450987613579246801234 ^ 標準展開の末尾 ^ 倍速展開の末尾 標準展開の末尾と倍速展開の末尾にあるカー
When Random Isn't Random Enough: Lessons from an Online Poker Exploit - Laura Diane Hamilton
When Random Isn't Random Enough: Lessons from an Online Poker Exploit Today I am going to retell a story from 1999, a story in which developers of a popular online poker platform implemented card-shuffling software with a handle of subtle but critical bugs. Image credit: David Wells on Flickr Although this story is 15 years old, the lessons it holds for algorithm developers are still relevant. It'
完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。
「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei
「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。 何故、木構造が自然数の重複あり集合で表現
Introduction to Octrees
What exactly is an Octree? If you're completely unfamiliar with them, I recommend reading the Wikipedia article (read time: ~5 minutes). This is a sufficient description of what it is but is barely enough to give any ideas on what it's used for and how to actually implement one. In this article, I will do my best to take you through the steps necessary to create an octree data structure through co
2013年度の文法圧縮の進展 - Yasuo Tabeiの日記
年が明けて2014年の１月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。 はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表現する小さいCFGを構築する圧縮方式です. ゲノム配列, バージョン管理されたテキスト, リポジトリー上でのソースコードなど反復する部分列を多く含むテキストに対して高い圧縮率を達成することができます. これらのテキストは反復テキストと呼ばれ, 次世代シーケンサー技術やバージョン管理ソフトの発展により文法圧縮は今後ますます重要な技術と言えます. 文法圧縮には２つの問題があります。一つ目は入力テキストを表現する小さいCFGをどのように構築するかという問題です。最小化問題はNP-hardとして知られていて, 現在までにさまざまな近似アルゴリズム
圧縮情報処理ノススメ - An Encouragement of Compression 坂本比呂志 (PDF)
圧縮情報処理ノススメ An Encouragement of Compression 坂本比呂志 データをどれだけ小さくできるかという根源的な問いは，現在もデータ圧縮の主要テーマであり続けている．一方で， データ圧縮は時代とともに新しい価値を獲得してきた．例えば，文字列データを圧縮することで高速検索する理論が 1990 年代に提案され，様々な分野で活用されている．そして現代は，圧縮しなければならない巨大なデータ，圧縮デー タに高速アクセスするための理論，それを実現するハードウェアの全てがそろっている．そこで，文字列圧縮について解 説し，初学者の道標としたい． キーワード：データ圧縮，文字列アルゴリズム，文法圧縮，ストリームデータ ．は じ めに どんな大きな情 縮前後のサイズの比が 1% 未満というのは損失がない可 逆圧縮の条件の下では通常考えられない値である． さて前置きが
jumbled pattern matchingというのを知った - EchizenBlog-Zwei
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths(http://arxiv.org/pdf/1401.2065v1.pdf)という論文がLOUDS論文をreferしていて興味があったので読んでいた。jumbled pattern matchingという問題の時間計算量を改善したよ、という話だった。 不勉強ながらjumbled pattern matchingという言葉を知らなかった(もしくは忘れていた)。幸い、この論文にどういう問題であるか解説があったので容易に理解することが出来た。 なので忘れないうちにメモしておく。 jumbled pattern matchingというのはマッチさせる単語の文字の順番が入れ替わっていてもマッチさせるパターンマッチ。つまりabracadabraに対してabraだけでなくbaraもマッ
Lock-free Multi-producer Multi-consumer Queue on Ring Buffer
My article "Lock-Free Multi-Producer Multi-Consumer Queue on Ring Buffer" was published by Linux Journal more than 30 days ago, so now I can post it here. Work queue has always been one of the most hot points in server software. Here is how to scale it effectively to multi-core environment. I. INTRODUCTION Nowadays high performance server software (e.g. HTTP accelerator) in most cases runs on mult
Introduction to contexual bandit
This document summarizes context-aware recommendation and factorization machines. It discusses how factorization machines improve on traditional matrix factorization models by incorporating additional context features. It also introduces gradient boosting factorization machines which further enhance factorization machines by optimizing the factorization model with gradient boosting algorithms.
Cache-Oblivious データ構造入門 @DSIRNLP#5
Semi supervised, weakly-supervised, unsupervised, and active learning
javascript - Ukkonen's suffix tree algorithm in plain English - Stack Overflow
I feel a bit thick at this point. I've spent days trying to fully wrap my head around suffix tree construction, but because I don't have a mathematical background, many of the explanations elude me as they start to make excessive use of mathematical symbology. The closest to a good explanation that I've found is Fast String Searching With Suffix Trees, but he glosses over various points and some a
n個のボールをm個の箱に入れよう - kuno4n's blog
この記事はCompetitive Programming Advent Calendar Div2013の 14 日目の記事です。 初めまして。kuno4nです。 社会人から競技プログラミングを始めたへっぽこです。 さて、競技プログラマの皆様であれば、日常的にn個のボールをm個の箱に入れているかと思います。 ただ、場合の数を数えるとき、 ・ボールは区別がつくか？ ・箱は区別がつくか？ ・１つの箱に２個以上入れていいのか？ ・空の箱があっていいのか？ といったことが悩みの種かと思います。 まとめると、次の12通りに場合分けされます。 ボール 箱 最低1個入れる 高々1個入れる 入れ方に制限なし 区別がつく 区別がつく count1 count2 count3 区別がつく 区別がつかない count4 count5 count6 区別がつかない 区別がつく count7 count8 coun
React's diff algorithm
Christopher Chedeau (@vjeux) is a Facebook Software Engineer in the Photos Team. Before that, he went to EPITA, a 5-year Computer Science school and majored in its R&D lab LRDE. He also worked for Curse during the nights and week-ends. React is a JavaScript library for building user interfaces developed by Facebook. It has been designed from the ground up with performance in mind. In this article
d.y.d. - シミュレーション問題について
20:43 13/12/31 本 今年読んで面白かった本ベスト20。 自分が今年読んだ基準なので遙か昔に出版された本も多数含みます。 しかもジャンル分けもせず適当に混ざっています。 ここ数年読書メーターでまとめてたんですけど今年ないみたいだし、 本棚機能もログインしていないと見られないようになってしまったみたいだし、 こちらで。 カクリヨの短い歌 和歌を詠むとその歌に応じた異能が発動するという能力バトルもの…というと情緒が飛んでしまいますかね。 読み終わったときはそうでもなかったのだけど、後からじわじわ来て、気づいたらこの話のことばかり考えるようになっていました。なんというか、歌を、この歌に込められた思いはこう…等々ロジカルな解題として語ってしまうのは勿体ないと思うんですよ。たとえば一面の桜吹雪、たとえば夜咲く紫陽花の花、その景色をただ再現するだけ、その具象が聴き手に何かを感じさせたならそ
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
chokudai先生の焼きなまし講座
コルン @colun 焼きなましは正直あんまり使ったことがなかったのだけれども、この間、大学院の後輩の焼きなましに関する説明を聞いてからは、根本的に焼きなまし法は凸凹している広域の探索には向かないんだなと思った。 2013-12-26 23:44:26 コルン @colun 距離や近傍の定義……「ある既知の一点に良さそうなものがある時に、べつの未知の一点に良さそうなものがある確率が高くなる時、近傍と推定される。まったく無関係である時、その２つの点は遠いと推定される」と僕は思う。 2013-12-27 00:17:21
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Reddit - Dive into anything
Range-Based Graph Search in D
Reddit - Dive into anything