「そらとぶあざらしさん」を遊んで頂くと、大体の温度感がご理解いただけるかと思います。 制限がされたページ今年の1月10日に、noteタイトルにもある「遺伝的アルゴリズムで最高にエッチな画像を作ろう！」というページを公開しました。 内容はタイトルの通りです。 ランダムに生成された2枚の画像から「エッチ」な方を選んでいくと、アルゴリズム学習によってだんだんとエッチな画像になっていくというものです。 遺伝的アルゴリズムで最高にエッチな画像を作ろう！ (エッチな画像が見れるとは言っていない) より このページには、筆者のささやかな収入源として、GoogleAdSenseの広告を貼っていました。 GoogleAdSenseとは、大企業であるGoogleが運営している個人クリエイター向けの広告プログラムです。 AdSenseのポリシーとして、「性的に露骨なコンテンツ」(Sexually explici
PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました。具体的には以下のバージョンで実装の大変更がありました。 PHP 7.0.0 HashTable高速化 (2015/11) Python 3.6.0 dictobject高速化 (2016/12) Ruby 2.4.0 st_table高速化 (2016/12) これらのデータ構造はユーザーの利用する連想配列だけでなく言語のコアでも利用されているので、言語全体の性能改善に貢献しています1。 スクリプト言語3つが同時期に同じデータ構造の改善に取り組んだだけでも面白い現象ですが、さらに面白いことに各実装の方針は非常に似ています。独立に改善に取り組んだのに同じ結論に至ったとすれば興味深い偶然と言えるでしょう2。 本稿では3言語の連想配列の従来実
fuzzy-finder を構成するアルゴリズム fzy や fzf といった fuzzy-finder を使うと、stdin などからリストを受け取り、ユーザの入力によってマッチする行を絞り込むことができます。このとき、入力文字列の各文字は隣接している必要がありません。例えば、以下の画像のように baz という入力が与えられた時、これにマッチする行が絞り込まれます。また、マッチした行のリストは、入力値に基づいてより最適な順番にソートされて表示されています。同じく以下の画像の例を見てみると、入力後では baz という行が foobarbaz よりもセレクタに近い位置に表示されていることが分かります。このように、入力値が曖昧でも目当ての文字列を即座に見つけることができるのが fuzzy-finder の便利なところです。 上記のような機能は、approximate string matchi
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
レベルデザインとはゲーム開発における作業の1つで、ゲーム中に登場するエリアの空間を設計したり、障害物やアイテムを配置したりして、プレイヤーが楽しめるステージを作成することです。ゲーム開発に携わっていない人にとっては取っつきにくそうなレベルデザインですが、レベルデザイナーのBobby RossさんがFPSやTPSなどのシューティングゲームにおけるレベルデザインの基礎を公式ブログで公開しており、わかりやすい内容になっています。 The Visual Guide for Multiplayer Level Design — Level Art+Design Portfolio http://bobbyross.com/blog/2014/6/29/the-visual-guide-for-multiplayer-level-design ◆01：デザインに考慮すべき要素 プレイヤーの行動はレベル
勤務先の社内勉強会で、機械学習を用いた文書推薦*1に関する基本的なことがらについて説明しました。その資料を公開します。 プログラマのための文書推薦入門 from y-uti 数学やコンピュータサイエンスを専門的に学んでいないエンジニアでも理解しやすいように、できるだけ数式を使わずに説明したつもりです。厳密性にはこだわっていないので、専門家からはあちこちツッコミを受ける内容かもしれません。 プログラマ向けということで、実際にコンピュータ上で動作を確認できるように、Wikipedia のデータを対象にして類似文書検索を行うスクリプトを作成しました。GitHub に置いてあります。 y-uti/document-recommendation · GitHub *1:推薦というより情報検索、類似文書検索という方が適切だったかもしれません。
必要にせまられて，pythonでgenetic algorithmを作成した．実際にはこれをスパコンでの特殊用途のために変更するから，汎用的でなくなる．．． アルゴリズムは以下： 特徴として： numpyやscipyなどが必要． ある目的のために，multiprocessingを利用して並列に関数値評価を行っている． 適応度を計算するルーチンも評価関数とは別にGAに外から与えなければいけない． ベストな値は保存して，ルーレット選択を行う． 終了判定は世代の上限のみ． ソースコードはここに載せるものなのかどうか悩ましいが．．． 使い方は面倒だから載せない．mainルーチンを見れば分かっちゃうかな． 以前のソースコードでは，multiprocessingを使った並列処理が間違っていて，並列処理になっていなかった． このバージョンでは，一応並列処理ができているはず．．． u""" Genetic
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル 1 2 3 4 5 CREATE TABLE user ( id INT UNSIGNED NOT NULL AUTO_INCREMENT, name VARCHAR(255) NOT NULL, PRIMARY KEY (id) )ENGINE=InnoDB; idカラムにIndex(PRIMARY KEY)を張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう？？ Indexとはその名の通り索引を意味します。特定のカラム
Posted by Nick Johnson | Filed under python, tech, coding, damn-cool-algorithms In a previous Damn Cool Algorithms post, I talked about BK-trees, a clever indexing structure that makes it possible to search for fuzzy matches on a text string based on Levenshtein distance - or any other metric that obeys the triangle inequality. Today, I'm going to describe an alternative approach, which makes it p
The crucial idea in speeding up the brute force n-body algorithm is to group nearby bodies and approximate them as a single body. If the group is sufficiently far away, we can approximate its gravitational effects by using its center of mass. The center of mass of a group of bodies is the average position of a body in that group, weighted by mass. Formally, if two bodies have positions (x1, y1) an
「wikipediaは6回リンクを辿ればどのページでもいけるらしいｗｗｗ」ということで話題になったのを受けて、その最短経路を探索するためのウェブサービス「うぃきったー」というのが登場しました。 うぃきったー http://wikitter.info/ 使い方は簡単、「スタート」に開始ページ名、「ゴール」に終了ページ名を入れて「探索開始」ボタンを押すだけ。例えば「フェイト・テスタロッサ」から「東尋坊」に、6回以内のリンクで行けるかどうかを見てみましょう。 『フェイト・テスタロッサ』→『声優』→『1990年代』→『男はつらいよ』→『東尋坊』という信じがたい経路で見事にたどり着きました。探索時間は82.88884ミリ秒。結果はそのままさくっとTwitterでつぶやくことも可能です。 また、「過去の結果」ページには以下のようにして様々な経路が記録されており、「これはすごい！」と思った場合には「スゴ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く