行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
定兼 邦彦 (Kunihiko Sadakane) - 圧縮接尾辞配列ライブラリ - researchmap
文字列を圧縮したまま検索するライブラリです． 文字列の一部を高速に復元することもできます． 圧縮接尾辞配列ライブラリ (2010-08-10版) Direct BWT construction External Memory BWT construction http://code.google.com/p/csalib/ にもあります． 注意: dbwt100717.zipにはバグがありました．Ubuntuでは動かない可能性が高いです． dbwt100730.zipを使ってください． 索引とは，本の索引と同じ意味で，検索を高速に行うためのデータのことです． ただし，本の索引では代表的な言葉のみが登録されていますが，このライブラリの索引は 任意の語が検索できるようになっています． このライブラリの索引は自己索引 (self-index) と呼ばれるもので，索引自体に 元のファイルの情報を全
- MYCOM BOOKS - プログラミングコンテストチャレンジブック
■内容紹介 現在、プログラミングコンテストは数多く開催されています。Google Code Jam、TopCoder、ACM/ICPCなどの名前を聞いたことがある人も少なくないでしょう。本書で扱うのはそれらのような、問題を正確にできるだけ多く解くことを競うプログラミングコンテストです。 プログラミングコンテストは気軽に参加することができます。例えば、Google Code JamやTopCoderはインターネット経由でコンテストが行われるので、Webサイトでの登録を済ませ、決まった時間にコンピュータの前に居れば参加することができます。 しかし、プログラミングコンテストの世界は非常に奥が深く、経験を積んだプログラマーであっても良い成績を残すことは容易ではありません。プログラミングコンテストで勝つには、柔軟な発想力と幅広い知識を用いて問題を解くアルゴリズムを考え、それらを正確に実装しデバッ
【レポート】GNU grepが高速な理由 | エンタープライズ | マイコミジャーナル
FreeBSD - The Power To Serve why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 G
データ圧縮法概説 目次
最終更新日：2001年7月2日 第1章へ webmaster@snap-tck.com Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)
C - で私も素数を数えてみた : 404 Blog Not Found
2010年07月26日18:30 カテゴリMath C - で私も素数を数えてみた 世間は夏休みだそうだし、連日の猛暑で体調も底だし、というわけで私も素数を数えてみた。 10兆までの素数のリストを作ってみませんか？ - 記者の眼：ITpro もしあなたがプログラマだったら、プログラムを書いて10兆までの素数のリストを作ってみてほしい。情報システムの開発に携わる人であれば、10兆までの素数のリストを出力するシステムの見積もりを考えてみてほしい。費用はどれくらいかかるか、納期はどれくらいか、あなたはどんな答を出すだろうか。仕様書はうまく書けるだろうか。 プライムナンバーズ David Wells / 伊知地宏監訳 / さかいなおみ訳 [原著:Prime Numbers: The Most Mysterious Figures In Math] といっても原田記者と同じように書いても芸がないので
10兆までの素数のリストを作ってみませんか？
もしあなたがプログラマだったら、プログラムを書いて10兆までの素数のリストを作ってみてほしい。情報システムの開発に携わる人であれば、10兆までの素数のリストを出力するシステムの見積もりを考えてみてほしい。費用はどれくらいかかるか、納期はどれくらいか、あなたはどんな答を出すだろうか。仕様書はうまく書けるだろうか。 記者がこんなことをいうのは、自分で10兆までの素数のリストを作ってみて、とても面白かったからだ。図1のプログラムを書いて出力が成功するまで約2週間、夢いっぱいの楽しいひとときを過ごせた。予期せぬ問題も発生したけれど、最後にはコンピュータがまだまだ発展する可能性を持つと感じられた。素数のリストを作る演習は、プログラミングと情報システムにおける有益な演習の一つである。 アルゴリズムの有効性が納得できる この演習の面白い点は、まずアルゴリズムの有効性を納得できる点だ。素数（prime）は
「ガベージコレクションのアルゴリズムと実装」という本を書きました。
gcbook, gcai, GCGCLoverのみなさん、お待たせしました。「ガベージコレクションのアルゴリズムと実装」の情報公開です。 書名：ガベージコレクションのアルゴリズムと実装 著者：中村 成洋／相川 光 監修：竹内 郁雄 ページ数：472ページ 本体価格：3,200円 発売開始日：2010年3月17日（水） ※地域・書店によって遅れることがあります ISBN：978-4-7980-2562-9 C3055 読み所 本書は次の2つのテーマを扱います。 1.GCのアルゴリズム（アルゴリズム編） 2.GCの実装（実装編） アルゴリズム編では、これまでに考案されてきた数多くのGCアルゴリズムの中 から、重要なものを厳選して紹介します。伝統的かつ基本的なものから、やや 高度なアルゴリズムを選定しています。GC独特の考え方や各アルゴリズムの特 性などを理解していただくのがアルゴリズム編の最大
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
人材獲得作戦・４ 試験問題ほか - 人生を書き換える者すらいた。
さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** という入力に対し、 ************************** *S* * $$$ * *$* *$$*$ ************
第1回 直線の幾何 | gihyo.jp
計算幾何学とは 小学生や中学生の頃、算数や数学の授業で、台形の面積を求めたり、直線の方程式を解いたりした記憶が誰にでもあることでしょう。計算幾何学とは、コンピュータサイエンスの立場から、こうした「図形」に関するアルゴリズムを研究する学問です。計算幾何学は、今日のコンピュータグラフィックスやCADの発展においてきわめて重要な役割を担っているほか、地理情報システム（GIS）やロボット工学といった数多くの分野に応用されています。 本連載では、ブログ可視化サイトの「Blogopolis」で採用されている計算幾何的アプローチを引き合いに出しつつ、Javaプログラムでアルゴリズムを実装しながら、計算幾何学の初歩を学びます。 Blogopolisとボロノイ図 Blogopolisは筆者の開発したWebサイトで、主に日本国内で開設された25万件以上のブログを解析し、「仮想都市景観」として視覚化したサービ
並行コンピューティング技法
The Art of Concurrency和訳書籍への推薦文 訳者まえがき まえがき 1章 速くしたい人、手を挙げて！ 1.1 さまざまな疑問 1.1.1 スレッドモンキー 1.1.2 並列と並行：その違いは？ 1.1.3 そんなことを知る必要があるの？ どんな役に立つの？ 1.1.4 並行プログラミングって難しくないの？ 1.1.5 スレッドって危険じゃないの？ 1.2 スレッド化の4つのステップ 1.2.1 ステップ1. 分析：並行性を持つ部分を見つけ出す 1.2.2 ステップ2. 設計と実装：アルゴリズムをスレッド化する 1.2.3 ステップ3. 正当性の検証：スレッド化の誤りの検出と修正 1.2.4 ステップ4. 性能チューニング：性能ボトルネックの排除 1.2.5 スクラッチ開発 1.3 並列アルゴリズムの背景 1.3.1 理論モデル 1.3.2 分散メモリプログラミング 1.
広く知られているinsertion sortのコードは駄目すぎる - やねうらお−よっちゃんイカを食べながら年収1億円稼げる(かも知れない)仕事術
insertion sortは「挿入ソート」と訳される。(Wikipedia→ http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88 ) ■ 日本語版 Wikipediaの日本語のページのコードを引用すると次のようになっている。 for (i = 1; i < n; i++) { tmp = data[i]; for (j = i; j > 0 && data[j-1] > tmp; j--) { data[j] = data[j-1]; } data[j] = tmp; }上のコードでは、内側のループでinsertの必要がなかった場合でも最後にdata[j] = tmpでtmp変数をwrite backしており、しかも、insertの必要のなかった場合でもj=iが1回実行される。それらの意味に
「最強最速」を見せつけた浪速の高専生
高専生にとっての大イベント、「高専プロコン」の季節がまたやってきた。競技部門では、大人をもうならせる良問に、優れたアルゴリズムを携えてしのぎを削る学生たちの姿があった。 秋晴れに包まれた10月17日、18日にかけて、千葉県木更津市にある「かずさアカデミアホール」にて、「全国高等専門学校 第20回プログラミングコンテスト」（高専プロコン）が開催された。 高等専門学校の学生を対象とした情報処理技術系コンテストといえば「高専ロボコン」が特に有名だが、1990年にはじまった高専プロコンも歴史を重ね、いまでは高専ロボコンとの二枚看板の様相を呈している。 大きな節目となる20回目を迎えた今回の高専プロコンのテーマは「集まれ手作りの未来たち――海を越え！翔けろ！橋になれ！――」。課題、自由、競技と3部門が設けられている同大会だが、競技部門はほかの部門と比べてエンターテインメント性を強く押し出し、メディア
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GC on C++
http://1978th.net/tech/promenade.cgi?id=88
マルチコア時代のLock-free入門