CPUに適度に間違わせることで節電する技術
ラビン-カープ文字列検索アルゴリズム - Wikipedia
ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種[1][2]。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出
Googleアルゴリズム変更：良サイトに「とばっちり」 | WIRED VISION
前の記事 「3DS講演と同時に新iPadイベント」の意味 58カ国からの仮想合唱、TED会議で大好評(動画) 次の記事 Googleアルゴリズム変更：良サイトに「とばっちり」 2011年3月 3日 メディア コメント： トラックバック (0) フィードメディア Ryan Singel 米Google社は2月24日(米国時間)、検索アルゴリズムを更新した。コンテンツの質が低いサイトを検索結果の上位から取り除くのが目的だったが、すべてがうまく行ったわけではなかった。 SEOソフトを作る独Sistrix社の分析によると、良質でないとされるサイトの多くが格下げになったが、その一方で、「コンテンツ工場」と呼ばれる『Demand Media』(日本語版記事)はほとんど影響を受けなかった。 さらに、良質なサイトの一部で「とばっちり」を受けたところも多い。 Apple社の話題を扱うニュースブログ『Cult
ビタビアルゴリズム - Wikipedia
ビタビアルゴリズム（英: Viterbi algorithm）は、観測された事象系列を結果として生じる隠された状態の最も尤もらしい並び（ビタビ経路と呼ぶ）を探す動的計画法アルゴリズムの一種であり、特に隠れマルコフモデルに基づいている。観測された事象系列の確率計算のアルゴリズムである 前向きアルゴリズム（英: forward algorithm）も密接に関連している。これらのアルゴリズムは情報理論の一部である。 このアルゴリズムには、いくつかの前提条件がある。まず、観測された事象と隠されている事象は1つの系列上に並んでいる。この系列は多くの場合時系列である。次に、これら2つの並びには一対一の対応があり、1つの観測された事象は正確に1つの隠されている事象に対応している。第三に、時点 での最も尤もらしい隠されている事象の計算は、 での観測された事象と での最も尤もらしい隠された事象の系列のみに依
【レポート】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
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
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)で判定できる。たとえば各格子点にあらかじめどの点が一番近いかを記録しておき、それを読
計算幾何学に出会う - 道化がつぶやく
最近棒探索について調べた 今作っている Ajax システムの中に 1000個オーダーの頂点を、マウスで選択できる仕組みを入れたくて 複数の点の中からマウスに一番近い点を探すアルゴリズムを調べていた なかなかうまい方法が見つからない。。。 でも、点の集合から最近点を見つけるなんて、よくありそうだしなぁ。。 絶対に何かジャンルがあるはずに違いない。。。 そう思い、はてなの人力検索 http://q.hatena.ne.jp/1239891135 本当に、たくさんの回答・アドバイスをいただきました！！ ブクマコメより paella 勉強, アルゴリズム 良い質問に良い回答（コメント欄も）。あとはこれが学校の宿題でないことを祈るのみ。 2009/04/19 学生ではないので、ご安心くださいｗ dan kogai さんにも取り上げていただいた！ http://blog.livedoor.jp/dan
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(
About - Project Euler
About Project Euler What is Project Euler? Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. The motivation for starting Project Euler, and
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://e0166nt.com/blog-entry-629.html