2006-05-03
Forbes の記事 [Forbes] によれば，現在， YouTube 社が帯域プロバイダーに対して支払っている通信料は，１ヶ月あたり 100 万ドル（約１億円）を越えるとされる。そのうちの多くは， YouTube のバックボーンを支えるプロバイダーである Limelight Networks 社 [Limelight] に流れ込んでいるものと推測される。
先月，ベンチャーキャピタルから新たな増資を受けたことにより， YouTube 社への総投資額は遂に 1,000 万ドルを越えることとなった [YouTube] 。その回収の目論みについては未だ不明な部分が多い。
インターネット上でのビデオ配信サービスは，音楽配信サービスに続く新たな市場の創出として，以前から注目が集められており，最近では YouTube の台頭をはじめとして様々な騒動が引き起こされているものの，未だ本格的な市場の形成には至っていない感がある。この騒動を経て，最も初めに儲けを手にすることになるのは，果たして誰なのだろう？
ゴールドラッシュで最も儲けたのは，ショベルを売る人々に違いない ― MIT Advertising Lab の Vedrashko 氏は， Forbes の記事をそう引用する [MITAdLab] 。そう遠くない未来 ― 2010 年頃には，ビデオ配信サービスは 10 億ドル規模の市場に発展すると予想されるが，その発展の途上においては，主にプロバイダーが儲けを得ることになると見られている。例えば，現在のコンテント配信市場の約半分を支えると言われる Akamai Technologies 社は，昨今の好調に支えられ，ここ１年の間に株価を３倍近くにまで引き上げている [AKAM] 。
19 世紀アメリカ西部においてゴールドラッシュが発生した背景には，交通網の拡充と通信手段の発展という，２大インフラの存在があったとされる [Wikipedia1] 。結局のところ，金を掘り当てて裕福になった人は稀であり，例えばリーバイ・ストラウス（ジーンズ『リーバイス』の創始者）のように，採掘者を相手に商売を行った者が財産を築き上げた [Wikipedia2] 。リーバイ自身は，当初から金の採掘を目的とせず，金を求めて集まってくる人々を相手に商売を行うことを考えていたと伝えられる [LeviStrauss] 。リーバイの視点は，現状の暗喩として面白く感じられる。
2006-05-16
Dr. Saul J. Berman, Louisa A. Shipnuck, Niall Duffy. The end of TV as we know it: A future industry perspective. IBM Institute for Business Value study.
これまで多くの消費者は，テレビ放送を地上波放送という単一の形態によって楽しんできた。しかし，昨今見られるデジタル技術の進展は，様々な形態による視聴の可能性を提示している。またそれに応じて，消費者側からも新たな種類の需要が生じつつある。これらの要素は，今後テレビ放送の形態をどのように変化させうるのだろうか。このレポートでは，今後の約 5 年間という中期的なスパンに焦点を当て，その未来像を映し出そうとしている。
平均視聴時間は成長を維持
テレビ放送と競合する娯楽分野は年々増加する傾向にある。インターネットやビデオゲーム， DVD レンタルや音楽配信サービスなどはその代表として挙げられる。こうした競合相手の存在にも係わらず，テレビ放送の平均視聴時間は今後も成長を維持する考えられている。
例えば，競合相手の中でもブロードバンドメディア配信は大きな脅威として考えられているが，調査によれば，ブロードバンド回線が一般普及する以前と以後を比較してみると，テレビ放送の視聴時間は減るどころか，かえって増加する傾向を見せている。つまり，少なくとも今のところ，ブロードバンドメディアとテレビ放送は「食い合い」を起こす関係にあるとは考えられない。
テレビ放送の視聴時間が成長を続ける理由のひとつとして，消費者側における視聴手段の拡大が指摘される。ポータブルプレイヤーや大容量メディアの普及は，消費者に対して「いつ観るか」「どこで観るか」「どのように観るか」という選択の幅を与えることになった。このような視聴手段の拡大は，消費者の視聴意欲を促進すると考えられている。
収益モデルに潜む矛盾
視聴時間は成長を続けると考えられているものの，その収益性については安泰な未来が保証されているわけではない。例えば，現在のテレビ放送の収益モデルが抱えている大きな矛盾の一つとして，ケーブルテレビの収益性の悪さが挙げられる。
北米では以前からケーブルテレビの普及率が非常に高く， 2002 年の時点でケーブルテレビの視聴率は地上波放送のそれを追い抜いている。他方で，テレビ放送の主要な収益源である広告収入に関しては，地上波放送からの収入が未だに全体の 70% を占めている。ここに見られる視聴率と広告収入の間の不整合は，最も消費量が大きいはずのチャネルから効果的に収益を得ることができていないという矛盾をあらわにしている。
最大の脅威は CM スキップ機能
もう一つ，既存の収益モデルを脅かす存在として， DVR （デジタルビデオレコーダー）に搭載された CM スキップ機能が指摘される。別の調査によれば， CM スキップ機能が広告収入に与える打撃は現時点で約 80 億ドルにも達しているとされている [MediaPost] 。その打撃の大きさは DVR の普及と共に今後も増え続け， 2009 年には広告収入の約 6%, 金額に換算して約 180 億ドルにも膨らむと予想される。
新たな収益モデルの模索
このように，従来通りの CM による広告収入を主軸とした収益モデルは，今後，収益効率の悪化を迎える危険性を孕んでいる。そこで放送メディア各社は，これに代わる新たな収益モデルの模索を開始している。
例えば Disney (ABC) などは， iTunes 上での番組の販売や，自社ウェブサイト上でのスキップ不可避広告 (skip-resistant ad) 付き無料配信などを試みている [ITmedia] [CNET] 。ウェブ上でのスキップ不可避広告付き無料配信をベースとしたモデルとしては他に， AOL Television の In2TV [AOL] や， MTV の MTV Overdrive [MTV] などが挙げられる。また， Akimbo 社 [Akimbo] のように， STB （セットトップボックス）を利用した古典的なオンデマンド放送を実践する企業もある。
特にユニークな収益モデルを推進する企業として TiVo 社が挙げられる。 TiVo は DVR のレンタルと EPG （電子番組表）の配信をセットにした月額固定サービスを展開しており，一部の消費者から絶大な支持を得ている。最近では，インターネットポータルサイト (Yahoo!) との提携 [MYCOM] や，商品紹介番組のオンデマンド配信 [TiVo] など，様々な動きを見せている。既存の放送メディアとは異なる存在だが，新たな収益モデルの模索の場において，今後も重要な役割を見せるものと予想される。
消費者のバイモーダル化
供給側では収益モデルの変革が予想されるとして，消費者側にはどのような変化が予想されるだろうか。この問いに対しては，「緩やかな二極化が進む」という回答が返される。
このレポートでは，現時点での多数を占める受身的な視聴者を "Massive Passives", 新しいもの好きの成年層を "Gadgetiers", コンテントの扱いに奔放な少年少女達を "Kool Kids" と称している。そして， Massive Passives が従来通りの受身の視聴を続けつつ， Gadgetiers や Kool Kids はコンテントに対して高い自由度と幅の広さを求めるという，二つの様式への分割が進むと予想する。この「二つの様式へ分割する性質」をバイモーダル性 (bimodality) と呼ぶ。
今後の 5 年間に限定して見れば，依然として Massive Passives が収益の大半を支え続けると予想される。いくら技術的な進展があったとしても，中年以上の受身的な視聴者がその視聴形態を現時点から大幅に変えるとは考え難い。言い方は悪いが，現時点で Massive Passives に属する人々は，死ぬまで Massive Passive として収益源であり続けることが保証されている。
故に，短・中期的な視点に立つ限りでは， Massive Passives を中心とした戦略が重要とされる。しかし他方で，長期的な視点に立った場合は， Gadgetiers や Kool Kids のように，コンテントに対して高い自由度と幅の広さを求める層が多数を占めるようになる可能性も考えられる。供給側としては，このような消費者層のバイモーダル性を認識し，戦略のセグメント化を積極的に推し進めていくことが必要とされる。
総括
今後もテレビ放送が成長を続けるという視点は予定調和的で新鮮さに欠けるが，収益モデルに関して見直しが計られている点や，消費者に対する接続チャネルの多様化によって収益性を向上させようという試みは，様々な工夫が見られて面白い。
恐らくは，インターネットがテレビを駆逐するという未来は既に無く，このレポートに示されるように，テレビが視聴者への接続チャネルのひとつとしてインターネットを用いるという構図になるのだろうと思う。 MTV Overdirve などを観ていると，既にその変化は始まっているのだという印象を受ける。
半導体に関してムーアの法則は陰りを見せているものの，回線の帯域あたりコストと，ストレージの容量あたりコストは，依然としてムーアの法則ばりに減少を続けている。そのコストの低下は，今後数年の間に映像配信のあり方を大きく変化させると予想される。その変化から目を離すことができない。
2006-05-17
茂木健一郎，クオリア入門 [ISBN4480089837]
[Wikipedia] および [Stanford] によれば，クオリア (qualia) の定義は文脈によって異なり一定しない。広く心理活動の現象的見地を指す場合もあれば，何らかの知覚的経験を特定して指す場合もある。特に日本語で「感覚質」と訳される場合の「クオリア」は，後者のような知覚的な概念を指していると考えられる。
茂木健一郎氏の「クオリア入門」は，この「クオリア」の定義を明確に行わないまま議論を開始する。結局最後までその定義がはっきりすることは無い。対象としている概念について曖昧にしか分からない状態で議論が展開されるため，その内容について納得することもできなければ，反論することもできない。
[Wikipedia] によれば，クオリアは哲学用語であるとされるが，著者はこれを脳神経学的な問題として捉え，クオリアと脳神経活動の関係について議論を展開する。つまり文脈としては科学的な議論であると考えられる。しかし，その論考は思考実験を基盤としており，どちらかと言えば哲学的な様式が感じられる。結局，科学とも哲学ともつかない曖昧な領域の上で議論を展開してしまっているように思えてならない。
著者は基本的に，脳内の活動は全て単なる「現象」に過ぎないとの考えを示している。その点はしっかりと伝わってくる。冒頭にある次の一節などは，その見方をよく表している。
どんなに雄大な景色が目の前に広がっていても，それを見て，感じている私の心は，脳の中のニューロンの活動に支えられている現象なのだ。（中略）自分の心が，自分が認識し，感じ，考えることの全てが，狭い頭蓋骨の中に閉じ込められている現象に過ぎないこと，そして，生きている限り，私がある限り，私の心はこの狭い空間の領域に閉じ込められたままだろうということを感じることは，人生観，世界観を変えるほどの衝撃を私たちに与える。
そして，その現象の中でも著者が最も重要と考える「クオリア」を問題として取り上げ，それがどのようにして脳内の「現象」として生じるのだろうかという点について議論を展開する。しかし，そのほとんどは脳神経活動に関しての結論の無い考察に終始しており，肝心のクオリアという概念についての議論は十分になされていない。「入門」と銘打つにはやや特殊過ぎる内容であると感じられる。
2006-05-19
Anthony J.H. Simons. The Theory of Classification Part1: Perspectives on Type Compatibility. In Journal of Object Technology, vol. 1, no. 1, May-June 2002, pp. 55-61.
Mars Climate Orbiter: NASA の火星探査機。火星上空 150 km 付近において大気摩擦により破壊。後の調査から，地上側の制御ソフトウェアにおいて，ヤード・ポンド法単位（重量ポンド毎秒）からメートル法単位（ニュートン毎秒）への変換を忘れている部分が存在することが判明した。当該ソフトウェアは Mars Global Surveyor 計画から引き継がれたものだったが，機体側の仕様変更に合わせてソフトウェアを更新した際に，単位系変換のための係数を計算式から見落としていたことが原因とされる。損失額は約 1 億 2500 万ドル [Wikipedia] [JamesOberg] 。
Ariane 5 #501: ESA （欧州宇宙機構）が開発した商用ロケット Ariane 5 の最初の試験機。離陸から約 40 秒後に爆発（機体分解により自爆装置が作動）。後の調査から， SRI （慣性基準装置）内で用いられている 16 ビット整数値がオーバーフローを引き起こしていることが判明した。 SRI は前世代の Ariane 4 から引き継がれたものだったが，これに入力される値が Ariane 5 の離陸時には想定を超えたものとなっていた。損失額は 5 億ドル以上 [ARIANE5] [DouglasArnold] 。
Mars Climate Orbiter は，単位系の扱いに不備があったために，火星上空で燃え尽きた。単位系を適切な型によって構成したうえで，型の変換チェックを行う機構が存在していれば，このような誤りを防ぐことができたかもしれない。
他方で Ariane 5 は， 16 ビット整数型の扱いに不備があったために，離陸から僅か 40 秒後に自爆した。 16 ビット整数型のふるまいをよく把握したうえで，値域を確認する処理が挿入されていれば，このような誤りを防ぐことができたかもしれない。
前者は，型の構成に誤りがあったことが原因であると考えることができる（型の統語論上の問題）。後者は，型の挙動の扱いに誤りがあったことが原因であると考えることができる（型の意味論上の問題）。
このような，たった一ヶ所の型の扱いの誤りが，数億ドルの計画をも無に帰すことがある。なぜ，このような誤りが生じるのだろうか？ どのように型を扱えば，このような誤りを防ぐことができるのだろうか？ そもそも，プログラミング言語における「型」とは，一体どのような概念として捉えられるものなのだろうか？
Anthony Simons 氏のコラム "The Theory of Classification" は，プログラミング言語における型システムを，数学的なモデルによって捉える方法を紹介する。ここで用いられる型理論やラムダ計算などの概念は，非常に抽象的な理論から構成されており，その全容を把握することは中々容易でない。しかしこのコラムは，これらの理論の専門家ではない人々をターゲットとしており，極力平易な解説によって理論の導入を行うことを試みている。
シリーズを通して閲覧するには Lambda the Ultimate からのリンク [LtU] が役立つ。
ところで，上で挙げた事例がいずれも，過去のソフトウェア資産を引き継いだ部分に問題を生じているという事実は興味深い。過去の実績から安定性を期待することができるという考え方自体に誤りは無いが，少しでも関連する要素の構成が変更されれば，結合時の安定性を保証することはできなくなる。その際には再び厳密な結合テストを行う必要があるが，それを怠れば，やがて Ariane 5 のような事故が発生してしまったとしてもおかしくない。
2006-05-23
Philip Wadler. Proofs are Programs: 19th Century Logic and 21st Century Computing.
数理論理学とコンピュータ・プログラムの間には深い関連性がある。この論文では，近代論理学の開祖であるフレーゲ (Gottlob Frege) [Wikipedia1] の概念記法 (Begriffsschrift) [Wikipedia2] を出発点として，ゲンツェン (Gerhard Gentzen) [Wikipedia3] の自然演繹 (natural deduction) [DanielClemente] と，チャーチ (Alonzo Church) [Wikipedia4] の型付きラムダ計算 [長谷川] [住井] の二つの流れを追い，最終的にそれらのモデルがカリー・ハワード対応 (Curry-Howard correspondence) [Wikipedia5] によって同型として対応付けられるところまでを辿る。
内容は非常に丁寧で分かりやすい。論理学の知識が無い人に向けた内容となっており，数学の心得が無いプログラマでも，なぜカリー・ハワード対応が「証明の簡略化」と「プログラムの実行」を同一のものとみなすのかということを理解することができる（もちろん，厳密な理解ではないものの……）。
ラムダ計算の概念は，自分らが普段触れているようなプログラムの概念とは装いがかなり異なるものであり，その背後にこのような理論が隠されていることは実感が湧きにくい。しかし，コンピューターやプログラムという概念が生まれるよりも数十年も前に考案された論理学のモデルが，今もなお形を変え我々に影響を与え続けているという事実は面白く感じられる。
チャーチは 1932 年の論文の中で，「この体系は，論理学への適用のほかに応用が存在するに違いない」と述べていたという。論理学の分野でのラムダ計算の研究はその後途絶えてしまうものの，代わりにプログラミング言語の世界で大きな影響を与えることになる。
ちなみに，チャーチは 92 歳，カリーは 82 歳まで生き，自らの業績から生み出された新たな世界の姿を，その人生の中で見届けることになる。本論文の著者の Wadler 氏は， 1982 年に開催された "Lisp and Functional Programming" 会合において，特別ゲストとして招聘されたチャーチ・カリーの両氏に会ったと述べている。両氏は，その新たな世界を目にして非常に驚いている様子だったという。
他方で，自然演繹のゲンツェンは，チャーチらとは対照的に悲劇的な結末を迎えることになる。ドイツ人であった氏は，当時ドイツの占領下にあったチェコのプラハ大学に勤務していたが，敗戦の騒動に紛れてチェコ市民に逮捕されてしまう。ソ連軍に引き渡された後も牢獄に閉じ込められ続け，約３ヶ月後に栄養失調で死亡したという [MacTutor] 。
2006-05-25
基本的なデータ構造のひとつであるヒープ [Wikipedia1] は，優先順位付きキュー (priority queue) の実装としてよく用いられる。この構造を用いると，任意の順序で入力されるデータ群から，最小（最大）のものを順に取り出すという操作を，高速に実行することができる。特にグラフ理論の解法（例えば最短経路問題や最小全域木問題など）において重要な役割を果たす。
ヒープ構造には幾つかのバリエーションがある。最も単純な構造としては二分ヒープ (binary heap) [Wikipedia2] が挙げられる。二分ヒープの操作はそれなりに高速ではあるが，２つのヒープの結合に最悪ケースで O(n) の時間が要されるという弱点がある。二項ヒープ (binomial heap) [Wikipedia3] を用いれば，これを O(logn) に改善することができる。しかしこちらは，最小要素の取得が最悪ケースで O(logn) になるという弱点がある。
少し変わったヒープ構造として，フィボナッチヒープ (Fibonacci heap) [Wikipedia4] と呼ばれるものがある。フィボナッチヒープは，基本的な動作としては二項ヒープに似ているが，ある種の操作を即時には行わず保留（遅延）させるという特徴がある。このような工夫により，挿入，結合，最小要素取得，キー値の減少，等の操作において O(1) の償却実行時間 (amortized time) を実現している。ただし，要素の削除のみは O(logn) が要される。フィボナッチヒープの詳細については [Wikipedia4] および Kevin Wayne 氏の講義ノート [Wayne] などが参考になる。
フィボナッチヒープよりも更に高速な手法として，プリンストン大学の Bernard Chazelle 教授が考案したソフトヒープ (soft heap) と呼ばれる構造がある [Chazelle] [Wikipedia5] 。この構造は，要素の削除を含む主要な操作を O(1) の償却実行時間で実現する。
とは言っても，タダで高速な操作が実現されるわけではない。この点がこの構造の面白い所でもある。
ソフトヒープは，一定のエラーを許容することによって効率の向上を図る。ソフトヒープに格納された要素の一部は，一定の規則に従って「一緒くた」にされてしまう。「一緒くた」にされた要素は同一のキー値を持つものとして扱われるため，実際のキー値との間には相違 (discrepancy) が発生する。当然，ヒープとしての挙動には一定のエラーが発生することになる。そのエラーが発生する割合は，ユーザーが任意に設定することができる。割合が高いほど実行速度は向上する。
情報理論的な見方をすれば，こうした扱いを行うことによって，データのエントロピーの低減を図っていると捉えることができる。エントロピーを押し下げることができれば，本来の理論的な効率の限界を超えて高速化を図ることが可能になる。
ソフトヒープは比較的マイナーな手法であり，ウェブ上で参照することのできる本格的な資料は [Chazelle] しか存在しない。しかし，この論文の多くの部分は各種操作の効率の証明に割かれており，処理の内容に関する説明は簡潔過ぎて分かり難いところがある。補助的な資料としては Maverick Woo 氏の講義ノート [Woo] が参考になると思われる。
このようにデータの損失をもって効率を向上させようという戦略は，データ圧縮の分野では一般的に用いられている手法ではあるものの，このようなデータ構造に適用されるのは比較的珍しいと感じられる。他にも approximate sorting [Giesen*1] のように，ある種の「不確かさ」を許容することによって，古典的な解法では超えられなかった理論的な限界を超えようという思想が存在する。一見，用途が狭いように思われるこれらの手法も，検索エンジンやデータマイニングなどのように，厳密な確度よりも高速な抽出を求められる分野においては，広い応用が考えられるのではないかと思う。
*1: 未読のため参考にならない可能性有り
2006-05-26
（5/29 改訂）
FNV (Fowler-Noll-Vo) ハッシュ関数は， Glenn Fowler, Phong Vo, Landon Curt Noll の３氏により考案されたハッシュ関数である [LandonNoll] [Wikipedia] 。非常に軽量でありながら比較的高い分散を持つという特徴がある（ただし，セキュリティ用途に用いることができるほどの耐衝突性は無い）。
FNV-1 ハッシュ関数は，以下のようなコードによって表される。
hash = OFFSET_BASIS;
while (*p) {
hash *= FNV_PRIME;
hash ^= *p++;
}
return hash;
FNV_PRIME と OFFSET_BASIS は，利用するハッシュ値のビット長によって固有の値が割り当てられている。 Noll 氏は FNV_PRIME の選択が重要であるとしているが，その根拠については述べていない。 OFFSET_BASIS の方は Noll 氏のシグネチャから得られる FNV-0 値を基にしている。この辺りの下地になる理論の危うさは FNV ハッシュの欠点であるとも言える。
検証
ここでは FNV-1 ハッシュ関数を，数個の英単語から構成される文字列に対して用いることを想定して，簡単な検証を行ってみる。文字列の生成には Brian Kelk 氏の頻出英単語リスト（57,046 語）を用いた [Kelk] 。また，比較対象として CRC-32 を用いても同様の試行を行った。
fnv_hash_test.cpp (8KB)
単語のみ
まず，全英単語に関してそれぞれ単独でハッシュ値を求め，衝突の確認を行った。この試行では FNV-1, CRC-32 共に衝突はひとつも発生しなかった。
２単語の組み合わせ
次に，二つの単語を組み合わせることによりキー数を 10 倍に増加させたうえで，衝突の確認を行った。この試行では， FNV-1 では 38 回の衝突が発生し， CRC-32 では 39 回の衝突が発生した。共に 1/15,000 程度の確率で衝突が発生した計算になる。
単語と番号の組み合わせ
次は，各単語に 0 から 9 の番号を付加することによりキー数を 10 倍に増加させたうえで，衝突の確認を行った。この検証では， FNV-1 では 26 回の衝突が発生し， CRC-32 では 58 回の衝突が発生した。
FNV-1 側で衝突の発生したキーの組み合わせに注目してみると，以下のようになっている。
dustmen0 == dupes1 (e618a451) dustmen1 == dupes0 (e618a450) dustmen2 == dupes3 (e618a453) dustmen3 == dupes2 (e618a452) dustmen4 == dupes5 (e618a455) dustmen5 == dupes4 (e618a454) dustmen6 == dupes7 (e618a457) dustmen7 == dupes6 (e618a456) dustmen8 == dupes9 (e618a459) dustmen9 == dupes8 (e618a458)
"dustmen" と "dupes" のキーは大きく異なるが，これらに FNV_PRIME を掛けた後の値は，下位数ビットの違いしかなくなってしまっている。このようなキーの組み合わせが出現した場合，末尾１文字の選択によって容易に衝突が発生しうる。
CRC-32 の方で発生している衝突もほぼ同じ理由であり，ハッシュ値が下位数ビットしか異ならないキーの組み合わせが出現した場合，やはり末尾１文字の選択によって衝突が発生してしまう。
今回の試行では CRC-32 の方が多くの衝突が検出されたが，一般に CRC-32 の方が衝突しやすいとする確証は無い。ともあれ，このような「あと一文字で衝突しやすいキーの組み合わせ」が存在することは，これらのハッシュ関数に共通する弱点として考えられる。
ハッシュテーブルへの応用
これらのハッシュ関数をハッシュテーブルで使用する場合を想定して検証を行った。ハッシュテーブルのエントリ数は 1024 個とし，ハッシュ値を 0x3ff (1023) でマスクすることによりインデクスを求めた。また， FNV-1 の場合は任意ビットへの折り込み (xor-folding) が定義されているため，これを使用した場合の検証も行った。特性の算出には，カイ２乗検定をベースとした Bob Jenkins 氏の手法を利用した [BobJenkins] 。
前出の単語リストにある全単語を単独で登録したところ， CRC-32 では +0.04, FNV-1 では -0.05 という値が得られた。この値は -3 から +3 の間が適切とされ，値が低いほど良い分散の傾向にあると考えられる。僅かに差があるものの，ほぼ同程度と捉えるのが妥当かと思われる。
XOR 折り込みを利用した場合については 1.77 という特に高い（悪い）値が得られた。 Noll 氏は XOR 折り込みの手法を紹介しているものの，その根拠についてはやはり触れていない。そのため，このような結果が想定されうるものなのかどうかも探る術が無い。今回の結果に基づく限りでは， XOR 折り込みよりも単純なマスキングを用いた方が良いということになる。
速度
最後に簡単な速度の比較を行った。結果として， CRC-32 よりも FNV-1 の方が 3% ほど速いという値が得られた。ただしこの結果については，厳密な測定方法を用いなかったことや，測定環境のセットアップの問題などがあり，あまり深い意味を求めることはできない。
FNV-1 と CRC-32 は，いずれもシンプルなアルゴリズムでありながらも特徴があり，プロセッサによっては速度に差が出る可能性も考えられる。 FNV-1 は乗算と XOR のみから構成されるが， CRC-32 は XOR が 2 回と AND とビットシフト，それにテーブル参照から構成されている。
これらの構成を比較すると， CRC-32 は，命令数が速度に直結しやすい（命令レベル並列性が低い）場合や，メモリ参照が高負荷である場合，テーブルがキャッシュ上に維持されないような呼び出され方が繰り返された場合などに，不利になる可能性がある。他方で FNV-1 は，乗算が高負荷である場合に不利になる可能性がある。逆に言えば，乗算さえ速ければ FNV-1 の方が有利であると考えられる。
2006-05-31
Joachim Giesen, Eva Schuberth, Miloš Stojaković. Approximate Sorting. Proceeding of the 7th Latin American Theoretical Informatics Symposium (LATIN), Lecture Notes in Computer Science 3887, (2006). pp. 524-531.
一般に，比較ソート (comparison sort) において必要とされる比較の回数は Ω(n log n) に従うとされている [Wikipedia1] 。これは理論上の下限であり，どのようなアルゴリズムも，最悪のケースを想定した場合にこの制約から逃れることはできない。
ただし，ソート結果に厳密な正確さを求めないのであれば ― つまり，いくらかの誤差を許容することができるのであれば，この理論上の制約を取り払うことができる。
Joachim Giesen 氏らの論文 "Approximate Sorting" では，ソート結果に誤差が含まれることを許容する場合に必要とされる比較の回数について考察を行っている。そこで行われている証明によれば， n 個の項目をソートし，その結果に Spearman's footrule 距離（全項目について正確な順序との差異の総計をとったもの）で n2/v(n) の誤差が含まれる場合，最低でも n(min{log v(n), log n}-6) 回の比較が必要であるとされる。
また， ASort と名付けられた近似ソートアルゴリズムを例示し，これを用いる場合， 6n(log v(n)+1) 回の比較で前述の結果が得られることを証明している。これはすなわち， v(n) が O(1) に従う限りにおいては， o(n log n) の比較回数で済むことを意味する。
ASort アルゴリズム自体は，中間値（メディアン）をピボットとしたクイックソートに似た内容になっている。ただし，完全にソートが完了するまでループするのではなく，所定の回数でループを打ち切ってしまうという点が，通常のソートアルゴリズムとは大きく異なる点として挙げられる。
ランダウの記号について
"O(n)", "o(n)", "Ω(n)" 等の表記は，ランダウの記号に基づく。ランダウの記号については [Wikipedia2] ないしは [Wikipedia3] が参考になる。
大雑把な言い方をすれば， x → ∞ において f(x)/g(x) が無限大にならないような f(x) を O(g(x)) として表す。これは，関数の上限の性質を表すのに用いられる。
逆に， x → ∞ において f(x)/g(x) が 0 にならないような f(x) を Ω(g(x)) として表す。こちらは，関数の下限の性質を表すのに用いられる。
また， x → ∞ において f(x)/g(x) が 0 に近づく場合は o(g(x)) とし，逆に無限大に近づく場合は ω(g(x)) とする。
アルゴリズムの計算量を表す際には Θ(g(x)) というような表記もよく用いられる。これは， x → ∞ において f(x)/g(x) が無限大にも 0 にもならないという性質を表す。
大文字の O 記号のみを用いる場合も多いが，今回の例のように，これらの記号が意図的に使い分けられている場合は，その意味の違いに注意する必要がある。