404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
404 Blog Not Found:アルゴリズム百選 - 配列を再発明する
2007年12月03日04:00 カテゴリアルゴリズム百選 アルゴリズム百選 - 配列を再発明する アルゴリズムを理解するのに最適な方法は、すでに当たり前のように使われている仕組みを、もう一度時分の手で作ってみることです。ここでは、配列に関するアルゴリズムを再実装してみます。 ここでは、MyArrayというオブジェクトを作って、それに配列としての機能を持たせることにします。まずは基本的な操作ができるようにしておきます。 残念ながらRubyなどと異なり、JavaScriptでは[]を演算子として再定義することは出来ないので、ここではget()メソッドとset()メソッドをその代わりとして用意することにします。また、利便性を考えて、組み込みのArrayに変換するtoArray()メソッドも用意しておくことにしましょう。 function MyArray(){ this.size = argum
404 Blog Not Found:アルゴリズム百選 - ハッシュを再発明する
2007年12月03日11:15 カテゴリアルゴリズム百選 アルゴリズム百選 - ハッシュを再発明する (実はハッシュを使って)配列を再発明したところで、今度は配列を使ってハッシュを再発明してみます。 現代におけるプログラミングでは、連想配列(associative array)というものを非常によく使います。通常の配列では、データを取り出すのに整数の番号を使いますが、連想配列ではその代わりに文字列を使います。これは非常に便利で、多くの言語ではオブジェクトの実装にこの連想配列を用いています。JavaScriptのオブジェクトも実は連想配列です。 しかし、これを実装するには、少し工夫が必要です。単なる配列であれば、ただ等間隔に並べておけば、「何番目を出してくれ」で事足りますが、連想配列で「'dankogai'番目」といっても人間にもコンピューターにもなんのことかさっぱりわかりません。 誰でも
404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?
2006年11月23日14:45 カテゴリLightweight Languages javascript - Array#sortがオレquicksortより遅い!? な、なんだってー!? ごっつええブログ - JavaScriptによるソートアルゴリズムの比較実験 『JavaScriptを使って一定以上の数量をもった数値配列をソートする場合は、組み込みメソッドよりもクイックソートを使用したほうが高速である』 自分でも検証してみた。 どうやらMozilla系列のJavaScript実装に関しては嘘ではないらしい。以下で確認してほしい。 Firefox 2に関してはほぼ同等だが、Mac IE 5, Safari 2.0.4, Opera 9.02ではbuiltinの方が速かった。しかしその差は最も大きかったSafariでも3倍程度で、builtinとしてはやはり遅いように見える。 # of
たらいを回すならHaskell : 404 Blog Not Found
2006年04月07日22:09 カテゴリLightweight Languages たらいを回すならHaskell たらい回し関数、またはtakと呼ばれる有名な関数が存在する。 C言語による最新アルゴリズム事典 奥村晴彦 同書をお持ちの方は、185ページに乗っている。 実はこれ、Haskellの売り込みには最高の関数なのだ。 ちなみに、これ最後にyを返すバージョンとzを返すバージョンがあるようで、それぞれtakyとtakzと呼ばれている模様。ここではtakyの方を採用。 まずは、私のnative tongueとも言えるperl。 tak.pl #!/usr/bin/perl use strict; use warnings; sub tak{ my ($x, $y, $z) = @_; ($x <= $y) ? $y : tak(tak($x-1, $y, $z), tak($y-1,
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
