d.y.d. 2倍だけじゃない
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%)となることがわかります
ブースの乗算アルゴリズム - Wikipedia
ブースの乗算アルゴリズム（ブースのじょうざんアルゴリズム）は、2の補数表現のふたつの符号付整数の乗算の手法である。 このアルゴリズムは1950年ごろアンドリュー・ドナルド・ブース（英語版）がロンドン大学バークベック・カレッジで結晶学を研究しているときに発明したものである。ブースは卓上計算機を使って研究していて、計算速度を向上させるために乗算を高速化する方法を探していてこれを発明した。彼の時代のマシンではシフトは加算よりも高速であり、ある種の数値では彼のアルゴリズムは高速であった。しかも負数についてもこのアルゴリズムは機能した。ブースのアルゴリズムはコンピュータ・アーキテクチャの研究において興味深い。 ブースのアルゴリズムは、符号付きの2の補数表現のNビットの乗数 Y において、最下位ビットよりさらに下に y-1 = 0 というビットを暗黙のうちに補って隣接する2つのビットを調べる。Yの各ビ
javascript - シャッフルシャッフル : 404 Blog Not Found
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 }); } でも、実践ではどうだろう。調べてみた。
Adobe - デベロッパーセンター : こくばん.in：リアルな書き味と消し味を実現するテクニック
「こくばん.in」とは 「こくばん.in」は、“黒板に落書き”という学生の頃に誰もが体験したことをWeb上で味わうことのできるお絵かきサービスです。絵に自信がない人でも気軽に落書きを楽しめる場所として、2008年2月末にサービスインしました。 使い方は、まさに黒板と同じです。画面下部に並ぶ6色のチョークのいずれかを選択し、黒板上をクリック＆ドラッグするだけで自由に線を書くことができます。線を書く際に、上下カーソルキーあるいはマウスホイールを使えば、線の太さが変わります。また、画面右下には黒板消しがあり、クリック＆ドラッグすることで書いた線を消すことができます。 図1：チョークを勢いよく動かすと線がかすれた感じになったり、黒板消しでこすると線がぼやけた感じになったりと、実際のチョークの書き味と消し味を再現しています 落書きが完成したら、画面右下の投稿ボタン使って「みんなのらくがき」コーナー
MySQLでの高速な重み付きランダム表示 - llameradaの日記
東京都で賢い借金返済方法を教えます！では、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,.
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
最速インターフェース研究会 :: Mozilla24でしゃべってきました
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
お手軽パーザー
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
てっく煮ブログ - 四則演算を JavaScript で実装する
aki note ≫ Google 電話面接を受けました orz （いまは消えてるけど）にて割り算が壊れました。自分で実装してみてくださいという質問が紹介されていた。せっかく(?)の機会なので、割り算だけでなく、四則演算を全部壊してみて、JavaScript で実装して見ることにした。JavaScript を選んだのは、コンパイル不要、ビット演算がある、Firebug で手軽に確認できる、という理由から。それ以上の深い意味はない。ということで、次のような問題に一般化してみた。問い四則演算を JavaScript で実装しなさい。演算子は ==、!= およびビット演算子のみ使ってよいものとします。補足例えば、for 文で for(var i = 0; i { // ... } と書くためには、++ 演算子は次のように定義できる。 function increment(i){ var c =
Javascriptでdiffる ( with 形態素解析 ) (nakatani @ cybozu labs)
Javascript で diff というのはいくつか試された例はあるようですが、まだこれといった決定打は出ていない様子です。 実は diff は見た目ほど軽い処理ではないので、Javascript にやらせるのはこれが結構大変…… diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例し（実際にはそれより小さくすることができるのですが、まあ話のイメージとして）、かつメモリを大量に消費するので、バッチ的な処理に最適化されていない Javascript にはどうしても荷が重いものとなってしまいます。 比較対象の要素数を減らせば当然計算量は減りますが、行単位で比較してもあまり嬉しくない（わざわざ Javascript で処理するということは自然文が対象と思って良いでしょう）。最小の文字単位だとギブアップ。 ということは形態素解析で分かち書きして、単語単位で diff するのが J
第8回 倉庫番を解くアルゴリズム - 地球にやさしいアルゴリズム：ITpro
「倉庫番」＊1というゲームをご存じでしょうか。図1のように盤面にはいくつかの「荷物」とそれを運ぶ「人」がいます。人は1個の荷物を押して運ぶことができます。荷物を引っ張ったり，二つ並んだ荷物を同時に押して運ぶことはできません。人と荷物は縦横4方向に動けますが，壁のある位置には進めません。人を使って盤面上の荷物を動かし，すべての荷物を目的地（ゴール）に収めることができればゲーム・クリアとなります。図1の問題を解くための手順を示すアルゴリズムを作ってください。 友人たちと車でスキーに行くとき，いつも困るのは「トランクへ荷物を詰め込む順番」です。大きなスキー靴やかさばるスキーウエアを詰め込んでいるうえ，人によってはゲーム機や本を持ってきたりするので，各自の荷物の量がまったく違うのです。狭い車のトランクには，これら荷物をうまい順番で入れていかないとなかなか全部収まりません。寒い冬の夜中にごそごそと詰
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ