fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <memory.h>
  4. #include <locale.h>
  5. #include <stdint.h>
  6. #include <time.h>
  7. #include <sys/time.h>
  8.  
  9. void insersion_sort(unsigned array[], unsigned length);
  10. #define swap(a, b)  do {unsigned tmp; tmp = *(b); *(b) = *(a); *(a) = tmp;} while (0)
  11.  
  12. typedef unsigned int aho_type_t;
  13. void insersion_sort2(aho_type_t* au_data, size_t u_n);
  14.  
  15. aho_type_t* aho_malloc_random_data(size_t u_n);
  16. aho_type_t* aho_malloc_clone_data(aho_type_t const* au_data, size_t u_n);
  17. aho_type_t const* aho_check_seq1(aho_type_t const* au_data, size_t u_n);
  18. aho_type_t const* aho_check_seq2(aho_type_t const* au_random_data, aho_type_t const* au_sorted_data, size_t u_n);
  19.  
  20. uint32_t aho_xorshift_u32(void);
  21. int32_t aho_xorshift_i32(void);
  22. aho_type_t const* aho_bsearch_upper_bound_p(aho_type_t const* au_data_s, aho_type_t const* au_data_e, aho_type_t value);
  23. double aho_sec_count(void);
  24. int aho_qcomp(const void *r, const void *l);
  25.  
  26. /*
  27.  32bit擬似乱数生成
  28.  */
  29.  
  30. static uint32_t u_seed = 2463534242;
  31.  
  32. uint32_t aho_xorshift_u32(void) {
  33. 	u_seed = u_seed ^ (u_seed << 13); u_seed = u_seed ^ (u_seed >> 17);
  34. 	return (u_seed = u_seed ^ (u_seed << 15));
  35. }
  36.  
  37. int32_t aho_xorshift_i32(void) {
  38. 	u_seed = u_seed ^ (u_seed << 13); u_seed = u_seed ^ (u_seed >> 17);
  39. 	return (u_seed = u_seed ^ (u_seed << 15));
  40. }
  41.  
  42. /*
  43.  n個の乱数列生成
  44.  */
  45.  
  46. aho_type_t* aho_malloc_random_data(size_t u_n) {
  47. 	aho_type_t* au_data = malloc(u_n * sizeof(aho_type_t));
  48. 	aho_type_t* pu_data = au_data;
  49. 	aho_type_t* pu_end_of_data = au_data + u_n;
  50. 	for ( ; pu_data < pu_end_of_data; ++pu_data) {
  51. 		*pu_data = aho_xorshift_u32();
  52. 	}
  53. 	return au_data;
  54. }
  55.  
  56. aho_type_t* aho_malloc_clone_data(aho_type_t const* au_data, size_t u_n) {
  57. 	aho_type_t* pu_data = malloc(u_n * sizeof(aho_type_t));
  58. 	memcpy(pu_data, au_data, u_n * sizeof(aho_type_t));
  59. 	return pu_data;
  60. }
  61.  
  62. /*
  63.  列が整列されているかﾁｪｯｸ
  64.   NULL：ﾁｪｯｸOK
  65.   NULL以外：整列された列のﾍﾟｹの要素のｱﾄﾞﾚｽ
  66.  */
  67.  
  68. aho_type_t const* aho_check_seq1(aho_type_t const* au_data, size_t u_n) {
  69. 	aho_type_t const* cu_data = au_data;
  70. 	aho_type_t const* cu_end_of_data = au_data + u_n - 1;
  71. 	for (; cu_data < cu_end_of_data; ++cu_data) {
  72. 		if (*cu_data > *(cu_data + 1)) {
  73. 			fprintf(stderr, "【診断結果】：列(=[%zu])の値(=%u)と列(=[%zu])の値(=%u)の大小関係が適切ではありません\n", (size_t)(cu_data - au_data), *cu_data, (size_t)((cu_data + 1) - au_data), *(cu_data + 1));
  74. 			return cu_data + 1;
  75. 		}
  76. 	}
  77. 	return NULL;
  78. }
  79.  
  80. /*
  81.  昇順ｿｰﾄされた列から先頭の値を検索（値は重複している）
  82.  */
  83.  
  84. aho_type_t const* aho_bsearch_upper_bound_p(aho_type_t const* au_data_s, aho_type_t const* au_data_e, aho_type_t value) {
  85. 	aho_type_t const* cu_data_s = au_data_s;
  86. 	aho_type_t const* cu_data_e = au_data_e;
  87. 	aho_type_t const* cu_data_m = NULL;
  88.  
  89. 	while (cu_data_s < cu_data_e) {
  90. 		cu_data_m = cu_data_s + ((cu_data_e - cu_data_s) >> 1);
  91.  
  92. 		if (*cu_data_m < value) {
  93. 			cu_data_s = cu_data_m + 1;
  94. 		} else {
  95. 			cu_data_e = cu_data_m;
  96. 		}
  97. 	}
  98.  
  99. 	return (cu_data_m != NULL && cu_data_e == cu_data_s && *cu_data_s == value) ? cu_data_s : NULL;
  100. }
  101.  
  102. #define BITS_TO_BYTES(bits)               ((size_t)(((((bits) - 1) >> 3) + 1) * sizeof(char)))
  103. #define BIT_POS_TO_BYTE_POS(bit_pos)      ((size_t)((bit_pos) >> 3))
  104. #define BIT_POS_TO_BYTE_BIT_POS(bit_pos)  ((bit_pos) & 0x7)
  105. #define GET_BIT(byte_array,bit_pos)       ((unsigned int)(((byte_array)[BIT_POS_TO_BYTE_POS(bit_pos)] >> BIT_POS_TO_BYTE_BIT_POS(bit_pos)) & 0x01))
  106. #define SET_BIT_ON(byte_array,bit_pos)    ((unsigned int)((byte_array)[BIT_POS_TO_BYTE_POS(bit_pos)] |= (0x01 << BIT_POS_TO_BYTE_BIT_POS(bit_pos))))
  107.  
  108. /*
  109.   入力の列の値が整列された列に全て含まれているかﾁｪｯｸ（当然、値は重複していることがある）
  110.   NULL：ﾁｪｯｸOK
  111.   NULL以外：入力された列のﾍﾟｹの要素のｱﾄﾞﾚｽ
  112.  */
  113.  
  114. aho_type_t const* aho_check_seq2(aho_type_t const* au_random_data, aho_type_t const* au_sorted_data, size_t u_n) {
  115.  
  116. 	aho_type_t const* cu_random_data = au_random_data;
  117. 	aho_type_t const* cu_end_of_random_data = au_random_data + u_n;
  118. 	aho_type_t const* cu_sorted_data;
  119. 	aho_type_t const* cu_end_of_sorted_data = au_sorted_data + u_n;
  120. 	size_t u_sorted_data_index;
  121. 	unsigned char* au_byte_array;
  122. 	size_t u_byte_size;
  123.  
  124. 	if (u_n == 0) {
  125. 		return NULL;
  126. 	}
  127.  
  128. 	u_byte_size = BITS_TO_BYTES(u_n);
  129. 	au_byte_array = malloc(u_byte_size);
  130. 	memset(au_byte_array, 0, u_byte_size * sizeof(unsigned char));
  131.  
  132. 	for (; cu_random_data < cu_end_of_random_data; ++cu_random_data) {
  133.  
  134. 		cu_sorted_data = aho_bsearch_upper_bound_p(au_sorted_data, cu_end_of_sorted_data, *cu_random_data);
  135. 		if (cu_sorted_data == NULL) {
  136. 			fprintf(stderr, "【診断結果】：入力の列(=[%zu])の値(=%u)がｿｰﾄされた列にありません(1)\n", (size_t)(cu_random_data - au_random_data), *cu_random_data);
  137. 			free(au_byte_array);
  138. 			return cu_random_data; // ｿｰﾄされた列に値がないからﾍﾟｹ
  139. 		}
  140.  
  141. 		/*
  142. 		 ﾁｪｯｸ済の要素かﾁｪｯｸし、ﾁｪｯｸ済でない要素を特定しﾁｪｯｸ済にする
  143. 		*/
  144.  
  145. 		u_sorted_data_index = cu_sorted_data - au_sorted_data;
  146.  
  147. 		if (!GET_BIT(au_byte_array, u_sorted_data_index)) {
  148. 			SET_BIT_ON(au_byte_array, u_sorted_data_index); // ﾁｪｯｸ済にする
  149. 			continue;
  150. 		}
  151.  
  152. 		++cu_sorted_data;
  153. 		++u_sorted_data_index;
  154.  
  155. 		for (; cu_sorted_data < cu_end_of_sorted_data; ++u_sorted_data_index, ++cu_sorted_data) {
  156.  
  157. 			if (*cu_sorted_data != *cu_random_data) {
  158. 				fprintf(stderr, "【診断結果】：入力の列(=[%zu])の値(=%u)がｿｰﾄされた列にありません(2)\n", (size_t)(cu_random_data - au_random_data), *cu_random_data);
  159. 				free(au_byte_array);
  160. 				return cu_random_data; // 重複値の余分がもうないからﾍﾟｹ
  161. 			}
  162.  
  163. 			if (!GET_BIT(au_byte_array, u_sorted_data_index)) {
  164. 				SET_BIT_ON(au_byte_array, u_sorted_data_index); // ﾁｪｯｸ済にする
  165. 				break;
  166. 			}
  167. 		}
  168. 	}
  169.  
  170. 	free(au_byte_array);
  171. 	return NULL;
  172. }
  173.  
  174. double aho_sec_count(void) {
  175. 	struct timeval tv;
  176. 	gettimeofday(&tv, NULL);
  177. 	return (double)tv.tv_sec + ((double)tv.tv_usec / 1000000.0);
  178. }
  179.  
  180. int aho_qcomp(const void *l, const void *r) {
  181. 	return *(aho_type_t*)l > *(aho_type_t*)r ? 1 : (*(aho_type_t*)l < *(aho_type_t*)r ? -1 : 0);
  182. }
  183.  
  184. int main(int argc, char **argv) {
  185.  
  186. 	size_t u_n;
  187. 	aho_type_t* au_data;
  188. 	aho_type_t* au_sort;
  189. 	aho_type_t* au_sort2;
  190. 	aho_type_t* au_qsort;
  191. 	double rs;
  192. 	double re;
  193. 	clock_t us;
  194. 	clock_t ue;
  195.  
  196. 	for (size_t i = 0; i < 17; ++i) {
  197.  
  198. 		u_n = (size_t)0x1 << i;
  199.  
  200. 		au_data = aho_malloc_random_data(u_n);
  201. 		au_sort = aho_malloc_clone_data(au_data, u_n);
  202. 		au_sort2 = aho_malloc_clone_data(au_data, u_n);
  203. 		au_qsort = aho_malloc_clone_data(au_data, u_n);
  204.  
  205. 		fprintf(stdout, "sort,%zu", u_n);
  206. 		rs = aho_sec_count();
  207. 		us = clock();
  208. 		insersion_sort(au_sort, u_n);
  209. 		ue = clock();
  210. 		re = aho_sec_count();
  211. 		fprintf(stdout, ",%.06lf,%.06lf,%.06lf,%.06lf\n", re - rs, (double)(ue - us) / CLOCKS_PER_SEC, (re - rs) / u_n * 100000, (double)(ue - us) / CLOCKS_PER_SEC / u_n * 100000);
  212.  
  213. 		fprintf(stdout, "diag,%zu", u_n);
  214. 		rs = aho_sec_count();
  215. 		us = clock();
  216. 		if (aho_check_seq1(au_sort, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ1\n"); free(au_data); free(au_sort); free(au_sort2); free(au_qsort); return 1; }
  217. 		if (aho_check_seq2(au_data, au_sort, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ2\n"); free(au_data); free(au_sort); free(au_sort2); free(au_qsort); return 1; }
  218. 		ue = clock();
  219. 		re = aho_sec_count();
  220. 		fprintf(stdout, ",%.06lf,%.06lf,%.06lf,%.06lf\n", re - rs, (double)(ue - us) / CLOCKS_PER_SEC, (re - rs) / u_n * 100000, (double)(ue - us) / CLOCKS_PER_SEC / u_n * 100000);
  221.  
  222. 		fprintf(stdout, "sort2,%zu", u_n);
  223. 		rs = aho_sec_count();
  224. 		us = clock();
  225. 		insersion_sort2(au_sort2, u_n);
  226. 		ue = clock();
  227. 		re = aho_sec_count();
  228. 		fprintf(stdout, ",%.06lf,%.06lf,%.06lf,%.06lf\n", re - rs, (double)(ue - us) / CLOCKS_PER_SEC, (re - rs) / u_n * 100000, (double)(ue - us) / CLOCKS_PER_SEC / u_n * 100000);
  229.  
  230. 		fprintf(stdout, "diag,%zu", u_n);
  231. 		rs = aho_sec_count();
  232. 		us = clock();
  233. 		if (aho_check_seq1(au_sort2, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ1\n"); free(au_data); free(au_sort); free(au_sort2); free(au_qsort); return 1; }
  234. 		if (aho_check_seq2(au_data, au_sort2, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ2\n"); free(au_data); free(au_sort); free(au_sort2); free(au_qsort); return 1; }
  235. 		ue = clock();
  236. 		re = aho_sec_count();
  237. 		fprintf(stdout, ",%.06lf,%.06lf,%.06lf,%.06lf\n", re - rs, (double)(ue - us) / CLOCKS_PER_SEC, (re - rs) / u_n * 100000, (double)(ue - us) / CLOCKS_PER_SEC / u_n * 100000);
  238.  
  239. 		fprintf(stdout, "qsort,%zu", u_n);
  240. 		rs = aho_sec_count();
  241. 		us = clock();
  242. 		qsort(au_qsort, u_n, sizeof(aho_type_t), aho_qcomp);
  243. 		ue = clock();
  244. 		re = aho_sec_count();
  245. 		fprintf(stdout, ",%.06lf,%.06lf,%.06lf,%.06lf\n", re - rs, (double)(ue - us) / CLOCKS_PER_SEC, (re - rs) / u_n * 100000, (double)(ue - us) / CLOCKS_PER_SEC / u_n * 100000);
  246.  
  247. 		fprintf(stdout, "diag,%zu", u_n);
  248. 		rs = aho_sec_count();
  249. 		us = clock();
  250. 		if (aho_check_seq1(au_qsort, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ1\n");; free(au_data); free(au_sort); free(au_sort2); free(au_qsort); return 1; }
  251. 		if (aho_check_seq2(au_data, au_qsort, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ2\n"); free(au_data); free(au_sort); free(au_sort2); free(au_qsort); return 1; }
  252. 		ue = clock();
  253. 		re = aho_sec_count();
  254. 		fprintf(stdout, ",%.06lf,%.06lf,%.06lf,%.06lf\n", re - rs, (double)(ue - us) / CLOCKS_PER_SEC, (re - rs) / u_n * 100000, (double)(ue - us) / CLOCKS_PER_SEC / u_n * 100000);
  255.  
  256. 		free(au_data);
  257. 		free(au_sort);
  258. 		free(au_sort2);
  259. 		free(au_qsort);
  260. 	}
  261.  
  262. 	fprintf(stderr, "ｵｹｰ\n");
  263. 	return 0;
  264. }
  265.  
  266. void insersion_sort(unsigned array[], unsigned length)
  267. {
  268. 	register unsigned *start = &array[0];
  269. 	register unsigned *sorted = start;
  270. 	register unsigned *end = &array[length - 1];
  271.  
  272. 	while (sorted < end) {
  273. 		register unsigned *crnt = sorted + 1;
  274. 		while (crnt > start && *crnt < *(crnt - 1)) {
  275. 			swap(crnt, crnt - 1);
  276. 			crnt--;
  277. 		}
  278. 		sorted++;
  279. 	}
  280. }
  281.  
  282. void insersion_sort2(aho_type_t* au_A, size_t n_A_length) {
  283.  
  284. 	/*
  285. 	①　i ← 1
  286. 	①　while i < length(A)
  287. 	②　　x ← A[i]
  288. 	③　　j ← i - 1
  289. 	④　　while j >= 0 and A[j] > x
  290. 	⑤　　　A[j+1] ← A[j]
  291. 	④　　　j ← j - 1
  292. 	⑥　　end while
  293. 	⑦　　A[j+1] ← x
  294. 	①　　i ← i + 1
  295. 	①　end while
  296. 	*/
  297.  
  298. 	const aho_type_t const* cu_end_of_data = au_A + n_A_length;
  299.  
  300. 	for (aho_type_t* au_i = au_A + 1; au_i < cu_end_of_data; ++au_i) { // ①
  301. 		aho_type_t u_x = *au_i; // ②
  302. 		aho_type_t* au_j = au_i - 1; // ③
  303. 		for ( ; au_j >= au_A && *au_j >= u_x; --au_j) { // ④
  304. 			*(au_j + 1) = *(au_j); // ⑤
  305. 		} // ⑥
  306. 		*(au_j + 1) = u_x; // ⑦
  307. 	}
  308. }
  309.  
Success #stdin #stdout #stderr 1.82s 9432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
sort,1,0.000002,0.000000,0.214577,0.000000
diag,1,0.000002,0.000001,0.214577,0.100000
sort2,1,0.000001,0.000000,0.095367,0.000000
diag,1,0.000000,0.000000,0.000000,0.000000
qsort,1,0.000001,0.000000,0.095367,0.000000
diag,1,0.000000,0.000000,0.000000,0.000000
sort,2,0.000001,0.000000,0.047684,0.000000
diag,2,0.000000,0.000001,0.000000,0.050000
sort2,2,0.000000,0.000000,0.000000,0.000000
diag,2,0.000000,0.000000,0.000000,0.000000
qsort,2,0.000000,0.000000,0.000000,0.000000
diag,2,0.000001,0.000000,0.059605,0.000000
sort,4,0.000000,0.000001,0.000000,0.025000
diag,4,0.000000,0.000000,0.000000,0.000000
sort2,4,0.000000,0.000000,0.000000,0.000000
diag,4,0.000000,0.000000,0.000000,0.000000
qsort,4,0.000001,0.000000,0.023842,0.000000
diag,4,0.000001,0.000000,0.023842,0.000000
sort,8,0.000000,0.000000,0.000000,0.000000
diag,8,0.000000,0.000000,0.000000,0.000000
sort2,8,0.000000,0.000000,0.000000,0.000000
diag,8,0.000001,0.000000,0.011921,0.000000
qsort,8,0.000001,0.000001,0.011921,0.012500
diag,8,0.000000,0.000000,0.000000,0.000000
sort,16,0.000001,0.000001,0.007451,0.006250
diag,16,0.000001,0.000001,0.005960,0.006250
sort2,16,0.000000,0.000000,0.000000,0.000000
diag,16,0.000001,0.000000,0.007451,0.000000
qsort,16,0.000001,0.000001,0.005960,0.006250
diag,16,0.000001,0.000000,0.005960,0.000000
sort,32,0.000001,0.000000,0.003725,0.000000
diag,32,0.000002,0.000001,0.005960,0.003125
sort2,32,0.000000,0.000001,0.000000,0.003125
diag,32,0.000001,0.000001,0.003725,0.003125
qsort,32,0.000001,0.000001,0.002980,0.003125
diag,32,0.000001,0.000001,0.002980,0.003125
sort,64,0.000002,0.000002,0.002980,0.003125
diag,64,0.000003,0.000003,0.004843,0.004687
sort2,64,0.000001,0.000001,0.001490,0.001562
diag,64,0.000002,0.000002,0.003353,0.003125
qsort,64,0.000003,0.000003,0.004843,0.004687
diag,64,0.000001,0.000001,0.001490,0.001562
sort,128,0.000004,0.000004,0.003166,0.003125
diag,128,0.000012,0.000007,0.009499,0.005469
sort2,128,0.000004,0.000004,0.003166,0.003125
diag,128,0.000004,0.000003,0.003166,0.002344
qsort,128,0.000006,0.000007,0.004657,0.005469
diag,128,0.000003,0.000003,0.002421,0.002344
sort,256,0.000014,0.000013,0.005495,0.005078
diag,256,0.000011,0.000011,0.004284,0.004297
sort2,256,0.000012,0.000012,0.004657,0.004687
diag,256,0.000009,0.000009,0.003539,0.003516
qsort,256,0.000018,0.000018,0.007078,0.007031
diag,256,0.000009,0.000009,0.003539,0.003516
sort,512,0.000050,0.000050,0.009779,0.009766
diag,512,0.000025,0.000024,0.004889,0.004687
sort2,512,0.000043,0.000043,0.008382,0.008398
diag,512,0.000022,0.000022,0.004331,0.004297
qsort,512,0.000031,0.000031,0.006054,0.006055
diag,512,0.000022,0.000022,0.004284,0.004297
sort,1024,0.000197,0.000197,0.019232,0.019238
diag,1024,0.000052,0.000052,0.005076,0.005078
sort2,1024,0.000157,0.000157,0.015320,0.015332
diag,1024,0.000050,0.000049,0.004866,0.004785
qsort,1024,0.000066,0.000066,0.006449,0.006445
diag,1024,0.000049,0.000049,0.004796,0.004785
sort,2048,0.000738,0.000737,0.036042,0.035986
diag,2048,0.000109,0.000109,0.005320,0.005322
sort2,2048,0.000573,0.000572,0.027986,0.027930
diag,2048,0.000128,0.000128,0.006252,0.006250
qsort,2048,0.000146,0.000146,0.007136,0.007129
diag,2048,0.000106,0.000106,0.005169,0.005176
sort,4096,0.002955,0.002954,0.072143,0.072119
diag,4096,0.000234,0.000233,0.005710,0.005688
sort2,4096,0.002273,0.002273,0.055495,0.055493
diag,4096,0.000235,0.000233,0.005739,0.005688
qsort,4096,0.000312,0.000312,0.007619,0.007617
diag,4096,0.000230,0.000230,0.005617,0.005615
sort,8192,0.011985,0.011985,0.146299,0.146301
diag,8192,0.000503,0.000501,0.006141,0.006116
sort2,8192,0.009056,0.009056,0.110545,0.110547
diag,8192,0.000501,0.000502,0.006118,0.006128
qsort,8192,0.000677,0.000675,0.008263,0.008240
diag,8192,0.000500,0.000501,0.006103,0.006116
sort,16384,0.048032,0.048037,0.293164,0.293195
diag,16384,0.001131,0.001130,0.006903,0.006897
sort2,16384,0.036061,0.036067,0.220099,0.220135
diag,16384,0.001150,0.001150,0.007020,0.007019
qsort,16384,0.001447,0.001446,0.008832,0.008826
diag,16384,0.001123,0.001123,0.006854,0.006854
sort,32768,0.190785,0.190680,0.582230,0.581909
diag,32768,0.002548,0.002541,0.007776,0.007755
sort2,32768,0.144712,0.144226,0.441626,0.440143
diag,32768,0.002509,0.002500,0.007656,0.007629
qsort,32768,0.003135,0.003123,0.009567,0.009531
diag,32768,0.002516,0.002504,0.007678,0.007642
sort,65536,0.765225,0.764950,1.167641,1.167221
diag,65536,0.005509,0.005508,0.008406,0.008405
sort2,65536,0.568910,0.568988,0.868088,0.868207
diag,65536,0.005519,0.005518,0.008421,0.008420
qsort,65536,0.006601,0.006599,0.010072,0.010069
diag,65536,0.005501,0.005500,0.008394,0.008392
stderr
copy 
ｵｹｰ
https://ideone.com/sylJTW
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!