第8回 遅延評価の仕組み
これまでの回で，何度か遅延評価の持つ性質について語ってきました。皆さんの頭の中には，すでに遅延評価に対して「なんとなくこういうものだ」という漠然としたイメージができていると思います。 多くの場合にはそうした漠然としたイメージだけでも十分なのですが，それでは困る場合もあります。例えば，プログラム全体の最適化（optimization）のために関数やデータ構造の効率化（efficiency improvement）を図ろうとする場合，遅延評価に対する理解がなければ完全に手探りで行うしかありません。 残念ながら，前回のIOモナドと同様に，遅延評価を実現するための仕組みもまた，Haskell標準ではほとんど触れられていません。実装のための余地を残しておくためです。ただ，IOモナドの場合と同様に，「このようなモデルで，このような性質を持つ」という仕様外でのだいたいの合意は存在します。 そこで今回は，
Bep: 大規模コレクション向けの連想配列
English 概要 Bepは大規模なコレクションからなる連想配列を扱うためのライブラリです．連想配列は文字列からなるキーを利用して任意のオブジェクトを登録・参照できるデータ構造です．C++ではSTL map, hash_mapなどが知られていますが，数千万から数億個のコレクションを処理する場合，使用メモリ量が非常に大きくなってしまう問題点がありました．Bepは内部に最小完全ハッシュ関数を利用し，従来の実装に比べ少ない作業領域量でコレクションを保持します．キー自体を除けば，1keyあたりの作業領域量は約3bitです（全体では，(keyを全てつなげた長さ) + (3/8*key種類数)バイト必要です） ダウンロード Bepはフリーソフトウェアです．BSD ライセンスに従って本ソフトウェアを使用,再配布することができます. bep-0.01.tar.gz: HTTP 更新情報 2007-
A Hash Function for Hash Table Lookup
I offer you a new hash function for hash table lookup that is faster and more thorough than the one you are using now. I also give you a way to verify that it is more thorough. All the text in this color wasn't in the 1997 Dr Dobbs article. The code given here are all public domain. Over the past two years I've built a general hash function for hash table lookup. Most of the two dozen old hashes I
高速かつ省メモリなbit vector「sucBV」を作る
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するデータ構造は「操作付きbit vector（SUCcinct Bit Vector:sucBV）」です。sucBVは、圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。STLのvector<bool>と同様に、bit列情報B[0....n-1]を保存します。このbit列情報は前もって与えられ、変更が無いことを前提とします。sucBVは、次の二つの操作を定数時間でサポートします。 rank(p,bit)――B[0...p]中のbit（bitは1
クラスタリング (クラスター分析) - Toshihiro Kamishima
クラスタリング (clustering) とは，分類対象の集合を，内的結合 (internal cohesion) と外的分離 (external isolation) が達成されるような部分集合に分割すること [Everitt 93, 大橋 85] です．統計解析や多変量解析の分野ではクラスター分析 (cluster analysis) とも呼ばれ，基本的なデータ解析手法としてデータマイニングでも頻繁に利用されています． 分割後の各部分集合はクラスタと呼ばれます．分割の方法にも幾つかの種類があり，全ての分類対象がちょうど一つだけのクラスタの要素となる場合(ハードなもしくは，クリスプなクラスタといいます)や，逆に一つのクラスタが複数のクラスタに同時に部分的に所属する場合(ソフト，または，ファジィなクラスタといいます)があります．ここでは前者のハードな場合のクラスタリングについて述べます．
Ruby on Railsの「えせMVC」の弊害
先日のエントリーでも少し触れたが、Ruby on Railsの最大の問題点は、それが持つ「一見そのフレームワークがMVCの形をとりながら、MVCの最も大切なところを外している『えせMVC』である」点にある。MVC（Model View Controller）がなぜ必要かを根底の部分でちゃんとと意識せずにRailsアプリケーションを作ると、後々ひどい目に会うので注意が必要である。 その意味では「RailsでMVCを学ぶ」などもっての他だし、「JavaにもRailsと同じようなフレームワークを作って業務用アプリの開発を効率化しよう」などという発想もとても危険である。 ということで、今日はまずはMVCの解説から。 MVCの発想の根底には、「モジュール化と情報の隠蔽により、プログラムがスパゲッティ化するの（コード間の相互依存関係が複雑に入り込んでしまってにっちもさっちも行かない状態になること）を避
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
次元が高い場合に関してのsimhashの計算 - tsubosakaの日記
最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介してあったので少し解説を行ってみる。ちなみに以下の解説では低次元のビットベクトルに縮約した後にハミング距離が近いものをどうやって探索するかについては述べないです、それに関しては[1],[2]を参照してください。 ちなみに自分が実装したのは各ビットごとに次元に対するハッシュ関数を定義して計算する方法でした。この方法だと以下で開設する手法よりもf倍の回数ハッシュ関数を計算する必要があるので実行時間が割とかかる。 解説 simhash[3](文献によってはLSHと呼ぶこともある[2])は次元削減の手法の一つで、高次元のデータを低次元のビット
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.pavis.org/essay/multidimensional_scaling.html