情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
アーリー法 - Wikipedia
アーリー法（英: Earley parser）は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。 アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。 以下の解説において、α、β、γは任意の終端記号と非終端記号の文字列（空文字列を含む）を表し、X、Y、Z は1つの非終端記号を表し、a は終端記号を表す。 アーリー法はトップダウン型の動的計画法である。以下では Earley のドット記法を使用する。生成規則 X → αβ があるとき、X → α • β という表記は、αが既に解析済みで、βをこれから解析しようとしていることを表す。 全ての入力位置（字
hamadakoichi blog
2017/10/28 "第60回 データマイニング+WEB ＠東京( #TokyoWebmining 60th ) ー 機械学習 活用 祭り ー" を開催しました。 第60回 データマイニング+WEB ＠東京( #TokyoWebmining 60th ) ー 機械学習 活用 祭り ーEventbrite Google グループ 会場提供して下さった FreakOut さん、どうもありがとうございました。素敵なトークを提供してくれた講師メンバーに感謝します。多くの方々の参加を嬉しく思っています。 参加者ID・バックグラウンド一覧： 参加者セキココ：第60回 データマイニング+WEB ＠東京 セキココ (作成してくれた [Twitter:@komiya_atsushi] さんに感謝） 以下、全講師資料、関連資料、ツイートまとめです。 AGENDA： ■Opening Talk： O1.「デー
A Fast Wait-Free Hash Table
February 21, 2007 lecture by Cliff Click for the Stanford University Computer Systems Colloquium (EE 380). Cliff presents a wait-free (lock-free) concurrent Hash Table implementation with better single-thread performance than most Hash Tables, and better multi-thread performance than all other implementations he's tried; and, time permitting, he provides a short case study of a java application d
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
okamoto7の日記 Online Computation and Competitive Analysis
オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ―数理技法編) 作者: 徳山豪出版社/メーカー: 共立出版発売日: 2007/08/10メディア: 単行本購入: 2人 クリック: 38回この商品を含むブログ (11件) を見る ようやく目にすることができました． 今年度は既にいろんなところに行き過ぎで，書籍すら買う余裕がなさそうなので未購入だけど，何とかして読みたいです． ぱらぱら立ち読みしたところ，本論と関係ないあとがきやまえがきや補足のところが個人的には好きです． まぁ，本論はぱらぱら読んだだけでは分からないので仕方ないですが． ちなみに，オンラインアルゴリズムとは一言でいうなら「分からない未来に対するアルゴリズム」で，それを統計的に扱おうとすると予測理論になるのですが，そうではない形で理論展開するところが面白いわけです． 一方，ストリームアルゴリズム
Algorithm - O(n log(n))より速いsort : 404 Blog Not Found
2006年12月03日01:45 カテゴリMath Algorithm - O(n log(n))より速いsort 404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?はちょっとした驚きですが、実はデータの種類さえ限定できれば、builtin sortを出し抜くことはJavaScriptでなくてもそれほど難しくありません。 例えば、ソートしたい対象が密集した整数値で、メモリーがふんだんにある場合には、bucket sortがあります。これを使えば、Perlにおいてすらbuilt-inを簡単に出し抜けます。 % perl bucket.pl 10000 Benchmark: running bucket, builtin, quick for at least 3 CPU seconds... bucket: 3 wallc
Sphere Online Judge (SPOJ) - Problems
SPOJ (Sphere Online Judge) is an online judge system with over 315,000 registered users and over 20000 problems. The solution to problems can be submitted in over 60 languages including C, C++, Java, Python, C#, Go, Haskell, Ocaml, and F#. SPOJ has a rapidly growing problem set/tasks available for practice 24 hours/day, including many original tasks prepared by the community of expert problem sett
Solving Every Sudoku Puzzle
by Peter Norvig Note: This page is the original 2006 essay; an updated Python 3 Jupyter notebook is available here and should probably be read instead of this page. In this essay I tackle the problem of solving every Sudoku puzzle. It turns out to be quite easy (about one page of code for the main idea and two pages for embellishments) using two ideas: constraint propagation and search. Sudoku Not
OBB vs AABB - Radium Software Development
This domain may be for sale!
コンピュータ将棋選手権でフリーソフトのBonanza初出場初優勝 - sumiiのブログ
http://www.computer-shogi.org/ らしい。作者の専門は化学らしい。某F社をやめてI研究室で将棋囲碁をやっている友人によると、プロの棋譜を統計処理して評価関数を学習した「だけ」（←褒め言葉のつもり）だそうで。詰み探索もしてないとか、特定の知識をベースにしていないとか何とか（引用の正確さは保証できません）。よくわからんが、すごいっぽい（もちろん良い意味で）。 IS将棋（東大将棋）はデバッグで欠場とか。残念。 追記：IS将棋が欠場して、激指もバグってたからボナンザが優勝できたんじゃないか、という意見もあるようで。 http://44840889.at.webry.info/200605/article_8.html http://journal.mycom.co.jp/articles/2006/05/08/shogi/
Algorithmist
Algorithmist is dedicated to anything algorithms - from the practical realm, to the theoretical realm. There are also links and explanation to problemsets. Algorithmic Topics Sorting Exhaustive Search Graph Theory Dynamic Programming Greedy Computational Geometry Number Theory Data Structures View the Table of Contents. Want a problem/algorithm/section written up? Leave a note on the Algorithmist
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - freenet/locutus: Declare your digital independence
Java Programming [Archive] - Rounding up an int to a power of two
並列処理に対応したプログラミング – 並列階層のパターン
The LEAPS Algorithms1 Don Batory Department of Computer Sciences The University of Texas Austin, Texas 78712 Abstract LEAPS is a state-of-the-art production system compiler that produces the fastest sequential executables of OPS5 rule sets. The performan
File: same_fringe.rdoc
http://www.nsl.com/papers/samefringe.htm
https://code-fetcher.com/uncategorised/algosort