0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@anonymously115

paiza問題集「累積和」のリファクタリング・入力チェック・テストコードを考えてみた。

0
Posted at

paizaラーニングレベルアップ問題集の累積和をやってみました。

問題

実行時間制限超過コード

#include <stdio.h>

int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	int A[N];
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	while (K--) {
		int Q;
		scanf("%d", &Q);
		int sum = 0;
		for (int i = 0; i < Q; i++) {
			sum += A[i];
		}
		printf("%d\n", sum);
	}
	return 0;
}

二重ループがあり、計算量は$O(NK)$になります。$1\le K\le N\le10^3$程度ならともかく、$1\le K\le N\le10^5$の条件では実行時間制限超過になってしまいます。

とりあえずリファクタリング

配列部分をコンストラクタの引数に、クエリ部分をメソッドの引数に渡すようなクラスを作成します（C言語に“クラス”はありませんが）。

IntArray.h
#ifndef INTARRAY_H_
#define INTARRAY_H_

#include <stdbool.h>

typedef struct __IntArray _IntArray;

typedef struct IntArray {
	_IntArray *_intArray;
	bool (*cumulative_sum)(const struct IntArray*, size_t, int*);
} IntArray;

IntArray* new_IntArray(size_t, const int*);

void free_IntArray(IntArray**);

#endif /* INTARRAY_H_ */
IntArray.c
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "IntArray.h"

struct __IntArray {
	size_t n;
	int A[];
};

static int IntArray_cumulative_sum(const IntArray *self, size_t q, int *sum) {
	errno = 0;
	if (q > self->_intArray->n) {
		errno = ERANGE;
		return false;
	}
	*sum = 0;
	for (size_t i = 0; i < q; i++) {
		*sum += self->_intArray->A[i];
	}
	return true;
}

IntArray* new_IntArray(size_t n, int *A) {
	IntArray *intArray = (IntArray*) malloc(sizeof(IntArray));
	if (!intArray) {
		return NULL;
	}
	intArray->_intArray = (_IntArray*) malloc(sizeof(_IntArray) + sizeof(intArray->_intArray->A[0]) * n);
	if(!(intArray->_intArray)) {
		free(intArray);
		return NULL;
	}
	intArray->_intArray->n = n;
	memcpy(intArray->_intArray->A, A, sizeof(intArray->_intArray->A[0]) * n);
	intArray->cumulative_sum = IntArray_cumulative_sum;
	return intArray;
}

void free_IntArray(IntArray **intArray) {
	free((*intArray)->_intArray);
	(*intArray)->_intArray = NULL;
	free(*intArray);
	*intArray = NULL;
}

このIntArray“クラス”を使って、main.cを書き換えます。

main.c
#include <stdio.h>
#include <errno.h>
#include "IntArray.h"
#ifndef NDEBUG
#include <time.h>
#endif

int main() {
#ifndef NDEBUG
	clock_t clockt = clock();
#endif
	size_t N, K;
#ifdef NDEBUG
	scanf("%zu %zu", &N, &K);
#else
	N = 100000;
	K = 100000;
#endif
	int A[N];
	for (size_t i = 0; i < N; i++) {
#ifdef NDEBUG
		scanf("%d", &A[i]);
#else
		A[i] = ((int) i) % 201 - 100;
#endif
	}
	IntArray *intArray = new_IntArray(N, A);
	while (K--) {
		size_t Q;
#ifdef NDEBUG
		scanf("%d", &Q);
#else
		Q = N - K;
#endif
		int sum;
		if (!intArray->cumulative_sum(intArray, Q, &sum)) {
			int e = errno;
			perror(NULL);
			return e;
		}
		printf("%d\n", sum);
	}
	free_Intarray(&intArray);
#ifndef NDEBUG
	fprintf(stderr, "%f sec.\n", (float) (clock() - clockt) / CLOCKS_PER_SEC);
#endif
	return 0;
}

Windows環境で、以下のバッチファイルを作って10回時間測定しました。

main.bat
echo off
gcc -Wall -Wextra -Werror -std=c99 main.c IntArray.c -o main 1>main.txt 2>&1
if exist main.exe (
	for /l %%i in (0,1,9) do (
		.\main 1>nul
	)
	del main.exe
	del main.txt
) else (
	type main.txt
)
pause

実施結果

15.041000 sec.
14.532000 sec.
14.527000 sec.
15.331000 sec.
14.949000 sec.
15.129000 sec.
15.054000 sec.
14.984000 sec.
15.180000 sec.
16.077999 sec.
続行するには何かキーを押してください . . .
計算量について意識する

累積和

S_i=\sum_{j=1}^iA_i

の値を予め計算しておきます。これは、

\begin{align}
S_0&=0\\
S_{i+1}&=A_1+A_2+\dots+A_i+A_{i+1}\\
&=\left(A_1+A_2+\dots+A_i\right)+A_{i+1}\\
&=S_i+A_{i+1}
\end{align}

とすれば、$O(N)$の時間で計算することができます。※実装時は、配列$A$の添字に注意！

IntArray.c
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "IntArray.h"

struct __IntArray {
	size_t n;
	const int *A;
	int sum[];
};

static bool IntArray_cumulative_sum(const IntArray *self, size_t q, int *sum) {
	errno = 0;
	if (q > self->_intArray->n) {
		errno = ERANGE;
		return false;
	}
	*sum = self->_intArray->sum[q];
	return true;
}

IntArray* new_IntArray(size_t n, const int *A) {
	IntArray *intArray = (IntArray*) malloc(sizeof(IntArray));
	if (!intArray) {
		return NULL;
	}
	intArray->_intArray = (_IntArray*) malloc(sizeof(_IntArray) + sizeof(intArray->_intArray->sum[0]) * -~n);
	if(!(intArray->_intArray)) {
		free(intArray);
		return NULL;
	}
	intArray->_intArray->n = n;
	intArray->_intArray->A = A;
	int *S = intArray->_intArray->sum;
	S[0] = 0;
	for (size_t i = 0; i < n; i++) {
		S[i+1] = S[i] + A[i];
	}
	intArray->cumulative_sum = IntArray_cumulative_sum;
	return intArray;
}

void free_IntArray(IntArray **intArray) {
	free((*intArray)->_intArray);
	(*intArray)->_intArray = NULL;
	free(*intArray);
	*intArray = NULL;
}

先程のバッチファイルを使って時間計測をした結果、以下の様になりました。

0.826000 sec.
0.714000 sec.
0.782000 sec.
0.722000 sec.
0.665000 sec.
0.742000 sec.
0.711000 sec.
0.722000 sec.
0.663000 sec.
0.714000 sec.
続行するには何かキーを押してください . . .
テストコード

IntArray“クラス”のコンストラクタとcumulative_sumメソッドのテストをしたいと思います。
コンストラクタは、2つの入力例に対し、不完全型へのポインタを用いてテストすることにします。
メソッドについては

  • $q=0$の時$0$を出力する
  • $q>N$の時falseを返す

ことを確認します。

単体テストツールとして、minunit.hを使うことにします。

IntArrayTest.c
#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <errno.h>
#include "minunit.h"
#include "IntArray.h"

int tests_run = 0;

static char* message(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* test_constructor(size_t n, const int *A, const int *expected) {
	IntArray *intArray = new_IntArray(n, A);
	int actual[n+1];
	memcpy(actual, (void*) (intArray->_intArray) + sizeof(size_t) + sizeof(int*), sizeof(actual));
	free_IntArray(&intArray);
	for (size_t i = 0; i <= n; i++) {
		mu_assert(message(expected[i], actual[i]), actual[i] == expected[i]);
	}
	return 0;
}

static char* test_constructor_0() {
	int S[] = { 0 };
	return test_constructor(0, NULL, S);
}

static char* test_constructor_1() {
	int A[] = { 69, 12, 28 };
	int S[] = { 0, 69, 81, 109 };
	return test_constructor(sizeof(A) / sizeof(A[0]), A, S);
}

static char* test_constructor_2() {
	int A[] = { 45, 74, -94, 68, -63, 19, -47, -69, 38, 60 };
	int S[] = { 0, 45, 119, 25, 93, 30, 49, 2, -67, -29, 31 };
	return test_constructor(sizeof(A) / sizeof(A[0]), A, S);
}

static char* test_cumulative_sum(int expected, size_t q, size_t n, ...) {
	va_list args;
	va_start(args, n);
	int A[n];
	for (size_t i = 0; i < n; i++) {
		A[i] = va_arg(args, int);
	}
	va_end(args);
	IntArray *intArray = new_IntArray(n, A);
	int actual;
	bool result = intArray->cumulative_sum(intArray, q, &actual);
	free_IntArray(&intArray);
	mu_assert("Error: expected: <true> but was: <false>", result);
	mu_assert(message(expected, actual), actual == expected);
	mu_assert(message(0, errno), errno == 0);
	return 0;
}

static char* test_cumulative_sum_fail(size_t q, size_t n, ...) {
	va_list args;
	va_start(args, n);
	int A[n];
	for (size_t i = 0; i < n; i++) {
		A[i] = va_arg(args, int);
	}
	va_end(args);
	IntArray *intArray = new_IntArray(n, A);
	int sum;
	bool result = intArray->cumulative_sum(intArray, q, &sum);
	free_IntArray(&intArray);
	mu_assert("Error: expected: <false> but was: <true>", !result);
	mu_assert(message(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_cumulative_sum_0() {return test_cumulative_sum(0, 0, 0);}
static char* test_cumulative_sum_1() {return test_cumulative_sum_fail(1, 0);}
static char* test_cumulative_sum_2() {return test_cumulative_sum(109, 3, 3, 69, 12, 28);}

static char* all_tests() {
	mu_run_test(test_constructor_0);
	mu_run_test(test_constructor_1);
	mu_run_test(test_constructor_2);
	mu_run_test(test_cumulative_sum_0);
	mu_run_test(test_cumulative_sum_1);
	mu_run_test(test_cumulative_sum_2);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

Windows環境では、以下のバッチファイルを作っておくと簡単にテスト実施できるでしょう。

IntArrayTest.bat
echo off
gcc -Wall -Wextra -Werror -std=c99 inputTest.c input.c -o inputTest 1>inputTest.txt 2>&1
if exist inputTest.exe (
	.\inputTest
	echo %ERRORLEVEL%
	del inputTest.exe
	del inputTest.txt
) else (
	type inputTest.txt
)
pause

入力チェック

問題集や競技プログラミングでは、制約条件通りの値が与えられますが、実際は数値が入力されるべき箇所に文字が入り込んだりします。そこで、不正な入力をはじくようにします。
今回は

  • $1\le K\le N\le 100000$
  • $-100\le A_i\le100$（$1\le i\le N$）
  • $1\le q_j\le N$（$1\le j\le K$）

のみ受け入れるように

  • 先頭行（要素数、クエリ数）の入力をチェックする
  • 配列要素の入力をチェックする
  • クエリ入力をチェックする

関数を作成します。

input.h
#ifndef INPUT_H_
#define INPUT_H_

#include <stdbool.h>

bool read_size(const char*, size_t*, size_t*);

bool read_element(const char*, int*);

bool read_query(const char*, size_t, size_t*);

#endif /* INPUT_H_ */
input.c
#include <string.h>
#include <ctype.h>
#include <inttypes.h>
#include <limits.h>
#include <errno.h>
#include "input.h"

static char* chomp(char *str) {
	size_t n = strlen(str);
	while (n--) {
		if (isspace(str[n])) {
			str[n] = '\0';
		} else {
			break;
		}
	}
	return str;
}

static bool is_unsigned(const char *str) {
	errno = 0;
	if (!(str && *str)) {
		errno = EINVAL;
		return false;
	}
	if (str[0] == '0') {
		if (str[1]) {
			errno = EINVAL;
			return false;
		}
		return true;
	}
	for (const char *c = str; *c; c++) {
		if (!isdigit(*c)) {
			errno = EINVAL;
			return false;
		}
	}
	return true;
}

static bool is_signed(const char *str) {
	errno = 0;
	if (!(str && *str)) {
		errno = EINVAL;
		return false;
	}
	if (str[0] == '-') {
		if (str[1] == '0') {
			errno = EINVAL;
			return false;
		} else {
			return is_unsigned(str + 1);
		}
	} else {
		return is_unsigned(str);
	}
}

static bool parse_unsigned(const char *str, uintmax_t max, uintmax_t *out) {
	errno = 0;
	if (!is_unsigned(str)) {
		return false;
	}
	char *s = NULL;
	*out = strtoumax(str, &s, 10);
	if (errno) {
		return false;
	} else if (s && *s) {
		errno = EINVAL;
		return false;
	} else if (*out > max) {
		return false;
	}
	return true;
}

static bool parse_signed(const char *str, intmax_t max, intmax_t *out) {
	errno = 0;
	if (!is_signed(str)) {
		return false;
	}
	char *s = NULL;
	*out = strtoimax(str, &s, 10);
	if (errno) {
		return false;
	} else if (s && *s) {
		errno = EINVAL;
		return false;
	} else if (*out < ~max || max < *out) {
		return false;
	}
	return true;
}

static bool parse_ulong(const char *str, size_t *out) {
	errno = 0;
	size_t tmp;
	if (!parse_unsigned(str, SIZE_MAX, &tmp)) {
		return false;
	}
	*out = (size_t) tmp;
	return true;
}

static bool parse_int(const char *str, int *out) {
	errno = 0;
	intmax_t tmp;
	if (!parse_signed(str, INT_MAX, &tmp)) {
		return false;
	}
	*out = (int) tmp;
	return true;
}

bool read_size(const char *str, size_t *n, size_t *k) {
	errno = 0;
	if (!str) {
		errno = EINVAL;
		return false;
	}
	char s[] = "100000 100000\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_ulong(strtok(chomp(strncpy(s, str, sizeof(s))), " "), n)) {
		return false;
	} else if (*n < 1 || 100000 < *n) {
		errno = ERANGE;
		return false;
	}
	if (!parse_ulong(strtok(NULL, " "), k)) {
		return false;
	} else if (*k < 1 || 100000 < *k) {
		errno = ERANGE;
		return false;
	}
	if (strtok(NULL, " ")) {
		errno = EINVAL;
		return false;
	}
	return true;
}

bool read_element(const char *str, int *a) {
	if (!str) {
		errno = EINVAL;
		return false;
	}
	char s[] = "-100\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_int(chomp(strncpy(s, str, sizeof(s))), a)) {
		return false;
	} else if (*a < -100 || 100 < *a) {
		errno = ERANGE;
		return false;
	}
	return true;
}

bool read_query(const char *str, size_t n, size_t *q) {
	if (!str) {
		errno = EINVAL;
		return false;
	}
	char s[] = "100000\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_ulong(chomp(strncpy(s, str, sizeof(s))), q)) {
		return false;
	} else if (*q < 1 || n < *q) {
		errno = ERANGE;
		return false;
	}
	return true;
}
テストコード
  • 不正文字列がはじけているか
  • 範囲チェックができているか
  • 適切なエラーコードが返っているか

をテストします。（"A" "abc"などの文字列入力は省略しておりますが、実際の業務ではキチンとパターンを洗い出して実施したいと思います）

inputTest.c
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "minunit.h"
#include "input.h"

int tests_run = 0;

static char* message_d(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* message_z(size_t expected, size_t actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* test_read_size(const char *str, size_t en, size_t ek) {
	size_t n, k;
	mu_assert("Error: expected: <true> but was: <false>", read_size(str, &n, &k));
	mu_assert(message_z(en, n), n == en);
	mu_assert(message_z(ek, k), k == ek);
	return 0;
}

static char* test_read_size_invalid(const char *str) {
	size_t n, k;
	mu_assert("Error: expected: <false> but was: <true>", !read_size(str, &n, &k));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_size_out_of_range(const char *str) {
	size_t n, k;
	mu_assert("Error: expected: <false> but was: <true>", !read_size(str, &n, &k));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_size_0() {return test_read_size_invalid(NULL);}
static char* test_read_size_1() {return test_read_size_invalid("");}
static char* test_read_size_2() {return test_read_size_invalid("1");}
static char* test_read_size_3() {return test_read_size_invalid("1 1 1");}
static char* test_read_size_4() {return test_read_size_out_of_range("0 1");}
static char* test_read_size_5() {return test_read_size_out_of_range("1 0");}
static char* test_read_size_6() {return test_read_size("1 1", 1, 1);}
static char* test_read_size_7() {return test_read_size("100000 100000", 100000, 100000);}
static char* test_read_size_8() {return test_read_size_out_of_range("100000 100001");}
static char* test_read_size_9() {return test_read_size_out_of_range("100001 100000");}

static char* test_read_element(const char *str, int expected) {
	int actual;
	mu_assert("Error: expected: <true> but was: <false>", read_element(str, &actual));
	mu_assert(message_d(expected, actual), actual == expected);
	return 0;
}

static char* test_read_element_invalid(const char *str) {
	int actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_element(str, &actual));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_element_out_of_range(const char *str) {
	int actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_element(str, &actual));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_element_0() {return test_read_element_invalid(NULL);}
static char* test_read_element_1() {return test_read_element_invalid("");}
static char* test_read_element_2() {return test_read_element_out_of_range("-101");}
static char* test_read_element_3() {return test_read_element("-100", -100);}
static char* test_read_element_4() {return test_read_element_invalid("-0");}
static char* test_read_element_5() {return test_read_element_invalid("00");}
static char* test_read_element_6() {return test_read_element("100", 100);}
static char* test_read_element_7() {return test_read_element_out_of_range("101");}

static char* test_read_query(const char *str, size_t n, size_t expected) {
	size_t actual;
	mu_assert("Error: expected: <true> but was: <false>", read_query(str, n, &actual));
	mu_assert(message_z(expected, actual), actual == expected);
	return 0;
}

static char* test_read_query_invalid(const char *str, size_t n) {
	size_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_query(str, n, &actual));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_query_out_of_range(const char *str, size_t n) {
	size_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_query(str, n, &actual));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_query_0() {return test_read_query_invalid(NULL, 0);}
static char* test_read_query_1() {return test_read_query_invalid("", 0);}
static char* test_read_query_2() {return test_read_query_out_of_range("0", 0);}
static char* test_read_query_3() {return test_read_query("1", 1, 1);}
static char* test_read_query_4() {return test_read_query_out_of_range("2", 1);}
static char* test_read_query_5() {return test_read_query("100000", 100000, 100000);}
static char* test_read_query_6() {return test_read_query_out_of_range("100001", 100000);}

static char* all_tests() {
	mu_run_test(test_read_size_0);
	mu_run_test(test_read_size_1);
	mu_run_test(test_read_size_2);
	mu_run_test(test_read_size_3);
	mu_run_test(test_read_size_4);
	mu_run_test(test_read_size_5);
	mu_run_test(test_read_size_6);
	mu_run_test(test_read_size_7);
	mu_run_test(test_read_size_8);
	mu_run_test(test_read_size_9);
	mu_run_test(test_read_element_0);
	mu_run_test(test_read_element_1);
	mu_run_test(test_read_element_2);
	mu_run_test(test_read_element_3);
	mu_run_test(test_read_element_4);
	mu_run_test(test_read_element_5);
	mu_run_test(test_read_element_6);
	mu_run_test(test_read_element_7);
	mu_run_test(test_read_query_0);
	mu_run_test(test_read_query_1);
	mu_run_test(test_read_query_2);
	mu_run_test(test_read_query_3);
	mu_run_test(test_read_query_4);
	mu_run_test(test_read_query_5);
	mu_run_test(test_read_query_6);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

で、テスト実施用のバッチファイルがこちら。

inputTest.bat
echo off
gcc -Wall -Wextra -Werror -std=c99 inputTest.c input.c -o inputTest 1>inputTest.txt 2>&1
if exist inputTest.exe (
	.\inputTest
	echo %ERRORLEVEL%
	del inputTest.exe
	del inputTest.txt
) else (
	type inputTest.txt
)
pause

エントリポイント

main関数を、入力チェック付きの関数に置き換えます。一応、速度計測用のデバッグコードも残しておきます（コンパイル時に-DNDEBUGを付けるか付けないかで切り替える）。

main.c
#include <stdio.h>
#include <errno.h>
#include "IntArray.h"
#ifdef NDEBUG
#include <string.h>
#include "input.h"
#else
#include <time.h>
#endif

int main() {
#ifndef NDEBUG
	clock_t clockt = clock();
#endif
	size_t N, K;
#ifdef NDEBUG
	do {
		char s[] = "100000 100000\n";
		if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
			for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
		} else {
			if (read_size(s, &N, &K)) {
				break;
			}
		}
		perror("The number of elements must be an integer between 1 and 100000.\n"
		       "The number of queries must be an integer between 1 and 100000.");
	} while (true);
#else
	N = 100000;
	K = 100000;
#endif
	int A[N];
	for (size_t i = 0; i < N; i++) {
#ifdef NDEBUG
		do {
			char s[] = "-100\n"; 
			if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
				for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else {
				if (read_element(s, &A[i])) {
					break;
				}
			}
			perror("The element must be an integer between -100 and 100.");
		} while (true);
#else
		A[i] = ((int) i) % 201 - 100;
#endif
	}
	IntArray *intArray = new_IntArray(N, A);
	while (K--) {
		size_t Q;
#ifdef NDEBUG
		do {
			char s[] = "100000\n"; 
			if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
				for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else {
				if (read_query(s, N, &Q)) {
					break;
				}
			}
			fprintf(stderr, "The index must be an integer between 1 and %zu.\n", N);
		} while (true);
#else
		Q = N - K;
#endif
		int sum;
		if (!intArray->cumulative_sum(intArray, Q, &sum)) {
			int e = errno;
			perror(NULL);
			return e;
		}
		printf("%d\n", sum);
	}
	free_Intarray(&intArray);
#ifndef NDEBUG
	fprintf(stderr, "%f sec.\n", (float) (clock() - clockt) / CLOCKS_PER_SEC);
#endif
	return 0;
}

main関数のテストも、以下のテストコード及びバッチファイルにて、自動化できないこともないです。入力エラーではじかれてもちゃんと再入力できることも確認します。但し、入力を間違えると無限に走ってしまいます…

test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include <errno.h>
#include "minunit.h"
#define SOURCE "main"
#define IN_FILE "in.txt"
#define OUT_FILE "out.txt"
#define ERR_FILE "err.txt"

int tests_run = 0;
char result[100000][11];

static char* message_u(size_t expected, size_t actual) {
	static char msg[72];
	sprintf(msg, "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* message_s(const char *expected, const char *actual) {
	static char msg[72];
	sprintf(msg, "Error: expected: <%s> but was: <%s>", expected, actual);
	return msg;
}

static size_t test(size_t n, const char *lines[]) {
	static unsigned k = 0;
	FILE *file;
	if (!(file = fopen(IN_FILE, "w"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	for (size_t i = 0; i < n; i++) {
		fputs(lines[i], file);
		fputc('\n', file);
	}
	fclose(file);
	clock_t start = clock();
	if (!!(errno = system(".\\" SOURCE " <" IN_FILE " 1>" OUT_FILE " 2>" ERR_FILE))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	fprintf(stderr, "#%u %f sec\n", ++k, (float) (clock() - start) / CLOCKS_PER_SEC);
	fflush(stderr);
	if (!(file = fopen(OUT_FILE, "r"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	size_t m = 0;
	while (fgets(result[m], sizeof(result[m]), file)) m++;
	fclose(file);
	return m;
}

static char* test0() {
	const char *lines[] = { "1 1", "0", "1" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(1, n), n == 1);
	mu_assert(message_s("0\n", result[0]), !strcmp(result[0], "0\n"));
	return 0;
}

static char* test1() {
	const char *lines[] = { "3 3", "69", "12", "28", "1", "2", "3" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(3, n), n == 3);
	mu_assert(message_s("69\n", result[0]), !strcmp(result[0], "69\n"));
	mu_assert(message_s("81\n", result[1]), !strcmp(result[1], "81\n"));
	mu_assert(message_s("109\n", result[2]), !strcmp(result[2], "109\n"));
	return 0;
}

static char* test2() {
	const char *lines[] = { "10 3",
		"45", "74", "-94", "68", "-63", "19", "-47", "-69", "38", "60",
		"9", "5", "5" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(3, n), n == 3);
	mu_assert(message_s("-29\n", result[0]), !strcmp(result[0], "-29\n"));
	mu_assert(message_s("30\n", result[1]), !strcmp(result[1], "30\n"));
	mu_assert(message_s("30\n", result[2]), !strcmp(result[2], "30\n"));
	return 0;
}

static char* test3() {
	const char *lines[] = {
		"100000  100000", "100001 100001", "0 0", "1 1 1", "2 2",
		"101", "-101", "-100", "100", "0",
		"3", "1", "2"
	};
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(2, n), n == 2);
	mu_assert(message_s("-100\n", result[0]), !strcmp(result[0], "-100\n"));
	mu_assert(message_s("0\n", result[1]), !strcmp(result[1], "0\n"));
	return 0;
}

static char* test4() {
	static char *lines[200001] = { "100000 100000" };
	for (size_t i = 1; i <= 100000; i++) {
		lines[i] = "-100";
	}
	static char chars[100000][8] = {};
	for (size_t i = 0; i < 100000; i++) {
		snprintf(chars[i], sizeof(chars[i]), "%zu", i + 1);
		lines[100001 + i] = chars[i];
	}
	size_t n = test(sizeof(lines) / sizeof(lines[0]), (const char**) lines);
	mu_assert(message_u(100000, n), n == 100000);
	for (size_t i = 0; i < 100000; i++) {
		char expected[11];
		snprintf(expected, sizeof(expected), "-%zu00\n", i + 1);
		mu_assert(message_s(expected, result[i]), !strcmp(result[i], expected));
	}
	return 0;
}

static char* all_tests() {
	mu_run_test(test0);
	mu_run_test(test1);
	mu_run_test(test2);
	mu_run_test(test3);
	mu_run_test(test4);
	return 0;
}

int main() {
	if (!!(errno = system("gcc -Wall -Wextra -Werror -DNDEBUG -std=c99 " SOURCE ".c IntArray.c input.c -o " SOURCE " 1>" SOURCE ".txt 2>&1"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		FILE* file = fopen(SOURCE ".txt", "r");
		if (file) {
			int c = 0;
			while ((c = fgetc(file)) != EOF) {
				putchar(c);
			}
			fclose(file);
		}
		return errno;
	}
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	remove(ERR_FILE);
	remove(OUT_FILE);
	remove(IN_FILE);
	remove(SOURCE ".exe");
	remove(SOURCE ".txt");
	if (errno) {
		return errno;
	} else {
		return result != 0;
	}
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?