状態のあるコードに対するテストの自動生成 - 西尾泰和のはてなダイアリー
BLUE*アルゴリズムを実装してみたので、せっかくだからテストの自動生成をやってみた。 今回テスト対象にするコードの仕様は 開く、閉じる、書き込む、の3つの操作ができる 開いてないのに書き込んだり閉じたりしたらエラーになる というもの そしてこちらがそれの「バグのある実装」： class Target(object): # bad impl. def __init__(self): self.opened = False self.closed = False def open(self): self.opened = True def write(self): if not self.opened: raise RuntimeError if self.closed: raise RuntimeError def close(self): if not self.opened: rais
Algorithm - Ruby 2.0 や Haskell の遅延リストを JavaScript で : 404 Blog Not Found
2013年03月10日23:45 カテゴリアルゴリズム百選Math Algorithm - Ruby 2.0 や Haskell の遅延リストを JavaScript で プロになるためのJavaScript入門 河村嘉之 / 川尻剛 これを書いたら欲が出て来たので。 dankogai/js-list-lazy ・ GitHub ちなみに「プロになるためのJavaScript入門」は参考書にした一冊。この場を借りて献本御礼。 無限リスト 自然数を受け取って対応する値を返す関数を一つ食わせるだけです。 var ll = List.Lazy(function(i){return i}); // also predefined as List.Integers p( ll.length ) // Inifity p( ll.get(42) ) // 42 p( ll.take(42) ) //
Algorithm - 配列の冪集合、順列、組み合わせを再帰なしで作る : 404 Blog Not Found
2013年03月08日11:00 カテゴリアルゴリズム百選Math Algorithm - 配列の冪集合、順列、組み合わせを再帰なしで作る C言語による最新アルゴリズム事典 奥村晴彦 ちょっと必要に迫られたので、JavaScript用のやつを作りました。 dankogai/js-combinatorics ・ GitHub こんな感じで使います。 var a = ['js', 'pl', 'py', 'rb'], c, e; p( '/* power set */' ); c = Combinatorics.power(a); p( 0 + c ); while (e = c.next()) p(JSON.stringify(e)); p( '/* combination */' ); c = Combinatorics.combination(a, 3); p( 0 + c ); p(J
TechCrunch | Startup and Technology News
When Alex Ewing was a kid growing up in Purcell, Oklahoma, he knew how close he was to home based on which billboards he could see out the car window.…
A/Bテストを超え、学習しながらウェブを最適化させる手法 (Bandit Algorithms for Website Optimization)
ふと気になったので読んでみたら、当たりをひいた。 強化学習をウェブサイトの最適化に利用する方法に関しての本で、A/Bテストの何が問題かを説明してそれを克服するためのアルゴリズムを3つ紹介している Epsilon-greedy SoftMax UCB1 コードはPythonで書かれているので読みやすい。 実際のビジネスでは、A/Bテストで等確率でAB振り分けるために劣っている方のテストの分だけ収益が減ってしまうし、かといってテストをしないと、よりよいサイトを見出す機会がなくなってしまう。つまりexploreを最大化するか、exploitを最大化するかというようなジレンマを抱えることになる。 求められているのは、劣っているサイトデザインに対するテスト（損失）を最小にしつつベストなサイトデザインに収斂していく手法である。そういう問題をMultiarmed Bandit Probremと呼ぶらしく
ランダムだと！？！？(ガタッ - 西尾泰和のはてなダイアリー
確かに、このテンプレには僕も飽きている： onk:「リンゴが10個あります。ランダムに3人で取り分けなさい」ってどうコードに落とすと綺麗かな。。 yoshiori: @onk ランダムだと！？！？ onk: @yoshiori 擬似ランダムでいいです yoshiori: @onk ふう、焦らせやがって……(俺の中でここまでテンプレ) yoshiori: もう、「ランダム」という言葉に反応してしまうのはネタでも良くない気がしてきた そこで新しいマサカリを考えてみた。「お前はなにを等確率にしたいんだ！？！？」 2個のりんごをAさんとBさんの2人に配ることを考えてみよう。全部で4通りの配り方がある。(A, A), (A, B), (B, A), (B, B)の4つだ。 この4通りを等確率にしたいのならば、それぞれのりんごについて1/2の確率でAとBに振り分ければ良い。ちなみにPythonのran
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
MD5やSHAの代替として利用可能な新たなハッシュ化技術「BLAKE2」登場 | OSDN Magazine
12月21日、ハッシュアルゴリズム「BLAKE2」とそのCおよびC#実装が公開された。BLAKE2はMD5やSHAといったハッシュアルゴリズムの代替として利用できるもので、セキュリティに優れ高速に動作するのが特徴という。 BLAKE2は、与えられた入力に対し指定されたビット長のハッシュ値を生成するためのアルゴリズム。既存のハッシュアルゴリズムであるMD5よりもセキュリティに優れ、かつSHAよりも高速に処理を実行できるのが特徴という。 同様のハッシュアルゴリズムとしてSHA-2やその後継となるSHA-3（Keccak）などがあるが、BLAKE2はSHA-3アルゴリズムの候補の1つであったBLAKEを改良したものとなっている。BLAKE2はSHA-3やBLAKEと同等のセキュリティを備えつつ、64ビット環境においてMD5と同等の速度で動作し、SHA-2やSHA-3と比べて33％少ないメモリで動
“共起サイテーション”がアンカーテキストに取って代わる？ 2013年のGoogleアルゴリズム大胆予想
[対象: 中〜上級] “共起サイテーション”が、“アンカーテキスト”に取って代わる重要なランキング要因に将来的になる。 SEOmozのRand Fishkin（ランド・フィッシュキン）氏によるこんな大胆な予想を今日は紹介します。 （余談ですけど、髭を剃ったのでランドを見慣れた人には別人に見えて一瞬戸惑いますね） “共起サイテーション”という言葉は、Rand Fishkin氏が使っている“co-citation”という用語を今僕が日本語にしたものです。 “co”は、「共同の」とか「共通の」、「共に」という意味を持ちます。 日本語では「共起語」として僕たちが使っている“co-occurrence”の“co”です。 “citation”は言及・参照されることです。 プレイス検索で、大きめのランキング要因になっていると考えられるあのサイテーションです。 したがって、“co-citation”、言い
ASSIOMA(アショーマ) » 変化するブロガーの発信力とそれに追いついていない検索アルゴリズムと広告モデル
ここ最近ブロガーを取り巻く環境は変わってきているように思う。TwitterやFacebookを導線とするようになったとはまた「違う」変化を感じる。blogosに代表される「ブログアグリゲイトメディア」や、ヤフーニュース個人のような選抜オーサタイプ、Naverまとめのようなキュレーションサイトの登場によって、自分の発言をより広い範囲へ届けてくれるメディアが登場している。これらの「自身のブログ(オウンドメディア)」以外からの記事閲覧が無視出来ない規模になってきていると感じる。 私の例だが、このブログに記事を書くと以下の三つに同じ記事が掲載される。 ・本サイト ・Blogos ・ヤフーニュース「個人」 この三つを合わせると10月の合計PVは45万Pvに達していた。これら以外にも商用媒体への寄稿やそこからExciteやgooといったニュースサイトへ配信されることも考えれば、10月の私の記事の総閲覧
データマイニングを仕事にする人の生態系 - dataminer.me
「データマイニングを仕事とする人＝データマイナー」はどういう人たちがいるかということについて ビックデータとかで世の中がバズってるけど「僕はデータマイニングをやってます！」といったときに適切にその人がやっている業務領域を把握している人ってかなり少ないと思う。 グリーで働いていたときもデータマイナーはどういった仕事をしていて、何をやっていて何ができるのかっていうことを理解していなくてミスコミュニケーションが生まれていたと思うのでちょっとその生態系についてまとめてみた。おそらく、データマイナーといわれる人は以下のタイプがいる： 研究開発をする人 統計学的に新しいイノベーションを起こせる人。Google のPageRankアルゴリズムを作りましたとか、NetfrixやAmazonのレコメンデーションエンジン作りましたとかいう人がこれにあたる。スキル的には統計学にかなり長けている必要があり、その他
ZDD入門-お姉さんを救う方法
3. 前回のあらすじ • 前回のランダムフォレスト(竹迫さん)は 決定木を「特徴をランダムに選んで、決 定しきらなくても適当に打ち切って、と にかくたくさん作って多数決！」だった • 今回も決定木だが「特徴を全部使って、 巨大な決定木をつくるぞ！」という話 3 4. 決定木が表現するもの • 0/1の特徴がたくさん与えられて0/1を返す関数 • 具体例： • 論理式(項が特徴、式の値が返り値) • 部分集合の族(各頂点が部分集合xに含まれる かどうかが特徴、その部分集合が族に含まれ るかどうかが返り値) 4
ブラジルの元Google社員が答えたSEOに関する8つの質問
[対象: 全員] ブラジルのGoogleのサーチクオリティチームに以前勤めていたPedro Dias（ペドロ・ディアス）氏という人がいます。 現在は、Search Quality Allianceという名の組織で他の元Google社員と共に検索エンジンの品質向上、健全化に取り組んでいます。 そのディアス氏が、あるSEOフォーラムで投稿のあったSEOに関する質問の回答をSearch Quality Allianceのブログで公開しました。 そのなかから、僕たちにとって役に立ちそうなQ&Aを8個抜粋してこの記事で紹介します。 Q1 : nofollowリンクは多少なりとも検索結果に影響しているのか。（nofollowが付いていない）通常リンクとnofollowリンクの割合いは重要か。たとえば、もし通常のリンクが100%だったらそれはスパムの兆候になってしまうのか。 A1 : そのリンクが存在す
「フカシギの数え方」の問題を解いてみた
先日、「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
Googleが取得した新しい特許は想定外の順位を見せてスパムを判定する
[対象: 上級] スパムを検出するための仕組みに関する新しい特許をGoogleが取得しました。 スパムらしい行為が発見できたものの確信が持てないときに想定外の順位変動をまず見せることで反応を伺い、本当にスパムかどうかの判定に利用するものです。 SEO by the SeaのBill Slawski（ビル・スロースキ）氏がこの新しい特許について解説しています。 僕なりに要点を絞って解説します。 3つのタイプの検索順位 特許では3つのタイプの検索順位を定義しています。 old rank（オールド ランク） target rank（ターゲット ランク） transition rank（トランジション ランク） “old rank”はページの元の検索順位です。 “target rank”は、そのページにランキングを不正に上げようとして加えられたスパムらしき変更、でもスパムとは確定できない変更が加え
プログラミングコンテストでの乱択アルゴリズム
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
平方根を使わずに高速で２点間の距離を近似する - きしだのHatena
２点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。 flipcode - Fast Approximate Distance Functions (12:02 補足：おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう) 距離関数高速近似 by Rafael Baptista (27 June 2003) ２点間のユークリッド距離を求める計算式は次のようになる。 二次元では次のようになる。 この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与え
http://swatmac.info/?p=942
See related links to what you are looking for.
「4人のロシア人の方法」で編集距離を高速化する - EchizenBlog-Zwei
ちょっと前に「4人のロシア人の方法(Method of Four Russians)」というのを論文で見かけて面白かったので紹介しておく。 簡単に言ってしまうと、ある処理を高速化したい時にデータ全体を小さなブロックに分割してブロック単位での結果を事前に計算したテーブルで持っておくよ、というアルゴリズム。 名前は知らなくてもアルゴリズム自体は知ってる人は多いかもしれない。 Method of Four Russians - Wikipedia, the free encyclopedia アルゴリズム自体は汎用的なものだが編集距離の高速化を例として説明するのが一般的なようなのでそれに倣う。 文章で書くとごちゃごちゃするのでスライドで。もっふる。 http://www.scribd.com/doc/94190119/MoFR ※追記：↑のスライド、正直自分でもわかりやすいとは思えないので余裕が
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
猫を認識できるGoogleの巨大頭脳