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 < 18; ++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_qsort);
  259. 	}
  260.  
  261. 	fprintf(stderr, "ｵｹｰ\n");
  262. 	return 0;
  263. }
  264.  
  265. void insersion_sort(unsigned array[], unsigned length)
  266. {
  267. 	register unsigned *start = &array[0];
  268. 	register unsigned *sorted = start;
  269. 	register unsigned *end = &array[length - 1];
  270.  
  271. 	while (sorted < end) {
  272. 		register unsigned *crnt = sorted + 1;
  273. 		while (crnt > start && *crnt < *(crnt - 1)) {
  274. 			swap(crnt, crnt - 1);
  275. 			crnt--;
  276. 		}
  277. 		sorted++;
  278. 	}
  279. }
  280.  
  281. void insersion_sort2(aho_type_t* au_A, size_t n_A_length) {
  282.  
  283. 	/*
  284. 	①　i ← 1
  285. 	①　while i < length(A)
  286. 	②　　x ← A[i]
  287. 	③　　j ← i - 1
  288. 	④　　while j >= 0 and A[j] > x
  289. 	⑤　　　A[j+1] ← A[j]
  290. 	④　　　j ← j - 1
  291. 	⑥　　end while
  292. 	⑦　　A[j+1] ← x
  293. 	①　　i ← i + 1
  294. 	①　end while
  295. 	*/
  296.  
  297. 	const aho_type_t const* cu_end_of_data = au_A + n_A_length;
  298. 	aho_type_t* au_j;
  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. 		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.  
Time limit exceeded #stdin #stdout 5s 12184KB
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.000000,0.000000,0.000000,0.000000
diag,1,0.000000,0.000000,0.000000,0.000000
qsort,1,0.000001,0.000001,0.095367,0.100000
diag,1,0.000000,0.000000,0.000000,0.000000
sort,2,0.000000,0.000000,0.000000,0.000000
diag,2,0.000001,0.000000,0.059605,0.000000
sort2,2,0.000001,0.000000,0.047684,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.000000,0.000000,0.000000,0.000000
sort,4,0.000000,0.000001,0.000000,0.025000
diag,4,0.000001,0.000000,0.023842,0.000000
sort2,4,0.000001,0.000000,0.023842,0.000000
diag,4,0.000001,0.000000,0.023842,0.000000
qsort,4,0.000000,0.000000,0.000000,0.000000
diag,4,0.000000,0.000000,0.000000,0.000000
sort,8,0.000000,0.000001,0.000000,0.012500
diag,8,0.000001,0.000000,0.011921,0.000000
sort2,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.000000,0.000000,0.000000
diag,16,0.000000,0.000001,0.000000,0.006250
sort2,16,0.000001,0.000000,0.005960,0.000000
diag,16,0.000000,0.000000,0.000000,0.000000
qsort,16,0.000001,0.000001,0.007451,0.006250
diag,16,0.000000,0.000000,0.000000,0.000000
sort,32,0.000001,0.000000,0.002980,0.000000
diag,32,0.000001,0.000001,0.003725,0.003125
sort2,32,0.000000,0.000001,0.000000,0.003125
diag,32,0.000001,0.000000,0.002980,0.000000
qsort,32,0.000001,0.000002,0.003725,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.000003,0.000002,0.004470,0.003125
sort2,64,0.000001,0.000001,0.001490,0.001562
diag,64,0.000002,0.000001,0.002980,0.001562
qsort,64,0.000003,0.000003,0.004470,0.004687
diag,64,0.000001,0.000001,0.001863,0.001562
sort,128,0.000004,0.000004,0.003166,0.003125
diag,128,0.000005,0.000005,0.003912,0.003906
sort2,128,0.000003,0.000004,0.002421,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.000013,0.000013,0.005122,0.005078
diag,256,0.000017,0.000013,0.006612,0.005078
sort2,256,0.000012,0.000012,0.004657,0.004687
diag,256,0.000009,0.000009,0.003539,0.003516
qsort,256,0.000016,0.000017,0.006240,0.006641
diag,256,0.000008,0.000009,0.003073,0.003516
sort,512,0.000049,0.000048,0.009593,0.009375
diag,512,0.000023,0.000024,0.004470,0.004687
sort2,512,0.000042,0.000041,0.008196,0.008008
diag,512,0.000021,0.000022,0.004098,0.004297
qsort,512,0.000030,0.000029,0.005867,0.005664
diag,512,0.000021,0.000021,0.004098,0.004102
sort,1024,0.000192,0.000192,0.018743,0.018750
diag,1024,0.000050,0.000050,0.004866,0.004883
sort2,1024,0.000153,0.000154,0.014948,0.015039
diag,1024,0.000048,0.000047,0.004703,0.004590
qsort,1024,0.000065,0.000064,0.006333,0.006250
diag,1024,0.000047,0.000046,0.004587,0.004492
sort,2048,0.000719,0.000717,0.035111,0.035010
diag,2048,0.000106,0.000106,0.005180,0.005176
sort2,2048,0.000559,0.000557,0.027299,0.027197
diag,2048,0.000105,0.000104,0.005122,0.005078
qsort,2048,0.000144,0.000145,0.007031,0.007080
diag,2048,0.000104,0.000104,0.005076,0.005078
sort,4096,0.002885,0.002884,0.070437,0.070410
diag,4096,0.000226,0.000226,0.005518,0.005518
sort2,4096,0.002194,0.002195,0.053563,0.053589
diag,4096,0.000224,0.000224,0.005466,0.005469
qsort,4096,0.000307,0.000305,0.007497,0.007446
diag,4096,0.000223,0.000223,0.005448,0.005444
sort,8192,0.011672,0.011672,0.142481,0.142480
diag,8192,0.000484,0.000484,0.005908,0.005908
sort2,8192,0.008946,0.008941,0.109203,0.109143
diag,8192,0.000481,0.000482,0.005873,0.005884
qsort,8192,0.000686,0.000684,0.008373,0.008350
diag,8192,0.000476,0.000477,0.005809,0.005823
sort,16384,0.046939,0.046934,0.286494,0.286462
diag,16384,0.001094,0.001094,0.006678,0.006677
sort2,16384,0.035129,0.035129,0.214411,0.214410
diag,16384,0.001086,0.001086,0.006628,0.006628
qsort,16384,0.001402,0.001401,0.008558,0.008551
diag,16384,0.001084,0.001084,0.006617,0.006616
sort,32768,0.187773,0.187768,0.573038,0.573022
https://ideone.com/g3SF36
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!