高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
MapReduce以外の分散処理基盤BSP, Piccolo, Sparkの紹介 - Preferred Networks Research & Development
どうも，実は今年から開発チームにjoinしていた中川です．可愛い犬の写真がなかったので，可愛いマスコットの画像を貼っておきます． 最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました．これはつまり，それだけ大量のデータをなんとか処理したいという要望があるからだと思います．しかし当たり前ですが，MapReduceは銀の弾丸ではありません． ということで，最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について，社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います． Bulk Sychronous Parallel このアルゴリズム自体は1990年に誕生したものです．長いのでBSPと書きます．さて，グラフから最短経路を求める時，MapReduceは使えるでしょうか？このような論文が出るくらいですから出来ないことはあ
双対分解による構造学習 - Preferred Networks Research & Development
入力\(x\)から出力\(y\)への関数を学習する機械学習の中で、出力が構造を有している問題は構造学習（Structured Output Learning）と呼ばれ、自然言語処理をはじめ、検索のランキング学習、画像解析、行動分析など多くの分野でみられます。 今回はその中でも複数の構造情報を組み合わせても効率的に学習・推論ができる双対分解による構造学習について紹介をします。 # 構造学習についてよく知っているという方は双対分解による構造学習のところまで読み飛ばしてください。 構造学習の導入 構造を有した出力の例として、 ラベル列 （品詞、形態素列の推定、時系列におけるアクションの推定、センサ列） 木 （係り受け解析における係り受け木、構文解析木、談話分析、因果分析） グラフ （DAG:述語項構造による意味解析 二部グラフマッチング:機械翻訳の単語対応） 順位付集合（検索における順位
クリエイティブなC++ライブラリ "Cinder" の紹介 - Preferred Networks Research & Development
こんにちは、人恋しい季節になってきましたね。 研究開発チームの祢次金(@nejigane)と申します。 本エントリではCinderというクリエイティブなコーディング向けのライブラリについてご紹介したいと思います。 Cinderとは Cinderとは、画像、音声、動画等を簡単に処理＆可視化できる、主にビジュアルデザイン向けの強力なC++ライブラリであり、The Barbarian GroupのAndrew Bell氏が中心となってオープンソースとして開発が進められています。 同様の思想を持つProcessingやopenFrameworksによく似ており、C++で簡単に記述できるうえ、Windows、MacOSX、iOS(iPhone/iPad)といった複数のプラットフォームをカバーしています。 細かい機能/特徴の紹介は本家サイトに譲るとして、Cinderを極めるとどのぐらいクリエイティブな
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Googleの並列ログ解析向け言語「Sawzall」が公開されたので使ってみた | Preferred Research Blog