タグ

algorithmに関するbayashi_netのブックマーク (111)

  • 差分検出アルゴリズム三種盛り - Object.create(null)

    こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説

    差分検出アルゴリズム三種盛り - Object.create(null)
  • Amazonの推薦システムの20年

    IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も

    Amazonの推薦システムの20年
  • どうぶつしょうぎ名人 - まめめも

    どうぶつしょうぎ AI を作りました。絶対に勝てません。無力感を味わってください。 ref: http://mame.github.io/dobutsu-shogi-master どうぶつしょうぎとは 3 マス x 4 マスの単純化された将棋です。ライオン(王相当)、ぞう(1 マスしか進めない角行)、キリン(1 マスしか進めない飛車)、ひよこ(歩相当、にわとりに成ったら金相当)の 4 種類の駒を動かして、相手のライオンを取るか、トライ(ライオンを一番奥の行まで運ぶ、ただし直後に取られる場合はだめ)に成功すれば勝ちです。詳しくは Wikipedia の記事を見てください。 どうぶつしょうぎは後手必勝であることが知られています(研究報告)。つまり、後手が正しくプレイする限り、先手は絶対に勝てません。どうぶつしょうぎ名人は常に正しくプレイするので、先手のあなたは絶対に勝てません。 なんで作ったの

    どうぶつしょうぎ名人 - まめめも
  • 電王・Ponanza開発者が語る、理由がわからないけどスゴイ“怠惰な並列化”

    皆さんこんにちは。 私は将棋プログラム「Ponanza」の作者、山一成と申します。Ponanzaは初めてプロ棋士を破った将棋プログラムで、近年最も強い将棋プログラムと言えると思われます。また、2017年もトッププロ棋士の方と対局することが予定されています。Ponazaの改良のための機械学習に現在ジサトライッペイさんのPC「大紅蓮丸」の計算リソースを借りているのですが、その関係で原稿を書いてとお願いされたので、3回に渡って将棋プログラムの今について、書いていきたいと思います。 フリーランチの終焉、並列化の効率問題 アスキー読者の方々には言うまでもないのですが、まずは近年のCPU事情について解説していきたいと思います。ちょっと昔まではCPUはシングルコアが当たり前で18ヶ月経過すればCPUのトランジスター数は倍になり、性能が向上するという流れが続いていました。ソフトウェアはその性能向上に伴い

    電王・Ponanza開発者が語る、理由がわからないけどスゴイ“怠惰な並列化”
  • Lepton image compression: saving 22% losslessly from images at 15MB/s | Dropbox Tech Blog

    Lepton image compression: saving 22% losslessly from images at 15MB/s This open-source project is no longer maintained or supported by Dropbox. Please refer to Lepton’s GitHub page for more information. ~ ~ ~ We are pleased to announce the open source release of Lepton, our new streaming image compression format, under the Apache license. Lepton achieves a 22% savings reduction for existing JPEG i

    Lepton image compression: saving 22% losslessly from images at 15MB/s | Dropbox Tech Blog
  • Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ウーン カーネルとか弄ったりのメモ

    Linuxカーネルのコードを読んでて、なるほど〜と思うことはよくあるけど、その中でも特に今までの考え方をぶち壊してくれたのはなんだっけと思ったところ、やっぱりリスト構造かなと言うところ。 c言語でリスト構造を作る場合、一般的な教科書方式だと↓のようにデータとnextポインタは密結合になってると思います。これの場合、struct foobarのポインタをnext要素に使っているので、他の構造体(例えば、struct hogehoge)で同じことをしようとすると、その構造体ではstruct hogehoge *nextというメンバ変数を持つ必要があります。 ヘッド要素はstruct foobarです。 struct foobar { int n; char s[64]; struct foobar *next; }; struct foobar head; Linuxカーネルの場合、データとリ

    Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ウーン カーネルとか弄ったりのメモ
  • GitHub - google/brotli: Brotli compression format

    You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert

    GitHub - google/brotli: Brotli compression format
  • Brotli - Wikipedia

    Brotli is a lossless data compression algorithm developed by Google. It uses a combination of the general-purpose LZ77 lossless compression algorithm, Huffman coding and 2nd-order context modelling. Brotli is primarily used by web servers and content delivery networks to compress HTTP content, making internet websites load faster. A successor to gzip, it is supported by all major web browsers and

    Brotli - Wikipedia
  • Noise shaping - Wikipedia

  • レベルデザインに遺伝的アルゴリズムを活用する

    2015年Apr6日レベルデザインに遺伝的アルゴリズムを活用する こんにちは。オインクゲームズの新藤です。 先日、弊社のデジタルゲーム第二弾となる「OLYM」がリリースされました。OLYM はターン制限のあるパズルゲームで、各ステージごとに決められたターン数が設けられてています。このターン数以内に目標を達成できないと、クリア失敗になってしまいます。そのため、このターン数をどう決めるかが、難易度に大きく影響する一因となっています。OLYM では、ステージごとのターン数を決定するのに遺伝的アルゴリズムを活用したので、今日はそれをご紹介します。 最終的にやったことは非常にシンプルです。端的に言えば、AI に実際にパズル解かせて、何手で解けたかをレベルデザインの参考にするということです。この AI を作る際に、遺伝的アルゴリズムを活用しました。そもそもは「自動でパズル解いてくれる AI がいたら面

    レベルデザインに遺伝的アルゴリズムを活用する
  • 合議システムと文殊

    合議アルゴリズムと文殊のページ 電気通信大学 情報工学科 伊藤研究室 伊藤毅志、小幡卓弥、塙雅織 取り急ぎ、2009年5月3日公開開始! (全般にまだまだ工事中、、、) 1.合議とは 「三人寄れば文殊の知恵」という諺がありますが、さまざまに違う意見を持った人が集まって、意思を決定 しなくてはならないことは、人間社会ではよくあります。一人で結論を出すよりも、みんなで意見を出し合っ てその意見を集約することでより良い結論を導くことがければ、まさに「文殊の知恵」となります。しかし、逆に 「船頭多くして船山に登る」という諺のように、意見がまとまらずにうまくいかなくなってしまうこともありえます。 どちらになるかは、この多数の意見の中から、どうやって意見を決めていくのかにかかっていると言えます。 ここでは、複数の意見をもとに一つの意見を集約することを「合議」と呼ぶことにします。 2.

  • [CEDEC 2014]「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」 - 4Gamer.net

    [CEDEC 2014]ナムコ作品で見る乱数の歴史。「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」レポート ライター:箭進一 神奈川のパシフィコ横浜で行われた,ゲーム開発者向けイベントCEDEC 2014の最終日である2014年9月4日,「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」という講演が行われた。 登壇したバンダイナムコスタジオ HE技術部 加来量一氏 この講演のユニークな点は,旧ナムコの作品を「乱数」という視点から振り返るということだ。バンダイナムコスタジオ HE技術部のプログラマーである加来量一氏は,旧ナムコの初期作品50を解析し,それぞれの時代でどのような乱数が使われていたかを特定した。そこから見えてくる乱数技術改良の歴史を見ていくというのが,講義の主旨なのである。 1980年代のナムコアーケ

    [CEDEC 2014]「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」 - 4Gamer.net
  • 平方数かどうかを高速に判定する方法 - hnwの日記

    平方数とは、ある整数の平方(=二乗)であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します(PHPでもgmp_perfect_square関数として利用できます)。稿ではこの実装

    平方数かどうかを高速に判定する方法 - hnwの日記
  • b-Bit MinHashによる高速かつ省スペースな類似度判定 | SmartNews開発者ブログ

    ゴクロの浜です。ネットカフェでコードを書くのが好きです。 前回のエントリーでも触れられていますが、SmartNewsはホットな話題をユーザにお届けするために、常時、膨大な数のツイートおよびURLをクロールしています。こうして収集した記事に対し、様々な分析が施されますが、その中でも重要な処理の1つに、記事の類似度判定があります。内容の似通った記事をインデックスから発見し、グループ化する処理です。 毎秒、大量の新着記事が到着することから、この類似度判定は高速に実行する必要があります。また、インデックスを全てメモリに載せているので、類似度判定を実現する際の空間効率も要求されます。 今回は、SmartNewsが高速かつ省スペースな類似度判定のために使用しているb-Bit MinHashと呼ばれる手法を紹介します。2年前に、PFIの岡野原さんが非常に分かりやすい解説記事を書かれており、エントリー

  • Cookpadのレシピを機械翻訳する · Naoki Orii's blog

    前回のつくれぽ数の予測に引き続き、今回もCookpadネタです。 皆さんご存知の通り、英語版Cookpad(https://en.cookpad.com)が8月5日にリリースされました。 今のところ、英語圏のユーザがレシピを投稿するのではなく、どうやら日語版サイトのレシピを翻訳しているみたいです: 日の家庭料理レシピ数では世界一を誇るクックパッドレシピのなかから、海外の家庭でも手軽に作りやすい人気レシピ英語に翻訳していきます。(中略)オープン当初は約1,500品の掲載レシピ数からスタートし、早期に数万品まで増やしていく予定です (クックパッド英語版『COOKPAD』をリリース) そのため、Cookpadの日語のレシピ英語レシピは1対1の関係にあります。例えば「たまにはね♪塩鯖のトマト煮(^m^*)」を英語に翻訳したものは「Salted Mackerel, Simmered

  • Cのrand()よりmt19937の方が速いことがあるという話 - Educational NLP blog

    おはようございます。2年ぶりの記事ですね。 もう1月程前になってしまいましたが、id:sleepy_yoshi:20130720 で id:sleepy_yoshi さんが高速な非復元抽出をやっておられ、その中で、Cのrand関数を使っておられました。僕は、普段、std::mt19937を使っていたので、ちょっと比較してみた、という記事です。 C++11では、大別して、2つの擬似乱数生成の方法があります。1つはC(cstdlib)のrand関数で、高速ですが乱数の質が低く、もう1つはrandomヘッダのmt19937(メルセンヌ・ツイスタ)で、低速ですが乱数の質が高い(科学実験に適する)と、一般には思われていると思います。この高速・低速ですが、mt19937を使うことがボトルネックになるほど遅いことは殆どない、というのが今までの実感でした。なので、僕は、非復元抽出のような処理では、特にボト

    Cのrand()よりmt19937の方が速いことがあるという話 - Educational NLP blog
  • Closest pair of points problem - Wikipedia

    Closest pair of points shown in red The closest pair of points problem or closest pair problem is a problem of computational geometry: given points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane[1] was among the first geometric problems that were treated at the origins of the systematic study of the computa

    Closest pair of points problem - Wikipedia
  • PHYSICAL AUDIO SIGNAL PROCESSING FOR VIRTUAL MUSICAL INSTRUMENTS AND AUDIO EFFECTS

    Next  | Index  | JOS Index  | JOS Pubs  | JOS Home  | Search PHYSICAL AUDIO SIGNAL PROCESSING FOR VIRTUAL MUSICAL INSTRUMENTS AND AUDIO EFFECTS JULIUS O. SMITH III Center for Computer Research in Music and Acoustics (CCRMA) Preface Organization Book Series Overview Acknowledgments Errata Physical Signal Modeling Intro But How Does It Sound? What is a Model? The Basic Science Loop Models for Music

  • 様々な全域木問題

    1. 2013 年 3 月 20 日 @ NTT DATA 駒場研修センター 第 12 回日情報オリンピオック春季トレーニング合宿 様々な全域木問題 前原 貴憲 (@tmaehara) 国立情報学研究所 2. 自己紹介 • 前原 貴憲(まえはら たかのり) • Twitter: @tmaehara • Web: http://www.prefield.com (Spaghetti Source) • 略歴: 2004 沼津工業高等専門学校卒 2007 東京大学 工学部 計数工学科卒 2012 東京大学大学院 情報理工学系研究科卒 現在 国立情報学研究所 • 専門分野:連続・離散最適化,数値計算 2/ 71

    様々な全域木問題
  • へ、変態っ!!読めないからやめてっ!bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking

    この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記: Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています!必読ですね!!!!:) はじめに Y^´       ∨// /,∠ ,. ' /l/// /, ' , '/ ! | l }´     〈 〉    変  〈/ , ' // ̄`>< /// /// _,.=‐|'"´l l〈  変  / 〈    態.   ∨, '/l|   ,.'-‐、`//`7/  /''"´__ | ハ l丿  態   { 人)   ! !   (/!  |ヽ〈_ ・.ノ〃  〃 /  '/⌒ヾ.! ,' !く   ! !  (_ ト、__/   ヽ、_,.イ    /l l |:::::::```/:::::/...´..

    へ、変態っ!!読めないからやめてっ!bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking