高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
svartalfheim.jp - 配列を少ない仕事量でシャッフルするFisher-Yates法
Fisher-Yates法は配列をシャッフルする際に用いる一般的なアルゴリズムのようです。 Wikipedia：Fisher-Yates法（英語） Javascriptで書くと（Wikipediaより抜粋） var n = a.length; for(var i = n - 1; i > 0; i--) { var j = Math.floor(Math.random() * (i + 1)); var tmp = a[i]; a[i] = a[j]; a[j] = tmp; } ActionScript（jp.ferv.blogさんより） var i:int = array.length; var j:int,tmp:Object; while(i){ var j = Math.floor(Math.random()*i); var tmp = array[--i]; array[i]
なぜBTreeがIndexに使われているのか - maru source
この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル 1 2 3 4 5 CREATE TABLE user ( id INT UNSIGNED NOT NULL AUTO_INCREMENT, name VARCHAR(255) NOT NULL, PRIMARY KEY (id) )ENGINE=InnoDB; idカラムにIndex(PRIMARY KEY)を張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう？？ Indexとはその名の通り索引を意味します。特定のカラム
[JavaScript] Nクイーン問題（ノンプリエンプティブマルチタスク風）
有名な Nクイーン問題を解く JavaScript です。 アルゴリズムは、単純なバックトラックのみです。 ブラウザの動作をロックせずに、 処理状況をアニメーション表示させている点がミソです。 ノンプリエンプティブマルチタスク風に定期的に処理をブラウザ側に返すようにクラスを組むことで、 複数の処理を並列動作させる習作です。 盤の大きさ（デフォルトは8マス＝8クイーン問題）を入力して、[開始] ボタンを押して下さい。 盤の大きさ： マス 0 個の解を検出しました。 [開始] ボタンを押して下さい。 アルゴリズム 深さ優先で、単純なバックトラックのみを使用しています。 また、再帰呼び出しもせずに、ぐるぐるループしています。 とりあえずなので、解の回転／反転すら使っていません。 試してませんが、JavaScript でビットマックを作ってマッチングさせると遅くなりそうですね。 上下反転くらいなら
自動微分 ≪フォワード・モード≫ - d.y.d.
23:21 11/12/22 今年読んだ面白コンピュータサイエンス論文紹介カレンダー 第 n (1<n) 週目モードです。 ☆ 「難しい問題」 ☆ 「名のない関数」 ☆ 「演算のせいしつ」 「難しい問題」 [5] R. Impagliazzo and L. A. Levin. "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random." FOCS 1990. ランダム生成に興味があります。 パズルゲームを作りました。 さて、手強い難易度の面データを無限にランダム生成するにはどうすればいいだろう。 プログラミングコンテストの問題を作りました。 さて、自動チェック用のテストデータをランダム生成するにはどうすればいいだろう。 適当なランダム生成では、簡単なケースばっかり作られてしまい 嘘解法 に突
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
