銀行員待行列(Banker's deque)、二つのリストで構成奴～～ｗｗｗｗｗ 入奴と出奴～ｗｗｗｗｗｗｗｗｗ ↓入奴 三(^o^)ノ　[(^o^)ノ, (^o^)ノ, (^o^)ノ] ヽ(^o^)三　[ヽ(^o^), ヽ(^o^), ヽ(^o^)] ↑出奴 追加は入奴にcons、取り出しは出奴にuncons奴～ｗｗｗリストなので基本定数時間奴～ｗｗｗｗｗｗ リスト枯渇防止の為、リストの長さに以下の条件課奴～～～ｗｗｗｗｗｗ length (入奴) <= length (出奴) * 3 + 1 length (出奴) <= length (入奴) * 3 + 1 条件充足不能場合、|length (入奴) - length (出奴)| <= 1なるよう余剰分反転後短い側の末尾に結合して調整奴～ｗｗｗｗｗ時間計算量O(length (入奴) + length (出奴))必要～～～～ｗｗｗｗ

id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文

Today we will learn how to implement the Aho-Corasick algorithm. It is used for finding occurences of words in text and it is faster than other common algorithms. Code will be in ActionScript 3, but implementation in C, C++, C# or Java will be very similar. You can also try a fullscreen version of an applett. Aho-Corasick algorithm We can divide the algorithm into 2 steps: constructing a finite st

04:40 04/06/04 ピーステーブル PieceTable とも言う。文字列の Piece（小片）を繋げて、 一つの巨大な文書を表現する方式。 検索すると引っかかる文書のほとんどが AbiWord 関係なので、 このワープロソフトの主要な内部データ構造ということなのかな。 他に、MS-WordやOpenOffice.org関連の文書にも登場していて、 基本的に単なるテキストエディタよりは、文字に付加情報をくっつける系の 編集ソフトに使われる場面が今のところ多いみたいです。 余談ですがAbiWordは、綱渡り的にですがBeOS版の開発が続いている貴重なワープロソフトなのです。感謝感謝。 概要 ファイルを読み込んだとしましょう。ABCDEFG、という７文字のファイル。 とりあえず、７文字分のOrigという名前のバッファを用意して、そこに格納します。 それと別に、Addという名前の空のバ

Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs. Data structures presented in the book include stacks, queues, deques, and lists implemented as arrays and linked-lists; space-efficient implementations of lists; skip lists; hash tables and hash codes; binary search

第一章　基本概念 [Handout] [Slide] 第二章　線分交差 [Handout] [Slide] 第三章　凸包 [Handout] [Slide] 第四章　ボロノイ図 [Handout] [Slide] 第五章　ドローネ三角形分割 [Handout] [Slide] 第六章　幾何的領域探索 [Handout] [Slide] 第七章　多角形の三角形分割 [Handout] [Slide] Created by Computational Geometry Team, 2008

線形計画問題に対するシンプレックス法 製作者：向　譲治 何はともあれ下の例題を考えてみよう。 例題 ある会社が、A、Bという製品を売り出している。　それらを製作するための材料はプラスチック、アルミ、ゴムである。　それぞれ１個を製作するために必要な材料の量は下の表のとおりである。

数学セミナー2011年2月号 特集◎ランダムネスを捕まえる数学セミナー 2011年 02月号 [雑誌]出版社/メーカー: 日本評論社発売日: 2011/01/12メディア: 雑誌購入: 1人 クリック: 1回この商品を含むブログ (2件) を見る　二ヶ月以上遅れて速報とはこれ如何に。　ランダムネスに関するランダムな年表（チョイスはかなり偏ってます）西暦出来事1919フォン・ミーゼスがランダム性を数学的に定式化しようと試みる1920--6Xランダム性の定式化に辿り着くまでの多数の数学者による試行錯誤の時代1933コルモゴロフによる確率論の公理化ランダムネス誕生の時代1960ソロモノフが現在コルモゴロフ複雑性と呼ばれる概念を導入（数年後にコルモゴロフが同じ概念を独立に発見）1966マーティン=レフによる構成的ランダム性の定式化1970ソロヴェイはランダム強制法を導入し， の部分集合が全てルベー

集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ