2013年03月10日

Algorithm - Ruby 2.0 や Haskell の遅延リストを JavaScript で

これを書いたら欲が出て来たので。

ちなみに「プロになるためのJavaScript入門」は参考書にした一冊。この場を借りて献本御礼。

  続きを読む

Posted by dankogai at 23:45Comments(0)TrackBack(0)

2013年03月08日

2013年02月18日

perl - Digest::SipHash released

cpan

Digest::SipHash というモジュールをリリースしたのでおしらせします。

  続きを読む
Posted by dankogai at 00:30Comments(0)TrackBack(0)

2013年02月14日

algorithm - PATRICIA に一番似合う姓は Crit-Bit かも

「高速文字列解析の世界」を読んだら、熱がぶりかえしてきたので。

ハッシュテーブルや平衡二分木に代わる連想配列を実装するにはどうしたらよいのかという、知恵熱が。

  続きを読む
Posted by dankogai at 04:30Comments(0)TrackBack(0)

2012年09月09日

ブラウザー上でJPEG圧縮して非可逆性を体感してみる

asin:4797344377
詳解 画像処理プログラミング

C言語で実装する画像処理アルゴリズムのすべて
昌達慶仁

GIMPでJPEGの蚊を退治して"PNG"化する」「javascript - で bilateral filter (選択的ガウスぼかし)を実装してみた」の反響で、「JPEGのqualityを100に設定すればいいんじゃね?」という誤解がかなり見受けられたので。

実際に体験していただければいいかと。

  続きを読む
Posted by dankogai at 16:00Comments(0)TrackBack(0)

2012年09月06日

javascript - で bilateral filter (選択的ガウスぼかし)を実装してみた

選択的ガウスぼかし」がえらい気に入ったので、アルゴリズムの学習も兼ねてJavaScriptでやってみたら思いの他使い物になりそうということで。

  続きを読む
Posted by dankogai at 18:03Comments(0)TrackBack(1)

2012年02月10日

博士の異常なアルゴリズム、または私は如何にして心配するのを止めて線形探索を愛するようになったか

これはちょっとプログラマーといふ生物を買いかぶりすぎてると思います。

プログラマへの誤解 | pineapple blog
プログラムを書かない人がプログラムを読んだときにする良くある間違いは,ああこんなプログラムなら自分にも書けそうだと思うことだ.プログラムは何百万とある可能性からたったひとつ(は言い過ぎにしてもわずかながら)の正しい方法を残したものであり,この捨てる能力こそがプログラマの実力だから.

少なくとも、プロ2グラマーの場合は。

  続きを読む
Posted by dankogai at 13:00Comments(0)TrackBack(0)

2012年01月23日

algorithm - JPEGminiの仕組みを推理する

JPEGの仕組みをおぼろげに知っている人ほど、むしろこれみて「ありえない」と思ったのではないのでしょうか。

でもよーく考えてみると、これでいけるという方法を発見というか再発見したので。

  続きを読む
Posted by dankogai at 19:30Comments(1)TrackBack(0)

2012年01月22日

algorithm - 基数木 + 平衡二分探索木 = 三分探索木

最有力候補は、これかも。

404 Blog Not Found:algorithm - Patricia Trie (Radix Trie) を JavaScript で
最近のTrie研究の傾向は、要素の動的変更が自在にできる一般向けのものではなく、一旦作成したら要素の追加と削除が困難な代わりにものすごくコンパクトになる、簡潔データ構造の応用手段の方に偏っていると素人目に感じるのですが、そろそろJudyたんのごとくハッシュテーブルとガチで闘うとか、逆に両方のいいとこどりを狙うとかという方向にも行ってくれないかなあ…
  続きを読む
Posted by dankogai at 16:36Comments(0)TrackBack(0)

2012年01月17日

Algorithm - 連想配列の実装としてのハッシュはオワコン?

つまり「終わったコンテナ」。

以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。

もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。

  続きを読む
Posted by dankogai at 11:45Comments(0)TrackBack(0)

2012年01月16日

Algorithm - Suffix Array を JavaScript で再発明してみた

asin:4774148318
WEB+DB 総集編

[Vol. 1〜60]

もう10年以上前に某社のCTOだったころ、Suffix array(接尾辞配列)の解説を毎週の技術者ミーティングでしたら一名を除いて「ハァ?」状態だったことを思い出しつつ。

  続きを読む
Posted by dankogai at 16:30Comments(0)TrackBack(0)

2012年01月13日

algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な

言い出しっぺの法則。

404 Blog Not Found:algorithm - bucket sort - 比較しなければソートは相当速い
これほど素晴らしいアルゴリズムなのに、なぜlibcやLL言語の組み込みとして用意されていないのでしょう?
https://plus.google.com/103748274114027132441/posts/VmpVES1hFds - Shiro Kawai さんのコメント
他のソートアルゴリズムのような汎用のライブラリになってないのは、目的によってチューニングポイントが違って、それらにすべて対応するのを書くよりはその都度書いた方が簡単だから、かなあ。
  続きを読む
Posted by dankogai at 08:00Comments(0)TrackBack(0)

2012年01月11日

algorithm - bucket sort - 比較しなければソートは相当速い

絶賛風邪こじらせ中につきコードと戯れることに。

新ソートアルゴリズム「配列挿入ソート」だ! - hp12c
その名も「配列挿入ソート」!

すでに突っ込み入ってるけど、それ、もしかしたら人類最古のアルゴリズムだから。

  続きを読む
Posted by dankogai at 07:00Comments(0)TrackBack(0)

2012年01月08日

algorithm - ソート済み配列をソートしなおすべからず

ぐぬぅ。男子ゆえ女子をこじらせようがないとはいえ、風邪が普通にこじれている。

というわけでアルゴリズムのことなどつらつら考えていた。

要はソートすべき配列中にすでに存在する秩序を活用するのがtimsortなのだと。

だけどすでにソート済みの配列を活用するなら、こういう方法もありではというわけでentry。

  続きを読む
Posted by dankogai at 20:30Comments(0)TrackBack(0)

2009年04月29日

algorithm - correction - 最近点検索

これ、「素直な解答」の方が間違っている。

  続きを読む
Posted by dankogai at 07:45Comments(0)TrackBack(1)

2008年03月16日

アルゴリズム - 合コンの効用を最大化する

実は、1対1という制約を課せば、全体として最も満足が行く縁結びを決定するアルゴリズムがすでに存在する。

金融日記:東京 - ニューヨーク - ロンドン - パリ 世界の先進国の恋愛シーンで今起こっていること
これから紹介する計量経済学モデルは、あらゆる社会科学の理論の中でも最もエレガントでそしてシンプルなもののひとつだと思います。
  続きを読む
Posted by dankogai at 19:00Comments(9)TrackBack(0)

2007年12月11日

アルゴリズム百選 - ユークリッドの互除法

今回は、ユークリッドの互除法を取り上げます。

  続きを読む
Posted by dankogai at 16:30Comments(6)TrackBack(1)

2007年12月09日

アルゴリズム百選 - 迷ったらbenchmark

この話題、以下の答えとしても適度なのでそのまま。

アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org
「O()が小さいからといって速いとは限らない」が抜けている。
  続きを読む
Posted by dankogai at 03:30Comments(6)TrackBack(2)

2007年12月06日

アルゴリズム百選 - 値と参照

今回は値と参照について取り上げます。

  続きを読む
Posted by dankogai at 15:30Comments(5)TrackBack(2)

2007年12月05日

アルゴリズム百選 - 用語の定義、またはその欠如

いい機会なのでお断りしておくと、

O(1)というのはご機嫌に速いということ? by Inquisitor
たとえばn桁の足し算は、2つの整数および結果が適当なレジスタに収まるうちは、1クロック(程度)でできるのでご機嫌に速いわけですが、O(1)というわけではもちろんなく、O(n)だと考えるのがふつうでしょう

それが「ふつう」だという人向けの本にするつもりはありません。

  続きを読む
Posted by dankogai at 03:00Comments(8)TrackBack(2)

2007年12月04日

アルゴリズム百選 - ベキ乗はO(1)でOK?

これ、Hyukiさんをはじめ多くの方が疑問に思っていらっしゃるようなので、いまのうちに答えておきましょう。blogで書く以上、書く順番は順不同で構わないのですし。

アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org
フィボナッチ数列の一般項を求める式を使ったときってO(1)って言えるのだろうか?
  続きを読む
Posted by dankogai at 23:00Comments(8)TrackBack(3)

アルゴリズム百選 - 二分探索(binary search)

今回は二分探索を取り上げます。

  続きを読む
Posted by dankogai at 08:30Comments(10)TrackBack(2)

2007年12月03日

アルゴリズム百選 - ハッシュを再発明する

(実はハッシュを使って)配列を再発明したところで、今度は配列を使ってハッシュを再発明してみます。

  続きを読む
Posted by dankogai at 11:15Comments(2)TrackBack(0)

アルゴリズム百選 - 配列を再発明する

アルゴリズムを理解するのに最適な方法は、すでに当たり前のように使われている仕組みを、もう一度時分の手で作ってみることです。ここでは、配列に関するアルゴリズムを再実装してみます。

  続きを読む
Posted by dankogai at 04:00Comments(7)TrackBack(1)

2007年12月02日

私ごときがアルゴリズム本を書くことにした訳

アルゴリズムを評価するのは、プロにとっても難しい。

アルゴリズム - 186::Diary
* あとメモ化のときの最初の呼び出し回数の評価も間違ってるよね. 1回目は関数をナイーブな実装で評価するから.

ところが、この下りに関して間違いなのは私の元発言ではなく、この突っ込みの方なのである。

  続きを読む
Posted by dankogai at 04:00Comments(0)TrackBack(0)

2007年11月28日

アルゴリズム百選 - フィボナッチ数列にO()を学ぶ

404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、#bookmarksもいくとは。

とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。

  続きを読む
Posted by dankogai at 18:00Comments(13)TrackBack(8)