fork(1) 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.  
  14. aho_type_t* aho_malloc_random_data(size_t u_n);
  15. aho_type_t* aho_malloc_clone_data(aho_type_t const* au_data, size_t u_n);
  16. aho_type_t const* aho_check_seq1(aho_type_t const* au_data, size_t u_n);
  17. 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);
  18.  
  19. uint32_t aho_xorshift_u32(void);
  20. int32_t aho_xorshift_i32(void);
  21. 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);
  22. double aho_sec_count(void);
  23. int aho_qcomp(const void *r, const void *l);
  24.  
  25. /*
  26.  32bit擬似乱数生成
  27.  */
  28.  
  29. static uint32_t u_seed = 2463534242;
  30.  
  31. uint32_t aho_xorshift_u32(void) {
  32. 	u_seed = u_seed ^ (u_seed << 13); u_seed = u_seed ^ (u_seed >> 17);
  33. 	return (u_seed = u_seed ^ (u_seed << 15));
  34. }
  35.  
  36. int32_t aho_xorshift_i32(void) {
  37. 	u_seed = u_seed ^ (u_seed << 13); u_seed = u_seed ^ (u_seed >> 17);
  38. 	return (u_seed = u_seed ^ (u_seed << 15));
  39. }
  40.  
  41. /*
  42.  n個の乱数列生成
  43.  */
  44.  
  45. aho_type_t* aho_malloc_random_data(size_t u_n) {
  46. 	aho_type_t* au_data = malloc(u_n * sizeof(aho_type_t));
  47. 	aho_type_t* pu_data = au_data;
  48. 	aho_type_t* pu_end_of_data = au_data + u_n;
  49. 	for ( ; pu_data < pu_end_of_data; ++pu_data) {
  50. 		*pu_data = aho_xorshift_u32();
  51. 	}
  52. 	return au_data;
  53. }
  54.  
  55. aho_type_t* aho_malloc_clone_data(aho_type_t const* au_data, size_t u_n) {
  56. 	aho_type_t* pu_data = malloc(u_n * sizeof(aho_type_t));
  57. 	memcpy(pu_data, au_data, u_n * sizeof(aho_type_t));
  58. 	return pu_data;
  59. }
  60.  
  61. /*
  62.  列が整列されているかﾁｪｯｸ
  63.   NULL：ﾁｪｯｸOK
  64.   NULL以外：整列された列のﾍﾟｹの要素のｱﾄﾞﾚｽ
  65.  */
  66.  
  67. aho_type_t const* aho_check_seq1(aho_type_t const* au_data, size_t u_n) {
  68. 	aho_type_t const* cu_data = au_data;
  69. 	aho_type_t const* cu_end_of_data = au_data + u_n - 1;
  70. 	for (; cu_data < cu_end_of_data; ++cu_data) {
  71. 		if (*cu_data > *(cu_data + 1)) {
  72. 			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));
  73. 			return cu_data + 1;
  74. 		}
  75. 	}
  76. 	return NULL;
  77. }
  78.  
  79. /*
  80.  昇順ｿｰﾄされた列から先頭の値を検索（値は重複している）
  81.  */
  82.  
  83. 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) {
  84. 	aho_type_t const* cu_data_s = au_data_s;
  85. 	aho_type_t const* cu_data_e = au_data_e;
  86. 	aho_type_t const* cu_data_m = NULL;
  87.  
  88. 	while (cu_data_s < cu_data_e) {
  89. 		cu_data_m = cu_data_s + ((cu_data_e - cu_data_s) >> 1);
  90.  
  91. 		if (*cu_data_m < value) {
  92. 			cu_data_s = cu_data_m + 1;
  93. 		} else {
  94. 			cu_data_e = cu_data_m;
  95. 		}
  96. 	}
  97.  
  98. 	return (cu_data_m != NULL && cu_data_e == cu_data_s && *cu_data_s == value) ? cu_data_s : NULL;
  99. }
  100.  
  101. #define BITS_TO_BYTES(bits)               ((size_t)(((((bits) - 1) >> 3) + 1) * sizeof(char)))
  102. #define BIT_POS_TO_BYTE_POS(bit_pos)      ((size_t)((bit_pos) >> 3))
  103. #define BIT_POS_TO_BYTE_BIT_POS(bit_pos)  ((bit_pos) & 0x7)
  104. #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))
  105. #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))))
  106.  
  107. /*
  108.   入力の列の値が整列された列に全て含まれているかﾁｪｯｸ（当然、値は重複していることがある）
  109.   NULL：ﾁｪｯｸOK
  110.   NULL以外：入力された列のﾍﾟｹの要素のｱﾄﾞﾚｽ
  111.  */
  112.  
  113. 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) {
  114.  
  115. 	aho_type_t const* cu_random_data = au_random_data;
  116. 	aho_type_t const* cu_end_of_random_data = au_random_data + u_n;
  117. 	aho_type_t const* cu_sorted_data;
  118. 	aho_type_t const* cu_end_of_sorted_data = au_sorted_data + u_n;
  119. 	size_t u_sorted_data_index;
  120. 	unsigned char* au_byte_array;
  121. 	size_t u_byte_size;
  122.  
  123. 	if (u_n == 0) {
  124. 		return NULL;
  125. 	}
  126.  
  127. 	u_byte_size = BITS_TO_BYTES(u_n);
  128. 	au_byte_array = malloc(u_byte_size);
  129. 	memset(au_byte_array, 0, u_byte_size * sizeof(unsigned char));
  130.  
  131. 	for (; cu_random_data < cu_end_of_random_data; ++cu_random_data) {
  132.  
  133. 		cu_sorted_data = aho_bsearch_upper_bound_p(au_sorted_data, cu_end_of_sorted_data, *cu_random_data);
  134. 		if (cu_sorted_data == NULL) {
  135. 			fprintf(stderr, "【診断結果】：入力の列(=[%zu])の値(=%u)がｿｰﾄされた列にありません(1)\n", (size_t)(cu_random_data - au_random_data), *cu_random_data);
  136. 			free(au_byte_array);
  137. 			return cu_random_data; // ｿｰﾄされた列に値がないからﾍﾟｹ
  138. 		}
  139.  
  140. 		/*
  141. 		 ﾁｪｯｸ済の要素かﾁｪｯｸし、ﾁｪｯｸ済でない要素を特定しﾁｪｯｸ済にする
  142. 		*/
  143.  
  144. 		u_sorted_data_index = cu_sorted_data - au_sorted_data;
  145.  
  146. 		if (!GET_BIT(au_byte_array, u_sorted_data_index)) {
  147. 			SET_BIT_ON(au_byte_array, u_sorted_data_index); // ﾁｪｯｸ済にする
  148. 			continue;
  149. 		}
  150.  
  151. 		++cu_sorted_data;
  152. 		++u_sorted_data_index;
  153.  
  154. 		for (; cu_sorted_data < cu_end_of_sorted_data; ++u_sorted_data_index, ++cu_sorted_data) {
  155.  
  156. 			if (*cu_sorted_data != *cu_random_data) {
  157. 				fprintf(stderr, "【診断結果】：入力の列(=[%zu])の値(=%u)がｿｰﾄされた列にありません(2)\n", (size_t)(cu_random_data - au_random_data), *cu_random_data);
  158. 				free(au_byte_array);
  159. 				return cu_random_data; // 重複値の余分がもうないからﾍﾟｹ
  160. 			}
  161.  
  162. 			if (!GET_BIT(au_byte_array, u_sorted_data_index)) {
  163. 				SET_BIT_ON(au_byte_array, u_sorted_data_index); // ﾁｪｯｸ済にする
  164. 				break;
  165. 			}
  166. 		}
  167. 	}
  168.  
  169. 	free(au_byte_array);
  170. 	return NULL;
  171. }
  172.  
  173. double aho_sec_count(void) {
  174. 	struct timeval tv;
  175. 	gettimeofday(&tv, NULL);
  176. 	return (double)tv.tv_sec + ((double)tv.tv_usec / 1000000.0);
  177. }
  178.  
  179. int aho_qcomp(const void *l, const void *r) {
  180. 	return *(aho_type_t*)l > *(aho_type_t*)r ? 1 : (*(aho_type_t*)l < *(aho_type_t*)r ? -1 : 0);
  181. }
  182.  
  183. int main(int argc, char **argv) {
  184.  
  185. 	size_t u_n;
  186. 	aho_type_t* au_data;
  187. 	aho_type_t* au_sort;
  188. 	aho_type_t* au_qsort;
  189. 	double rs;
  190. 	double re;
  191. 	clock_t us;
  192. 	clock_t ue;
  193.  
  194. 	argc= argc;argv= argv;
  195. 	setlocale(LC_ALL, "");
  196.  
  197. 	for (size_t i = 0; i < 18; ++i) {
  198.  
  199. 		u_n = (size_t)0x1 << i;
  200.  
  201. 		au_data = aho_malloc_random_data(u_n);
  202. 		au_sort = aho_malloc_clone_data(au_data, u_n);
  203. 		au_qsort = aho_malloc_clone_data(au_data, u_n);
  204.  
  205.  
  206. 		fprintf(stdout, "sort,%zu", u_n);
  207. 		rs = aho_sec_count();
  208. 		us = clock();
  209. 		insersion_sort(au_sort, u_n);
  210. 		ue = clock();
  211. 		re = aho_sec_count();
  212. 		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);
  213.  
  214. 		fprintf(stdout, "diag,%zu", u_n);
  215. 		rs = aho_sec_count();
  216. 		us = clock();
  217. 		if (aho_check_seq1(au_sort, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ1\n"); free(au_data); free(au_sort); free(au_qsort); return 1; }
  218. 		if (aho_check_seq2(au_data, au_sort, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ2\n"); free(au_data); free(au_sort); free(au_qsort); return 1; }
  219. 		ue = clock();
  220. 		re = aho_sec_count();
  221. 		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);
  222.  
  223.  
  224. 		fprintf(stdout, "qsort,%zu", u_n);
  225. 		rs = aho_sec_count();
  226. 		us = clock();
  227. 		qsort(au_qsort, u_n, sizeof(aho_type_t), aho_qcomp);
  228. 		ue = clock();
  229. 		re = aho_sec_count();
  230. 		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);
  231.  
  232. 		fprintf(stdout, "diag,%zu", u_n);
  233. 		rs = aho_sec_count();
  234. 		us = clock();
  235. 		if (aho_check_seq1(au_qsort, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ1\n"); free(au_data); free(au_qsort); free(au_qsort); return 1; }
  236. 		if (aho_check_seq2(au_data, au_qsort, u_n) != NULL) { fprintf(stderr, "ﾍﾟｹ2\n"); free(au_data); free(au_qsort); free(au_qsort); return 1; }
  237. 		ue = clock();
  238. 		re = aho_sec_count();
  239. 		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);
  240.  
  241. 		free(au_data);
  242. 		free(au_sort);
  243. 		free(au_qsort);
  244. 	}
  245.  
  246. 	fprintf(stderr, "ｵｹｰ\n");
  247. 	return 0;
  248. }
  249.  
  250. void insersion_sort(unsigned array[], unsigned length)
  251. {
  252. 	register unsigned *start = &array[0];
  253. 	register unsigned *sorted = start;
  254. 	register unsigned *end = &array[length - 1];
  255.  
  256. 	while (sorted < end) {
  257. 		register unsigned *crnt = sorted + 1;
  258. 		while (crnt > start && *crnt < *(crnt - 1)) {
  259. 			swap(crnt, crnt - 1);
  260. 			crnt--;
  261. 		}
  262. 		sorted++;
  263. 	}
  264. }
  265.  
Success #stdin #stdout #stderr 4.06s 11080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
sort,1,0.000002,0.000001,0.190735,0.100000
diag,1,0.000002,0.000001,0.190735,0.100000
qsort,1,0.000001,0.000001,0.095367,0.100000
diag,1,0.000000,0.000001,0.000000,0.100000
sort,2,0.000001,0.000000,0.047684,0.000000
diag,2,0.000000,0.000001,0.000000,0.050000
qsort,2,0.000001,0.000000,0.047684,0.000000
diag,2,0.000001,0.000000,0.047684,0.000000
sort,4,0.000000,0.000000,0.000000,0.000000
diag,4,0.000000,0.000001,0.000000,0.025000
qsort,4,0.000000,0.000000,0.000000,0.000000
diag,4,0.000000,0.000000,0.000000,0.000000
sort,8,0.000001,0.000000,0.011921,0.000000
diag,8,0.000001,0.000000,0.014901,0.000000
qsort,8,0.000000,0.000001,0.000000,0.012500
diag,8,0.000001,0.000000,0.011921,0.000000
sort,16,0.000000,0.000001,0.000000,0.006250
diag,16,0.000001,0.000000,0.007451,0.000000
qsort,16,0.000000,0.000001,0.000000,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
qsort,32,0.000001,0.000002,0.002980,0.006250
diag,32,0.000001,0.000000,0.002980,0.000000
sort,64,0.000002,0.000001,0.003353,0.001562
diag,64,0.000002,0.000003,0.002980,0.004687
qsort,64,0.000003,0.000003,0.004843,0.004687
diag,64,0.000002,0.000002,0.003353,0.003125
sort,128,0.000003,0.000004,0.002421,0.003125
diag,128,0.000006,0.000005,0.004657,0.003906
qsort,128,0.000007,0.000006,0.005402,0.004687
diag,128,0.000004,0.000003,0.003166,0.002344
sort,256,0.000013,0.000013,0.005122,0.005078
diag,256,0.000011,0.000011,0.004284,0.004297
qsort,256,0.000022,0.000017,0.008661,0.006641
diag,256,0.000010,0.000010,0.003912,0.003906
sort,512,0.000049,0.000049,0.009593,0.009570
diag,512,0.000023,0.000023,0.004517,0.004492
qsort,512,0.000031,0.000030,0.006054,0.005859
diag,512,0.000022,0.000023,0.004284,0.004492
sort,1024,0.000191,0.000192,0.018650,0.018750
diag,1024,0.000050,0.000051,0.004866,0.004980
qsort,1024,0.000064,0.000064,0.006240,0.006250
diag,1024,0.000049,0.000049,0.004796,0.004785
sort,2048,0.000718,0.000717,0.035053,0.035010
diag,2048,0.000107,0.000106,0.005227,0.005176
qsort,2048,0.000140,0.000140,0.006834,0.006836
diag,2048,0.000104,0.000104,0.005076,0.005078
sort,4096,0.002903,0.002903,0.070879,0.070874
diag,4096,0.000225,0.000226,0.005495,0.005518
qsort,4096,0.000303,0.000304,0.007398,0.007422
diag,4096,0.000227,0.000225,0.005541,0.005493
sort,8192,0.011710,0.011706,0.142943,0.142896
diag,8192,0.000490,0.000490,0.005981,0.005981
qsort,8192,0.000667,0.000665,0.008140,0.008118
diag,8192,0.000486,0.000486,0.005931,0.005933
sort,16384,0.048225,0.048218,0.294343,0.294299
diag,16384,0.001100,0.001099,0.006714,0.006708
qsort,16384,0.001408,0.001406,0.008594,0.008582
diag,16384,0.001141,0.001141,0.006965,0.006964
sort,32768,0.193648,0.193558,0.590966,0.590692
diag,32768,0.002456,0.002455,0.007495,0.007492
qsort,32768,0.003000,0.002998,0.009155,0.009149
diag,32768,0.002443,0.002442,0.007456,0.007452
sort,65536,0.751056,0.750842,1.146020,1.145694
diag,65536,0.005530,0.005529,0.008438,0.008437
qsort,65536,0.006428,0.006426,0.009808,0.009805
diag,65536,0.005572,0.005568,0.008502,0.008496
sort,131072,2.991084,2.989660,2.282016,2.280930
diag,131072,0.013571,0.013565,0.010354,0.010349
qsort,131072,0.013564,0.013561,0.010349,0.010346
diag,131072,0.013754,0.013751,0.010494,0.010491
stderr
copy 
ｵｹｰ
https://ideone.com/FwRQ0E
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!