イントロソート（英: introsort）は、David Musser（英語版） が1997年に設計した、クイックソートとヒープソートを組み合わせたソートアルゴリズムである。 最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。時間計算量は最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。 イントロソートは、クイックソートやヒープソートと同様、比較ソートである。 クイックソートは、性能がピボット（データ列を分割する境界値）の選択に強く依存するという欠点があった。 例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。 ニクラウス・ヴィルトはこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては

16:46 08/03/30 YZ1.DLL 0.30 リリース しました。 具体的には、ヘッダの格納ファイル数フィールドに実際より大きい値が入ってると変なとこ読もうとして落ちるバグ修正。 GreenPad の修正は来週くらいには…。 Booooooost Boost 1.35.0 来てました。 Asio と Fusion と GIL の三枚看板がでかいですが、Bimap が地味に便利だ。 あと、mbさんのEgg のレビューが明日からでしょうか。（また スケジュール から消えてますが…Protoが入る前までロールバックしてる？） 他人事ながらドキドキ。 17:36 08/03/28 ケース 十年来の疑問なんですが、"case" に単独で対応する日本語ってなんになるんですかね。 "case-insensitive" や "lowercase" の "case"。単に "case-insens

1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい

文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis

この章では、現在のデータ圧縮・画像圧縮などで広く用いられているLZ法について説明します。 前章までで説明したハフマン圧縮では、個々のデータをハフマン符号に変換して圧縮を試みるというものでしたが、LZ法では、あるデータ列に着目して、それが以前に出現したことがあるかをチェックし、すでに出現したことがあるのならば、そのデータ列を示す何らかの符号(当然、データ列より短くなければなりません)に置き換える処理を行うことにより、圧縮を行っています。 LZ法には、いくつかの種類があり、その種類によってさらに名称が変わります。しかし、その違いは符号化の方法だけで、処理の内容については全て同じです。 LZ法は、Abraham LempelとJacob Zivの二人による共同開発によって、1977年に誕生しました。正式名称はZiv-Lempel codingですが、間違ってLZ法として紹介したことから、現在の

ここでは、C言語によるプログラミングでありがちな間違いを紹介します。 C言語によるプログラミングで犯しやすい間違いは、 C言語 FAQ 日本語訳 や Ｃ言語のよくある間違い に数多くの例が紹介されていますので、一度、目を通してみることをお勧めします。 ここでは、これらのページに見当たらなかった間違いの例を紹介します。 なお、C言語だけでなく、基本的にC++言語でも同じことが言えます。

コンピューター：C言語講座：fork,exec,pipeについて このテーマはどちらかというとUNIX系の話題になってしまうのですが、PC系ではDOSの時代にはマルチタスクができませんでしたので、平行には走れませんでしたが、C言語の処理系独自の関数がたくさんありました。WindowsになってからはUNIX系と似てきましたが、まだ少し違うようです。 自分で作成したプログラムから他のコマンドを実行したい、ということは良くあることだと思います。例えば、ディレクトリーの中身を簡単に得たい場合などはUNIXではlsコマンドを実行させて、結果をもらうのが簡単に思い付くと思います。とくにUNIXのコマンドはそのように組み合わせて使いやすくできていて、必要な情報だけを明確に返答するコマンドがほとんどです(その分、初心者が自分でコマンドを使う時に不親切なのですが)。 system() 大抵の人が上記のような