再帰的な構造のデータの同値性判定はどうしたらいいか - 貳佰伍拾陸夜日記
数日前にTwitterで, JavaScriptのオブジェクトに対する===の挙動が初心者には難しいみたいな話を見かけた. 発端や周辺の議論をちゃんと追いかけてないからとくに出典は貼らない. たぶん元々の話は「へぇ, こういう挙動なんだ, 簡単ではないね」くらいの話だったのかもしれない. 自分のタイムラインの観測範囲では「そうだそうだ, (参照の同一性ではなく)同値性にしとけばいいのに」と思っている人もそれなりにいそうに見えた. 個人的にも同値性が簡単に確認できるとよい気はするものの, 「なんでそうしないんだ, オブジェクトの中身を確認していくだけだろ!」みたいな簡単な話ではないことも知っているため, 以下のようなツイートをしたのだった. JavaScriptのオブジェクトの同値性、再帰的な構造とか作るとぜんぜん自明じゃないんだよなぁ。リンクの構造は違うけどプロパティを辿ったときのパスはど
高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
Multiplicative Persistence - Qiita
Multiplicative Persistence 11を求めたという話題がありましたので、Pythonで実装してみました。自力で書いたあと、調べてさらに探索空間を減らして高速化しました。 自力で書いたもの できるだけ大きなMultiplicative Persistence Nを持つ数（以下MP-N数と書く）を求めれば良いので、MP-N数の中で最小の数（以下最小MP-N数と書く）のN=11を求めることとした。このとき、各桁を掛け算するというMPの求め方から、桁の並べ方はどうでもよいので、各桁の数字が単調非減少になるような場合だけを対象として探索空間を減らした。 0, 1はN > 2では最小MP-N数には含まれない（0があるとMP-N=1になるため、1は単にその1を除いた数とMP-Nが同じでかつ除いたほうが小さい数であるため）として省略してある。 from collections imp
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
PHP の壊れた mt_rand の品質を統計的に検証した - iwiwiの日記
メルセンヌ・ツイスターと似て非なるアルゴリズムが実装されていたことが発覚して話題の PHP の mt_rand 関数の品質を統計的に検証しました．果たして，PHP の「壊れた」mt_rand は安心して使うことができるのでしょうか……？ ちなみに，結論から言うと，PHP の壊れた mt_rand は，（少なくともこのテストの範囲では）本家メルセンヌ・ツイスターと遜色ない品質を持っているようです．ただし，最後に PHP の乱数の別の懸念点についても紹介します． 壊れた mt_rand とは PHP の mt_rand は，ドキュメントによると，有名な乱数生成アルゴリズム「メルセンヌ・ツイスター」を利用して高品質の乱数を生成する関数です．ところが，どうやら一部では知られていたこととして，PHP の mt_rand の実装にはバグがあり，本家メルセンヌ・ツイスターと挙動が一致していませんでした．
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
Rooms and Mazes: A Procedural Dungeon Generator – journal.stuffwithstuff.com
← → December 21, 2014 code dart game-dev roguelike Several months ago I promised a follow-up to my previous blog post about turn-based game loops in my roguelike. Then I got completely sidetracked by self-publishing my book, Game Programming Patterns, and forgot all about it. I totally left you hanging. Well, I finally got some time to think about my roguelike again and today, I’m here to… keep yo
[KMP77] を読んでみた - d.y.d.
17:53 14/12/22 ソートの逆流れ クイックソートってあるじゃないですか、クイックソート。 配列、たとえば [4,2,1,7,0,6,5,3] があったときに、 小さい方を左に、大きい方を右にまず適当に集める。 この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、 分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7] が出来上がるというアルゴリズムです。 逆向き！ このデータの流れを「逆向きに」見てみたい。つまり、ソートが終わった最終状態から話が始まります。 しかも、さっきから説明なしで意味ありげにくっついていた、 「入力配列で元々どの位置にあったか」を表す値に注目していきます。 0の上に[4]がくっついているのは、最初は値0は配列のインデックス[4]の位置にあった、 ということを意味しています。（上のソート
![[KMP77] を読んでみた - d.y.d.](https://cdn-ak-scissors.b.st-hatena.com/image/square/e6fe840dfdcca31b69f48171e0de96a69b93595b/height=288;version=1;width=512/http%3A%2F%2Fwww.kmonos.net%2Fwlog%2Fsub%2Fdual%2F8.png)
［CEDEC 2014］「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」 - 4Gamer.net
［CEDEC 2014］ナムコ作品で見る乱数の歴史。「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」レポート ライター：箭本進一 神奈川のパシフィコ横浜で行われた，ゲーム開発者向けイベントCEDEC 2014の最終日である2014年9月4日，「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」という講演が行われた。 登壇したバンダイナムコスタジオ HE技術部 加来量一氏 この講演のユニークな点は，旧ナムコの作品を「乱数」という視点から振り返るということだ。バンダイナムコスタジオ HE技術部のプログラマーである加来量一氏は，旧ナムコの初期作品50本を解析し，それぞれの時代でどのような乱数が使われていたかを特定した。そこから見えてくる乱数技術改良の歴史を見ていくというのが，講義の主旨なのである。 1980年代のナムコアーケ
data.priority-mapを使ってダイクストラ法で迷路を解く - Homoiconic Days
(このエントリは Clojure Contrib Library Advent Calendar 14日目の記事です。) はじめに 今回はdata.priority-mapについてです。以前はclojure.contrib.priority-mapと呼ばれていました。 data.priority-mapは優先度つきマップ(priority map)の実装を提供します。優先度つきマップは，Clojureコアが提供するソートされたマップ(sorted map)と非常に類似したデータ構造です。両者の違いは，ソートされたマップがキーによってソートされるのに対し，優先度つきマップは値によってソートされるという点です。 今回は，data.priority-mapの基本的な使い方と，優先度つきマップの応用例としてダイクストラ法を使って迷路を解く例を見ます。 インストール data.priority-ma
Tetris Printer Algorithm
By rotating, positioning and dropping a predetermined sequence of pieces, the Tetris Printer Algorithm exploits the mechanics of Tetris to generate arbitrary bitmap images. For a full discussion of the algorithm, see the link below. http://meatfighter.com/tetrisprinteralgorithm/ Royalty Free Music Kick Shock Kevin MacLeod (incompetech.com) Licensed under Creative Commons: By Attribution 3.0 ht
Gauche Devlog - Fun with primes
About On development of Gauche, and other topics related to Lisp/Scheme in general. More details. Author Shiro Kawai, shiro at acm dot org. Recent Entries Exact and repeating decimalsRunning prebuilt Gauche on GitHub workflowCaching formatter procedurePipeworksReal numerical functionsPretty print indentationSegmented completionHints for unbound variable error:immutable slot optionSource info propa
Tabasco Sort: a super-optimal merge sort - Paul Khuong: some Lisp
EDIT: 2012-08-29: I added a section to compare comparison counts with known bounds for general comparison sorts and sorting networks. In an earlier post, I noted how tedious coding unrolled sorts can be. Frankly, that’s the main reason I stopped at leaf sorts of size three. Recently, Neil Toronto wrote a nice post on the generation of size-specialised merge sorts. The post made me think about that
Why You Should Be Excited About Garbage Collection in Ruby 2.0 - Pat Shaughnessy
While not very glamorous, Bitmap Marking Garbage Collection is a dramatic, creative innovation! You may have heard last week how Innokenty Mihailov’s great Enumerable::Lazy feature was accepted into the Ruby 2.0 code base. But you may not have heard about an even more significant change that was merged into Ruby 2.0 in January: a new algorithm for garbage collection called “Bitmap Marking.” The de
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムビジュアル大事典
GitHub - soniakeys/meeus: Implementation of "Astronomical Algorithms" by Jean Meeus
ウェーブレット木の世界 - Preferred Networks Research & Development
はてなブログ | 無料ブログを作成しよう
Engineering a list merge sort - Paul Khuong: some Lisp
http://rubysource.com/narihiro-nakamura-rubys-gc-innovator/
