Algorithm - Suffix Array を JavaScript で再発明してみた : 404 Blog Not Found
2012年01月16日16:30 カテゴリアルゴリズム百選Lightweight Languages Algorithm - Suffix Array を JavaScript で再発明してみた WEB+DB 総集編 [Vol. 1〜60] もう10年以上前に某社のCTOだったころ、Suffix array(接尾辞配列)の解説を毎週の技術者ミーティングでしたら一名を除いて「ハァ?」状態だったことを思い出しつつ。 Suffix Arrayは何が画期的だったのか? 以下は、計算機科学者でなくても直感的に理解できると思います。 ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))がかかる。 ソート済みのデータであれば、二分探索でデータの大きさの対数時間(O(logn))でキーを検索できる。 さらにキーからIDを定数時間で作成でき
最速並び替え研究会 - Yappo::タワシ
1000万行とか10億行でも何でもいいけど、いっぱいデータが入ってるテーブルのsortカラムの値を並び替えたい。 例えば以下のようにsort_testテーブルを作る use strict; use warnings; use DBI; my $dbi = DBI->connect('DBI:mysql:database=test'); $dbi->do('DROP TABLE IF EXISTS sort_test'); $dbi->do(<<SQL); CREATE TABLE sort_test ( id INT, sort INT, index(id), index(sort) ) ENGINE=InnoDB SQL my $sth = $dbi->prepare('INSERT INTO sort_test VALUES' . join(', ', ('(?,?)')x10_000
素朴なBigtable、できること できないこと
素朴なBigtable、できること できないこと：分散Key-Valueストアの本命「Bigtable」（2）（1/2 ページ） RDBとは別の、クラウド時代のデータベースとして注目を浴びている「分散Key-Valueストア」。その本命ともいえる、Googleの数々のサービスの基盤技術「Bigtable」について徹底解説 あまりにもRDBとは異質な「Bigtable」 前回の「もう1つの、DBのかたち、分散Key-Valueストアとは」では、連載第1回目として、クラウドコンピューティングにおける新しい潮流である「リレーショナルデータベース（RDB）から分散Key-Valueストア（分散KVS）への移行」が、どのようなパラダイムシフトをもたらすのかを解説しました。今回からは、グーグルが運用する代表的な分散KVS「Bigtable」の内部構造を紹介し、クラウドの本質をより深く掘り下げます。 前
http://www.ritsumei.ac.jp/~inabam/class/coginfo/3.html
認知と情報（稲葉） 第３回 認知科学と人工知能 前回に引き続き、認知科学の基礎概念として、人間の思考・認知をシステム的に捉える「情報処理モデル」について学習する。本講義では特に、人間の知的活動のモデル化に大きな影響を与えた人工知能研究の成果について概説する。 １．認知科学と人工知能 行動主義心理学は一般的に、人間の行動に関する実験を重視するのに対して、認知科学（認知心理学を含む）では、実験に加えて、一種の情報処理システムとしての人間のモデル作成と、そのシミュレーションという手法を重視する。 このため認知科学は、コンピュータサイエンスと密接に関係している。コンピュータシステムは、入力装置や記憶装置、推論や考察をつかさどる処理装置を備えていると同時に、ソフトウェアによって様々な情報処理モデルを定義・操作できるため、人間の認知に関するモデルを作成し、検証することに適している。 人工知
データ構造の選択次第で天国と地獄の差
データ構造の選択次第で天国と地獄の差：コーディングに役立つ！ アルゴリズムの基本（2）（3/3 ページ） この木何の木、木構造 「木構造（根付き木）」と呼ばれるデータ構造について説明します。リンクリストは直線的にノードがつながっているデータ構造でしたが、木構造は木のような形でノードがつながっているデータ構造です。 木構造はデータを持つノードで構成されています。 ノードの中には1つだけルート（根）というノードがあります。図にした場合、一般的に一番上に書かれます。 2つのつながっているノードを見たとき、ルートに近い方を親ノード、ルートから遠い方を子ノードといいます。 あるノードの親ノードは1つだけしかありません。子ノードは複数あります。子ノードは1つの場合もあり、1つもない場合もあります。 ルートノードには親ノードがありません。親ノードがないのはルートノードだけです。 最も末端のノードをリーフ
はてなブックマーク全文検索機能の裏側
そろそろ落ち着いて来たころ合いなので、はてなブックマーク全文検索機能の裏側について書いてみることにします。 PFI側は、8月ぐらいからバイトに来てもらっているid:nobu-qと、id:kzkの2人がメインになって進めました(参考: 制作スタッフ)。数学的な所は他のメンバーに色々と助言をしてもらいました。 はてな側は主にid:naoyaさんを中心に、こちらの希望や要求を聞いて頂きました。開発期間は大体1〜2か月ぐらいで、9月の上旬に一度id:naoyaさんにオフィスに来て頂いて合宿をしました。その他の開発はSkypeのチャットで連絡を取りながら進めてました。インフラ面ではid:stanakaさん、契約面ではid:jkondoさん、id:kossyさんにお世話になりました。 全文検索エンジンSedue 今回の検索エンジンはSedue(セデュー)という製品をベースにして構築しています。Sedu
はてなブックマークFirefox拡張, JavaScript で IS 法 による Suffix Array 構築 - naoyaのはてなダイアリー
昨日、はてなブックマークFirefox拡張をリリースしました。おかげさまでベータ版からダウンロード数は累積で1万ダウンロードを突破し、アクティブユーザー数も伸びています。 はてなブックマークFirefox拡張で新しいインターネットを体験しよう http://b.hatena.ne.jp/guide/firefox_addon 開発者の id:secondlife が g:subtech:id:secondlife:20090415:1239804170 で技術的な側面からのちょっとした TIPS なども紹介していますので、興味のある方はご一読ください。 検索では思いのほか SQLite の like 検索が高速なのに驚いた。はてブ検索では、検索ワードから URL, Title, コメント にマッチしたものを表示していて、それ専用の search_data だかかんらかの検索用カラムがある。
Google File System(GFS)技術メモ — ありえるえりあ
* 参照した論文 + http://labs.google.com/papers/gfs-sosp2003.pdf * 特徴 + 安いPC(OSはGNU/Linux)で分散ファイルシステムを構築しています(*注1)。 + PCは壊れるという前提で設計しています(*注2)。このため、分散システムを構成するノードが壊れた時、データが失われないことと、自動で復旧できることに主眼を置いています。 + ファイルシステムを利用する側(アプリ)に、ある程度の想定を求めています。任意の利用ケースに対してそこそこのパフォーマンスを出す(=平均的に良い性能)のではなく、特定の利用ケースで性能を発揮できるように設計しています。 + 性能を発揮できる利用ケースは次のようなケースです。 ++ 主にサイズの大きいファイルを扱う(*注3)。 ++ ファイルへの書き込みは追記(append)が多い(ファイルの一部分を何度
mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
特集 人工知能について考える