検索と挿入がともにO(1)であるようなHashを作るにはコツがいる
このところ立て続けに表記の事実を理解していない俺実装のHash(しかもCで!)を見かけたので、おそらく知られていないんだと思う。以降、同じ轍を踏む人が少なくなればと思い、啓蒙のために公開しておく。 先に言っておくがおまえらはHashを再発明するんじゃねよボケが。おとなしくありもののライブラリ使えよ。つうかHashのある言語使えよ。Cとかマゾかよ。 言葉と前提とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、 class Hash { typedef lis
B-trees, Shadowing, and Clones Ohad Rodeh IBM Haifa Research Labs B-trees are used by many file-systems to represent files and directories. They provide guarantied logarithmic time key-search, insert, and remove. File systems like WAFL and ZFS use shad
B-trees, Shadowing, and Clones Ohad Rodeh IBM Haifa Research Labs B-trees are used by many file-systems to represent files and directories. They provide guarantied logarithmic time key-search, insert, and remove. File systems like WAFL and ZFS use shadow- ing, or copy-on-write, to implement snapshots, crash-recovery, write-batching and RAID. Serious difficulties arise when trying to use b-trees and s
フォント同士を交配させて新しいフォントを作る「genoTyp」が面白い - てっく煮ブログ
「この発想はなかった！」と驚いた。genoTyp はフォント同士を交配させて新しいフォントを生み出す実験サイトだ。早速、試しにやってみた。1. 第一世代の親を決めるgenoTyp を開いて左上の [Breed] タブをクリックすると「交配ページ」が表示される。[add original font] ボタンをクリックして、祖先となるフォントを２つ追加してみた。交配させるために２つのフォントをドラッグしてくっつけた。くっついた状態になれば交配の準備は完了だ。2. 交配させてみる中央の [cross] ボタンを押すと第一世代が誕生する。４人の子供が誕生した。父親似だったり、母親似だったり、子供によって雰囲気が異なっている。3. 第一世代でも交配別の [original font] を追加させて、第一世代の中から気に入ったものと交配させてみた。３人の子供が第二世代に誕生した。4. さらに交配！今度
Regular Expression Matching Can Be Simple And Fast
Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) Russ Cox rsc@swtch.com January 2007 Introduction This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep.
ガベージコレクションの実装法と評価
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは ― ＠IT
2008/04/11 すべての暗号はいずれ破られる。2000年前のシーザー暗号の時代から高度な暗号技術が一般化したデジタル通信の現代に至るまで、それが暗号通信の歴史が証明し続けた事実であると同時に、もっとも人口に膾炙したクリシェでもあった。例えば、鳴り物入りでリリースされたDVDのコンテンツ暗号技術「CSS」（Content Scramble System）が、リリースからわずか数年で10代のノルウェー人ハッカーに破られたことは記憶に新しい。 【追記】（2008年4月15日） この記事は取材に基づいて執筆したものですが、一部専門家らから「CAB方式暗号は解読不能」というのは誇大表現ではないかとの疑義が呈されています。アルゴリズムの公開や第三者による検証がない現在、この記事に登場するCAB方式が発案者・実装者の主張通り画期的な暗号方式で、本当に解読が不可能であるかどうか分かりません。現在、専
SAT ソルバで数独を解く方法 - まめめも
数独は非常に SAT に変換しやすい問題です。全部参考文献 *1 に載っている内容ですが、なるべくわかりやすく説明してみます。ちょっと長いです。 SAT とは まず SAT をごく簡単に説明します。すでに SAT を知っている人はここは読み飛ばしてください。 命題論理式の形の一つに乗法標準形のというのがあります。変数か変数の否定 (リテラルと言います) を or だけでつないだ式 (節と言います) を and だけでつないだ論理式のことを言います。つまり以下みたいな形です。 ( a1 or !a2 or ... or an) and ( b1 or !b2 or ... or !bn) and ... and (!z1 or z2 or ... or !zn)SAT は「a1 や zn などの変数にうまく true か false を代入して、上の式全体を true にできるか」という問題
集合知と多量情報の可視化アルゴリズム本 Programming Collective Intelligence | fladdict
先日購入したBen FryのVisualizing Dataとあわせて買ってみた、Programming Collective Intelligence: Building Smart Web 2.0 Applications という本もかなりよさげ。 端的にいうとWEB2.0コンテンツ用に特化した、統計解析の理論とアルゴリズムの解説本。 いわゆる「これを買った人はこれを買ってます」を筆頭に、市場予測やスパム抽出、特徴データのグルーピングなど、集合知を抽出するアルゴリズムが大集合してる感じです。各アルゴリズムの原理の説明から、シンプルな自力実装までが書いてある感じっぽい。こういう系は数式だけあって理解不能か、動作がライブラリに隠蔽されてて理解不能で手が出せなかったけど、この本あれば大分理解できそう。以下、乗ってる内容メモ。 ・Amazon的なリコメンドのしくみ ・データのグループ化(クラス
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
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
Wikipediaのキーワードリンクを使って関連語データを作ってみた
Wikipediaのキーワードリンクを使って関連語データを作ってみた 2007-06-09-3 [NLP][Programming][Algorithm] Wikipedia のキーワードリンクを使って関連語データ（関連キーワード集） を作ってみた。 Wikipedia のデータはダウンロードページからbz2形式のを取ってきた。 日本のウィキペディアのXMLデータね。 (see Wikipedia:データベースダウンロード) で、Perlスクリプトで以下の関連語データ作成処理を行った。 （スクリプトはこの記事の末尾に載せておく） (1) 各キーワードページに含まれているキーワード（リンク）を取り出す。 例えばキーワードAのページにB,C,Dが含まれていたら、A => B,C,D というデータを蓄積。 またキーワードAが他のキーワードのページ（例えばX）に含まれていたら、それも蓄積。その場合
[を] Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なアルゴリズム。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二
Bayesian Sets - mots quotidiens.
Bayesian Sets (Ghahramani and Heller, NIPS 2005)は Google Sets と同じようなことをベイズ的に行うアルゴリズムです。 いくつかアイテムを入れると, それを「補完する」ようなアイテムを 返してくれます。 これは NIPS の accepted papers が出た去年の8月から気になっていて, 本会議ではオーラルの発表もあって大体のやっていることはわかった ものの, 何と(本会議の時も!)論文がなく, 直接Hellerに連絡して もらえるように頼んでいたところ, Online proceedings の締切りがあった 時に連絡があって, 読めるようになりました。(リンクは下のページ参照) 岡野原君に先に 紹介 されてしまいましたが, 以下は, 岡野原君が書いていない話。 Bayesian Sets は, アイテム集合 D に対して,
僻地 - Bayesian Setの種明かし
Bayesian Setとは集合D_Cが与えられたとき、そこから「類推」して、元の集合C⊃D_Cに入る元xを(「自信」の度合いを表す数値つきで)求めるというもの。ただし、D_Cの元やxは特徴データ{c_i}をもっているとする。で、原論文を読むとΓ関数がずらずらでてきておどろおどろしいのだけれど、実はやっていることは簡単だということに気がついたので、書いてみる。簡単のために、特徴はあるかないかの2値的とする。(一般的には連続量も扱える。)すると、Bayesian Setのアルゴリズムがやっていることは、xについて観測された特徴c毎に重みwを足していくだけである。重みwはハイパーパラメーターα、βを使って,と書ける。ハイパーパラメータというと難しいそうだが、α_t = (Nc:D_Cでcをもつ元の数) + α、β_t = (N-Nc:D_Cでcを持たない元の数) + βと定めるので、α、βは先
データ圧縮の昔話
1988年 1989年 1990年 1991年 1992年 1993年 1999-10-11: David Huffman 没 2000-04-14: Phil Katz 没 (享年37才) 2001-02-26: Claude Shannon 没 当時の畏友［これもずっと前の情報です。間違っていたら教えてください］ 吉崎栄泰さんは帯広協会病院の忙しいお医者さんです。 三木和彦（まむし）さんは株式会社情報管理の代表取締役をしておられます。 MASSAN（massangeana，益山健）さんについてはここをご覧ください。 ＲＯＭ男さんについてはここをご覧ください。 岡本継男さんはここでUNIX版LHAをメンテしてくださっています。 大久保謙二郎先生は どうしておられるでしょうか お元気で活躍されておられます。 奥村晴彦 Last modified: 2008-03-20 07:30:19
suffix array
更新履歴 2004/01/07 O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
SQLで木と階層構造のデータを扱う――入れ子集合モデル
ESMAJ
IDEA * IDEA
