Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
レーベンシュタイン距離 - Wikipedia
レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される[1]。名称は、1965年にこれを考案したロシアの学者ウラジーミル・レーベンシュタイン (露: Влади́мир Левенште́йн) にちなむ。 レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。 例[編集] 実際的な距離の求め方を例示すれば、「kitt
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
Bresenham's line algorithm - Wikipedia
Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap image (e.g. on a computer screen), as it uses only integer addition, subtraction, and bit shifting, all of which are very cheap opera
アルゴリズムイントロダクション輪講 動的計画法の発表資料 - てっく煮ブログ
2009年3月2日に、はてな京都オフィスで開催された アルゴリズムイントロダクション輪講 の第12回で「動的計画法」について発表しました。資料をここにおいておきます。View more presentations from nitoyon.分かりやすくしようと気合を入れてまとめたら165ページの大作になっちゃいました。無駄に長くてすいません。アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)作者: T.コルメン, R.リベスト, C.シュタイン, C.ライザーソン, Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一出版社/メーカー: 近代科学社発売日: 2007/03メディア: 単行本
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
アルゴリズムコンテストの挑み方 (2) - d.y.d.
21:25 08/10/27 論文 の締め切り終わったら頑張った自分へのご褒美（笑）であれとこれとそれをやる時間をとるぞー！ ……みたいなことを思っていたはずなのに、いざ提出し終わると気が抜けて何一つやる気がでない問題。 困った困った。 ナイチル たくさん人がいらしてる今のうちに 「ナイトメア☆チルドレン」新装版 面白いよみんな買おうぜ！ などと書いてみる。 自分のマンガの趣味はわりと平凡だと思ってて、 流行ってるマンガは大抵好きだし自分の好きなのはだいたい流行ってるし。 なのになぜだか藤野もやむ作品だけは唯一の例外で、とっても不思議でならない。 100回くらいアニメ化されてて然るべきだと思う。 何回か書いてますがとにかく最終話が好きで、 そこまでのシナリオが一気に集まって一つ一つのセリフが３倍の重みを持つように収斂していく幕引き。 あれは良い。 17:12 08/10/24 アルゴリズム
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GC¥¢¥ë¥´¥ê¥º¥à¾ÜºÙ²òÀâ ÆüËܸì¤Î»ñÎÁ¤¬¤¹¤¯¤Ê¤¤GC¥¢¥ë¥´¥ê¥º¥à¤Ë¤Ä¤¤¤Æ¾ÜºÙ¤Ë²òÀ⤷¤Þ¤¹ ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼ÊÔ½¸ GC ºÇ½ª¹¹¿·¡§ author_nari 2010ǯ03·î14Æü(Æü) 20:47:11ÍúÎò Tweet ¤³¤ÎWiki¤¬Ìܻؤ¹½ê GC¤È¤Ï¡© GC¤ò³Ø¤ÖÁ°¤ËÃΤäƤª¤¯»ö ¼Â¹Ô»þ¥á¥â¥ê¹½Â¤ ´ðËÜ¥¢¥ë¥´¥ê¥º¥àÊÔ Reference Counter Mark&Sweep Copying ±þÍÑ¥¢¥ë¥´¥ê¥º¥àÊÔ IncrementalGC À¤ÂåÊÌGC ¥¹¥Ê¥Ã¥×¥·¥ç¥Ã¥È·¿GC LazySweep TwoFinger Lisp2 Pa
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
贅沢は敵ですっ！ - methaneのブログ
http://d.hatena.ne.jp/w_o/20060419#p1 ネタ受け。組み込み屋ならスマートにムダを消せないとね。 struct q { char *buf; int buflen; int head; int tail; }; void init( struct q *q, char *buf, int len ) { q->head = 0; q->tail = 0; q->buf = buf; q->buflen = len; } void push( struct q *q, char c ) { if ( q->head == q->tail + q->len ) { /* 知らない */ return; } q->buf[q->head%q->len] = c; //< これがミソ q->head++; } int pop( struct q *q ) { in
ナンバープレース(数独）
ナンプレ（ＮｕｍｂｅｒＰｌａｃｅ）も有名なパズルですので、ルールの説明は割愛します。 ナンプレは、Hand Ｓｏｌｕｔｉｏｎ向きのパズルです。ナンプレの問題そのものをコンピュータで解くのは簡単ですので、あまり面白くありません。 ここでは、皆さんも一度は気にされた事があると思われる以下の話題を扱ってみます。 （１） 解法アルゴリズム 一般的な解法は、試行錯誤を用いたアルゴリズムでしょう。 しかし、答えは、ユニークになるのにどうして解法アルゴリズムには試行錯誤が必要なのでしょうか？ 確定的な解法アルゴリズム（試行錯誤を用いないで解く方法）は存在しないのでしょうか？ （２） 作図問題 枠だけを指定されたとき(枠の数とその位置）、その枠の数字をきめてナンプレの問題を完成させるという問題です。（これがうまくいくと、好みのレイアウトのナンプレ問題が簡単に作れてしまいます） 例えば、以下のような問題は作
lucille 開発日記 » Flash sort
http://www.neubert.net/FSOIntro.html I think flash sort algorithm( O(N) time complexity ) is one of the fastest sorting algorithm in the world. Flash sort というソートアルゴリズムが、なかなかよさげです。 紹介文には、『クヌースは「その場での(in-situ, つまり extra なメモリ領域がいらない)ソートアルゴリズムは、平均して O(n log n) 時間を要するだろう」という予測をしたが、しかしこれはもうハズレである。新しいアルゴリズムであるこのフラッシュソートは、 O(n) 時間のその場でのアルゴリズムである』とあるくらいですから、なんとも”スゴ味”が伝わってきます。 ソートのアルゴリズムといえば、 o クイックソート(+ 挿
d.y.d.
21:21 05/09/29 ですのーと 本棚をぼけーっと 見ててふと、写真で左から４冊目の数論入門、訳者名と著者名をあわせて やがみライト だ！ と、大発見をした気分になっていました。どうでもいいですね。 20Q 20Q。おお、商品化されるのか。 これは買わねば！ 05:31 05/09/29 ICFP Programming Contest 結果でてますね。 combat３位おめでとーございます。 今回のコンテストは二段階制になっていて、『最初の３日間で、 テーマとして与えられたゲーム（マップ上の銀行から金を盗んで逃げる"泥棒"と、 それを捕まえるべく頑張る"警官"の駆け引きゲーム）の２種類のボットを作ってsubmit。 その２週間後にゲームが微妙に拡張されたり仕様変更されたりするので、 １日でボットを作り直して、再submit』というものでした。 もちろん最終的ルールにおいて一番強い
OBB vs AABB - Radium Software Development
iPhoneの一般修理店は予約なしでも来店できる？ 基本的には飛び込みで修理に行ってもOK iPhoneを置いていたソファにうっかりと腰かけてしまい、パネルを割ってしまった、こんな時はスマホの一般修理店へ行きましょう。画面割れは、スマホやタブレットの故障原因として非常に多いものです。予約なしで突然お店に行っても平気かしらと、不安に思う方々もいらっしゃるかもしれません。結論としては特に問題はなく、予約なしで訪問しても画面割れの修理はお願いできます。 ただし他のサービス業のお店同様、予約なしの場合、お店が混雑していると順番待ちをしなければいけないです。特に繁盛しているスマホ修理のお店だと、行列が店内で出来ており、予約なしだと、自分の順番が巡ってくるまで長時間待たされる可能性があります。平日の朝、昼なら利用客が少ない場合が多く、飛び込みでも比較スムーズに修理が頼めます。 予約は入れた方が時短に、
アルゴリズムとデータ構造 演習第 11 回
アルゴリズムとデータ構造 演習第 11 回 サーチ２（平衡木） 平衡木（へいこうぎ） （アルゴリズムＣ 第２巻 p.27） として 2-3-4 木 （アルゴリズムＣ 第２巻 p.28） を扱います。 通常の木とは違い、バランスのとれた（平衡した）木を作ることができます。 木が平衡している（木の高さが低い）と、 データの探索を速く行うことができます。 問題１ ［印刷用 PostScript］ (1) 次のデータから 2-3-4 木を作成しなさい。 ただし、途中の過程も書くこと。 C O C A C O L A (2) (1) で作成した木を赤黒木で書き直しなさい。 演習第７回でやったような二分木の作り方では、 バランスの悪い偏った木ができることがある。2-3-4 木を用いれば、 バランスのとれた（平衡した）木を作ることができます。 二分木では という手が二本のノード（2-ノード）だけでしたが
Red/Black Tree Demo
As of 24 June 2006 every important rule which the applet uses to execute an insertion or deletion step is displayed in a textfield prior to its graphical rendering. We believe this will help understand the complex interaction of rules and current tree configuration, especially in the case of deletion. Rules have numbers which correspond with detailed explanations at the bottom of this page (s
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
<h2>C言語によるアルゴリズム(コメント付き)</h2>
http://members.at.infoseek.co.jp/mukun_mmg/mmg/cpp.html
アルゴリズムとデータ構造(pdf)