タグ: アルゴリズム

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[JavaScript] UUID.js を更新しました!

以前公開したまま放置していたJavaScript用のUUID生成ライブラリ、UUID.jsの最新バージョンを公開しました!

大幅な機能追加とバグ修正が行われて、ホスティング先もCodeReposからGitHubに変更されました!

LiosK's UUID.js at master - GitHub

UUID.js: The RFC-compliant UUID generator for JavaScript.

↓こんな感じのRFC 4122に準拠したUUIDをJavaScriptで簡単に生成することができます!

368606ed-98b5-11df-8fd2-0ba59ea365b9

UUIDは大量に生成しても重複が起きないように工夫されているので、中央で統制を取らなくとも一意のIDを生成できて何かと便利です!

使用例や動作サンプルは続きで!

続きを読む

スポンサーサイト

JavaScriptの乱数の精度の話

前回の記事で予告したとおり、今回はJavaScriptのMath.random()で生成できる乱数の精度の話。

前回の記事で、JavaScriptでは2^53未満の正整数を扱うことができるということがわかったから、今回の記事では2^53未満のランダムな正整数を生成してみる。

具体的には↓のようなコード。

var ub = Math.pow(2, 53), list = [];
for (var i = 0; i < 16; i++) {
  list[i] = Math.floor(Math.random() * ub).toString(2);
  while (list[i].length < 53) { list[i] = "0" + list[i]; }  // padding
}
window.alert(list.join("\n"));

続きを読む

[Concurrent Haskell] 無限リストが止まらない

HaskellのControl.Concurrent.Chanを使って、簡単な並行処理プログラムを作ろうとして試行錯誤したのでメモ。

Control.Concurrent.ChanはHaskellで並行処理をするときに使うことができるFIFOキューライブラリ。複数のスレッドからキューにデータを流し込んで、別のスレッドがそのデータを読み取って処理をしたりすることができる。

Control.Concurrent.Chanを使えば、スレッド間の排他処理とかを全く考えずに済むので、簡単に並行処理プログラムを書けるかと思っていたけど、処理終了時の扱いに悩んだので、ちょこちょこと試行錯誤してみた。

詳細は続きで。

続きを読む

UUID.js を CodeRepos に放流しました

[追記] UUID.jsの最新版はGitHubで公開されています! (解説記事)

表題の通り、UUID.js を CodeRepos に放流しました!

root/lang/javascript/UUID.js - CodeRepos

まだまだ育て甲斐のある状態なので、どんどんいじっちゃってください!

続きを読む

UUID.js が UUID version 1 に対応しました

[追記] UUID.jsの最新版はGitHubで公開されています! (解説記事)

[追記] UUID.js の最新版は CodeRepos に放流しました。

今までは UUID version 4 にしか対応していなかった UUID.js を、UUID version 1 にも対応させてみました。

UUID.js

使い方

使い方はやっぱり簡単。

1. UUID.js をロードする
<script type="text/javascript" src="uuid.js"></script>
2. 引数に { version: 1 } を渡して生成する
var uuid = UUID.generate({ version: 1 });  // "3db93340-91f7-11dd-a2aa-69df78d74e01"

引数を渡さずに生成すれば、前回通り version 4 の UUID を生成するよ!

続きを読む

[UUID.js] バグがあったので修正しました><

[追記] UUID.jsの最新版はGitHubで公開されています! (解説記事)

[さらに追記] UUID.js の最新版は CodeRepos に放流しました。

[追記] 新バージョンを公開しました!

前回のエントリーで公開したばかりの UUID.js ですが、いきなりバグが出てしまったので修正版を公開しました><

UUID.js (修正済み)

バグの内容は、Math.random() の精度が 32 ビットしかないブラウザで、生成される UUID の下四桁が全部ゼロになってしまうという問題でした><

しかも、その「Math.random() の精度が 32 ビットしかないブラウザ」っていうのが、Opera, Safari, Google Chrome の 3 つで、IE と Firefox 以外では再現してしまうバグでした><

ちょっと確認すればすぐわかるはずの初歩的なミス><

バグの原因は、32 ビットの精度しかない乱数を 48 ビットとして扱ったことによるものだったので、乱数生成関数を工夫して 32 ビット精度の乱数から 48 ビットの乱数を生成できるように修正しました><

[JavaScript] UUID.jsを作成しました

[追記] UUID.jsの最新版はGitHubで公開されています! (解説記事)

[さらにさらに追記] UUID.js の最新版は CodeRepos に放流しました。

[さらに追記] 新バージョンを公開しました!

[追記] バグが見つかったので修正版を公開しました><

UUID (Universally Unique Identifier) を生成する JavaScript ライブラリを作ってみたので公開します。

UUID.js

UUID は、128 ビットの長さを持つ識別子です。普段使うときは↓のように 16 進法で表現されて、ところどころにハイフンが入ります。

e8783d5e-90dd-4af9-8aa6-371d43fcbcb4

UUIDは 128 ビットで 2128 = 3.4e+38 通りもあるので、偶然同じ ID が生成されることが (ほぼ) ないんです。だから、ID の一意性を維持するためにわざわざ統制する必要がなくて、面倒くさがりな人間にとっては便利すぎる ID なんですね!

で、そんな便利な UUID を JavaScript で使うためのライブラリを探してみたのだけれど、あまり良いものが見つからず。英語版 Wikipedia に書いてある JavaScript UUID Class というのも試してみたけれど、RFC 4122 に書いてある UUID の仕様とはちょっと違う感じの不思議な ID を生成するのでいまいち。ということで、自分で RFC を読みながら実装してみました。

使い方等は続きで。

続きを読む

[Haskell] 素数列を生成するアルゴリズム×3

最近すっかりブログから離れていたので、リハビリがてらにメモ代わりのエントリー。

Haskellで素数の無限リストを生成する関数を3つほど作ったのでメモ。

primes1 = 2:f [3,5..] where f (x:xs) = x:f [y | y <- xs, mod y x /= 0]

primes2 = 2:filter f [3,5..]
    where f n = all ((/= 0) . (mod n)) (takeWhile ((<= n) . (^ 2)) primes)

primes3 = 2:f [3] [3,5..]
    where f (x:xs) ys = let (ps, qs) = span (< x^2) ys
                        in  ps ++ f (xs ++ ps) [z | z <- qs, mod z x /= 0]

primes2に関しては1000000個の素数 - HaHaHa! - haskellを、primes3に関しては誇大宣伝ではないエラトステネスの篩 - HaHaHa! - haskellをそれぞれ参考にした。

以下解説。

続きを読む

HaskellでProject Eulerに挑戦してみた

id:gomi-boxに触発されて、Project Eulerに挑戦してみた。

Project Eulerみたいな、アルゴリズム的なものを書いて一人でくねくねする遊びは、Haskellとの相性が良すぎる。

コードは続きで。

続きを読む

昨日の問題を遺伝的アルゴリズムっぽく

昨日の問題[1][2][3]を、遺伝的アルゴリズムのようなもので解いてみた。解くのに使ったPerlコードは最後に添付。

一応、前々回のエントリで提示したサンプルデータに対しては、10個の実験枠と40人の参加希望者を全て使い切る最適解を一つ見つけることができた。パラメータ変えながら50回くらい繰り返した末にだが。

とはいえ、実験枠数と参加希望者数の関係が変わったりするとまだうまく最適解を推測できないようなので、もう少しチューニングしたほうがよさそう。

続きを読む

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。