https://github.com/trekhleb/javascript-algorithms/blob/master/README.ja-JP.md
kd木 - Mae向きなブログ
「algorithm - 最近点検索をkd-treeで」を読んで，kd木というアルゴリズムを知りました。非常に面白いです。 ちゃんと理解したかったので，上記のページを参考にRubyで書いてみました。実際，書いてみると理解が深まるような気がします． 例えば，pts2kdtreeメソッド内で，配列をソートしているのは，2分木のバランスを保つためなんだろうなとか，kd木を作れても，最近点を検索するのは結構，難しいなとか。 汚いソースですが，以下に載せます。 kdtree.rb class Point attr_accessor :x, :y def initialize(x, y) @x = x @y = y end def to_s '(' + @x.to_s + ', ' + @y.to_s + ')' end def dsquare(p) dx = @x - p.x dy = @y - p
CodeIQで結城先生が出題されたCrossingが神がかっていた件 - やねうらおブログ(移転しました)
CodeIQで挑戦者数が400人超えという異例の事態になったCrossingとはどんな問題だったのか。twitterでも恐ろしい勢いで拡散され、最終日に100人を超えるチャレンジがあった、この問題。一体どこにそんな魅力があったのかについて考えてみる。 まず、このように注目されるためには満たすべき条件が二つある。 繁盛する飲食店を考えてもわかるように、まず美味しくなければならない。CodeIQで言うと、問題として良問でなければならない。解答後の達成感がなくてはならない。 次に、飲食店なら、その店に入ってみようという気にさせなければならない。入りにくそうなお店でも、料理さえ美味しければその後口コミで広がることもあるだろうが、それだと繁盛するまでに時間がかかりすぎる。だからCodeIQで言うと、まず問題を解いてみようという気にさせなければならない。 このどちらが欠けても駄目である。この問題はこの
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
高層ビルのエレベーターホールには、なぜ階数表示がないのか - 本当は怖いHPC
以前に高橋幸雄先生の授業で聞いて非常に面白いと思ったこと。 オフィスビルとかホテルとか、エレベーターが何基も設置されているビルの場合、エレベーターホールに階数表示が無いことが多い。エレベーターホールで画像検索してみればわかると思う。 これはなぜだろうか。 その理由は、「客がいても、その階を通過することができるようにするため」だ。 基本的に、多数のエレベーターを効率よく動かすのは難しい。工夫された高度なアルゴリズムが使われていることが多い。目標は「客の平均待ち時間を短くする」ことだ。ある階でボタンが押された場合、どのエレベーターがその客を迎えに行くか、という判断が平均待ち時間に大きな影響を与える。難しいアルゴリズムの中で、この点がもっとも重要なところだ。 高層ビルの場合、エレベーターはかなりの速度で走っている。既に客を乗せて走っているエレベーターが他の客を乗せるために停止すると、減速→停止→
PRML副読本「パターン認識と機械学習の学習」を出版します | TAKESAKO @ Yet another Cybozu Labs
2010年～2011年に社内で開催した機械学習勉強会の『パターン認識と機械学習』読書会で、光成さんが素晴らしいアンチョコを作ってくれました。PDFファイルは既にgithub 上で公開されていますが、このまま埋もれさせておくのはもったいないということで、暗黒通信団の同人誌として正式に出版されることが決まりました。 ※ 表紙のデザインは今後変更される可能性があります。 目次は以下の通りです。 第 1 章 「序論」のための確率用語 1.1 確率変数は変数なのか.............................. 7 1.1.1 確率空間(Ω, F, P)............................. 7 1.1.2 σ 加法族..................................... 8 1.1.3 確率変数X..........
プログラミングコンテストでの乱択アルゴリズム
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
テキストデータを使ってお手軽にNgram統計を取る方法 - EchizenBlog-Zwei
テキストデータの言語的な特徴を知りたい場合、そのデータを使ってNgram統計を取ることがよくある。Ngram統計というのはテキスト中の連続したN文字それぞれが何回出現したかの統計をとること。 といわれてもピンとこない人もいるかも知れない。実例を見るのが早いので当ブログの昨年12月の記事タイトルを使ってNgram統計を取ってみる。 まず記事タイトルを一行一列でテキストファイルに書き出す。 $$ cat blog-title.txt 「PIANO OPERA FINAL FANTASY I/II/III」がとても気になる そっくりヒロインなラノベ「おおコウスケよ、えらべないとはなさけない！」を読みました PSP「探偵オペラ ミルキィホームズ1.5」第5話(最終話)だよ？ 簡潔ビットベクトル性能評価実験のソースコード(rx-trie編) 簡潔ビットベクトル性能評価実験のソースコード(ux-tri
最近のSuffix Arrayによる全文検索について調べてみた - EchizenBlog-Zwei
ちょっと興味があったので調べてみた。 全文検索には主に転置インデックス(Inverted Index)によるものと接尾辞配列(Suffix Array)/接尾辞木(Suffix Tree)によるものがある。 前者は効率的にデータを扱えるものの、キーワード単位でしかインデックスを付けられないので形態素解析するなどして検索対象のテキストからキーワードを取り出す必要がある。 後者は任意のクエリにマッチすることができるもののデータサイズが大きくなりがちであることと検索結果となる文書にスコア付けができないなどの問題がある。 最近ではSuffix Array/Treeによる全文検索に対して簡潔データ構造(Succinct Data Structure)を導入してデータサイズを小さくしたり、スコアをもたせる方法が提案されたりと何かと話題が多い。 Suffix Array/Treeが持つ文書検索の機能は、
連想配列はトライでしょ的な話がでていたので入門記事を書いてみた - EchizenBlog-Zwei
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
algorithm - 基数木 + 平衡二分探索木 = 三分探索木 : 404 Blog Not Found
2012年01月22日16:36 カテゴリアルゴリズム百選翻訳/紹介 algorithm - 基数木 + 平衡二分探索木 = 三分探索木 珠玉のプログラミング Jon Bentley /小林健一郎訳 最有力候補は、これかも。 Ternary search tree - Wikipedia, the free encyclopedia 三分探索木 - Wikipedia 404 Blog Not Found:algorithm - Patricia Trie (Radix Trie) を JavaScript で最近のTrie研究の傾向は、要素の動的変更が自在にできる一般向けのものではなく、一旦作成したら要素の追加と削除が困難な代わりにものすごくコンパクトになる、簡潔データ構造の応用手段の方に偏っていると素人目に感じるのですが、そろそろJudyたんのごとくハッシュテーブルとガチで闘うとか、逆
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
Algorithm - Suffix Array を JavaScript で再発明してみた : 404 Blog Not Found
2012年01月16日16:30 カテゴリアルゴリズム百選Lightweight Languages Algorithm - Suffix Array を JavaScript で再発明してみた WEB+DB 総集編 [Vol. 1〜60] もう10年以上前に某社のCTOだったころ、Suffix array(接尾辞配列)の解説を毎週の技術者ミーティングでしたら一名を除いて「ハァ?」状態だったことを思い出しつつ。 Suffix Arrayは何が画期的だったのか? 以下は、計算機科学者でなくても直感的に理解できると思います。 ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))がかかる。 ソート済みのデータであれば、二分探索でデータの大きさの対数時間(O(logn))でキーを検索できる。 さらにキーからIDを定数時間で作成でき
大規模グラフアルゴリズムの最先端 - iwiwiの日記
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
algorithm - 重みをつけて乱択する : 404 Blog Not Found
2011年12月27日17:15 カテゴリ algorithm - 重みをつけて乱択する 数学ガール/乱択アルゴリズム 結城浩 同意なのだけど… Perlで生でrand関数をごちゃごちゃ使うコードはもう嫌だ | hirobanex.net とにかく、プログラムッチクというとなにかとランダムという要件が多いし、こんなコードばかりグチャグチャ書くのはもういやですね。 これを一般化するという問題はアルゴリズムの実習にちょうど手頃なサイズなので。 JavaScriptによる実装 頻度を高い順に並べて、乱数＜合計頻度となったところでそれを選択します。O(n)ですが選択肢を頻度順に並べることでその分ループが回る確率を抑えています。 (function(global){ var make_random_picker = function(picks){ var choices = Array.proto
データマイニングで使われるトップ10アルゴリズム - データサイエンティスト上がりのDX参謀・起業家
2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C
リンク構造を用いてスコアを計算する HITS アルゴリズム
リンク構造を用いてスコアを計算する HITS アルゴリズム 2011-11-10-1 [Algorithm][Programming] HITS とはハイパーリンク構造（リンクや被リンクなど）を用いてウェブページのスコアを計算する方法。Google で用いられている PageRank の仲間。 HITS は Authority score(以下、auth) と Hub score(以下、hub) の2種類のスコアを算出する。 アルゴリズム概要 各ページiの持つ auth を 、hub を とする。 をウェブグラフ全てのリンクの集合とし、 はページiからjへのリンクを表す(有無：1 or 0)とする。そして、以下の式（オリジナル論文での式）を繰り返し計算し最終的な auth と hub を得る。初期値は何らかの方法で与えられるとする。 実例で解説。下図のようなウェブグラフがあるとする。 初期
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
P2Pの専門知識ゼロから独自DHTを実装評価するまでの学習方法と参考資料まとめ - 情報科学屋さんを目指す人のメモ（FC2ブログ版）
何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。 P2P、特にDHTの前提知識が無い状態から、オリジナルDHTアルゴリズムを実装・評価できるようになるまでの学習方法と参考資料をまとめました。 基本的なアルゴリズムの仕組みから、実装評価に用いるツールキットの使い方までを短期間で学習することが出来ます。 「P2Pに関する卒論を書こうと思っている人」や「P2Pアプリケーションの開発前に、アルゴリズムをテストしたい人」、「なんとなくP2Pアルゴリズムに興味が出た人」などにぴったりだと思います。また、研究室での後輩教育用資料にするのも良いと思います。実際に使いましたし。 ここで紹介する資料一覧は以下の通りです。 資料１：「ChordアルゴリズムによるDHT入門」 資料１ーオプション１：「DHTアルゴリズムSymphony
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
幅優先探索すら知らない素人がDevQuizで満点を取るまでの話
