基数ソート - Wikipedia
基数ソート（きすうソート、英: radix sort）は、「比較によらないソート」[1]のアルゴリズムの一つで、位取り記数法で表現可能な対象について、下の桁から順番にソートしてゆき、最後に最上位桁でソートすると、全体が順序通りに並ぶ、という手法である。 nをデータの数、kを桁数として、計算量のオーダーはO(nk)である。また、アルゴリズム自身の性質により、素直な実装が安定ソートになる。[2] このアルゴリズムは、データの種類が有限で、最大値・最小値がはっきりしているという仮定を置いており、全ての入力データが「3桁の整数」や「2文字のアルファベット」など決まった形式であることが分かっていなければならない。なおそれに加え、ある値のデータが必ず一つしか現れないとか、同じ値のデータは同一のものとしてしまって良い、といった場合には、もはやソートするのではなく、単純に、全体が入る大きさの配列を用意し、
バケットソート
バケットソートとは、別名バケツソートとも呼ばれ、あらかじめ順番通り並べて準備されたバケツに、データを放り込むことで並べ替えを行おうという、いささか乱暴なソートアルゴリズムです。 この方法は、データの存在する範囲が有限個に限定されていないと使えませんが、使える場合は非常に高速に並べ替えを実行できる、きわめて有用なアルゴリズムです。 1～100までの数字が書かれたたくさんのカードがあるとします。カードに書かれている数字には重複があっても構いません。また、最初、カードはばらばらに混ざっています。 これらのカードを、数字が小さい順に並べ替えるのに、バケットソートでは、1～100までの数字が横に書かれている100個のバケツを準備します。 そして、カードを適当に取り出して、その番号と一致するバケツに放り込みます。また、別なカードを取り出しては、対応するバケツに放り込みます。 これをカードがなくなるまで
レコメンデーションとエディットグラフ
レコメンデーションとエディットグラフ：コーディングに役立つ！ アルゴリズムの基本（10）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 実際のアプリケーションで使われるアルゴリズム これまで見てきたアルゴリズムは、実際のアプリケーション開発の際にそのまま使われることはあまりなく、プログラム言語やライブラリなどですでに機能が用意されているものが大半でした。 今回は最終回ということで、実際のアプリケーション開発でそのまま使えるものを紹介したいと思います。 レコメンデーション ECサイトで、「あなたにお勧めの商品」を表示していることがあります。いろいろなデータベースや行動履歴のデータから、その人ごとにお勧めの商品をはじき出して推薦する機能をレコメンデー
1時間でわからせたコンシステントハッシュで仮想ノードが必要な理由 - 西尾泰和のはてなダイアリー
ConsistentHashing - コンシステント・ハッシュ法 とあるチャットで聞かれて図まで書いて解説したのでもったいないからエントリー化。ちなみにチャットが1時間弱だったのでこういうタイトルにした。 で、Bが消えるとBの責任範囲が全部Dに押し付けられてDがかわいそうでしょ。 Dの仕事が増えるでしょ。Cとか暇そうじゃん！サーバを複数用意しているメリットが薄れてる。みんなが同じくらい働くのが望ましい。 で、Bが1個の点で表現されているから「Bの手前」もDの1個だけで、そのせいで全部Dが引き受けるはめになった。つまり、仕事が細かく分割されてなくて1個の塊だから引き継ぐ人も1人だけで引き継いだ人涙目。あらかじめ仕事を100分割しとけばみんなで分担して肩代わりできて幸せだよね。 だからサーバが5個だけど点は5個じゃなくて500個打とう。それが仮想ノード。 実装はどうするの？という質問に対して
Canonical Huffman Codes - naoyaのはてなダイアリー
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。 ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率が分かっているときに、その各シンボルに最適な符号長の接頭語符号を求めるものです。 通常のハフマン符号はポインタで結ばれたハフマン木を構築して、ツリーを辿りながら各シンボルに対する接頭語符号を計算します。このハフマン木には曖昧な箇所が残されています。ハフマン木は木の辺を右に辿るか左に辿るかで符号のビットが決まりますが、右が 0 で左が 1 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
Google Japan Blog: Google検索ランキングの背景にある技術
毎週月曜日のエンジニアリングブログの4回目です。今週も検索テクノロジーについて、過去に米国のブログにポストされたもの を日本語でお届けします。 前回の投稿で、私は Google 検索ランキングの背景にある理念を紹介しました。今回はサーチクオリティについてお話しする努力の一環として、Google 検索ランキングの背景にある技術についてもう少し詳しく説明したいと思います。私たちのランキングシステムのコアテクノロジーは、情報検索（ Information Retrieval または IR ）という学問分野に由来しています。IR コミュニティーは、すでに 50 年近くにわたって検索について研究しています。ページのランキングには、単語の登場頻度のような単語の統計的特徴が用いられています※1。私たちは IR という強固な基礎の上に、リンク、ページ構造、その他多くの革新的技術を用いて最高レベルのシステム
Tail call - Wikipedia
In computer science, a tail call is a subroutine call performed as the final action of a procedure.[1] If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion (or tail-end recursion) is particularly useful, and is often easy to optimize in implementations. Tail calls can be implemented without adding a
コサイン距離ベースのLSHをRubyで - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
参考文献:Web+DB press vol.49 レコメンド特集のPart3など。 アルゴリズムの概要 詳細(特に数学的な)はぐぐれ。 モチベーションとしては、高次元における近傍点探索を高速で行いたい。まじめにやるとどう工夫しても計算量がすごいことになるので、近似で。 どうするかというと、「距離が近いと同じような値になるハッシュ関数」を使う。あるベクトルの近傍を求めたい場合、そのベクトルのハッシュと同じ(もしくは近い)値のハッシュを持つベクトルをテーブルから引いてきて返す。計算量がどうなるかはややこしいけど、とりあえず全部探すよりは速い。 で、どういう関数をハッシュとするのか。これは距離の定義によって異なる。ハミング距離、コサイン距離、ユークリッド距離などにはそういった関数の存在が知られている。 コサイン距離の場合、ランダムなベクトルをいくつか用意して、入力されたベクトルがそれらと似ている
分布推定アルゴリズム - yukobaのブログ
分布推定アルゴリズム。遺伝的アルゴリズムを改良した物です。個体の集合を交叉・突然変異させるのではなく、個体の生成確率を進化させます。最適化問題のアルゴリズムです。以下、自分へのメモです。わかったことが増えたら追記するかも。 ビットストリング 計算量に関しては、ビット数をn、反復数をTとしています。 Population-Based Incremental Learning (PBIL) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.8554 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5424 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.1108 Population-ba
wonderfl build flash online | 面白法人カヤック
wonderflは、サイト上でFlashをつくることのできるサービス。 通常Flashをつくるためには、Flash IDEやFlex、FlashDevelop等といったツールを使って、コードを書き、コンパイルする必要がありますが、wonderflでは、サイトにあるフォームにActionscript3のコードを書けば、サーバサイドでコンパイルを行えます。 つまり、ブラウザさえあれば、Flashをつくれます。コンパイル結果はサイト上に表示され、作成されたFlash（swf）はページ上に自動的に表示されるので、完成したFlashをリアルタイムに見ながらコードを書くことができます。 ※APIとして、はてな OpenIDを使用してネットにさえつながれば、誰もがFlashクリエイターになれます。世界中のFlashクリエイターがユーザーになるwonderflは、 文字通り、世界のFlash図鑑となってい
Perlのstable quicksort - てきとうなメモ
stableなquicksortないかなと思っていろいろ探していたらPerlのquicksortがstableな実装だった． perl5.10.0のpp_sort.cより引用． Perlのquicksortについては以下のようなデータ構造を利用している． indir list1 +----+ +----+ | | --------------> | | ------> first element to be sorted +----+ +----+ | | --------------> | | ------> second element to be sorted +----+ +----+ | | --------------> | | ------> third element to be sorted +----+ +----+ ... +----+ +----+ | | ----
アルゴリズム再入門
2012-07-16 14:25:12 WEB+DB PRESS総集編［Vol.1～36］ | 技術評論社 WEB+DB Press 総集編［Vol.1〜36］に書いた記事『Webエンジニアのための基礎，徹底理解 3章：アルゴリズム再入門 C#編』を公開します。 ちなみにこの記事ではデータ構造についての話を最小限にしています。出てくるデータ構造は配列と二分木だけ。それは、データ構造については別のライターさんが記事を書くことになっていたからです。 ちなみに、書いてみたかった(というか、書いてみたけどやめた)アルゴリズムは、 ハッシュ法 (これはデータ構造の章にあります。すばらしいです) 木の探索 (traversal) 平衡木 (AVLとか) その他の有名なソート (バブルソート、シェルソート、ヒープソート、etc) Skip List (これはどちらかと言うとデータ構造メインな話なのでため
Wavelet Tree - naoyaのはてなダイアリー
圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;
algorithm - correction - 最近点検索 : 404 Blog Not Found
2009年04月29日07:45 カテゴリMathアルゴリズム百選 algorithm - correction - 最近点検索 これ、「素直な解答」の方が間違っている。 404 Blog Not Found:algorithm - 最近点検索 ぬじゃらだーさんのコメント このアルゴリズムって点が原点から等距離に分布している場合はまったく働かないですよね。 その通り。その一方で、「近い順にソート」は合っている。しかしこれだとO(n log n)。 TSさんのコメント もとの最近点探索の問題を解くには、点集合Pのボロノイ図データを作っておいて問い合わせに答えるのが正攻法ではないでしょうか これだと確かに高速。点がすべて格子点上にある場合(たとえばビットマップ)、ボロノイ図があらかじめ用意してある場合はO(1)で判定できる。たとえば各格子点にあらかじめどの点が一番近いかを記録しておき、それを読
Selection algorithm - Wikipedia
For simulated natural selection in genetic algorithms, see Selection (genetic algorithm). In computer science, a selection algorithm is an algorithm for finding the th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the
algorithm - 最近点検索 : 404 Blog Not Found
2009年04月28日23:30 カテゴリMathLightweight Languages algorithm - 最近点検索 食後のデザートにちょうどよいサイズの問題。 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです .. - 人力検索はてな 条件は次の通りです 集合Pはあらかじめ、任意の順番でソートしておける 点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる まずは素直に答えを。 点集合は、あらかじめ原点からの距離順にソートしておく。 その集合を、検索したい点の原点からの距離を使って二分探索(binary search)する。 二分探索は exact match でなくてもいいので、この方法でOKです。O(
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
In-place algorithm - Wikipedia
西尾泰和のブログ: Javaで破壊的クイックソート
LR-NET(R-Tree)