長さ制限つきのハフマン符号化(The Coin Collector's Problem) - sileのブログ
冬休みの取り組みとして、ZIP*1圧縮/解凍器を作ってみることにした。 ZIPで使われている圧縮アルゴリズム(圧縮フォーマット?)は、DEFLATEアルゴリズムと云って、簡単に云えばLZ77とハフマン符号化を組み合わせたもののようだ。日本語版仕様(RFC1951) ハフマン符号化は、以前に簡単なものを実装したことがあるが、DEFLATEアルゴリズムで使用するハフマン符号化では、一般的なそれとは異なり、(符号化される)各コードを表現するビット列の長さに制限(15ビットまで)を付けられる必要があるらしい。 なので今回はまず、その長さ制限付きのハフマン符号化アルゴリズムの実装を試してみることにする。 The Coin Collector's Problem 参考にしたのは、以下のWikipediaの記事。 Package-merge algorithm 編集日時: 2007/06/23 00:2
Minimal Perfect Hash-Tables in Common Lisp
Recently, my twitter pal @ifesdjeen wrote a line that resonated with me: "Looks like it's easier for people to read 40 blog posts than a single whitepaper." And although he used it in a negative context, I recognized it as a very precise (and, actually, positive) description of what a research engineer does: read a whitepaper (or a dozen, for what it's worth) and transform it into working code and
フロイドの循環検出法 - Wikipedia
フロイドの循環検出法（英: Floyd's cycle-finding algorithm）とは、任意の数列に出現する循環を検出するアルゴリズムである。任意の数列とは、例えば擬似乱数列などであるが、単方向連結リストとみなせる構造のようなもののループ検出にも適用できる。ロバート・フロイドが1967年に発明した[1]。「速く動く」と「遅く動く」という2種類のインデックス（ポインタ）を使うことから、ウサギとカメのアルゴリズムといった愛称もある。 グラフの最短経路問題を解くワーシャル–フロイド法とは（同じ発案者に由来するので同じ名前がある、という点以外は）無関係である。 アルゴリズム[編集] 単方向連結リストのループ検出なども典型的なのであるが、形式的（フォーマル）な説明には数列のほうが向いているのでここでは擬似乱数列生成器の例で説明する。ポラード・ロー素因数分解法などで擬似乱数列生成器の分析が重
Sorting algorithms used in the CL implementations
Jorge Tavares Notes Personal bits around AI, Programming and other things I might find interesting Which sorting algorithm should one implement when developing a program? The best answer is probably none. Use the sort provided by your system/library/etc. Unless you know your input data has some special properties that you can take advantage of, the provided sort should be enough for your needs and
ソート済みのリストに対する破壊的マージソートの改良 - sileのブログ
以前に載せたマージソート(をベースとしたもの)をSBCL(1.0.58)にコミットしてくれたPaul Khuongさんが、こんな記事を書いていて、なるほどなー、と思ったので、表題に関係する部分を参考にさせて貰って変更前後での比較を行ったメモ。 オリジナルのマージソート まず、SBCL(1.0.58)のリストに対する破壊的マージソートの実装*1: ;; 二つのソート済みリストのマージ関数 (declaim (inline merge-lists*)) (defun merge-lists* (head list1 list2 test key &aux (tail head)) (declare (type cons head list1 list2) (type function test key) (optimize speed)) (macrolet ((merge-one (l1 l
BloomFilter - sileのブログ
オンラインで読める『Real World Haskell』という本の目次を眺めていたら、BloomFilterという言葉を発見。 どうやらデータ構造の一種らしいが、聞いたことがなかったので調べてみた(Wikipediaで)。 結果、セット(集合)を表すためのデータ構造だということが分かった。 偽陽性*1はあるが、メモリ使用量が凄く少なくて済むのが特徴で、例えば-目安として、だが- 要素数が100万のセットなら1MB程度のメモリで表現できるようだ。ちなみに、集合中の要素の列挙や削除といった操作は出来ない 実装としては、衝突を考慮しない and 要素を格納しないハッシュ、といった感じ。 BloomFilterの初期化、要素追加、帰属判定を行うcommon lispのプログラムを書いてみたので、下に載せる。 ;; 構造体: ビット配列と要素の追加・判定に用いるハッシュ関数のリストを持つ (def
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
algorithms and data structures term1
Reddit - Dive into anything
似ている文字列を探す - umeajiの日記
Priority Queues in CL
GitHub - ruricolist/cl-bloom: Simple Bloom filters in Common Lisp with efficient hashing.
Lemonodor: Bloom Filters
A packrat parser for Scheme
http://dev.lshift.net/tonyg/json-scheme/
tony packrat.ss - Google 検索
f-zipper-with-pipe-forward