2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。 これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文
ウェーブレット行列のテスト実装に、rank(), select() の他、wat-array で実装されているものをだいたい追加しました。ウェーブレット木でできることは、ウェーブレット行列でも同じようにできる（元論文の最後にちゃんとそう書いてある）ということが確認できました。 なぜ可能なのかというと、ウェーブレット行列でもウェーブレット木のブロックがそのまま保たれているからです。 例として、11, 0, 15, 6, 5, 2, 7, 12, 11, 0, 12, 12, 13, 4, 6, 13, 1, 11, 6, 1, 7, 10, 2, 7, 14, 11, 1, 7, 5, 4, 14, 6 という配列に対してウェーブレット木とウェーブレット行列を作ることを考えます。 まず、ウェーブレット木の場合から見てみます。 初めに、最上位ビットが 0 か 1 かを調べて、その配列を作ります
Lempel-Ziv-Oberhumer (LZO) は、可逆データ圧縮アルゴリズムであり、解凍速度の速さに特徴がある。Markus Franz Xaver Johannes Oberhumer が1996年より開発していて、ライブラリとしての LZO とコマンドライン版の lzop がある。[1] LZOは以下のような特徴があるアルゴリズムである。 圧縮速度はdeflate圧縮に匹敵する 解凍速度は非常に速い 圧縮時にはバッファ領域を必要とする（圧縮レベルによるが、8kBや64kB等である） 解凍時には解凍元・解凍先以外のメモリ領域は必要としない 圧縮品質と圧縮速度のバランスを指定できる。それは解凍速度に影響を与えない
GeoHash(http://en.wikipedia.org/wiki/Geohash)は、緯度経度を文字列のハッシュで表現する仕様です。 GeoHashにより表現された緯度経度の情報は、一つの文字列で緯度と経度という2次元の情報に加えて精度も表すことができるという特徴を持っています。 例えば、どうでしょうバカの聖地である北海道札幌市の平岸高台公園は、北緯43.025東経141.377ですが、これをGeoHashで表現すると、"xpssc0"となります。 この"xpssc0"というGeoHash表現は、「北緯43.0224609375から43.0279541015625の間で、東経141.3720703125から141.383056640625の矩形範囲」であり、座標はこの矩形範囲の中心点になります。 @masuidrive blogさんの緯度経度を文字列で表すGeoHash - @ma
こんにちは、二台目のmbaを買うのをためらっている岡野原です。 アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。 アイテムが低次元（例えば2, 3次元）の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元（数百万次元）中の点であったり、アイテム間の距離のみが定義されている場合（カーネル関数など）です。アイテム数は数万から数億ぐらいを想定しています。 最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、 「アイテム集合X = x1,
[Python]multiprocessingを使ったオセロ
Pythonのmultiprocessingを使ってオセロの分散並列処理をやってみました。 サーバのキューに登録されるタスクをクライアントが黙々と計算して結果を返します。 構成はこんな感じです。 server.py タスク配布用と結果受け取り用のキューを持っているサーバ。 Othello.py オセロの探索を行うクラス。 game.py Othelloのサブクラス。オセロの探索対象の局面をサーバのキューに登録するクラス。 client.py Othelloのサブクラス。キューに入ったタスクを探索して、評価値を返すクラス。 game_launcher.py ユーザからの入力を受け取ってgameに初期条件等を与える。 使い方は サーバでserver.pyを立ち上げる クライアントでclient.pyを立ち上げる クライアントorサーバでgame_launcher.pyを立ち上げる あとはプロン
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
Python: 画像で与えられた迷路に対し2点間の最短経路を求める
迷路の描かれた画像に対して、ピクセルの座標で指定したスタート地点とゴール地点の最短経路を求めるプログラムをPython+PILで書いてみた。使用する画像は、デジカメで撮ったものでも、ウェブから拾ってきたものでも、ペイントソフトで自作したものでも構わない。 まずは使用例を見て欲しい。この画像は携帯カメラで撮った自作の簡単な迷路だ(画像上)。それに対して指定した2点間の最短経路を赤線で示してみた(画像下)。ピクセル単位で計測しているので赤線が若干ガタガタしていて完全な最短経路ではないがほぼ最短と考えていいだろう。迷路画像(画像上)をmaze01.jpgとし、スタート地点の座標が(240, 160)、ゴール地点の座標が(210, 400)の場合、コマンドラインで以下のように実行する。 maze_solver.py maze01.jpg -s 240 160 -g 210 400 これで最短経路を
PCA 解析と呼ばれる，あるデータの中から表現しやすい基底ベクトルを探す方法．だと思う． http://www.logos.ic.i.u-tokyo.ac.jp/~s1s5/pukiwiki/index.php?programming%2Fpython%2Fscipy を参考にとりあえずやってみた． #!/usr/bin/python import random import numpy from numpy import array from numpy import linalg def PCA(X): x_mean = array( map( sum, X.T) ) / len( X ) X_ = X - x_mean X_t = numpy.dot( X_.T, X_ ) / len(X) lam, vec = linalg.eig( X_t ) ans = zip( lam, v
原著者：Guido van Rossum 原文：http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html 原文公開日：OCTOBER 22, 2008 Pythonの著者のGuidoのブログが引っ越しをしたようです。そこに載っていた記事を一本翻訳してみました。今マイブームはオペラ座の怪人で、楽譜を買ったり、小説を買ったりして読んでいるんですが、小説の日本語がやたら直訳で堅いんです。柔らかい翻訳に触れたくて、衝動的に翻訳してみた次第です。動機とPythonは何の関係もないですが。 誰かからジョーク交じりに、100万個の32ビットの数値を2メガバイトのメモリでソートできるか？と聞かれたことがある。私はこれに挑戦してみたが、この中でI/Oのバッファリングについていくつか学ぶことができた。
2. ï ï É»¾ Ù±±¹´» ²»© ¿¹®·¹¿¬·±²ÅïÃ î ¹±± ² î í Ñø² ÷ ì ïòï ÔÍØøÔ±½¿´·¬§ Í»²·¬·ª» Ø¿¸·²¹÷ ÔÍØ ÔÍØ ïòïæ ï æ î ¸¬¬°æññ©©©ò¿¬³¿®µ·¬ò½±ò¶°ñ²»©ñîððèïîñðïñ®¿µ«¬»²ò¸¬³´ í ì ÐÔÍ× ÔÜß ï 3. ÔÍØ ×²¼§µ Þ·¬ Í¿³°´·²¹ Ø¿³³·²¹ ÔÍØ Åîà ޮ±¼»® Ó·²ó©·» ײ¼»°»²¼»²¬ л®³«¬¿ó ¬·±²øÖ¿½½¿®¼ ÔÍØ÷Åíà ݸ¿®·µ¿® ο²¼±³ Ю±¶»½¬·±²ø½±·²» ÔÍØ÷Åìà ײ¼§µ °ó¬¿¾´»øÔ° ÔÍØ÷Åëà ë ÉÛÞ ÔÍØ °ó¬¿¾´» ÔÍØ °ó¬¿¾´»øÛ«½´·¼ ÷ ο¼±³ Ю±¶
2017-05-08 世界コンピュータ将棋選手権 世界コンピュータ将棋選手権/第27回 2016-05-06 世界コンピュータ将棋選手権/第26回 2015-07-05 GPSshogi Gpsfish_minimal 2015-05-08 世界コンピュータ将棋選手権/第25回 2014-12-16 使い方 2014-05-06 世界コンピュータ将棋選手権/第24回 2014-04-25 第2回将棋電王戦/QandA 2014-04-23 osl/Tutorial 2014-04-13 使い方/viewer 2014-04-12 osl/Install ダウンロード GPSFish 2013-05-10 世界コンピュータ将棋選手権/第23回 2013-04-24 第2回将棋電王戦 2013-03-20 戦績 2012-12-17 関連論文 2012-07-08 ダウンロード/過去の記録 2
文書間の類似度を求める方法の一つとして、コサイン尺度が挙げられます。コサイン尺度とは、2つのベクトルのなす角度であり、文書をベクトル化することにより、文書間の類似度を求めることが出来ます。 sub cosine_similarity { my ($vector_1, $vector_2) = @_; my $inner_product = 0.0; map { if ($vector_2->{$_}) { $inner_product += $vector_1->{$_} * $vector_2->{$_}; } } keys %{$vector_1}; my $norm_1 = 0.0; map { $norm_1 += $_ ** 2 } values %{$vector_1}; $norm_1 = sqrt($norm_1); my $norm_2 = 0.0; map { $nor
K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。 これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。 K-means and X-means implementations http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。 調べたところ、Javaのデータマイニングツー
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
This webpage contains the code and other supporting material for the textbook "Machine Learning: An Algorithmic Perspective" by Stephen Marsland, published by CRC Press, part of the Taylor and Francis group. The first edition was published in 2009, and a revised and updated second edition is due out towards the end of 2014. The book is aimed at computer science and engineering undergraduates studi
図1に示す(1)から(3)までの麻雀（マージャン）の手牌があります。「あがり牌」はすべて山からツモったものとし，リーチはかけていません。またドラやハイテイ＊1なども関係ないものとします。これらの役を判定して，親の場合の点数を計算するプログラムを作ってください。 「ややこしや～ややこしや～」というのは野村萬斎ですが，思わずそううなってしまうことがプログラミングをしているとよくあります。今回の麻雀の役判定は，考えれば考えていくほどややこしく，そうしたものの代表と言えるでしょう。排他処理や優先順位が複雑にからんでいて一筋縄ではいきません。 今回はややこしい組み合わせを解決する方法を考えてみます。麻雀になじみのない方も，ちょっとしたパズル気分で試してみてください。 麻雀の役を考える 麻雀を知らない方のためにルールをおおざっぱに説明しておきましょう＊2。麻雀の牌には，大きく分けて「萬子（マンズ）」「
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
