算術式を記述するにはいくつかの方法があります。算数、数学に使われる中値記法はその一つです。中値記法は、英語ではInfix Notationと表記されます。計算機で使用される言語では、数学のように大括弧(bracket)、中括弧(brace)、括弧(parenthesis)を使い分け…

先日のエントリにて、一貫した二分検索木の可視を行うアルゴリズムについて記載しました。また、木構造、特に二分木や二分検索木と親和性が高い、通りがけ順について説明しました。以下は、通りがけ順にてkd木を走査する様子を可視したものです。さて、木の…

名著アルゴリズム Cの特筆すべき点の一つとして、可視の美しさが挙げられます。特に二分木の可視は美しく、計算されつくされた様にいつも唸らされます。以下は、アルゴリズム C 第2巻の14章、初等的な検索法の章に掲載されている二分木の可視です。この木は9…

Snow Leopardがリリースされてから早くも2ヶ月が経過しましたが、CVS先端のCocoa Emacsのビルドが通るようになっていました。勿論、嬉しいことに、64ビットバイナリです。ビルド方法は以前と変わっていないようです。私の環境ではlibtiffとlibungifを入れる…

Mac OS X 10.6 Snow Leopardの雑感をつらつらと書き留めています。 Mac OS X 10.6にバンドルされているPythonのヴァージョンは2.6.1でした。流石のAppleもPython 3.x系の採用には踏み切れなかったのでしょうか。何れにせよ、itertools.(permutations|combina…

Snow Leopardと呼ばれているMac OS X 10.6をインストールしました。今回のリリースはLeopard、Mac OS X 10.5から大きく変更されることはないだろうという予想の元、アップグレードインストールをしようかと考えていたのですが、結局スクラッチからインストー…

Snow LeopardをインストールしようとしているEmacsユーザーは少々気を付けたほうがよいかもしれません - Snow Leopardリリース直後現在において、Cocoa EmacsおよびCarbon Emacsの双方ともにビルドすることが出来ません。ただし、LeopardにてビルドしたCocoa…

先日のエントリでは射影を用いた矩形の交差判定について記載しました。その際の実装は以下のようなものでした。 def intersect(A, B): for a, b in zip(zip(*A), zip(*B)): if max(b) < min(a) or max(a) < min(b): return False return True 実装にはベクト…

さて、先日までのエントリにて矩形と射影について各々解説しました。今回のエントリでは、射影を応用した矩形の交差判定について記載したいと思います。早速、以下のようなAとBの二つの矩形の交差判定について考えてみましょう。先日のエントリにて解説した…

先日のエントリでは、射影(Projection)を用いた領域検索について解説し、簡単な実装を行いました。今回はその実装をリファクタリングしてみます。 では、早速始めましょう。先日のコードをジェネレータとしてsequential_search()関数にまとめたコードから開…

先日のエントリでは、矩形の交差判定を行う際の用語の紹介を行いました。今回のエントリでは、射影(Projection)という技法を紹介します。一見、射影は単純なことを難しく表現しているだけに感じられるかもしれません。しかし、計算幾何や領域検索を考えるに…

先日のエントリではマンハッタン幾何を紹介し、総当たりによる実装を行いました。その際、水平と垂直の線分を縮退した矩形とみなし、交差判定を行いました。今回のエントリでは、矩形の交差判定アルゴリズムを考えるための用語の解説を行います。また、次回…

先日kd-treeについてのエントリを記載したことは、自分にとって計算幾何の面白さを再認識する良い機会となりました。計算幾何で用いられる幾何学的アルゴリズムは比較的若く、今でも進化の過程にあります。また、人間には単純に見える問題も計算機にとっては…

先日のエントリに引き続き、Quick Selectアルゴリズムについて考えてみたいと思います。Quick Selectアルゴリズムを考えるに至った動機は、メディアンを選択することでした。今回は以下の9個の要素を持つ配列を使って考えてみましょう。ここでは、配列のイン…

先日のエントリではメディアンの選択にsort()を用い、より効率のよいメディアンの選択方法を課題としました。さて、今回そのアイデアの一つとして紹介するのはQuick Selectというアルゴリズムです。Quick Selectというアルゴリズム名は一般的ではないかもし…

さて、先日のエントリにて、メディアンを加味した2d木の構築を紹介しました。コードの見通しを簡潔にする目的もあり、メディアンの選択にはsort()を用いました。 #!/usr/bin/python -t from operator import itemgetter from random import seed, randint de…

先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成し…

前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。 二次元の値(x, y)をもつ集合P …