末尾再帰のクイックソートつづき - maoeのブログ
先日のエントリに対してid:nozomさんからトラックバックをいただいた．どうやら先に挙げたページにあるquicksort/cpsのcpsは継続渡しスタイル(CPS)のことだったようだ．調べてみると確かにこのCPSは末尾再帰に変換するときによく使われるらしく，Wikipediaにも Besides space and execution efficiency, the tail recursion is important to allowing a common idiom in functional programming, continuation passing style (CPS), without quickly running out of stack space. とあり，リンク先には用例も載っている． ということで，昨日のqsortをCPSに変換する． その前にfilt
末尾再帰のクイックソート - maoeのブログ
階乗とかフィボナッチを末尾再帰に書き換えるのはわかるのだけれど，クイックソートを末尾再帰に書き換えるのはどうすればよいのか? ナイーブな実装 Haskellではクイックソートは次のように書ける． qsort [] = [] qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]SchemeではHaskellのリスト内包表記の部分をfilterで代用すればよい*1． (define (filter pred? lst) (if (null? lst) lst (let ((x (car lst)) (xs (cdr lst))) (if (pred? x) (cons x (filter pred? xs)) (filter pred? xs)))))このfilterを末尾再帰に書き直すと
再帰クイックソートの可視化: Days on the Moon
「いやなブログ - JavaScript でソートアルゴリズムを可視化」より。何も考えずに再帰処理のクイックソートの様子を逐次描画しようとするとこうなります。 function quickSort(data, begin, end, log) { if (begin >= end) return data; var pivotPos = begin; var pivot = data[pivotPos]; for (var i = begin + 1; i < end; i++) { if (data[i] < pivot) { var temp = data[i]; data[i] = data[pivotPos + 1]; data[pivotPos + 1] = data[pivotPos]; data[pivotPos] = temp; pivotPos++; } } log(da
Rhino in Spring、継続 - FAX
Rhino in Spring、継続 RHINO, JavaScript Rhino in Spring DI + JavaScriptで、反射的に見送ってしまいそうでした。 (サーバーサイドJavaScriptで、DIが出てくるものは、JavaScript/スクリプトの性質を本質的に誤解しているんだと思います。のっけから脱線になりますが、Seasar(DIコンテナ)を使ってたときに最終的にメリットとして感じたのはAOPだけで、これはプロトタイプベースのアプリケーションではパターンの一つに過ぎないと思っています。) こんな毎日・・・ - RhinoinSpringのExample 私も、上記サンプルを簡略化し試してみました。 送信された値を、累積的に加算していくアプリケーションです。 こんな画面です。 コントローラーは、こんな感じです。 var tape = [0]; // 履歴 for(
Shibuya.js: ActionScript でクロージャ、継続渡し : torus solutions!
Shibuya.js Technical Talk #2 で、 発表をさせていただきました。ありがとうございました。 5 分の中にいろいろ詰め込もうとしたら、 訳の分からない発表になってしまいました。 発表者やスタッフのみなさんお疲れさまでしたー。 今回の発表では、 まず ActionScript（JavaScript）でのクロージャと継続渡しスタイルの実装方法の説明をし、 その後、 A* アルゴリズムというグラフの最短経路探索アルゴリズムを例にとって、 クロージャや継続渡しスタイルの便利さをアピールしようとしました。 発表資料 当日使った発表資料をおいておきます。 スライドの PDF デモの Flash（SWF） デモの ActionScript ソース Flash 8 を持っていれば、次の Fla ファイルを使ってデモを試すことが出来ます。 （Flash 8 の体験版 でも OK です
Javaで継続渡し - ヒビノキロク
id:carbuncle:20060317を見て面白そうだったので、Javaで継続渡しを書いてみた。 public interface Continuable { public Object applyN(Continuable cont, Object[] args); }public class NullContinuation implements Continuable { private static NullContinuation instance; public static NullContinuation getInstance() { if (instance == null) { instance = new NullContinuation(); } return instance; } // This class cannot be instantiated f
Javascriptで継続渡し - ヒビノキロク
id:nozom:20060317#1142577630の続き。世界で最も誤解された言語とも呼ばれるJavascriptを使って継続渡しを書いてみた。 なお、Javascriptの処理系としてRhino*1を使った。参考文献は『入門Javascript』(ISBN:4756138713)。 function fib(n) { if ((n == 1) || (n == 2)) return 1; else return fib(n - 1) + fib(n - 2); } function fib_cps(n, k) { if ((n == 1) || (n == 2)) return k(1); else return fib_cps(n - 1, function(v1) { return fib_cps(n - 2, function(v2) { return k(v1 + v2);
継続を使ってSjaxをAjaxに簡単に変換する方法 - llameradaの日記
JavaScriptによる全文検索エンジンの最初のバージョンはAjaxではなく、Sjaxであった。その為、サーバへのリクエストが発生する毎にブラウザが固まってしまい、応答性が悪かった。なぜ、Sjaxで記述したかというと、連続してサーバへリクエストを送り、しかも、サーバからのレスポンスに応じてリクエストを変更するようなAjaxプログラミングが面倒だった為である。このようなSjaxのコード例を次に示す（prototype.jsを使用）。 // (Sjax)サーバからpathのデータをoffsetの位置からlengthバイト取得 function fetch(path, length, offset){ var range = ["bytes=" + offset + "-" + (offset + length - 1)].join(""); var options = { method: "
Geekなぺーじ：他人のやる気を引き出す方法
「8 simple things you can do to encourage others」という記事がありました。 当たり前の事ばかりかも知れませんが、ついうっかり忘れがちであるような気がしました。 原文のブログを書いている人は起業を目指している(もしくは起業中)のソフトウェアエンジニアのようです。 原文著者は、やる気がなくなってきたときに家族や友人が励ましてくれることが大変ありがたいそうです。 そこで、どのような励ましを受けると自分がやる気になるかなどの経験を元に、他人のやる気を引き出す方法を紹介していました。 以下のような事を、何かをしようとしている友人に対してしたり、自分の子供と向き合うときにしたりすることを原文では提案しています。 やる気が出れば物事の達成度も上がると思われます。 1. 凄く興味を示す 原文では、最も効率よく相手のやる気を引き出す方法であると書いてありました。
.NETアプリを軽快にするためのガベージ・コレクション講座（1/4） - ＠IT
マウスやコントローラなどのデバイス入力から、映像や音声の出力までを限りなく実時間に近いタイミングで処理しつづけなければならないアプリケーションがある。身近なところではゲームをその筆頭に挙げることができるだろう。また、近年は様々なジャンルのアプリケーションでコモディティ化が起こっており、機能面での差別化が困難になってきたことから、非機能要求である応答性の良さで製品を選ぶという人も増えているのではなかろうか。その意味では、デスクトップ上で動くアプリケーションはほとんどすべてリアルタイム性が求められているといえる。 従来、ガベージ・コレクション（以下GC）により非同期的にスレッドが停止する.NETアプリケーションは、応答性が重視される分野には不向きだと言われてきた。これはある意味では事実であるものの、実際には工夫次第でGCの影響をかなり軽減することが可能である。何より、「XNA Field」や「
整数型に対する Compare の実装 (2) - NyaRuRuが地球にいたころ
(追記その 3) すみません．派手に勘違いしていました． Int32 は IComparable<T> を明示的にではなく通常の方法で実装していますし，CompareTo(int value) はパブリップメソッドとして公開されています．4649.CompareTo(x) は普通に書けます． static int HardCmp(int x, int y) { return (x == y) ? 0 : (x > y) ? 1 : -1; } は， static int HardCmp(int x, int y) { return x.CompareTo(y); } のように書くことが，実際に可能です． (追記) 前回のネタ『[.NET]整数型に対する Compare の実装』へのリンクが切れていて意味不明なエントリになっていたのを修正しました． 追記：.NETは関係ないよ。32ビット整数
PowerPoint 絶対主義
プレゼンテーションが登場する前には、会話があった。プレゼンテーションと少し似たところもあるが、箇条書きは少なくて済んだし、だれかが照明を暗くする必要もなかった。ここにある女性がいる。仮にその名前を Sarah Wyndham とでもしておこう。国防関係のコンサルタントで Virginia 州 Alexandria に住んでいる。彼女は、自分の 2人の娘が、最近どうも言うことを聞かないような気がしていた。部屋を片付けなさいとか、家事を手伝いなさいとかいっても耳を貸さないようなのだ。そこで、ある朝、彼女はコンピュータの前に座り、Microsoft 社の PowerPoint を開いてこう入力した。 新しいページには、こう書き入れた。 整理整頓を怠ると、他の家族全員が混乱しイライラする 無秩序は学業にも社会生活にも悪影響を及ぼす 無秩序は家族全員の効率を下げる 家庭内の和を訴えるかわりに、Sar
ITmedia エンタープライズ：第1回 ディストリビューションの選び方、試し方
春は出会いと別れの季節。入学や就職で、新しい生活を始める人も多いだろう。そこで本連載では、新入学生／新社会人応援企画として、オープンソースで作る環境構築を解説していく。また、デスクトップ環境のほか、新しくプログラミングを始める人のために、Web/Java開発の第一線でいまどのように環境が使われているかを紹介する。 オープンソースを使う動機は人それぞれ。Windowsに飽きた人もいれば、大学や仕事で必要になるからと始める人もいるでしょう。ところが、いざ始めようとしたときに、どこから手をつけて良いか分からないことも多いものです。「どのディストリビューションが良いか」は、いつも論争になる話題ですし、本当のところは自分で試さないとよく分かりません。そこで今回から2回に分けて、ディストリビューションを選ぶための目安と、気軽に試すための手引きを紹介していきます。 どのディストリビューションを選ぶか か
最速インターフェース研究会 :: 遅延評価を使ってSjaxをAjaxに変換する方法
継続を使ってSjaxをAjaxに簡単に変換する方法 http://d.hatena.ne.jp/llamerada/20070220/1171984586 を見て。こんなのはどうだろう。 ユーザーからの入力や、非同期のHTTPリクエストなんかを、具体化されてないオブジェクトとして捉えて、それらを受け取った関数側が遅延オブジェクトを具体化するためのリクエストを投げて再試行する。ネストが深くならないですむ、同期処理で書く場合との変更点が少ない、あるいは完全に差異を無くすことができる。 alert(args)のコメントを外せば、引数が具体化されていく様子が分かるはず。 Function.prototype.receive_lazy = function(){ var orig = this; return function(){ var thisObj = this; var me = argu
【インタビュー】アドビ副社長が語る、未来の写真
Photoshop LightroomやCS3のパブリックベータ公開など、最近の米Adobe Systems(以下、アドビ)はユーザーの意見を取り入れながら、自らの姿勢を知らしめる活動を積極的に行なっている。こうした活動の一環として、同社が「アドビ・ラボ」で取り組んでいる技術開発を、デジタルイメージング製品開発副社長であるデイブ・ストーリー氏が、デジカメWatchに説明してくれた。 1982年に創設されて以来、デジタルイメージングのリーダーとして君臨してきた同社だが、意外なことに、このような「エンジニアリング・ツアー」を行なうのは初めてのことだという。 「ジャーナリストの皆さんが、アドビのマーケティング部門以外の人間から話を聞くのは初めてでしょう。このエンジニアリング・ツアーを開催する理由は2つあります。1つは、アドビとして、もっといろんなことを語っていこう、もっとオープンな会社になってい
坊やがゆく - Railsでソーシャルブックマークを作ってみようか（第2回）
エンジニア説明Railsアプリを作る「はじめの一歩」としての足がかりになればと思いまとめました。手順に沿ってコピペしていくといつのまにかアプリケーションが完成するというサンプルです。第1回のmasuidriveさんベースにRails勉強会＠東京第11回での高橋征義さんバージョンとInternet Week 2006でのかずひこさんバージョンをミックスしました。環境やインストール、趣旨や概要につきましては第1回をご覧ください。 ■第1回との相違点Internet Week 2006のT24 : はじめよう Ruby on Rails 〜フレームワークで作るWebアプリケーション〜をベースに内容を変更しました。基本的な流れは変わっていませんが、機能／モデルが変更されています。文字コードの設定を先に行うようにしました。モデルの定義を先に明示しました。モデルの作成にマイグレートを使用するようにしま
進化する“Webスクレイピング”技術の世界 ― ＠IT
2007/02/20 WebサービスのAPIやRSSフィードを使って複数サイトのサービスや情報をマッシュアップ――。これはWeb2.0が包含するいくつかの概念のうち、最も重要なものの1つだ。Amazon.comやGoogle、Yahoo!、楽天といった大手Webサイトは、RESTやSOAPを用いたAPIを公開しており、さまざまなサービス提供者や個人がAPIを通して各種サービスを利用している。その一方、世の中のWebサイトの大多数はWeb1.0的なHTMLやCGIフォームしか提供していないのが現実だ。こうした背景からWeb1.0サイトから構造化されたデータを引っ張り出す“Webスクレイピング”技術が急速に発展してきているようだ。 HTMLをXML化し、XPathで関連データだけを抽出 例えば価格情報サイトでは製品名から価格が簡単に調べられるが、Webサーバから提供されるのは、製品名や価格にレ
WindowsからLinux領域を読み書きできる ext2fsd
ext2fsdは，Linux用のハード・ディスク領域へのアクセスを可能にする，Windows用のデバイス・ドライバである。このドライバを組み込めば，WindowsアプリケーションからLinux領域内の各種ファイルを読み書きできる。 WindowsとLinuxのデュアル・ブート環境において，どちらのOSで起動した場合でも，もう一方のOS用のハード・ディスク領域に自由にアクセスできると便利だ。 Linuxからなら，WindowsのFATファイル・システムが読み書きできるので問題ない。最近ではNTFSファイル・システムに対しても読み書きが可能だ。一方，Windowsからは，LinuxのExt2ファイル・システムや，その拡張版であるExt3ファイル・システムに対して読み書きができず不便である。 ext2fsdは，Ext2/Ext3ファイル・システムでフォーマットされたLinux用のパーティション（
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
IBM Developer
再帰の練習帳３ - carbuncleの日記
hereticanthem co.,ltd. » なにかと使えるWebジェネレータのまとめ その１