特集・プログラミング入門 図 13 基列法と挿入整列法を用いて整列するプログラム #define BSIZE 8 #define CSIZE ( 1 くく BSIZE) #define CMASK (CSIZE ー 1 ) arr ; tO = brr; from int i , j , k ; int *from, *to, int scale ; sort(void) VOid int c [CSIZE] ; for (scale 16 ; scale く BSIZE * sizeof(int) / sizeof(char) ; > > scale) & CMASK] CSIZE; j + + ) scale) & CMASK] + + ; CSIZE; j + + ) 0 ; i く f0 て (i ! = arr) if (p from = p; tO from; p = t0 ; to [c C(fromCi] for (i = N ー 1 ; c [j ] + = c Cj ー 1 ] ; 1 ; j く for (j c [ 0 ] ー c [(from[i] > > for (i = 0 ; i く 0 ; j く for (j arr [j ] ; arr Cj + 1 ] arr[j + 1 ] break; if (arrCj] く = k) 1 for (j k = arr Ci] ; for (i 1 ; i く N ; i + + ) { arr Ci] = brr [i] ; scale 十 = BSIZE) { ではなく 24 ビットとする (for 文の初期化部で scale を 8 とする ) ことで、より高速に処理することができます。 今回は、上交によらない整列法の例として基委各列法を 紹介しました。キーとしてとりうる値の観月と同じ大きさ の配列か準備できれは、きわめて高速に動作する当」法が あります。また、同しサイズの配列か準備できなくても、 部分的に利用することで高速な整列法とすることができま した。整列をおこなう場合、キーの値の範囲があらかじめ 分かるような局面では、これらの整列法も考慮に入れると よいでしよう。 ☆ 128 9 回にわたってアルゴリズムとデータ構造の基礎につ いて説明してきましたが、代表的なものをほんのすこしと りあげた程度です。もちろん、こで紹介したもの以外に も有用なアルゴリズムはありますし、アルゴリズムを必要 とする間題も探索や整列だけではありません。新たな間題 に直面したとき、この記事がはんのすこしでも役に立った こまで書いてきた甲斐があるというものです。頭の ら、 片隅にでも入れておいて、新たなアルゴリズムについて考 えなけれはならなくなったとき、思い出していただけれは さいわいです。 UNIX MAGAZINE 2003.9 ( いまいすみ・たかし千葉大判

特集・プログラミング入門 図 8 基数交換法を用いたプログラム void sortsub(int 10W , int high, int base , int i , 」 , cur ; int cnt [ 10 ] , save [ 10 ] ; for (j 0 ; j く 10 ; j + + ) cnt [j ] for (i 10W ; i く high; i + + ) cnt[(arr[i] base) / step] + + ; save [ 0 ] cnt [ 0 ] ; cnt [ 0 ] ー for (j 1 ; j く 10 ; j + + ) { int step) cnt Cj ] ; save [j ] cnt [j] + = cnt Cj for (i = high ー 1 ; i > = brr C10w + cnt [(arr [i] for (i 10W ; i く high; arr Ci] brr[i] ; cur = 10W ; 10W ; 十十 ) base) / step] ーー ] arr Ci] ; for (j 0 ; j く 10 ; j + + ) { if (save[j] > 1 & & step > 1 ) { ます、最後に定義している s 。 rt 関数からみていきまし のようになります。 これらの条件を考慮してプログラムを作成すると、図 8 ことにします。 にするために、処理対象の範囲の最小値も引数として渡す 桁目なら 10 といった値で表現します。また、引・算を簡単 うは桁数で直孑旨定するのではなく、 3 桁目なら 100 、 2 を渡すことにしましよう。一方、処理の対象とする桁のほ はすです。そこで、その添字の範囲の最小値と最大値 + 1 グループに入るデータは連続して並んた ) 伏態になっている ード群は配列にオ内されていて、直前の処理によって同し どの桁に注目するのかといった情幸ゞ必になります。カ どのカード群を分類しなけれはならないのか、そのとき、 ら、再帰的な関数として実現するのが簡単です。関数では、 sortsub(), N, 0 , M / 10 ) ; sort(void) VOid cur + = save [j] ; sortsub(cur, cur 十 save [j] , base 十 j * step, 120 step / 10 ) ; ょっ。これは直前で定義している sortsub 関数を呼び出 すだけの関数ですが、その際、配列全体を扱うために 0 か ら N ー 1 までの要素を処理する必要があります。そこで、 0 と N を引数として渡します。また、対象範囲のキーの 値の最小値は 0 ですからそれを指定し、桁数を表す値とし て M / 10 を渡しています。この M は、レコードのキーの 匆月値を決めるときに、 rand() % M という形式で用いているものです。つまり、 M / 10 という 値を使うことで、ちょうど 10 個のグループに分割できる ようになります。テストのために、 M の値を 1000 とし てこのフログラムを実行してみました。したがって、桁数 を表す値には 100 か渡されます。このとき、 0 ~ 99 、 100 ~ 199 、 ・・・ 900 ~ 999 という 10 個のグルーフに分かれ UNIX MAGAZINE 2003.9

特集・プログラミング入門 よいので、 drr 配列のその値の添字の場所にコピーしてお きます。これをすべてのカードに対しておこなうだけで す。最後に、 drr 配列から crr 配列にコピーしなおすこ とで、 crr 配列自身か整列された状態になるようにしてい ます。 あまりに簡単すぎて拍子抜けしたかもしれませんが、ち ゃんと順番どおりになるのですから、これも立派な整列法 の 1 つです。なお、この条件であれば、 0 ; i く NCARD; i + + ) fo て (i crr [i] としても正しい状態のものか得られます。しかし、これは 整列しているわけではありません。レコードのサイズが大 きく、一部の値がキーとなっている場合を考えれは、たん に数値を並べるだけでよいというものではないことが分か るでしよう。 トランプを例に説明しましたが、もちろんこのガ去はト ランプを並べるとき以外にも使えます。とくに、キーの値 が一一 - ・定範囲内にあることが分かっている場合は有効です。 たとえば、あるクラスで実施した試験の結果を出席番号順 に並べ替えるといったときにも使えます。この場合、試験 がカードで、出席番号がカードに書かれた数字に対応する わけです。 さて、この方法にかかる手間を考えてみましよう。 for ループが 2 つありますか : どちらも要素数、すなわちれ回 ループしています。つまり、このガ去であれは 0 ( れ ) の手 間で整列が可能ということになります。上記の七並べの例 からも分かるとおり、キーの値の示回川内にびっしりと 1 つ すつの要素がある場合には ( 実際には、たかだか 1 つの要 素がある場合 ) 、通常の整列法の限界を超えるような整列 が可能だということが分かります。 この制限をすこし緩めることもできます。どのキーの値 に対しても要素がたかだか 1 っという制限を外し、それぞ れのキーにいくつの要素があってもかまわないことにしま しよう。つまり、キーの値が NI までであり、要素数が N 個だとすると、、 > NI のケースにも対応するのです。 この場合には、前記の方法をそのまま適用するわけには いきません。こで、整列法の見方を変えてみましよう。 分配計数法 116 図 1 分酉十去を用いたプログラム VOid sort (void) int i , j ; for (j 0 ; j く M; for (i 0 ; i く for (j 1 ; j く M; m Cj ] + = m [j ー 1 ] ; for (i = N 1 ; brr[m[arr[i]]- for (i 0 ; i く 十十 ) i > = 0 ; arr[i] ; UNIX MAGAZINE 2003.9 回までと同様ですが、キーの値は M までに制限されてお ムを作ってみましよう ( 図 1 ) 。配列などの前提条負 : は前 counting) などと呼ばれます。この手法を用いてプログラ このようなアルゴリズムは、分配引嚶去 (distribution いことになります。 目的のレコードは 40 番目から 49 番目の要素とすればよ り、 150 というキーをもつレコードが 10 個あるのなら、 る場合、これよりも小さいキーをもつレコードが 40 個あ とするわけです。 150 というキーをもつレコードに注目す あるかを数え、そこからレコードを各内する ・あるキーの値よりも小さいキーをもつレコードがいくつ 数ある場合も簡単に拡張できます。つまり、 このような見方をすれは、あるキーをもつレコードか複 は 50 番目の要素とすれはよいことカ吩かります。 から 149 までの 50 個があります。そこで、このレコード ーをもつレコードよりも小さいキーをもつレコードは 100 と読み替えることができます。たとえは、、 150 というキ あるかを数え、そこにレコードをイ褓内する ・あるキーの値よりも小さいキーをもつレコードがいくつ れは、 100 を引いた位置に↑内しなけれはならないからです。 ーの値の範囲が 100 から 200 であれは、キーの値から ことを書きましたが、これは正確ではありません。もしキ さきはど、、キーの値と同じ場所にオ褓内する " という意味の brr[i] ; arr[i]

特集・プログラミング入門 図 4 配列て表現したリスト 図 6 ビンソートを用いたプログラム void sort (void) 003 20 30003 ■ int i , j , k ; for (j 0 ; j く M; j + + ) m[j] for (i N 1 ; i > = 0 ; m[arr[i]] i = 0 ; 0 ; j く M ; j + + ) for (j for (k = m Cj ] ; k > = 0 ; k = a Ck] ) brr [ i + + ] arr Ck] ; fo て (i 0 ; i く N ; i + + ) arr[i] brr[i] ; 図 5 配列て表現した 2 つのリスト ■ 30 300 0 ■ するための配列もこの全体のレコード数ぶんを用意すれは よく、このサイズもあらかしめ判明しているために都合が よいわけです。 す。これは、再丿髄勺データ構造をとりあげたときに、配列 からの導入として紹介したガ去です。 この考え方を使ってプログラムを作成すると、図 6 の ようになります。データは arr に入っているので、これ たとえは、添字が 0 から始まる配列に 3 、 4 、 6 、 7 、 5 、 2 というデータかオ内されているとします。この場合、 これ をキーの値にもとづいて M 個のリストに分割します。 を昇順に並べたリストを表現するために、 1 、 4 、 3 、 のとき、リストの頁を M 個の要素をもつ酉冽 m にオ褓内 2 、 0 というリストを用意します。すると、 : 頁が 5 番目の し、それ以降の要素はさきほど紹介した次の要素尉寺す る形式で a という配列にオ褓内します。最後に、 M 個のリス 要素だという情報さえあれは、そこから順に 5 、 0 、 1 、 4 、 トの要素を順番に配列にオ内して整列します。ただし、要 2 、 3 番目の要素をたどっていくことができます ( 図 4 ) 。 素は別の酉改」にオ内したはうか簡単なので、いったん brr そして、配列にイ褓内されているデータをみれは、 2 、 3 、 という配列に褓内し、最後に arr 配列にデータを戻すよう 4 、 5 、 6 、 7 と昇順に並んだデータか得られます。さらに にしています。 このガ去なら ( 独立した ) 複数のリストを表現するのも簡 単です。今度は、偶数と奇数の昇順のリストを表現してみ 最初の for ループでは、各キーの値に対応するリスト ましよう。偶数と奇数の 2 つの麪頁 &f 尉寺する必要があ の地頁をイ尉寺する配列を匆化します。すべての要素に対 りますが、これは 5 と 0 になります。このとき、次の要 し、レコードがないことを示す一 1 を代入しています。次 ー 1 、 3 、 1 です。こうする のループでは、キーの値にもとづくリストにレコードを追 素を表す配列は 4 、 2 、 と、偶数の配列は要素の番号でいえば 5 、 1 、 2 に、奇数 加します。ここでは、新たにみつけたレコードをリストの のリストは同しく 0 、 4 、 3 になります。実際の値にする 地頁に追加するため、レコード全体を末尾から頁に向か と 2 、 4 、 6 と 3 、 5 、 7 ですから、正しく表現できている って処理しています。これによって、各リストに悩求され ことが分かります ( 図 5 ) 。 る順番がもともとの順番と同じになるようにしています。 実際のリストへの追加処理では、ます、注目しているレコ この場合には、それぞれのリスト : されるレコード ードの次を指すものとして、その時点でリストの地頁にな 数は不明だが、全体のレコード数は分かっていることが前 っているレコードを指定します。その後、注目しているレ 提条件となっています。つまり、すべてのリストにイ求さ コードを頁に指定するだけです。 れるレコード数は事前に分かっています。次の要素を各内 118 UNIX MAGAZINE 2003.9

特集・プログラミング入門 図 2 サンカレデータ 0 2 3 1 3 4 3 2 0 4 図 3 レコード数の計算と配列の格納位置 り、要素数 M の配列 m が宣言されていると仮定してい ます。 for ルーフ。がたくさん並んでいますが、それそれの内容 はごく簡単です。最初の for ループは、キーの値の範囲と 等しい要素をもっことができる配列 m をすべて 0 に初期 化しています。次の f 。 r ルーフで、それぞれのキーの値を もつレコードがいくつあるのかを数えています。この処理 は簡単で、キーの値を添字にして配列の要素を j 尺し、そ れをインクリメントすれは計算できます。この処理をおこ なうと、図 2 のようなデータカえられたときには、それ ぞれのキーの値のために図 3 の上段のような値カ引・算され ることになります。 次の for ルーフでは、あるキーの値よりも前に要素がい くつあるかを数えるために、その値よりも前のものをすべ て合計しています。といっても、 1 番目の要素から順番に 直前の要素の値を加えているだけです。値を加えようとす る点では、すでにその位置までの値は合計されているた め、直前の要素を加えるだけでそのキーの値までのすべて の要素数を表すことができます。なお、 0 番目に関しては 1 つの要素があるのなら、それは 0 番目に入れなけれは ならないので、処理を開始する前にデクリメントしていま す。この処理をおこなうと、配列 m の内容は図 3 の下段 のようになります。 4 番目の for がもっとも重要な部分です。配列 rn に格 納されている値には、、そのキーをもつ値を入れるべきもっ とも後ろの場所 " が入っています。ですから、キーの値に もとづいて、配列 m が示す場所にデータを入れれば正し い位置に褓内できます。ただし、いったんデータ翻勺し たら同じ場所にはデータを入れることができないので、次 はその前の位置にデータを↑絲できるようにデクリメント しています。 0 1 2 3 4 2 202 02020 UNIX MAGAZINE 2003.9 こだけ for ルーフ。の向きか異なりますか : これには大 切な理由があります。ほかのループは頁から順に調べて いますが、 こだけは末尾からう曰頁に向かってのループに なっています。これは、配列 rn が、、そのキーをもつ値を 入れるべきもっとも後ろの場所 " を表現しているため、後 ろから処理することて整列の安定性カ躱てるからです。 こまでの処理で、 brr 配列には正しいレコードが並ん でいます。そこで、最後のループでこれを arr 配列に戻し て整列処理を終了します。 この整列法は、キーの値の範囲が限定されていれは利用 できるため、さきほどの方法よりも適用範囲が広くなりま す。それでは、この整列法の手間を考えてみましよう。ル ープは 4 つあり、 2 つは N 回、残りの 2 つは M 回の ルーフになっています。ところが、この M は固定になる ため、けっきよくは N だけが残り、 0 ( れ ) となります。 ただし、注意しなけ川まならないのは、さきほどの方法 と上は交して M に比例する領域が必要になる点です。場合 によっては、 N よりも M のはうがはるかに大きいことも あります。 M がきわめて大きいときは、これは現実的な 鮹去とはなりえません。 さて、同じ間題をすこし違った去て解決してみましょ う。さきほどは、各キーの値をもつレコードの個数を数え ましたが、今度は M 不鶤頁のキーの値しかないのなら、そ こに並べてしまおうというものです。ちょうど、ハッシュ において、ハッシュ値か衝突したとき、 ノ、ツン - ュノヾウ - ッ トにリストを作ってレコードをつなげていったう地旧些饋法 とよく似た考え方です。 複数のレコードを並べる可能生があるため、これをな んらかの方法て表現しなければなりません。分旧鎖法で は、糸彡リストを用いてレコード : 早しました。求さ れるデータの量か事前には分からないため、重加勺にサイズ の変史ができるデータ構造の利用は理にかなっていたので す。せつかくなので、今回はすこし異なる形式を利用して みましよう。配列を用いてリスト構造を表現するのです。 あるレコードに注目したとき、リスト構造の次の要素 : ゴ翻タされるレコードを表す配列の添字をデータとしても つ配列を用意すれは、配列だけでリスト構造が表現できま ビンソ - ト 117

特集・プログラミング入門 つのデータに注目します。これらのデータの下 1 桁目は、 昇順に整列しています。これはたまたまこのように整列し たわけではなく、しかるべき理山があります。 しつは、 こでそれぞれの桁について当リをおこなうた めに安定性のある整列法を使っています。つまり、下 2 桁目を整列しているとき、同じキーの値をもつものについ ては整列前の段階の順序かイ尉寺されているのです。、、整列 前の段階 " というのは下 1 桁目て整列した状態ですから、 けっきよく、下 2 桁目が同しキーとなっているデータは 下 1 桁目で整列した状態になっているわけです。これは、 とりもなおさす、下 2 桁を数値とみなして整列しているの と同じ結果になります。これをさらに 3 桁目でも繰り返す と、今度は下から 3 桁ぶん ( つまり全体 ) を数値とみなし て整列することができます。 かって、言算機にデータを入力するときにカードを利用 していた日罸にがありました。各カードには、 1 つのデータ か書かれています。このカードの束を整列するのに、この 整列法はたいへん便利だったのです。カードを入力する場 所は 1 カ所ですが、カードを出力する場所は図 7 のよう に 10 カ所あります。最初に、下 1 桁目でカードを分類し ます。すると、それぞれの場所に何枚かすっカードがう嶽頁 されることになります。このように分類されたカードを、 0 の箱に入ったものが一番上に、 1 の箱のものがその次に、 ・・・ 9 の箱に入ったカードが一番下になるようにまとめま す。これで、下 1 桁の整列ができたことになります。 次は、下 2 桁目を使った分類です。ここでも同しよう に、う嶽頁されたカードを順番にまとめます。この処理を必 要な桁数ぶん繰り返すと、ぶじにカード全体か整列した状 態になります。 この直接基去をフログラムとして組むと、図 11 のよ うになります。 このプログラムの基本も、やはりう・颪去です。一番 下の桁から順に、各桁についてう・去を適用していま す。 中身については、とくに難しいところはないでしよう。 ある範川の要素数を数えるのに、 m[(fromCi] / scale) % 10 ] + + ; という式を用いています。このとき、 scale 変数は下 1 桁 目なら 1 、下 2 桁目なら 10 となっています。つまり、ま UNIX MAGAZINE 2003.9 図 11 直接基去を用いたプログラム VOid sort (void) int scale; int *from, *to, int i , j ; from = ; tO = brr; f0 て (scale 1 ; for (j 0 ; j mCj] scale く 1000 ; く 10 ; j + + ) ー 1 の { f or ( i = 0 ; i く N ; i + + ) mC(fromCi] / scale) % 10 ] + + ; mCO] ー for (j 1 ; j く mCj] + = m[j for (i = N 1 ; to[m[(from[i] fromCi] ; P = t0 ; t 0 from = p; if (p for (i 0 ; i く 10 ; j + + ) / scale) % 10 ] 十十 ) arr Ci] brr [ 幻 ; 125 て重要です。これは無視できないので、やはり別の配列を した。一方、今回の直接基去では整列の安定性はきわめ を犠牲にしてよけいな領域を使わすにすむようにしていま ので、ビットごとのプログラムを作成するときには安定性 ただし、基数交換法では整列の安定性は重要ではなかった 場合と同様、ビットごとの処理を考えることもできます。 さらにプログラムを張するのであれは・、基数交去の 注意が必要です。 一番外側の for ループの条「牛がかなり書きにくくなるので ら対応可能とすることもできます。ただし、その場合には 満に限定していましたが、この限定を取り払って int 型な さきほどのプログラムでは、キーの値の範囲を 1 , 000 未 に書き戻す処理が省けます。 ている点です。これにより、ある桁を整列した時点で arr いう 2 つのポインタを用いてデータの入った配列を指定し もう 1 つ、ちょっと工夫しているのは、 to と from と は、目的の 1 桁の値を取得できるわけです。 ることになります。そこで 10 による剰余演算をおこなえ すこの値て割ることで、調べたい桁が一番下の桁に移動す

連載 / UN Ⅸの道具箱ーの 図 5 permitopen オプション付き公開鍵によるポートフォワード ・ポートフォワードの準備 10Ca1 ost % slogin -L 10110 : pophost : 110 remotehost Enter passphrase for key ' /home/local/hoehoe/ . ssh/id—rsa' Escape character iS Connected to localhost . Trying : : 1 ・ localhost% telnet localhost 110110 ・作成されたトンネルで pophost の 110 番ポートにアクセス remotehost% We1come to FreeBSD ! 図 6 permitopen オプション付き公によるポートフォワード ( 許可されていない車医 ) —nara. ac . JP> + OK Qpopper (version 4.0.4 ) at pophost. aist—nara ・ ac. jp starting. く 31947.1057652588@pophost.aist Enter passphrase for key '/home/local/hoehoe/ . ssh/id—rsa' localhost% slogin —L 10080:webhost : 80 remotehost ・ポートフォワードの準備 Connection closed by foreign host . Escape character iS Connected to localhost . Trying : : 1 ・ localhost% telnet localhost 10080 ・作成されたトンネルで webhost の 80 番ポートにアクセス remotehost% We1come to FreeBSD! 図 7 command オプション付き公開鍵によるパックアップ 10Ca1 五 ost % slogin remotehost Enter passphrase for key ' /home/local/hoehoe/ . ssh/id—rsa Backup start . Backup /home ー > /Backup/home Connection tO remotehost closed . localhost% トを図 8 に示します。 工スケープ・シーケンス SSH でポートフォワードを使用している場合、途中で 転送するポートを追加したくなることがあります。しか し、そのたびに新たに一 L オプション付きでログインする のは面倒です。また、一印判勺にローカルホストのシェルを 利用したい場合などもあるでしよう。そのような場合のた めに、エスケーフ・シーケンスによるいくつかの機能が用 92 図 8 パックアップ・スクリプト列 # ! /bin/sh echo "Backup start . if [ -f /usr/local/bin/rsync ] ; then /usr/local/bin/rsync —a - —delete /home /Backup echo "Backup /home ー > /Backup/home" echO fi echO 意されています。 ェスケーフ・シーケンスとは端木を制征卩する牛朱文字の ことで、子の直後に入力することによりなんらかの制御 ( チルダ ) がエスケーフ がおこなえます。 SSH では 文字で、この後ろにいくつかの文字を入力することて制御 が可能です。これは設疋ファイルの EscapeChar ノヾラ メータや ssh の -e オフションで変更できます。 チルダそのものを入力するには、、 " とします。 SSH でサポートされているエスケーフ・シーケンスの一覧を表 UNIX MAGAZINE 2003.9

特集・プログラミング入門 図 12 直接基去を用いたプログラムの改良版 = 0 ) arr ; to = brr; from int i ; int *from, *tO, illt zero, one; unsigned bit ; sort(void) void 1 ; bit; bit くく一 0 ; i く N ; i + + ) for (i zero = 0 ; for (bit if ((from[i] 十十・ one = N ; for (i = N ー 1 ; to [from[i] & fromCi] ; p = t0 ; from; t 0 from = p; if (p ! = arr) { & bit) bit? for (i 0 ; i く N; arr [i] = brr Ci] ; 0 ; —zero] —one : 十十 ) 利用することになります。ただし、ある範囲内にある値の 個数を言 1 算するのに配列は不要になります。ビットごとの 処理になるため、 0 か 1 のどちらかしかありません。した がって、片方の数を数えればもう一方の数も分かります。 これらの工夫を施したプログラムは、図 12 のようにな ります。 この関数では、変数 zer 。に注目しているビットが 0 の 要素の数を数えています。要素数を数え終えると、一番後 ろの要素から順に正しい位置へとコヒーしていきます。注 目しているビットが 0 の要素は、この変数の値が示す場 所の直前の位置か引内していけはよいはすです。また、 1 の要素の場合は、末尾から順番に各内していけばよいで しよう。そのため、 one を要素数を示す N に初期化し、 one や zero をデクリメントしつつデータをオ褓内していき ます。 全体のルーフ。の終了条件はすこし変わっています。プロ グラムに書かれた条件は、 bit 変数の値が 0 になったとこ ろでループを終了するようになっています。普通に考えれ は、 1 をいくらシフトしたところで 0 にはなりませんが、 126 変数が使用する領域をはみ出るほどシフトしてしまうと、 けっきよくは値が残らないことになるため、オー ノヾーフ ローしたときに 0 になるわけです。つまり、このループ は、もっとも右のヒ、ツトからみていって、ヒ、ツトが存 するあいだは左に進みながらループを繰り返すことを表し ています。 さて、この妾基去の手間は、フログラムを見ても分 かるとおり、 0 ( れ ) となります。ただし、基数交去と同 しく、定数部分には注意が必要です。配列として用意でき る程度のれに対する logn と上交すると、大きな値 ( た とえば、ビットごとの言算をしていて int が 4 バイトな ら 32 ) カ症数部分として掛けられています。基数交換法で は、グループにうリされたデータ数が少ないとき、処理を そこで終了することができましたが、直接基新去では困難 です。どのような場合にも、すべてのビットや桁について 処理をしなけ川まなりません。そのため、調べるべきビッ ト数が多いときなどは、けっきよくは遅くなってしまうの で注意してください。 基数整列法の改良 基数交去と妾基颪去は、どちらも基数整列法と呼は れる整列法の一重です。この手法では、調べるビット数が 多いと時間がかかってしまいます。これは、 1 ビットを調 べるために、すべての要素を処理しなけれはならないから です。つまり、調べるビット数をわとすると、回の処 理が必喫となってしまうのです。 処理の回数を減らすには、複数のビットをまとめて処理 する力法か有効です。たとえば、 2 ピットすっ処理したと すると、もともとはわ回繰り返さなけれはならなかったも のが、り 2 回繰り返すだけて処理を終えられるようになり ます。もちろん、 4 ビットすっ処理をすれは、全体の区 しの回数はり 4 となります。 これだけをみると、できるだけ多くのビットをまとめて 処理したほうか彳お区しの回数を減らせるため、処理か高速 におこなえると期待できます。極端にいえば、 32 ビット をまとめて処理すると、 ( int が 32 ピットであれは ) たっ た 1 回の区しで整列することができます。 しかし、これは無制限におこなえるわけではありませ ん。多くのビットをまとめて処理しようとすると、それに UNIX MAGAZINE 2003.9

SC 翡 FREEBSD/NET 日 SD/ ロ PEN 日 SD/ 日 SD/ ロ S AND OTHERS BSD ハッカーに なる。 2003 NO 15 繧売中 ! ! 特集 1 目指せ ! *BSD ハッカー 特集 2 Mac OS X システム管理者虎の巻 SpeciaI RAVAntiVirus for Mail Servers 841 株式会社アスキー 〒 160-8584 東京都新宿区信濃町 34 番地 J 日信濃町ビル電話 ( 03 ) 5362-3300 http://www.ascii. CO. jp/

プログラ第ング入門 今泉責史 アルゴリスムとデ - タ構造の基礎知識ー整列 ( 3 ) 0 前回は、整列に要する手間の理論的な限界値である 0 ( れ log れ ) て整列が可能なアルゴリズムとして、マージ ソートとヒープソートを紹介しました。この 0 ( れ 1 。 g れ ) は、値を上交しながら整列する場合の限界です。 1 ~ 4 月号でとりあげた、、探索 " で普通に上交操作をお こなうと、かならす〇 ( I 。 g れ ) の手間がかかってしまいま した。しかしハッシュ法では、要素数とバケット数の関 係によって 0 ( 1 ) に抑えられます。整列についても、これ とよく似た状況が考えられます。 今回は、おもに上師交によらない整列法をとりあげます。 これらの当リ法は、条件か限定されたき竟では、より高速 に動作する場合もあります。 これまでは、任意のキーが含まれるレコード集合の整列 Ⅲ題を考えてきました。こで、ちょっと条件を限定して みることにしましよう。ジョーカーを除いた 52 枚のトラ ンフ ( カード ) の整列に間題を限定します。スーツの順番 は適当でかまいませんが、曰列としてスペード、 ダイヤ、クラブの順であるとしておきます。 このように条件を限定すれは・、これまでとは違ったアフ ローチて整列を実現することができます。トランプを用い た、、七並べ " というゲームはご存しだと思います。七並べ では、最糸勺にはすべてのカードを場に並べることになり ます。この状態になっていれは、並んでいるカードを順番 七並べで整列 UNIX MAGAZINE 2003.9 に取り出すだけて整列した状態の 1 組のトランフ。か得られ ます。これを使ってみることにしましよう。実際の整列 方法は、カードの集合から 1 枚取り出したら、七並べです べてのカードか並べられた様子を思い浮かべながら、その カードがあるべき箇所に置いていきます。これを繰り返す だけです。そして最後に、並んだカードの順番を崩さない ように集めます。 それでは、この間題を言機で実現してみましよう。簡 単のために、各カードに 0 から 51 の番号を付けたとしま す。つまり、それぞれのカードを 0 から 51 という値て表 現するわけです。そして、その直の順番にカードを並べ 替えることか整列に相当します。 フログラムとして作成するのは簡単です。カードのもと もとの状態は、 crr 配列 ( ゴ尉寺されているものとします。 カードの枚数は NCARD マクロて袂められています。ま た、言 t 算に使える crr と同サイズの配列 drr を用意しまし た。この条「牛に沿ってフログラムを書くと、次のようにな ります。 VOid sort—cards (void) crr[i] という値をもつカードは、その値の順番にすれは・ int i ; for (i 0 ; i く NCARD; i + + ) drr Ccrr Ci] ] crr Ci] ; for (i 0 ; i く NCARD; i + + ) crr Ci] drr[i] ; 115