今回の課題は、１と２が必須、３は余力あらば、という出題形式でした。
- データ例(num_data.txt)を読みとり、ソートして返すプログラムを作成せよ
- プログラムの実行にはリダイレクションを用いよ
- プログラムの処理結果が正しいか検証する方法を考え、可能であれば実現せよ
プログラムが a.out の場合の実行例
% ./a.out < num_data.txt
1
4
7
19
28
簡単ですね。
今回の課題のねらいは、ソートプログラムの作り方...、ではなくてテストについてです。なんというか、テストはとても大事です。
プログラムのテストを作る目的として「そのプログラムの動作保証をする」ということと、どんなテストをするかを定義する過程で、「そのプログラムが何をアウトプットするべきかを考える」ということがあります。
今回のテストについての考え方は、開発手法の一つである XP(エクストリーム・プログラミング)の考えにのっとったものですので、興味のある人は調べてみて下さい。
となるべきことは提示されています。つまり、課題中では「ソートして返す」としか言っていませんが、具体例を見ることで、
という風に、出力について曖昧な箇所がなくなります。
このように、これからどんな実装をするのか、どんなアルゴリズムを使うべきか、を考える上でも、最終的なアウトプットを考えることは重要なのです。
最終的なアウトプットの予定あれば、それと実際のアウトプットを比べる仕組みを作ることは、そんなに難しくありません。実際に、簡単なテストを定義してみましょう。使うのは、Linux のコマンドである sort, diff で、プログラムのコンパイルとテストを実行するために make を用います。
３ですが、「ソートが完了した配列について、隣の数との大小を比較して
きちんと昇順になっているか確かめる」くらいしか思いつきませんでした。
という意見を貰いました。まぁそんな感じですが、今回については、「信頼できる物と比べる」という手法を取りましょう。例えるならば、「私の身長は 170cm だ！」と言い張る人が正しいかをテストするには、信頼できる長さの指標(メジャー)とか、を持ってきて実際に比べてみればよいのです。つまり、確実に正しい結果と、自分が正しい思っている結果を比べればよいのです。
今回は sort を使ってソートした結果と、プログラムを実行してソートした結果を比較します。
% sort -n num_data.txt
1
4
7
19
28
という風にソートできることを利用し、この結果と自分のプログラムのアウトプットを比べる仕組みを作ります。これには、シェルコマンドの diff を用います。
% sort -n num_data.txt > expected.txt
% ./a.out < num_data.txt > actual.txt
% diff expected.txt actual.txt
この手順を実行すると、sort と a.out の結果が一致していればなにも表示されず、一致していなければ diff の結果が出力されます。
このようなコマンドをコンパイル毎に手入力で実行するのは面倒です。というか、無駄です。コンパイルとテストの実行を簡単に行うための Makefile を以下に示します。
# Makefile for sort
# Satofumi KAMIMURA
# $Id$
# Compile options
CXXFLAGS = -O0 -Wall -Werror
LDFLAGS =
LDLIBS =
# Target
TARGET = sort
all : ${TARGET}
clean :
${RM} *.o ${TARGET} actual.txt expected.txt
test : all
@sort -n num_data.txt > expected.txt
@./sort < num_data.txt > actual.txt
@diff expected.txt actual.txt && echo "O.K." || echo "!!! fail"
.PHONY : all clean
######################################################################j
と入力すると sort.cpp をコンパイルして sort を生成し、
と入力すると、先ほどのテストを行い、テストが成功したかどうかを出力します。ちなみに「make test」はコンパイルするようにも調整してあるので、毎回「make test」と入力すると、プログラムは必要に応じてコンパイルされます。
テストとテストを実行する仕組み、これを確実に実現して、いつでも実行できるようにするのが大事です。なれてきたら、「xUnit」と呼ばれるテストの枠組みなどを勉強するとよいでしょう。
今回の課題はテストについて意識してもらうことなので、プログラムはおまけです。私が作ったプログラムは、C++ ですが、こんな感じです。C++ の標準ライブラリである STL を利用して、さくっと作りました。
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[]) {
vector<int> data((istream_iterator<int>(cin)), istream_iterator<int>());
sort(data.begin(), data.end());
for (std::vector<int>::iterator it = data.begin(); it != data.end(); ++it) {
cout << *it << endl;
}
return 0;
}
プログラムが数行しかありませんが、プログラムが短いことで、バグの混入する可能性も減るので、いい感じです。
他の実装の例としては、ソートするデータに重複がないと分かっていれば、ビット列にソートの数値があったかどうかを格納していく、という荒技もあります。おそらくトータルで必要なバイト数は減るはずです。
#include <stdio.h>
#define NUM 5
int main(void)
{
int box[NUM];
int i, j, tmp;
for(i=0; i<NUM; i++) {
scanf("%d", &box[i]);
}
for(i=0; i<NUM-1; i++) {
for(j=i+1; j<NUM; j++) {
if(box[j] < box[i]) {
tmp = box[j];
box[j] = box[i];
box[i] = tmp;
}
}
}
for(i=0; i<NUM; i++) {
printf("%d\n", box[i]);
}
return 0;
}
↑ぶっちゃけ、「バブルソートで読み込む数は 5 限定かよ！」とか思いました。数値を読み込むあたりについては、以下のようにするとよいと思います。
数値を読み込むサンプルプログラム
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
enum { DATA_SIZE = 1024 };
int data[DATA_SIZE];
int size;
int i;
int ret;
for (size = 0; size < DATA_SIZE; ++size) {
int ret = 0;
if ((ret = scanf("%d", &data[size])) == EOF) {
break;
}
if (ret <= 0) {
--size;
}
}
if (i == DATA_SIZE) {
printf("data is too many! (over %d)\n", DATA_SIZE);
exit(1);
}
あと、「#define NUM 5」の後ろに全角の空白があってコンパイルに失敗しました。メールに添付する直前にコメントを付けたのでしょうか...。できれば、コメントを先に書いてプログラムすべきです。何を作るのか意識してプログラミングすることになりますから。
あと、emacs で、全角の空白はカラー表示するための設定は、こんな感じです。(
.emacs より設定を抜粋) この設定を .emacs に追記することで、全角スペースや空白文字だけの行がカラーで強調表示されます。
#include<stdio.h>
#include<stdlib.h>
int cmp(int *n, int *m)
{
if(*n>*m)
return 1;
if(*n<*m)
return -1;
else
return 0;
}
int main(void)
{
int i=0,sort[5],c;
while(i!=5){
scanf("%d",&c);
sort[i]=c;
i++;
}
qsort(sort,5,sizeof(int),(int(*)(const void*, const void*))cmp);
for(i=0;i<5;i++)
printf("%d\n",sort[i]);
i=1;
while(cmp(&sort[i],&sort[i-1])>=0){
i++;
if(i==5){
printf("Sorting ended accurately\n");
return 0;
}
}
printf("Sorting failed\n");
for(i=0;i<5;i++)
printf("%d\n",sort[i]);
return 0;
}
qsort() 使っているのは、いい感じです。あと、main() は本の目次のように、何が書いてあるかすぐわかるような構成になっていると、さらによいです。
main() の中に、何をするか分かるような関数を定義する。
int main(int argc, char *argv[]) {
enum { DataSize = 1024 };
int data[DataSize];
inputData(data, DataSize);
sort(data, DataSize);
outputData(data, DataSize);
}
こんな感じなら、コメントがなくても、何をしているかの推測はつきます。でも、コメントはあった方がよいです。１行でいいので。
あと、ソート正当性の検証部分については、やり方はともかく明らかに for ループを使うべき箇所です。あと、できれば関数化。
while ループを for ループに変更し、エラー処理をループ内に移動
for (i=1;i<5;++i) {
if(cmp(&sort[i],&sort[i-1])<0) {
printf("Sorting failed\n");
for(i=0;i<5;i++)
printf("%d\n",sort[i]);
exit(1);
}
}
printf("Sorting ended accurately\n");
return 0;
}
ただ、この処理だとソート結果が 1, 1, 1, 1, 1 みたいなのでもテストを通過します。あと、どうせなら accurately でなく、correctly かと。
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *x, const void *y);
int main(){
int a[5],i;
for(i=0;i<5;i++)
{
scanf("%2d",&a[i]);
}
qsort(a,5,sizeof(int),cmp);
for(i=0;i<5;i++){
printf("%2d\n",a[i]);
}
return 0;
}
int cmp(const void *x, const void *y)
{
return *(int*)x - *(int*)y;
}
cmp() が減算で組んであるあたり、C++ なら、演算子オーバーロードがあるので、< で作りましょう、とかいうコメントが有効ですが...、まぁ、減算でもよいです。 でも、最低限、数値の 5 はマクロ化しましょう。
#include<stdio.h>
int main(void){
int n=5;
int num[n];
int i,j;
int min;
for(i=0;i<n;i++)
scanf("%d",&num[i]);
for(i=0;i<n;i++){
min=num[i];
for(j=i;j<n;j++){
if(min>num[j]){
min=num[j];
num[j]=num[i];
num[i]=min;
}
}
printf("%d\n",num[i]);
}
}
できれば、ソート部と出力部は分けましょう。
int n=5; にコメントがあるのは、よいです。できれば num も重要なのでコメントをつけましょう。
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> IntVector;
void
QuickSort(IntVector& arr, int first, int last)
{
int i, j;
int x;
x = arr[(first + last) / 2];
i = first;
j = last;
for(;;){
int tmp;
while(arr[i] < x) i++;
while(x < arr[j]) j--;
if(i >= j) break;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
if(first < i - 1)
QuickSort(arr, first, i - 1);
if(j + 1 < last)
QuickSort(arr, j + 1, last);
}
int
main()
{
IntVector arr;
for(;;){
int num;
cin >> num;
if(cin.eof()) break;
arr.push_back(num);
}
QuickSort(arr, 0, arr.size() - 1);
int arrSize = arr.size();
for(int i = 0; i < arrSize; i++){
cout << arr[i] << endl;
}
arrSize = arr.size();
int tmp = -INT_MAX;
for(int i = 0; i < arrSize; i++){
if(tmp > arr[i]){
cerr << "sort failed" << endl;
break;
}
else{
tmp = arr[i];
if( i == (arrSize - 1) )
cerr << "sort succeeded" << endl;
}
}
return 0;
}
どうせなら、失敗時の main() の戻り値は return 1 が通例です。あとは、arrSize を取得し直す必要がないのと、INT_MIN と INT_MAX は値が違います。それに、C++ 風に書くなら #include <limits> を使うべきです。
あと、ソートが成功とのメッセージを表示するあたりは、チェックに失敗したらフラグがたつように変更すると、すっきりするかも。
bool isCorrect = true;
int tmp = numeric_limits<int>::min();
for(int i = 0; i < arrSize; ++i){
if(tmp > arr[i]){
cerr << "sort failed" << endl;
isCorrect = false;
break;
}
tmp = arr[i];
}
if(isCorrect) {
cerr << "sort succeeded" << endl;
return 0;
}
