What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by Okasaki in 1998, but not present in that book) Finger trees (and their generalization over monoids) There are also some interesting ways of implementing already known datastructures, such as using "nested
Lossy Compressed Image Formats Study (October 2013)
Mozilla Corporation, October 2013 Introduction This study compares the compression performance of four different image formats: JPEG, JPEG XR, WebP, and HEVC-MSP. The latter three formats were chosen because they are frequently discussed as possible JPEG successors. It is our intent to only address compression performance in this study. Other technical, legal, and market factors that might be cons
Display Ad Allocation に関する論文をいくつか読んだ - blog.sparsegraph.com
Tuesday, October 15, 2013 Display Ad Allocation に関する論文をいくつか読んだ proceedings や reference を辿りながら気になった RTB に関する論文，特に Display Ad Allocation （demand-side player における impression と campaign の割り当て）を扱う論文を読んだ．要約と感想だけ整理してメモする． Optimal Online Assignment with Forecasts. [1] Erik Vee, Sergei Vassilvitskii, Jayavel Shanmugasundaram. Optimal Online Assignment with Forecasts. In EC 2010. (pdf) Allocation problem
アップル、圧縮技術を開発するAlgoTrimを買収か
Appleが、スウェーデンを拠点に画像、動画、ソフトウェアを圧縮するためのアルゴリズムを専門に扱うAlgoTrimを買収したと、スウェーデンの報道社Rapidusが現地時間8月28日に報じた。 AlgoTrimは当初、フィーチャーフォン向けにアルゴリズムを開発していたが、その後スマートフォンへと対象を拡大した。同社のウェブサイトによると、同社の技術は、「Android 4.0」（開発コード名：「Ice Cream Sandwich」）向けのGoogleの「Gallery」アプリにおける画像の高速デコードに使用されているほか、一部の端末メーカーではAndroid搭載端末向けのファームウェアアップデートの圧縮に使用されているという。 この報道に関する問い合わせに対してAppleは声明で、「Appleは小規模な技術企業を適宜買収しているが、通常、当社の目的や計画については説明しない」と述べた。
朝日新聞デジタル：プロ野球日程を瞬時に計算 数学者がソフトを開発 - スポーツ
プロ野球の移動距離を短くする計算例 【藤島真人】１カ月以上かかるプロ野球の日程づくりが、あっという間にできるソフトウエアを数学者が開発した。日程を工夫するだけで、球団の移動距離を２割以上減らすこともできるという。シーズン開幕を控え、彼らの計算式と現実とのギャップはいかに。 開発したのは、国立情報学研究所の河原林健一教授と星野リチャード・前外来研究員。２人は効率の良い鉄道網や電気回路の設計などにも応用できる「グラフ理論」と呼ばれる分野の研究者だ。 ソフト開発は、３年前の３月、カナダからリチャードさんが来日し、たまたま千葉ロッテの本拠地の近くに住んだことがきっかけ。鉄道網のような「グラフ」を球団の移動に置き換え、最適な日程をはじき出せないかを考えた。 続きを読むこの記事の続きをお読みいただくには、会員登録が必要です。登録申し込みログインする（会員の方） 無料会員登録はこちら朝日新聞デジタ
疑似乱数 - 186 @ hatenablog
ちょっとした思いつき。 疑似乱数列を生成する計算方法の妥当性を調べるのにチューリングテスト的方法は使えるか。 放射線などを用いた真の乱数列と、調査したい計算方法の生成する疑似乱数列とが、二つのチャネルA, Bから流れ出てくる。でもどちらの数列がどちらのチャネルから流れてくるかは分からないとする。乱数を検定するアルゴリズムを別途用意しておき、二つのチャネルのどちらが真の乱数列であるか判定できるか。 ――という話題。 それができるなら、ランダムネスと知能との類似性という逆説的で面白い話題につながるね。 チューリングテストでは、本物の人間と適切な判定者によって、コンピュータのプログラムの知能性(?)を判定する（言い換えるとそれを知能の定義とする）。上に書いたテストでは、真の乱数列（本物の人間の代わり）と検定をするアルゴリズム（適切な判定者の代わり）によって、 疑似乱数列の計算方法の妥当性を判定す
アルゴリズムを学ぼう
関連サイト出版社による関連ページが公開されています。 アルゴリズムを学ぼう (KADOKAWA/アスキー・メディアワークス) 関連書籍本書の続編『続・アルゴリズムを学ぼう』も好評発売中です。 内容紹介本書のテーマは、ガチのアルゴリズムとデータ構造、そして計算量です。 いや、確かに本書は女の子がいろいろでてきたり、小話が入っていたりと、ゆるふわなオーラが漂っています。しかし、あえていいましょう。それは、見かけだけである、と。 プログラミングを学ぶにあたって、アルゴリズムとデータ構造は、どの言語を用いるにしてもすべての基礎であり、避けて通ることはできない道です。アルゴリズムとデータ構造を知らずにプログラムを書くことは、無免許で車を運転するぐらいに危険な行為です。 しかし、アルゴリズムとデータ構造をきちんと理解せずに、プログラムを書いているプログラマーが多数いるのも事実です。それは、アルゴリズム
指数時間アルゴリズム - てきとーな日記
指数時間アルゴリズムというのは，NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで，できるだけ指数の底の小さいアルゴリズムを開発することが目指されています． コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが特に有名だと思います． この分野は近年盛んに研究され始め，自分も大学でこの分野を中心に研究をしています． 今回，情報オリンピック春合宿講義とPFIセミナーで発表する機会があったので，この分野の基礎的な手法から最先端の手法までをまとめてみました． 指数時間アルゴリズム入門@情報オリンピック春合宿講義 http://www.slideshare.net/wata_orz/ss-12131479 指数時間アルゴリズムの最先端(キャンセリング)@PFIセミナー http://www.slideshare.net/wata_orz/ss-12208032
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
行列（画像）分解アルゴリズムGoDec (Zhou+, ICML2011)の実装を公開しました - Educational NLP blog
つい2週間ほど前，機械学習のトップカンファレンスICMLが開催されました．その中のGoDecという行列分解アルゴリズムを実装したので公開します．このアルゴリズムは，簡単にいえば「外れ値抜き特異値分解」で，昨日のICML読み会で発表しました．論文はこれです． GoDec: Randomized Low-rank & Sparse Matrix Decomposition in Noisy Case. Tianyi Zhou, Dacheng Tao. ICML2011. 厳密な版（Nai:ve GoDec）は遅いですが実装は非常に簡単です．遅い版でも，数百x数百ピクセルの小さな画像であれば，十分実用的な速度で動くので，実装して試してみた次第です．GoDecの論文では，この厳密な版（Nai:ve GoDec）が線形収束することを証明した上で，さらに，実用的に早くなるように（証明はないようですが
Software Updates: Courgette (Chromium Developer Documentation)
How Courgette works As I described in Smaller is faster (and safer too), we wrote a new differential compression algorithm for making Google Chrome updates significantly smaller. We want smaller updates because it narrows the window of vulnerability. If the update is a tenth of the size, we can push ten times as many per unit of bandwidth. We have enough users that this means more users will be pr
Chromeがバイナリ差分で新アルゴリズム実装 － ＠IT
2009/07/17 グーグルのChromeチームは7月16日、Chromeの自動アップデートで使われるバイナリアップデートに新たなアルゴリズムを実装したことを明らかにした。実際の例として、実行形式のフルアップデートで10MBの容量が必要だったものが、従来の差分方式で704KB、今回発表した新方式では78KBにまで縮小したという。 Chromeには自動アップデートの仕組みが組み込まれており、脆弱性の報告などがあると、これに対応するパッチを当てたバージョンをChromeユーザーにプッシュすることができる。これにより攻撃者が脆弱性を利用する時間が短くなるため、安全性が高まる。 セキュリティパッチなどは、ソースコードレベルで数行の変更であることも多いため、新バージョンの実行バイナリを丸ごとユーザーに送りつける代わりに、差分だけ送ることで転送量を抑えることができる。これまでChromeチームではb
竹内関数が音楽的に聴こえる理由について考えてみた - aike’s blog
前回のエントリーが予想以上に反響が大きくてびっくりしています。 プログラミング言語好きの僕にとってはヒーローみたいなすごいプログラマーたちにツイートしてもらってびびっていたところ、今日になって竹内先生ご本人からのコメントをいただいてしまって本気で腰抜かしそうになりました。せっかくなので自分なりに竹内関数が音楽的に聴こえる理由についての考えを書いてみます。 ■ちょっとした工夫 最初に少し種明かしをすると、より音楽的になるように以下のような工夫をしています。 ・ダイアトニックスケール（白鍵）だけを使用し調性の外れた音が出ないようにした ・最小値(-1)をレにわりあてることで少し寂しげなドリアンスケールにした （とはいえ-1の出現頻度が低いのでミからはじまるフリジアンスケール的かも） ・オートアルペジオ、テンポ、音色の設定でミニマルミュージック風にした 上記のことをおこなうと、ただの乱数でもわり
竹内関数で音楽生成 - aike’s blog
Lisperの人ならみんな知ってる竹内関数（たらいまわし関数）という関数があります。 定義としてはこんな感じ。 そのシンプルな定義からは想像もつかないほど複雑で膨大な再帰呼び出しがおこなわれるとても興味深い関数です。たとえば引数にTarai(10,5,0)を与えると343,073回も再帰呼び出しされたりします。 この関数呼び出しの引数がどのように変化するか知りたくてプログラムを書いて調べてみたところ、Tarai(10,5,0)の場合は3つの引数がそれぞれ0〜10（xは-1〜10）の間で少しずつ変化するなかで、2つの値を固定してひとつの値が下降していくような挙動があったりして、なんだか音楽の3和音のコード進行を思わせるような動き方です。 そういうことなら、ということで実際に音にして聴いてみました。Tarai関数が呼ばれるたびに引数のx、y、zを、0=ミ、1=ファ、2=ソ、……、のように音に割
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Cache-Oblivious データ構造入門 @DSIRNLP#5
http://raftconsensus.github.io/
Raft: The Understandable Distributed Consensus Protocol
How algorithms shape our world | TED Talk Embed
Naked Security – Sophos News
JPEG Tilt