#92の処理時間計測プログラムでは基数ソートの計測をするにはデータサイズが小さいようである。 ...snip int main(void) { const int nelems[] = {500, 707, 1000, 1414, 2000, 2828, 4000}; const int ntrials[] = {200, 140, 100, 70, 50, 35, 25}; ...sni…

書き忘れたが、前回の結果はUbuntu上で動作させたものである。 この結果から、かなり面倒くさいリスト操作を色々やっているにも関わらず、 バケツソートによる基数ソートは非常に速いことが分かる。 また、この基数ソートの実装では、 ある要素からその一つ…

非比較整列法であるバケツソートを利用した基数ソートでは、 整列にどれくらいの時間がかかるのか計測してみる。 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <time.h> #include "intlist.h" static intlist_t rsort(intlist_t list, int n) { int i, s; intlist_t buck</time.h></assert.h></stdlib.h></stdio.h>…

飽きたというのは純粋に飽きたというだけで、 たまには南極や北極の空気なんかになったら目先が変わっていいのにという程度です。 ご心配おかけしました。今日はいろいろ書き物をしたのだが、 書き散らしっ放しでまとまっていないので、 明日以降の記事で。…

夏の気温にはいつもさっさと慣れるのだが、そろそろこの暑気にも飽きてきた。 とはいえ、冬になれば同じことを寒気に対して言うことになるのだろう。

ですね。 でも日照りになったりするわけではなく、 水はきちんとある暑さなので、 お米とかがたくさんできたりするのだろうか。

ここに書くための断片の元を書くのがどうにも…… ネタはいろいろあるけれど。

うちにある複数のPCはもちろんLANで繋いでいるのだが、 PC間でデータの授受を行う場合は当然送信側と受信側の両方が起動していないといけない。 ただでさえ暑いのに短時間でも二台動作させるのは嫌だし、 いちいち片方の都合でもう一方を起動するのは面倒で…

今年は今日が処暑だった。 暑さは相変わらずだが今日は湿度が低めで風があったので汗をあまり掻かずに済んだ。

今日か明日あたりが処暑だったと思う。 今まで暑さに暑さを重ねるだけだったのが、 涼しさの成分が少しずつ加わり始める夏の山場。 なので、これ以上に暑くはならないだろうけど、 暑さはまだまだ続くしこれまでの暑さ疲れが出る頃。 体調には気をつけて。

一羽を捕獲するために二羽が犠牲に…… 入場者を増やすだけが工夫の為所ではない。

これまで、基数ソートにおけるステップごとの整列アルゴリズムに隣接交換法を使ってきた。 そのためこの基数ソートは要素数の二次オーダ、もしくはリストの実装次第ではそれ以上の時間計算量となる。 今回は、in-placeな整列という前提を崩すことになるが、 …

RAND_MAXを表現するときに必要なビット数を4ビット単位で。 セットされている最上位ビットの位置を見るのでもいいかもしれないがシンプルに。 #include <stdio.h> #include <stdlib.h> int main(void) { int i, n = 0; for (i = RAND_MAX; i != 0; i /= 16) n++; printf("%d %d\</stdlib.h></stdio.h>…

前回の二つの例の結果から見えてくるように、 整数値の各桁を構成する数字にその整数値の符号を付けたもので順位を比較するようにした場合、 最後の符号による比較は不要になる。 それより前の段階で、負数よりも非負数の方が順位が上になるように自然に定義…

負数から10進数での各桁の数字を取り出すときに9からその数字を減じた値でもって比較した。 つまり、10進法での9の補数で順位を定義したことになる。 しかし、わざわざ補数表現にせずに、 負数の場合はその桁の数字に負符号を付けたものを値とすることでも問…

これまで3桁の自然数という範囲にリスト要素の値がある場合の基数ソートだったが、 桁数に制限は付くのは同じだが負の場合も含む整数値に拡大した時の整列について。 とりあえず10進数一桁を単位とする基数ソートで行ってみる。 #include <stdio.h> #include <stdlib.h> #includ</stdlib.h></stdio.h>…

前回、十進数での一桁単位で基数ソートを行ったわけだが、 別に十進数一桁でなければならないなんてことはない。 ...snip static int issup(cintelem_t p, cintelem_t q, void *base) { return intelem_get_val(p) / (int)base % 16 > intelem_get_val(q) / …

6月初頭に書いたように、昨夜というか今日の早朝というか金星食があった。 しかし、またしても雲に阻まれた。 昨日の夜の始まり頃にはまだ何とか空に晴れた部分もあったのだが、 結局、食が始まる頃には、全面、雲で覆われることに。 惑星食の頻度は高いとは…

何か物を整理するときに、まず大分類で分けて、同じ大分類の物について中分類で分類し、 さらに小分類へというように整頓することはよくある。 これに対して基数ソートはまず最小の単位について整列させて、 次々と上の単位に関する整列を行うことで整列を完…

最終日。 参加者の皆さん、お疲れ様でした。

暑中の混雑第二日目。 非常に局地的には雨が降ったり、全く降らなかったり。

例のあれの一日目。

同じ順位の要素の順序が入れ替わっても別に問題ないと言われればそうなのだが、 整列法が安定であると便利な使い方もできる。3桁の自然数が収められたリストを昇順に整列することを考える。 これはこれまでやってきたことであり、 普通に各要素の自然数間の…

両者無気力試合をアクティブにさせたいのならお互いのユニフォームを交換させればいい。 審判や大会運営はとんちを利かせてその場で対処するくらいの余裕をもつべきだろう。 注意だけで止まるなら赤信号は要らない*1。 *1:黄色も止まれの意だという意見もあ…

立秋なのに暑いと言ってる人がいるようだが、 立秋だから暑いのだ。 体温近くまで気温が上がるとちょっときついと思うので、 水分等をきちんと摂って熱中症に気をつけて。

先週の土曜日に近所の川で花火大会があった（らしい）。 らしい、というのは花火の音すら聞こえなかったからだ。 先々週の土曜日にも海方向で花火が打ち上がっていたが、 こちらはかなり低空にだが丁度見えていたし、音も聞こえてきていた。 打ち上げ場所の…

もうすぐ立秋なので今のうちに暑中お見舞い申し上げます。 この辺りは普通の夏の暑さ程度で大したことないので大丈夫。 どちらかというと、西の方とか内陸とかの方が大変そうだと、 天気概況を見ていていつも思ってたり。 熱中症などに気を付けて身体をいた…

前回示したように基本選択法は隣接交換法に比べて時間性能が随分よくなっている。 しかし、基本選択法には、問題にしなくていいのなら問題にならないが、 場合によっては困ったことになるようなある性質がある。 #include <stdio.h> #include "intlist.h" #define UNU</stdio.h>…

さて、前回の結果から冪関数への回帰分析を行い、結果をプロットしてみよう。 比較、交換回数の性質は数値による結果だけでも明白なので、 ここでは整列に要した時間に関するものだけを表示する。 'plot2.dat'は隣接交換法による双方向連結リストの整列の結…

例によって整列に要する時間を計測する#71のプログラムに基本選択法の整列コードをリンクして実行する。 単連結リストintlistを利用した場合、 # nelems ncmps nswps elapsed 200 19900.0 194.2 36.5 300 44850.0 293.8 78.1 400 79800.0 393.5 135.4 600 17…