Data Structures – Unraveling the Complexity of Data OrganizationMobile trading has revolutionized the forex market, with statistics showing that over 65% of retail traders now use smartphones for…
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
はてなブックマーク全文検索機能の裏側
そろそろ落ち着いて来たころ合いなので、はてなブックマーク全文検索機能の裏側について書いてみることにします。 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
バイオ系雑誌に載った機械学習/計算機科学の解説記事 - Loud Minority
主に計算機科学の機械学習・データマイニング系の説明で、バイオの雑誌に載った解説記事です。ツールを使いこなす人が、中身を知りたかったり、作る人に変身したい場合や、情報科学(機械学習、データマイニング系）の人が、ゲノム解析などでどうやって利用されているのかを知るのに良いとおもう。追加する記事募集です。 決定木の解説 What are decision trees? Carl Kingsford & Steven L Salzberg Nature Biotechnology 26, 1011 - 1013 (2008) http://www.nature.com/nbt/journal/v26/n9/abs/nbt0908-1011.html EMアルゴリズムの解説 What is the expectation maximization algorithm? Chuong B Do & Se
アルゴリズムコンテストの挑み方 - d.y.d.
17:29 08/09/30 クロスワード 暇つぶしに "Clueless Crossword" という冊子を買ってみて意外とハマっています。 クロスワードパズルなんだけど、単語のヒントの代わりに、 各マスに1～26の数字が振ってあって同じ数字のマスには同じA～Zが入るように埋めるというもの。 「母音っぽくて二連続して語尾にも出てくるのは多分 E だろう、もしかしたら O の可能性はなくもないけど」 みたいに埋めていく。 ちょっと違うけど フラッシュであった。 20:15 08/09/28 だいちのよろい そろそろ日本に戻る前に観光するぞ月間、ということにして、ウルル（エアーズロック）に行ってきました。 もっとワイルドな感じかと思ったら、完全にリゾートのリゾートによるリゾートのための地帯になってました。 まあそんなもんか。 本日は強風のため登るの禁止とのことだったので、周りから見るだけ。
講義資料 配列解析アルゴリズム特論I 情報生命科学基礎/演習 他 -渋谷哲朗
平成20年度 東京大学大学院 情報理工学系研究科・コンピュータ科学専攻 配列解析アルゴリズム特論I 4/10 4/17 4/24 5/1 5/8 5/15 5/22 5/29 (The problem to be reported - in English) 6/5 6/12 6/19 7/3 7/10 7/17 東京大学 理学部・情報科学科 情報科学特別講義３ （情報科学とバイオインフォマティクス） 6/10 7/15 7/22 東京大学大学院 新領域創成科学研究科・情報生命科学専攻 情報生命科学基礎/演習 5/27 6/17 京都大学大学院 薬学研究科・医薬創成情報科学専攻 情報科学概論 6/3 中央大学大学院 理工学系研究科・物理学専攻 物理学特別講義第二 TBA 創価大学工学部 生命情報工学科 TBA TBA 戻る Copyright (c) 2004- Tetsuo
マージ・ソート : 巨大データのソート法
はじめに まずはともあれ腕試し、この問題を解いてみてくださいな: 【問1】 デタラメな順序で並んだ文字列の集合がテキストファイル「input.txt」に収められています。この文字列群を辞書順（昇順）に並び換えたテキストファイル「sorted.txt」を作りなさい。 ※各文字列は改行で区切られています。 プログラミング教本の練習問題、あるいは学校の課題で出てきそうな“お馴染み”の問題です。ソート（整列）アルゴリズムの実装には配列/代入/条件分岐/ループなどなどプログラミングの基本中の基本となる構文を総動員するため、練習問題としてよく使われますね。 早速解いてみましょう、ソート・アルゴリズムにはこれまたお馴染みのバブル・ソートを使います。C#、VB.NET、C++/CLIの3本まとめて一気にいきますよ: using System; using System.IO; using System.C
著名ソーシャルメディアが使っているアルゴリズムを大公開！ | Moz - SEOとインバウンドマーケティングの実践情報
“アルゴリズム”は、もっとも非人間的なものの代表だともいえる。ソーシャルメディアにとって、そのアルゴリズムが不可欠だというのは、実に皮肉めいている。 僕はこの間、グーグルがどうやってユーザーデータを集めているかについて書いた記事を掲載した（前編、後編）。今回は、著名なソーシャルメディアサイトが、ユーザーデータを活用する上でどのようにアルゴリズムを用いているのか、白日の下にさらそう。 ソーシャルメディアを成り立たせているのは人間の力だが、ユーザーが入力したデータを利用できる状態にする仕組みは、アルゴリズムによって作られている。現在活動している無数のソーシャルメディアサイトで実証済みのことだが、ユーザーの関与とアルゴリズムによる処理ルールの上手いバランスを見出すことは、とても難しくなりがちだ。これから紹介するアルゴリズムは、悪意のないユーザーと結びついて初めてうまくいくものだ。 人気ソーシャル
アルゴリズムイントロダクション輪講@京都のお知らせ - motemenの日記
2008-08-18 12:19 追記 多数のご応募ありがとうございます。ここでいったん募集を打ち切らせて頂きます。なお、人数の関係で、応募された方からも今回参加できない方が出ることになりますが、あしからずご了承下さい。 社内エンジニアの間に、計算機科学をマジメにやろうという機運が高まっています。それを受けはてな社内で計算機科学に関する教科書の輪講をやろうという話になりました。という訳でまずはアルゴリズムの教科書「数学的基礎とデータ構造 (アルゴリズムイントロダクション)」を輪講してみることにします。はてなスタッフだけでなく社外からの参加も募集しているので、京都オフィスに近い方はぜひご参加下さい。 数学的基礎とデータ構造 (アルゴリズムイントロダクション) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,
Tx: Succinct Trie Data Structure
English 概要 TxはコンパクトなTrieを構築するためのライブラリです．従来のTrieの実装（darts等）に比べ1/4〜1/10の作業領域量で辞書を保持することができ、数億〜十億キーワードなど大規模な辞書を扱うことが可能です．Trieは文字列からなるキー集合を処理するデータ構造で、キーが辞書に含まれているかのみではなく、キーのPrefixが含まれているかを高速に求めることができます．内部データ構造にはSuccinct Data StructureであるLevel-Order Unary Degree Sequence (LOUDS)を利用しています． ダウンロード Txはフリーソフトウェアです．BSD ライセンスに従って本ソフトウェアを使用,再配布することができます. tx-0.12.tar.gz: HTTP Archives tx-0.11.tar.gz: HTTP tx
キーワード抽出モジュール Lingua::JA::Summarize を使うコツ (nakatani @ cybozu labs)
いわゆる「Web2.0」っぽい要素である「タグ」。 一般にはタグ付けは手動で行うわけですが、自然言語テキストへのタグ付け(キーワード抽出)を自動で行うことができれば、あれこれと可能性が広がって楽しそう……しかし、それは実現が難しかったり高コストだったりして、簡単に手を出せる解はあまりありません。 ラボの奥さんの作成したキーワード抽出モジュール Lingua::JA::Summarize は次の特徴を持っています。 動作要件の敷居が低い 辞書のメンテナンスをしなくても、未知語や熟語もある程度抽出してくれる 希望の結果に近づけるためのチューニングが可能 本モジュールを使って、サイボウズ・ラボ内での情報交換を行っている社内掲示板をスレッド単位で解析しているのですが、辞書を一切チューニングしていない状態でも「しょこたん☆ぶろぐ」や「猫かぶり隊隊員ニャンコ達」などの特徴的なキーワードが抽出されます（
協調フィルタリング
協調フィルタリング 渡辺 崇文, 廣安 知之, 三木 光範 ISDL Report No. 20071019004 2007年 9月 19日 Abstract レコメンデーションサービスのための手法として，協調フィルタリングがある．協調フィルタリングは，ユーザの嗜好情報を元に各ユーザ間の類似度を計算し，その類似度に基づいてユーザの嗜好を推測するシステムである．協調フィルタリングは，Amazonのお勧め機能に採用されていることで有名である． 本報告では，協調フィルタリングについて，その背景や関連概念，応用されているサービス等について調査を行った． 1 はじめに レコメンデーションサービスを提供する際に使用される手法として，協調フィルタリングがある．協調フィルタリングは，ユーザの嗜好情報を元に各ユーザ間の類似度を計算し，その類似度に基づいてユーザの嗜好を推測するシステムである． 本報告
共立出版株式会社 新刊・近刊2008年7月『アルゴリズムデザイン』
アルゴリズムデザイン （ISBN978-4-320-12217-8） Jon Kleinberg， Éva Tardos 著 浅野孝夫・浅野泰仁・小野孝男・平田富夫 訳 B5，832頁，15000円 ●内容 本翻訳書は，Jon Kleinbergと Éva Tardosの著書"Algorithm Design"の全訳である。訳者が原書の翻訳に至ったのは，2005年5月にボルチモアで開催されたACMのSTOC（Symposiumon Theory of Computing）の国際会議において，Addison-Wesley社のブースで原書を手に取ったときの新鮮な感銘からである。組合せ最適化の分野の著名な賞であるファルカーソン賞を受賞した Éva Tardos教授と翌2006年にチューリング賞と並ぶ情報科学のネバンリンナ賞を受賞したJon Kleinberg教授の初めての本であるとい
アルゴリズムデザイン - やねうらおブログ(移転しました)
以前、アルゴリズム関係の本をいろいろ紹介したが(http://d.hatena.ne.jp/yaneurao/20050522)、この度、「アルゴリズムデザイン」という832ページもある本格的なものが発売されたようだ。 共立出版のサイトから目次一覧が確認できる。 http://www.kyoritsu-pub.co.jp/shinkan/shin0807_03.html 組合せ最適化の分野の著名な賞であるファルカーソン賞を受賞した Eva Tardos教授と翌2006年にチューリング賞と並ぶ情報科学のネバンリンナ賞を受賞したJon Kleinberg教授の初めての本である (snip) 著者はこのようなアルゴリズムデザインの世界観に基づいて，原書の目標を以下のように設定している。すなわち，様々な分野で生じる複雑な形式の問題から明快な定式化を発見する方法と，その定式化に基づいて実際の問題に対
形態素解析と検索APIとTF-IDFでキーワード抽出
形態素解析と検索APIとTF-IDFでキーワード抽出 2005-10-12-1 [Programming][Algorithm] 形態素解析器と Yahoo! Web 検索 API と TF-IDF を使ってキーワード抽 出するという先日の検索会議でのデモ、KEYAPI[2005-09-30-3]。 教科書に載っているような基本中の基本ですが、あらためてエッセンスを 簡単な例で解説したいと思います。 目的：キーワード抽出対象テキストから、そのテキストを代表する キーワードを抽出します。TF-IDF という指標を用います。（この値が大 きいほどその単語が代表キーワードっぽいということでよろしく。） TF-IDF を計算するためには、 (1) キーワード抽出対象テキスト中の代表キーワード候補出現数 (TF)、 (2) 全てのドキュメント数 (N)、 (3) 代表キーワード候補が含まれるドキュメ
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
ガベージコレクションの実装法と評価
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
秋元@サイボウズラボ・プログラマー・ブログ: 各ソート技法をアニメーションで表示するAnimated Sorting Algorithm Demo
ソートアルゴリズムのアニメーションデモでは、様々なソート手法(挿入、選択、バブル、シェル、マージ、ヒープ、クイック、三分割クイック)について、ソート対象のデータが完全ランダムの場合、ほぼソートされている状態、逆順にソートされている場合、同じ値のものが多数ある場合のデータをソートする様子を、Javascriptを使ったアニメーションで見せてくれる。 それぞれのソートアルゴリズムがどのようなものか見せるというだけでなく、ソートのアルゴリズムに「常にこれが最適」というものはない、というのを示すのも目的、ということだ。 各アルゴリズムのリンクからは、そのアルゴリズムのコード、特徴や計算量が解説されたページに飛ぶ。 このようなソートアルゴリズムの可視化というテーマ、Javaベースではこういうのやこういうの、こういうのも過去にあった。 via del.icio.us/popular
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
共立出版株式会社 刊行中のシリーズ「アルゴリズム・サイエンス シリーズ」: ３．適応的分散アルゴリズム
はてな