もっとAVL木で木構造を学ぼう （1/2）－ ＠IT
第4回 もっとAVL木で木構造を学ぼう はやしつとむ アナハイムテクノロジー株式会社 2009/5/25 オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか（編集部） 第3回「AVL木で木構造を学ぼう」では、AVL木に節点を追加する際に、バランスを回復する動作までを解説しました。 今回は、AVL木の実装をさらに進めて、節点を削除する際の動作を取り上げます。 筆者はDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードして、インストールしてみてください。
American Mathematical Society :: Feature Column - Voronoi Diagrams and a Day at the Beach
Introduction Suppose that you live in a desert where the only sources of water are a few springs scattered here and there. For each spring, you would like to determine the locations nearest that spring. The result could be a map, like the one shown here, in which the terrain is divided into regions of locations nearest the various springs. Maps like this appear frequently in various applications a
分布数えソートと逆写像ソート - kkobayashi_a’s blog
どちらも範囲の決まった整数をソートするときにO(n)でソートできるという優れものです。アルゴリズムがどうだったか忘れてしまったので改めて調べることに。例として 最大値 = 30 最小値 = 20 データ数 = 5 の場合を考えたいと思います。 分布数えソート これは簡単。データの範囲で分布を数え、その数にしたがってソート済みの配列を復元します。分布を格納するため、データの範囲と同じ大きさの配列(dist)が使われます。 data[000]=21 dist[000(20)]=0 sort[000]=21 data[001]=26 dist[001(21)]=2 sort[001]=21 data[002]=27 dist[002(22)]=0 sort[002]=26 data[003]=21 dist[003(23)]=0 sort[003]=27 data[004]=29 dist[00
ミニマックス法 - Wikipedia
思考プログラムの基本は、局面がどの程度自分にとって有利か点数を付ける(評価する)ことである。局面の有利度を適切に評価することができれば、自分の打てる手のうち、最も評価の高い局面を出現させるような手を選択すればよいことになる。 局面に置かれている駒の位置・数などだけから算出した評価値を静的評価値、算出する関数を静的評価関数と呼ぶ。「静的」とはここでは先読みをしていないことを意味する。通常、静的評価関数だけで適切な局面評価を行うことは困難である。そのため、先読みを実現するのがこのミニマックス法である。 先を読んだ上で、ある局面がどの程度有利であるかを評価するには、以下の考え方を用いればよい。 読みたい局面が相手の番であれば、その局面の次に出現するすべての局面のうち最も悪い（不利な）、つまり相手にとって最も有利な(評価値が最小)手を相手は打ってくるはずである。そこで、次に出現するすべての局面の評
Radix Sort Revisited
Pierre Terdiman Last revision: 04.01.2000 In every decent programmer’s toolbox lies a strange weapon called a Radix Sort. Where does it come from ? Who invented it ? I don’t know. As far as I can remember it was there, fast, easy, effective. Really effective. So unbelievably useful I’ve never really understood why people would want to use something else. The reasons ? Most of the time, they tell m
更新履歴兼雑記 - 音楽シャッフルクイズ
http://www.hyuki.com/d/200510.html#i20051020190000 しない。 以下 N=size。ありえる順列は N! 個。SWAPの全組み合わせは N^N 。よって N^N/N! 通りの組み合わせができれば正しくシャッフルされていると言える (コメントで指摘いただいた通り、「正しくシャッフルされていると言えるためには N^N/N! 通りの組みあわせができなければならない」が正しいです…) が、これは N>=3 で整数ではない。 なぜなら、 N^N/N! が整数になるには 1 から N の全ての n に対して N/n が割り切れなければならないが、 N/N-1 は偶奇の違いから N>=3 で常に割り切れない。 (翌朝追記。ここもひどい… N/N-1 が割り切れないのは偶奇は本質的じゃない。 N が 奇なら 2k+1/2k = 1+1/2k で割り切れない、
キャッシュアルゴリズム - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "キャッシュアルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年8月) キャッシュアルゴリズム（英: cache algorithm）は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。置換アルゴリズムあるいは置換ポリシーとも。 キャッシュのヒット率（hit rate）とは、探しているデータがキャッシュ上で見つかる率（頻度）である。キャッシュサイズを増やさずにヒ
Binomial heap - Wikipedia
In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps.[1] Binomial heaps were invented i
はてなダイアリーのようにキーワードを自動でリンクするアルゴリズムを知りたいです。…
はてなダイアリーのようにキーワードを自動でリンクするアルゴリズムを知りたいです。単純に考えると、①キーワードのリストを持っておく。②対象となる文章に、あるキーワードが含まれているかを検索する。③「②」の検索をキーワードの数だけ繰り返す。ということになると思います。1万語のキーワードリストがある場合、1万回の検索を行うことになり、たとえば多数の投稿がある場合は効率も悪いですし負荷も掛かります。もっと効率のいいアルゴリズムがあるのでしょうか。
MA38SU - Hotels in Bangkok - best rates and availability of selected accommodations
wp.Vicuna Ext. The template VICUNA WordPress theme wp.Vicuna for CMS tools is available. Here, we have released the theme wp.Vicuna Ext. , Which makes customization easier . Vicuna Adaptor We have released Vicuna Adapter , an extension plug-in for wp.Vicuna Ext . Comments:10 rikuto 08-10-15 (Wed) 13:00 Nice to meet you, if you newly introduce WordPress 2.6.2, upload wp.Vicuna Ext. Ver.1.58 to them
単純ベイズ分類器 - Wikipedia
単純ベイズ分類器（たんじゅんベイズぶんるいき、英: Naive Bayes classifier）は、単純な確率的分類器である。 単純ベイズ分類器の元となる確率モデルは強い（単純な）独立性仮定と共にベイズの定理を適用することに基づいており、より正確に言えば「独立特徴モデル; independent feature model」と呼ぶべきものである。 確率モデルの性質に基づいて、単純ベイズ分類器は教師あり学習の設定で効率的に訓練可能である。多くの実用例では、単純ベイズ分類器のパラメータ推定には最尤法が使われる。つまり、単純ベイズ分類器を使用するにあたって、ベイズ確率やその他のベイズ的手法を使う必要はない。 設計も仮定も非常に単純であるにもかかわらず、単純ベイズ分類器は複雑な実世界の状況において、期待よりもずっとうまく働く。近頃、ベイズ分類問題の注意深い解析によって、単純ベイズ分類器の効率性に
基数ソート - 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 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
In-place algorithm - Wikipedia