最小完全ハッシュ関数の作り方 を JavaScript で - てっく煮ブログ
JavaScriptActionScript/Flex ネタが続いているので、たまには JavaScript ネタを。はてブ経由で知った 最小完全ハッシュ関数の作り方 が面白そうだったのだけど、「最小完全ハッシュ関数」が何か分からないまま読み進めたら、やっぱり話が分からなくなってしまった。分からないまま JavaScript に移植。 /* 順列型の最小完全ハッシュ関数 */ function ChangeNumber(arr) { var work = arr.concat(); var hash = 0; // 階乗値テーブル作成 var FACTOR = [1]; for(var i=0; i { FACTOR.unshift(FACTOR[0] * (i+1)); } for(var i=0; i { hash += work[i] * FACTOR[i]; for (j=i+1;
Algorithm - Suffix Array を JavaScript で再発明してみた : 404 Blog Not Found
2012年01月16日16:30 カテゴリアルゴリズム百選Lightweight Languages Algorithm - Suffix Array を JavaScript で再発明してみた WEB+DB 総集編 [Vol. 1〜60] もう10年以上前に某社のCTOだったころ、Suffix array(接尾辞配列)の解説を毎週の技術者ミーティングでしたら一名を除いて「ハァ?」状態だったことを思い出しつつ。 Suffix Arrayは何が画期的だったのか? 以下は、計算機科学者でなくても直感的に理解できると思います。 ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))がかかる。 ソート済みのデータであれば、二分探索でデータの大きさの対数時間(O(logn))でキーを検索できる。 さらにキーからIDを定数時間で作成でき
Type Inference brings JS improvements to Firefox Beta – Future Releases
Blog by Brian Hackett, Firefox Engineer Firefox 9 features the release of Type Inference, or TI, a research project under way for over a year. TI is a feature in the SpiderMonkey Javascript engine which generates type information about Javascript programs through a combination of analyzing the program’s code and monitoring the types of values as the program executes. This type information is used
Fast and Precise Hybrid Type Inference for JavaScript
Fast and Precise Hybrid Type Inference for JavaScript Abstract1 JavaScript performance is often bound by its dynamically typed na-2 ture. Compilers do not have access to static type information, mak-3 ing generation of efficient, type-specialized machine code difficult.4 To avoid incurring extra overhead on the programmer and to im-5 prove the performance of deployed JavaScript programs, we seek6 t
JavaScriptの文字列を反転する１０の方法とそのパフォーマンス - 風と宇宙とプログラム
はじめに JavaScriptで文字列を反転する１０の方法を（無理矢理？）思いついたので、ちょっと簡単に紹介したい。また、それぞれについて、各ブラウザでパフォーマンスを測定してみたので、その結果も合わせて載せる。 文字列のStringオブジェクトには、部分切り出し(substring, slice)や置換(replace)、連結(concat)など豊富な機能があるのに、反転(reverse)機能はない。Arrayのreverseはあるのに、Stringのreverseがないのはどうしてなのだろうか。 各ブラウザとそのバージョンは以下の通り： Chrome Firefox Opera Safari IE 13.0.782.112 m 6.0 11.50 5.1(7534.50) 8.0.7600.16335 rev01: C言語的発想 空の配列を作って、そこに元の文字列の後ろから１文字つづ入
A* pathfinding algorithm in JavaScript
A JavaScript implementation of the A* algorithm for pathfinding and graph traversal. Designed for browser-based games using HTML5/canvas with JavaScript. Your browser must support canvas to view this demo. Your browser must have JavaScript enabled.
JavaScriptの乱数の精度の話 / LiosK-free Blog
2010-06-03 カテゴリ: Client Side タグ: JavaScript Tips アルゴリズム 前回の記事で予告したとおり、今回は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 }
JavascriptのMath.random()でユーザートラッキングができるという話 - kogelab::memo
表題の件について。 地味な話ですが、javascript（というかECMAの仕様）にあるMath.random()には、乱数のシードを与える方法が無いようです。 そんなわけで、われわれ一般市民は各ブラウザが独自に実装している、謎のシードで初期化された謎のアルゴリズムで作られた乱数を通常使うわけですが。 Mozillaからこんなの出てた。 曰く、Math.random()のシードによる初期化は、ブラウジングセッションごとに1度しか行われないと。 で、シードはまあ、かぶる率そんなに高くなさそうなので、そのシードをUSERの（擬似的な）ID代わりにしてしまえば、ユーザーのトラッキングができるよーん、とのこと。 はじめ読んだとき、「おおー、かっけー！」と思ったんですが、ちょっと待て。 シードって外から取れんのか。 というわけで、色々調べたところ、各ブラウザは（多分IEも）線形合同法による擬似乱数を
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
javascript - Mathを再発明してみた : 404 Blog Not Found
2010年09月14日06:30 カテゴリMathLightweight Languages javascript - Mathを再発明してみた 「基本というからには四則演算で三角関数実装しないとねー」と思いつつ書いていたら… C言語による最新アルゴリズム事典 奥村晴彦 [javascript]三角関数の基本 Math.random()を除いてMathを全部再発明しおえたので。 多倍長演算バージョンを作る時の下ごしらえにもなるかも。 下ごしらえ 仕様は Math - MDC アンチョコはもはや最新というにはあまりに古い、しかし代わりなき「C言語による最新アルゴリズム事典」。低レベルな車輪を再発明する人必携! 初期化と定数 定数の精度はおおげさに。 MyMath = {}; MyMath.E = 2.718281828459045235360287471352662497757; MyMat
MersenneTwister JavaScript Version
March 2025 (1) January 2025 (1) November 2024 (1) July 2024 (1) June 2024 (2) January 2024 (1) September 2023 (1) April 2023 (2) March 2023 (1) November 2022 (3) October 2022 (1) September 2022 (1) June 2022 (1) July 2021 (1) May 2021 (1) April 2021 (2) February 2021 (1) January 2021 (1) September 2020 (1) July 2020 (2) March 2020 (1) August 2019 (1) April 2019 (2) August 2018 (1) May 2018 (1) Apr
TeXの行分割アルゴリズムをJavaScript実装 | エンタープライズ | マイコミジャーナル
TeX is a typesetting system designed and mostly written by Donald Knuth. Bram Stein氏がTeX line breaking algorithm in JavaScriptにおいて、JavaScriptでKnuth/Plass行分割アルゴリズムを実装した例を紹介している。Knuth/Plass行分割アルゴリズムはTeXで使われている行分割アルゴリズム。これをJavaScriptで実装し、HTML5 Canvas要素経由で表示するというもの。TeX line breaking algorithm in JavaScriptではそれ以外にもCSS text-align: justifyの表示結果や、左寄せ、左寄せをベースに使った中寄せ、可変幅の例が掲載されている。 TeX line breaking algorit
Tutorial: Building a Force Directed Graph from XML on kylescholz.com :: blog
Part of my upcoming talk at The Ajax Experience is, of course, about graph-based data visualizations using JSViz. I've worked up a couple of tutorials using the new JSViz 0.3.1 and I'm sharing abbrieviated versions of them here. Conference attendees should find these posts useful as a recap and additional reference for coding your own apps. In this first tutorial, we'll introduce the JSViz 0.3.1 A
組込みのsortが自作ソートより遅いらしい - inamori’s diary
http://blog.livedoor.jp/dankogai/archives/50695905.html さもありなんという感じだ。 pushもsliceも遅かったし。 http://d.hatena.ne.jp/inamori/20061107 実際にやってみたところ、 IE6では自作ソートの方がやや遅い、 Firefox1.5でも同様だった。 ただ、このコードを見るともうちょっと速くできそうだ。 ほとんど他人のふんどしで失礼だが、 ちょっと改変してみよう。 function SortBench(n){ ... var qsort = function(ary, cmp){ function q(ary, head, tail) { ... return ary; } return q(ary, 0, ary.length - 1); } ... }; このqは外に出したほうが速い
FN0212002 - 配列をランダムに並替えるメソッドを定義する[上級テクニック] - Flash : テクニカルノート
Platform: All Version: 5.0 and Above このノートでは、Arrayオブジェクトにエレメントをランダムに並替えるメソッドを定義する上級者向けのサンプルを、ご紹介します。 1. Arrayオブジェクトにメソッドを定義する 'new'演算子を使ってインスタンスを生成するオブジェクト(クラス)には、'prototype'プロパティがあります。この'prototype'プロパティに'function'を設定すると、そのオブジェクト(クラス)にメソッドを追加して定義することができます。 Arrayもそうした定義のできるオブジェクトのひとつです。ArrayオブジェクトにメソッドnewMethodを定義するには、つぎのようなスクリプトを記述します。 Array.prototype.newMethod = xNewMethod; function xNewMethod ()
文字列繰り返しベンチマーク take 2 - moriyoshiの日記
追記: もっとよいアルゴリズムについて教えてもらいました (1, 2)。新しい結果とコードはこちら。 TraceMonkeyの結果が不正確だったので取り直した件ですが…。 速くはなったけど、あまり変わらず。 という残念な結果に。 Chrome FF3.0 FF3.1b2 IE6 IE8 Opera9.63 Safari WebKit concat_op 98 193 138 1230820.5 375 172 263.5 175.5 join 109.5 258 166.5 1398.5 398.5 648.5 200 82.5 hybrid 20.5 93.5 82 70 39 31.5 36 33 bulk 1 104.5 86 17633 23 15.5 55 54 (単位は ms)
同じ文字列のn回繰り返しを作る「最速」の方法 - by edvakf in hatena
同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang パズルっぽくておもしろかったのでやってみた。と、別のところにも書いたのだけど、あそこじゃあ反応が薄いので、見てる人が多そうなこっちで聞いてみる。 function(s,n){ var q = ''; while(n){ if(n%2) q += s; s += s; n >>= 1; } return q; } javascript:alert((function(s,n){var q='';while(n){if(n%2)q+=s;s+=s;n>>=1;}return q;})('hoge',10)) //=> hogehogehogehogehogehogehogehogehogehoge 速さのベンチはこっちの一番下にある data:uri をアドレス欄に入れてみたらいいと思います。 もっ
同じ文字列のn回繰り返しを作る最速の方法を探求してみた - moriyoshiの日記
注意: FF3.1b2の結果が不正確です。取り直したのはこちら。 ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 あらまし JavaScriptの文字列型 (およびStringオブジェクト) はJavaのようにイミュータブルなので、こういう文字列構築を行う方法としては、以前から、+や+=演算子を用いるよりも、一旦Array()に入れておき最後にjoin()するという方法が有効だと言われていてですね、まあ確かに、文字列用メモリ領域の確保
Introducing SquirrelFish Extreme.ja – WebKit – Trac
This page contains a Japanese translation of the post on Surfin' Safari blog "Introducing SquirrelFish Extreme". この文書について "Introducing SquirrelFish Extreme" の日本語訳です http://webkit.org/blog/214/introducing-squirrelfish-extreme/ 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... SquirrelFish Extreme を紹介します ちょうど三ヶ月前、私達は SquirrelFish を発表しました。 これは私達の JavaScript エンジンを大改造するもので、 高性能なバイトコードインタプリタを導入しました。 今日は次世代の JavaScript エン
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SquirrelFish Extreme の紹介 - Backnumbers: Steps to Phantasien