中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
CPUはオワコン - きしだのHatena
FPGAでCPUを組んでると、フェッチ部やデコーダ部で足し算や掛け算をしようとして、そんなことしたらCPUの意味ないなーと思ってしまうことがありました。 で、よく考えたら、FPGAでロジックを組むならCPUの意味はないんです。 だいたい、ひとつの処理実行するのに何クロックかかってんですか！と。 CPUでは、計算効率をよくするためにパイプラインという仕組みが使われています。 最近では、18段とかのパイプラインもあるようです。 ここで、18段のパイプラインのうち、実際に計算を行うのは2段か3段だったりします。残りの15段くらいは、命令や計算結果を読んだり書いたりしているだけです。 このパイプラインも、ほとんどはメモリの読み書き、それも命令の読み込みに多くが使われます。 であれば、CPUにしなければ、18段全部計算に使えるんじゃね？という話になりますね。 決まりきった計算を行うのに、いちいちメモ
モナドへの近道・Haskell からの寄道
モナドへの近道・Haskell からの寄道 中村翔吾∗ 2007 年 1 月 26 日 本稿の趣旨 圏論のモナドとプログラミング言語 (Haskell) の間にはどの様な関係があるのか．この問いに答えるた めには，当然だが，少なくともモナドが理解できる程度に圏論を知らなければならない．本稿は，圏論の知 識が全くないところから，モナドを理解するまでの，最短コースの道のりをたどり (第 1,2 章)，これを前 提にして Haskell と圏論との関係を考察する (第 3 章)．読者には圏論の知識を要求しないが，Haskell の 文法の基本的な理解は前提としている．また，圏論に関しては，あくまでも「モナドへの最短コース」なの で，米田の補題，普遍性，コンマ圏，極限などの重要な概念は解説していない． 1 基礎知識の準備 定義 1 (メタグラフ metagraph) メタグラフは射 (arrow
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
