algorithm - Patricia Trie (Radix Trie) を JavaScript で : 404 Blog Not Found
2012年01月21日21:45 カテゴリTipsLightweight Languages algorithm - Patricia Trie (Radix Trie) を JavaScript で スマホ手袋 5本指全てタッチできる smarttouch 5105 ミドリ安全 寒いのでこれをしたまま書きました。 dankogai/js-trie-patricia - GitHub 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? Trieが連想配列の代わりになるというのを体でも納得しておきたかったので。 はじめてのTrie というわけで早速作ってみましょう。あっけにとられるほど簡単です。ここではObject、つまり連想配列で分岐点を実現するというある意味本末転倒なことをしていますが、JSならばしかたがない。 var Trie =
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
レインボーテーブルを用いてmd5ハッシュ値から平文を得る | guro_chanの日記
随分以前からずっと気になっていたレインボーテーブルに漸く取り組んだ。 総当たり攻撃でハッシュ値から平文を得る場合、(1)平文を推測し、(2)そのハッシュ値を計算し、(3)解析したいハッシュ値と比較する、というプロセスを経る。平文の長さや構成する文字によっては大変な時間を必要とする。翻ってレインボーテーブルを使う方法では、予め解析用のデータを用意して臨む。そのため総当たり攻撃で言うところの(1)と(2)のプロセスが事実上、必要なくなる。(3)+αの処理で済むから解析に要する時間が劇的に短くなる、という仕組みである。忙しいビジネスパーソンにマッチするソリューションと言える。 しかしながら、考え得るあらゆる文字列の組み合わせとそのハッシュ値のデータは一般的に夥しい数になる。例えば 8 文字の小文字アルファベットの文字列だけで考えても、組み合わせの数は 26 の 8 乗すなわち 208827064
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
StackをLinked Listを使って実装 - yasuhisa's blog
自分用メモ。データ構造とちょっとしたコードの例。 StackA stack is a last in, first out data structure. There are two main fundamental operation for stack: push and pop. The push operation adds an item to the top of the stack. The pop operation removes an item from the top of stack, and returns the value. We can implement the stack with linked list or array. Stacks are often used in the computing world. For example, expres
C++でページランクを実装 - yasuhisa's blog
実験で使いそうなベースラインがページランク的なアルゴリズムだったので、Rubyの実装を適当にC++に翻訳してみただけ。超簡単なのでよい。 Rubyでもっとも重要なライブラリは何か？PageRankで計算してみた - aikeの日記 #include <map> #include <cmath> #include <iostream> #include <vector> typedef std::map<int, std::vector<int> > AdjacentMatrix; class PageRank { public: PageRank(AdjacentMatrix graph, int n, double damping = 0.85) { graph_ = graph; N_ = n; damping_ = damping; for (AdjacentMatrix::iter
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
C言語による輪郭追跡処理について
ここでは、私、酒井理雄（TSUGU)が卒業研究において作成した DIB画像の輪郭追跡プログラムのアルゴリズムについて解説をしたいと思います。 ご意見やご感想、また、ここおかしいんじゃない？というような所があれば連絡していただけると作者が喜びます。 最初にこのドキュメント中の画像の見方について説明します。 下のような画像が多数出てきますが、その色は次のような意図で塗られています。
画像処理におけるアルゴリズム
ここでは各画像処理におけるアルゴリズムを簡単に解説する。 2値化 明るさ調整 色成分の抽出 色反転 コントラスト調整 切り出し ガンマ補正 グレイスケール化 増色 画像枠付加 鏡像反転 ノイズ除去 輪郭抽出 輪郭追跡 拡大縮小 任意角回転 セピア調化 ぼかし 2値化 指定画像を白と黒の2階調の画像に変換する処理であり、本研究で作成した2値化処理は単一手動閾値方式、P-タイル法、また、誤差分散法およびその拡張型である Floyd&Steinberg 型誤差分散、Jarvice,Judice&Ninke 型誤差分散の5つである。 次にそれぞれのアルゴリズムについて解説する。 単一手動閾値方式 指定された色深度を基準として、その値より入力画素の色深度値が明るければ白、暗ければ黒色として2値化する。下の式を用いている。 このとき、出力画像は初期状態で黒色となるので、入力画像の画素値が閾値以
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
【レポート】GNU grepが高速な理由 | エンタープライズ | マイコミジャーナル
FreeBSD - The Power To Serve why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 G
前向きアルゴリズム、Vitebiアルゴリズム - yasuhisa's blog
Viterbi書くの何回目だろ。。。週末にはバウムウェルチ(Baum-Welch)のアルゴリズムこと前向き後ろ向きアルゴリズムを書きたいところ。 www.yasuhisay.info # -*- coding: utf-8 -*- # 確率的言語モデル(東京大学出版)第4章(隠れマルコフモデル) require 'pp' # 品詞iから品詞jへの遷移確率 # 番号と品詞の対応付け: 0(名詞)、1(冠詞)、2(動詞)、3(形容詞)、4(前置詞) a = [[0.3, 0.0, 0.4, 0.1, 0.2], [0.7, 0.0, 0.0, 0.3, 0.0], [0.3, 0.2, 0.1, 0.2, 0.2], [0.5, 0.1, 0.0, 0.4, 0.0], [0.6, 0.3, 0.0, 0.1, 0.0]] # 品詞jから単語iを生成する確率 # 番号と単語の対応付け: 0(T
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
大規模グラフアルゴリズムの最先端
幅優先探索すら知らない素人がDevQuizで満点を取るまでの話
Engadget | Technology News & Reviews
