クイックセレクト(Quick Select) - LifeTimeException@hrk623
今回は選択アルゴリズムの紹介です。 これは、配列からk番目に小さい数を線形時間で 探しだすクイックセレクト(Quick Select)という クイックソートの派生アルゴリズムです。 問題 ソートされていないa1からanまでの数字がn個あり、 その中からk番目に小さい数字を探せ。 例： サイズが9の配列、[2, 5, 3, 7, 1, 8, 6, 0, 4]において、 3番目に小さい数は2です。 解1：ソートする。 ソートしてk番目の数字を取る方法です。 ソートにθ(nlogn)と見つけるのにθ(n)なので、T(n) ∈ θ(nlogn) 解2：選択ソート的解 リストから一番小さい数字を見つけ、取り出します。 これをk回繰り返します。 リストから最小値を見つけるのにO(n)なので T(n) ∈ O(kn)です。 解3：ヒープソートの利用 ヒープソートの構成にO(n)、取り出しにO(logn)
超大規模テキストにおけるN-gram統計 - Negative/Positive Thinking
はじめに 超大規模なテキストデータでのN-gram統計を取る場合、そもそもデータがメモリにのらなくてSuffixArrayを使ったカウントも無理だったりする。近似値でよい場合、効率的な方法があると知ったのでちょっとメモ＆試してみた。 与えられるデータ 大量のデータがストリーム形式で与えられるとする 高速にどんどん与えられる 例えば、データパケット監視やtwitterなど カウントしたいデータの種類が膨大 種類をメモリに保持するのが無理 ストリームデータにおける頻度カウント法 正確なカウントは難しいが、近似的に頻度カウントを行うことができる Sticky Sampling Algorithmは解釈が間違っているかもしれない Sticky Sampling Algorithm カウントする要素をサンプリングで選ぶ方法 保持するのは以下の2つのペアの集合 e : 要素(例えばN-gram) f
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
データマイニングで使われるトップ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
自然言語処理の教科書はもう全部FSNLP一冊でいいんじゃないかな - EchizenBlog-Zwei
自然言語処理の優秀なエンジニア各位にオススメ本を聞くと大抵FSNLP(Foundations of Statistical Natiral Language Processing)という答えが返ってくる。またブログ等でFSNLPを絶賛している方も多い。 私は自然言語処理は長尾本で満足してしまっていたのでFSNLPは読んでいなかったのだけれど､長尾本は現在入手困難ということもあって入手しやすい自然言語処理の教科書があるといいなと思っていたのでFSNLPを読んでみた。 その結果。自然言語処理の教科書はもう全部FSNLP一冊でいいんじゃないかな。という結論に至ったので全力でFSNLPを推薦する記事を書くことにした。 参考： ［を］FSNLP @ytoさん 自然言語処理の定番の教科書まとめ - 生駒日記 @mamorukさん Perl で自然言語処理 @overlastさん ざっと読んでみてFSN
【これはすごい】Twitter検索を3倍高速化した記事の翻訳 - nokunoの日記
これはすごい！ というわけでTwitter検索を3倍高速化したという記事を翻訳してみました。Twitter Engineering: Twitter Search is Now 3x Faster2010年春。Twitterの検索チームは、我々の増え続けるトラフィックに対応し、エンドユーザにとっての遅延を減らし、我々のサービスの可用性を向上させ、新しい検索の機能を素早く開発できるようにするため、検索エンジンを書きなおす作業を始めた。 その努力の一部として、我々は新しいリアルタイム検索をリリースし、検索のバックエンドをMySQLからLuceneのリアルタイム版に変更した。そして先週、我々はRuby-on-Railsに取って代わるフロントエンドをローンチした。我々がBlenderと呼ぶJavaサーバーである。我々はこの変更によって検索のレイテンシが3分の1になり、検索機能の開発を促進できるよう
Undo,Redoの実装って何十回もやってる気がする - あしあと日記
undo,redoの実装って何十回もやってる気がする。毎回同じパターンだ。undo,redoが登場するような編集ソフトは大体同じパターンに落とせる。フレームワークも作った。ブログにそういう内容を書きたいが面倒くさい。需要があれば面倒でも書くんだけどなあ http://twitter.com/youpychan/status/994486992 という発言をしたら何人か反応を頂いたので書いてみることにする。 需要があるなら書こう。undo,redoだけじゃなくてグラフィカルな編集ソフト全般の話をいつかまとめたいと思っていたので、ちょいとシリーズで書いてみようかとおもう http://twitter.com/youpychan/status/994636764 書こうと思う。 まずUndo,Redoについて。 Unod,Redoってみなさんどういう風に実装しているでしょうか？ 私はコマンドパタ
「ガベージコレクションのアルゴリズムと実装」という本を書きました。
gcbook, gcai, GCGCLoverのみなさん、お待たせしました。「ガベージコレクションのアルゴリズムと実装」の情報公開です。 書名：ガベージコレクションのアルゴリズムと実装 著者：中村 成洋／相川 光 監修：竹内 郁雄 ページ数：472ページ 本体価格：3,200円 発売開始日：2010年3月17日（水） ※地域・書店によって遅れることがあります ISBN：978-4-7980-2562-9 C3055 読み所 本書は次の2つのテーマを扱います。 1.GCのアルゴリズム（アルゴリズム編） 2.GCの実装（実装編） アルゴリズム編では、これまでに考案されてきた数多くのGCアルゴリズムの中 から、重要なものを厳選して紹介します。伝統的かつ基本的なものから、やや 高度なアルゴリズムを選定しています。GC独特の考え方や各アルゴリズムの特 性などを理解していただくのがアルゴリズム編の最大
実践プログラミング�T(2007年度)
本学科において，プログラミング能力を身に付けることは最優先事項といっても過言ではない． 3年生以上のほとんどすべての専門科目で（多かれ少なかれ）必要とされる． 特に4年生から始まる卒業研究では当然「友達のプログラムを参考にさせてもらう」などということはできない． つまり，今のうちに自分自身の力だけで組めるようになることが必須である． プログラミング能力を向上させる方法は，経験を積むことしかない． よって，本科目では毎回プログラミングの課題がある． 決しておろそかにしないこと． 欠課は極力しないこと．欠課時数が1/3を超えるとＤ評価となる． 電車の遅延などやむをえない事情がある理由も1/3内にカウントするし，1/3以上休んだ場合サボリが1回でも含まれていたら即アウトとなる． やむを得ず欠課した場合，配布プリントの入手や課題提出などは自己責任で対処すること． 遅刻については，出席
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
すごい乱数生成アルゴリズム「xorshift」 - Pashango’s Blog
みなさん、こんにちは、今回は乱数の話です。 特に複数機種でのコンシューマ機でゲームを開発をしていると、機種間で乱数値を統一するために乱数生成アルゴリズムを自作しますよね。 そこでよく使われるアルゴリズムが「線形合同法」です、内容は至って簡単で、以下の漸化式を使います。 A,B,Mは定数で、どの値が入るかは処理系依存です。 例えばUnixなどの処理系ではA=1103515245,B=12345,M=2147483647などが入ります。 C言語ですと以下のようになります。 static unsigned int x=1; void srand(unsigned int s) { x=s; } unsigned int rand() { x=x*1103515245UL+12345UL; return x&2147483647UL; } この「線形合同法」は計算が簡単で高速ですから、いろいろな環
PythonでA*(A-Star)アルゴリズム - Pashango’s Blog
今回はA*アルゴリズムをPythonでやってみます。 ゲームプログラマの間では、もはや常識となりつつある最短経路問題解決アルゴリズムです。 A*は、古典的手法である「ダイクストラ法」を改良したものです。 スタート地点からノードnを通ってゴールに辿り付くとき、最短距離をf(n)とすると、 f(n) = g(n) + h(n) とすることができます、g(n)は「スタートからノードnまでの最短距離」、h(n)は「ノードnからゴールまでの最短距離」です。 でも、最初から適切なg(n)とh(n)が判ってるなら苦労しませんよね。 だから、テキトーな予測値を使って、最短経路をある程度予測して効率的に経路探索をしてみようという事です。 テキトーな予測値を使った最短経路距離をf*(n)とすると f*(n) = g*(n) + h*(n) となります、f*(n)を求めるためにテキトーなg*(n)とh*(n)を
グーグルの検索順位を決定する4要素――重要度が増えたのは？ 減ったのは？ | Moz - SEOとインバウンドマーケティングの実践情報
各評価基準を簡単に分析してみると、こんな感じだ。 ホストドメインの信用度／オーソリティこの要素については、「Florida」アップデート（2003年11月）まで、ほとんどのSEO業者が真剣に考えていなかったと思う。でもFloridaアップデートの後、あっという間に大勢が知るところとなった。その後じわじわと影響力を強めてから、この2年で再び重要度が急上昇し、グーグルで高い検索順位を得る上で支配的な要因となった。 ただし、「キーワードに完全一致するドメイン名＋さまざまなルートドメイン名からの大量のアンカーテキスト」といった手法ではもう、Wikipedia、Amazon、BBCに時たま顔を出すページを凌ぐことはできない、と言っているわけじゃない。要は、こういったオーソリティサイトが一段と重んじられるようになったということだ。 僕らはつい数日前から、Technoratiのようなオーソリティサイトの
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
音声データのつくりかた 第5回 (まとめ)
houyhnhnmのエキセントリックらぶらぶ音声データ講座 第5回 ～ まとめ ～ 音声データ形式の比較 厳密な比較ではなく主観的な比較です。 結局どの音声データ形式がいいかという話になったときに、このくらいのイメージなら選びやすいんじゃないかなということです。実際は音源や実装に左右されます。 アンケート(2004年) http://www.hydrogenaudio.org/forums/index.php?showtopic=18634 不可逆圧縮 総論 各論 音質 速度 シェア 可逆圧縮 総論 各論 効率性 シェア リンク集 の順で書きます。 1不可逆圧縮 普通はMP3を使います。 他の不可逆圧縮形式はMP3くらいサイズを小さくしつつMP3より質を重視する場合に使います。 総論 広く使われておりほとんどすべてのハードウェアが対応している ISOに規格化されMPEGの仕様に含まれている
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
TechCrunch | Startup and Technology News
愛人学芸 | 探求者のブログサイト
Levitated | Levitated Daily Source, the good source
IdentFavIcon – Get this Extension for 🦊 Firefox (en-US)