bitsliceによる超高速ビット演算 : DSAS開発者の部屋
bitslice とは Hack the Cell '09 に参加して知った、Cellに限らず一般的に使えるビット演算の高速化手法について紹介します。 Bitslice と呼ばれる手法では、ビット順を90度回転します。言葉で説明するよりもコードを見たほうが早いので、回転させるコードの例を見てください int x[32], y[32]; // x が元のデータ、y が回転後のデータ. for (int i = 0; i < 32; ++i) { int t = 0; for (int j = 0; j < 32; ++j) t |= ((x[j] >> i) & 1) << j; // x[j] の i ビット目を y[i] = t; // y[i] の j ビット目にする } この変換をすることで、y[0] には x[0] - x[31] の最下位ビットが、 y[1] には 2番目のビット
blog.katsuma.tv
greeさんで開催されたKey Value Store勉強会に行ってきました。 時間にして4時間超え、内容も国内のKey-Value Storeなソフトウェアの最前線の話ばかりで相当なボリューム。以下、メモってたのを残しておきたいと思います。（誤字、脱字、内容に誤りを含むものなどありましたらお伝えください）また、発表者の方やプロダクトについて、ざっくり調べてURL見つけられたものについてはリンク張っています。 森さん / 末永さん groonga Sennaの後継エンジン 融通が効かないのがSennaのデメリット スコア算出式のカスタマイズなど Sennaの転置索引 索引の構成部品を自由に組み合わせて使える APIもいろいろ QL DB Low Level memcached互換のkey-value store バイナリのみ対応 計測 クライアント memstorm-0.6.8 mem
大規模データ処理のための行列の低ランク近似 -- SVD から用例ベースの行列分解まで -- - 武蔵野日記
id:naoya さんのLatent Semantic Indexing の記事に触発されて、ここ1週間ほどちょくちょく見ている行列の近似計算手法について書いてみる。ここでやりたいのは単語-文書行列(どの単語がどの文書に出てきたかの共起行列)や購入者-アイテム行列(どの人がどの本を買ったかとか、推薦エンジンで使う行列)、ページ-リンク行列(どのページからどのページにリンクが出ているか、もしくはリンクをもらっているか。PageRank などページのランキングの計算に使う)、といったような行列を計算するとき、大規模行列だと計算量・記憶スペースともに膨大なので、事前にある程度計算しておけるのであれば、できるだけ小さくしておきたい(そして可能ならば精度も上げたい)、という手法である。 行列の圧縮には元の行列を A (m行n列)とすると A = USV^T というように3つに分解することが多いが、も
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
アルゴリズムとデータ構造演習
本演習の目的は、プログラミング言語C及びSchemeの基礎を習得し、 それらの言語を通じて、講義「アルゴリズムとデータ構造」の理解を深めることにあります。 重要なお知らせ 特に重要な連絡事項はここに掲載されます。 課題について 課題には、A課題とB課題があります。（課題番号の末尾が種類を表します。） B課題が基礎的な課題で、A課題が発展的な課題となっています。 B課題を全問解くことが、単位取得の目安です。 C入門第1回（10月10日） C入門第2回（10月17日） C入門第3回（10月24日） C入門第4回（10月31日） C第1回（11月7日） C第2回（11月14日） C第3回（11月21日） C第4回（11月28日） C第5回（12月5日） Scheme第1回（12月12日） Scheme第2回（12月19日） Scheme第3回（1月9日） Scheme第4回（1月16日） C補講
ウノウラボ Unoh Labs: 圧縮アルゴリズム
尾藤正人(a.k.a BTO)です コンピュータを使ってる方ならいつもお世話になってるデータ圧縮。 gzipのようなツールで意識して圧縮していることもあれば、フォーマット自体に圧縮機能が備わっていて、意識しないで使っているケースもあるかと思います。 毎日のようにお世話になってるデータ圧縮ですが、その原理を知らない方も多いのではないでしょうか。 かくいう僕自身も、つい最近までは全く知りませんでした。 そこで、先日の社内勉強会で圧縮アルゴリズムについて一通りやってみました。 その資料を公開します。 僕も専門家ほど詳しいわけでもなく、単に勉強してみただけのくちなので、いろいろおかしな点もあるかもしれません。 何かありましたら、いろいろご指摘いただければと思います。 プレゼン資料の作成にはデータ圧縮法概説を大いに参考させていただきました。 参考っていうか、ほとんどそのまんまです。 ぶっちゃけデータ
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GCアルゴリズム詳細解説 日本語の資料がすくないGCアルゴリズムについて詳細に解説します トップページページ一覧メンバー編集 GC 最終更新： author_nari 2010年03月14日(日) 20:47:11履歴 Tweet このWikiが目指す所 GCとは？ GCを学ぶ前に知っておく事 実行時メモリ構造 基本アルゴリズム編 Reference Counter Mark&Sweep Copying 応用アルゴリズム編 IncrementalGC 世代別GC スナップショット型GC LazySweep TwoFinger Lisp2 Partial Mark and Sweep -Cycle Collection- Mostly Parallel GC train gc MostlyCopyingGC(Bartlett 1989) TreadmillGC(Barker 1992) 補足
mixi Engineers’ Blog » おすすめマイミクシィ／コミュニティ
はじめまして。mixi開発部・運用グループでアプリケーションの運用を担当しているmikiokatoといいます。週に一日興味があることについて研究や開発ができるOneDayFree の制度を使って開発し、12月25日にリリースしたインディーズ機能「おすすめ マイミクシィ／コミュニティ」について書いてみたいと思います。 おすすめ マイミクシィ／コミュニティとは マイミクシィやコミュニティのリンクを分析して、マイミクシィになる可能性の高い人や興味がありそうなコミュニティをおすすめします。膨大な情報の中から検索などでユーザーにいろいろと探してもらうよりも、データを分析して興味がありそうなものをシステムからおすすめする試みです。 実際の画面はこちらです。 人によって精度は差があるので、結果がいい場合もよくない場合もありますが、マイミクシィやコミュニティの発見につながればと思います。では、どういった仕
アルゴリズム百選 - 値と参照 : 404 Blog Not Found
2007年12月06日15:30 カテゴリアルゴリズム百選 アルゴリズム百選 - 値と参照 今回は値と参照について取り上げます。 突然ですが問題です。以下のJavaScriptプログラムを実行すると、何と表示されるでしょうか? プログラム: var a = [0, 1, 2, 3]; var b = a; b[0] = 'zero'; p(a); 出力: エラー: 答えは、"zero, 1, 2, 3"です。しかし、なぜaを直接変更していないのにaの中身が変わっているのでしょうか? ここで、二行目に注目してみます。ここでは変数bに変数aを代入しています。変数aは配列です。ここだけ見ると、内部で起こっているのは以下のようなことに見えなくもありません。 array b -+ array b -+ | 0 | | 0 | | 1 | = | 1 | | 2 | | 2 | | 3 | | 3 |
404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
404 Blog Not Found:アルゴリズム百選 - 配列を再発明する
2007年12月03日04:00 カテゴリアルゴリズム百選 アルゴリズム百選 - 配列を再発明する アルゴリズムを理解するのに最適な方法は、すでに当たり前のように使われている仕組みを、もう一度時分の手で作ってみることです。ここでは、配列に関するアルゴリズムを再実装してみます。 ここでは、MyArrayというオブジェクトを作って、それに配列としての機能を持たせることにします。まずは基本的な操作ができるようにしておきます。 残念ながらRubyなどと異なり、JavaScriptでは[]を演算子として再定義することは出来ないので、ここではget()メソッドとset()メソッドをその代わりとして用意することにします。また、利便性を考えて、組み込みのArrayに変換するtoArray()メソッドも用意しておくことにしましょう。 function MyArray(){ this.size = argum
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ : 404 Blog Not Found
2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
ソート処理時間、選ぶアルゴリズムでこんな差が！ ― ＠IT自分戦略研究所
ソート処理時間、選ぶアルゴリズムでこんな差が！：いまから始めるアルゴリズム（2）（1/2 ページ） 連載第1回「『＋1』だけで四則演算をするには？」に引き続き、プログラミングにおけるアルゴリズムの重要性と面白さを紹介したいと思います。例としてプログラミングで頻繁に使われる並べ替えと検索のアルゴリズムを取り上げ、それぞれがどういった処理を行っているのか考えてみましょう。 同じ問題でも解き方（アルゴリズム）によってかなりの速度の違いが出てくる可能性があることは、前回紹介したとおりです。今回は代表的な並べ替えのアルゴリズムを基にプログラムを作成し、実行にかかった時間を測定して、具体的な処理速度の違いをお見せしようと試みています。 プログラミング言語では、すでに並べ替えの仕組みが用意されていることが多いので、このアルゴリズムをあまり意識していない人もいるのではないでしょうか。しかし、すべてのプログ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
11年前のPSソフト『カルネージハート』に教わった私の原点と言えるプログラムの基礎*ホームページを作る人のネタ帳
