10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
Adobe PhotoShop で RGB モードの画像を 256 階調のグレースケールへ変換する方法は、1 通りではありません。グレースケールへの変換コマンドは、ガンマや色空間などの概念が絡み合っていて、結構複雑です。仕組みを理解していなかったために、モード メニューから グレースケール を選んでも望んだような結果が得られなかったり、不適切に彩度を取り除いて画像の階調を潰してしまうというようなことも考えられます。ここでは、何通りかのグレースケール化方法を、計算式から考えていきたいと思います。計算式は、PhotoShop 以外の一般的な画像処理でも利用できる汎用的なものです。
さて，前回の記事では，べき乗を計算するpower関数の例を紹介した。power関数は，フィボナッチ数列を計算するfib関数と並んで，関数型言語のプログラムとして，最もよく引き合いに出される例の一つである。ただ，あまりにも数学的な例ばかりなので，「関数型言語は実用的ではない」という印象の原因の一つになっているのではないか，という気もする。本当は，再帰の考え方は現実の問題に対しても大いに役立つのだが，関数型言語をできるだけ簡潔に説明するという目的では，やはり数学の例題も便利だ。そこで，今回はpower関数とfib関数について，ちょっとマニアックに掘り下げてみたい。 power関数の改良 前回は，整数mのn乗を計算する関数powerを，以下のように定義した。
2008-10-04 カテゴリ: Client Side タグ: JavaScript UUID アルゴリズム [追記] UUID.jsの最新版はGitHubで公開されています! (解説記事) UUID (Universally Unique Identifier) を生成する JavaScript ライブラリを作ってみたので公開します。 UUID.js UUID は、128 ビットの長さを持つ識別子です。普段使うときは↓のように 16 進法で表現されて、ところどころにハイフンが入ります。 e8783d5e-90dd-4af9-8aa6-371d43fcbcb4 UUIDは 128 ビットで 2128 = 3.4e+38 通りもあるので、偶然同じ ID が生成されることが (ほぼ) ないんです。だから、ID の一意性を維持するためにわざわざ統制する必要がなくて、面倒くさがりな人間にとっては
ブースの乗算アルゴリズム（ブースのじょうざんアルゴリズム）は、2の補数表現のふたつの符号付整数の乗算の手法である。 このアルゴリズムは1950年ごろアンドリュー・ドナルド・ブース（英語版）がロンドン大学バークベック・カレッジで結晶学を研究しているときに発明したものである。ブースは卓上計算機を使って研究していて、計算速度を向上させるために乗算を高速化する方法を探していてこれを発明した。彼の時代のマシンではシフトは加算よりも高速であり、ある種の数値では彼のアルゴリズムは高速であった。しかも負数についてもこのアルゴリズムは機能した。ブースのアルゴリズムはコンピュータ・アーキテクチャの研究において興味深い。 ブースのアルゴリズムは、符号付きの2の補数表現のNビットの乗数 Y において、最下位ビットよりさらに下に y-1 = 0 というビットを暗黙のうちに補って隣接する2つのビットを調べる。Yの各ビ
スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。 Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅停車のように、全要素を結んでいます。一方、上層のリンクは急行や特急のように、途中の要素をスキップするようになっています。この路線を特急→急行→…→各駅と乗り継ぐことで、目的の要素に高速に到達できる仕組みです。もっと詳しい解説はこちらやこちらにあります。 で、ここからが本題です。Skip Listの実装はいくつも出ているんですが、Sorted Listとしての実装ばかりで、要素を任意順序で格納できてランダムアクセス（indexを指定してのアクセス）可能なSkip Listが見つからなかったので、自分で作ってみました。 通常のSkip
JSのArrayは#(?:un)?shiftが遅くてキューとして使いにくいため，自作すると良いらしい。 /// q.js /// // wrapper of native array function Qa(){ var q = []; q.enq = q.push; q.deq = q.shift; return q; } // relies on property-order-retention (wouldn't work on Rhino) function Qd(){ var q = {}, p = 0; this.enq = function(o){ return q[p++] = o }; this.deq = function(){ for(var k in q){ var o = q[k]; delete q[k]; return o; } }; } // based o
2006年08月30日18:30 カテゴリLightweight Languages javascript - シャッフルシャッフル なるほど。Schwartzian Transformの意外な利用法だなあ。 snippets from shinichitomita’s journal - JavaScriptの配列をsort関数でシャッフルする Array.prototype.shuffle = function() { return this.map(function(a){ return { weight: Math.random(), value: a } }) .sort(function(a, b){ return a.weight - b.weight }) .map(function(a){ return a.value }); } でも、実践ではどうだろう。調べてみた。
目次 2005年10月31日 - まだ名前のない実験ページ / 2005年10月30日 - 「再帰的な木を描くJavaのソースコード」を公開 / 「さまざまな方のための祈り」を更新 / 2005年10月29日 - 「ミルカさんとフィボナッチ数列」のLaTeXファイル公開 / 2005年10月28日 - わたっていく言葉 / ながれていく時間 / 仕事 / みなさんからのメッセージを読む / 『改訂第2版Java言語プログラミングレッスン』無料プレゼント抽選 / 2005年10月27日 - 夜 / 本 / 朝 / 2005年10月26日 - 夜 / 自分の理解を確かめて学習するということ / 朝 / 2005年10月25日 - 日記ダイジェストを更新 / 必要条件と十分条件 / 仕事 / おはようございます / 2005年10月24日 - コクヨのSlimB5ノートを使った感想 / 2005
100ます計算の問題を作る、というプログラムを作ってみようと考えています。 問題となる数列は、1から9までの数字をランダムに並べ替えた物になるはずです。 さて、この「ランダムに並べ替えた数字」というのは、どういったアルゴリズムで作成するのが最適なのでしょうか？ 個人的に思いついたのは、以下のような方法です。 １．整数型の配列変数(要素が9個)を作成し、それぞれ1から9まで数字を入れておきます。 ２．乱数を使って、「x番目とy番目の数字を入れ替え」という風に、何度も入れ替えを行います。 これだと非常に単純なのですが、正直言って素人の考えなので、最適なのかどうか疑問なのです。 もっと最適な方法があれば教えて頂きたいです。
はじめに TagGridでは16000毎のFlickrの写真を、写真のタグにしたがって格子状に配置しています。この配置アルゴリズムについて簡単に説明したいと思います。 基本的なアイデア まず、入力となるのはN個のタグ付きデータとします。また、K種類のタグがあるとします。 TagGridでは、このN個のデータとK種類のタグがそれぞれ平面上に配置されるとします。 データだけでなく、タグも2次元平面上に配置するのが大事な点です。 基本的な考え方としては、あるデータのタグが例えばseaとsunの場合、このデータの位置がseaタグと sunタグの近くになるようにデータとタグを配置します。データは複数のタグを持つので、一番良い配置方法というのは簡単には決定できません。そこで、なるだけ良さそうな配置を求めてみます。 フォーマルな問題定義 基本的なアイデアを、もう少しフォーマルに定義します。 n番目のデー
「こくばん.in」とは 「こくばん.in」は、“黒板に落書き”という学生の頃に誰もが体験したことをWeb上で味わうことのできるお絵かきサービスです。絵に自信がない人でも気軽に落書きを楽しめる場所として、2008年2月末にサービスインしました。 使い方は、まさに黒板と同じです。画面下部に並ぶ6色のチョークのいずれかを選択し、黒板上をクリック＆ドラッグするだけで自由に線を書くことができます。線を書く際に、上下カーソルキーあるいはマウスホイールを使えば、線の太さが変わります。また、画面右下には黒板消しがあり、クリック＆ドラッグすることで書いた線を消すことができます。 図1：チョークを勢いよく動かすと線がかすれた感じになったり、黒板消しでこすると線がぼやけた感じになったりと、実際のチョークの書き味と消し味を再現しています 落書きが完成したら、画面右下の投稿ボタン使って「みんなのらくがき」コーナー
東京都で賢い借金返済方法を教えます！では、MySQLに格納したWikipedia記事をランダムに表示している。速度を気にしないなら、 SELECT * FROM docs ORDER BY RAND() LIMIT 10; で良いのだけど、レコード数が多いと遅くて使いものにならない。そこで、記事IDを1から始まる連番になるようにDBに格納している。このようにすると、アプリケーション側でDBに格納されている文書IDが全て分かるので、ランダムに文書IDを10個選択して、その文書IDのレコードを表示することで、ランダム表示を実現している。 例えば、IDは10個選択するRubyコードは、 ids = Array.new(10){ rand(num_docs) + 1 } で、DBに発行するSQLはこんな感じになる。 SELECT * FROM docs where ID in (id1,id2,.
st_table メソッドテーブルやインスタンス変数テーブルとしてst_tableは既に何度か登 場してきた。本章ではまずこのst_tableについて詳しい作りを見ていくことに しよう。 概要 st_tableはハッシュテーブルだということはもう言った。ではハッシュ テーブルは何かと言うと一対一対応を記録するデータ構造である。一対一の対 応とは例えば変数名とその値、関数名とその実体、などだ。 ただしもちろんハッシュテーブル以外でも一対一対応は表せる。 例えば次のような構造体のリストを使ってもいい。 struct entry { ID key; VALUE val; struct entry *next; /* 次のエントリを指す */ }; しかしこの方法は「遅い」。もしリストが1000個あったら最悪1000回リンクを たぐって探さなければならない。つまり要素の個数に比例して検索時間が長く
This webpage was generated by the domain owner using Sedo Domain Parking. Disclaimer: Sedo maintains no relationship with third party advertisers. Reference to any specific service or trade mark is not controlled by Sedo nor does it constitute or imply its association, endorsement or recommendation.
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
9/15日にMozilla 24 出張Shibuya.js 24でしゃべってきました。 http://shibuyajs.org/articles/2007/08/24/Shibuya-js-24 資料はこちら。 http://ma.la/files/shibuya.js/mozilla24.html JavaScriptでBloom filterのデモ。今のところ実用性が無い。仕組みを理解するのには良いかも。 http://la.ma.la/misc/js/bloomfilter/ Bloom Filterについてはここら辺が詳しい。 http://chasen.org/~taku/blog/archives/2006/01/bloom_filter_1.html http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
aki note ≫ Google 電話面接を受けました orz （いまは消えてるけど）にて割り算が壊れました。自分で実装してみてくださいという質問が紹介されていた。せっかく(?)の機会なので、割り算だけでなく、四則演算を全部壊してみて、JavaScript で実装して見ることにした。JavaScript を選んだのは、コンパイル不要、ビット演算がある、Firebug で手軽に確認できる、という理由から。それ以上の深い意味はない。ということで、次のような問題に一般化してみた。問い四則演算を JavaScript で実装しなさい。演算子は ==、!= およびビット演算子のみ使ってよいものとします。補足例えば、for 文で for(var i = 0; i { // ... } と書くためには、++ 演算子は次のように定義できる。 function increment(i){ var c =
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
