정렬 속도 비교

2018년 2월 16일
baekjoon
댓글 (8개)
정렬

여러가지 언어와 정렬 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다.

방법: N (= 10,000,000)개의 정수를 입력받은 다음, 오름차순으로 정렬하는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김

입력 파일: https://github.com/Startlink/boj-sort-test

더 읽기 댓글 쓰기

순위	언어	출력 방법	평균 (초)
1	C11	`fwrite`	0.4423
2	C++17	`ios_base::sync_with_stdio(false); cout << i << '\n';`	0.827
3	C++17	`ios_base::sync_with_stdio(false); cout.tie(NULL); cout << i << '\n';`	0.8272
4	C++17	`printf("%d\n",i);`	0.8614
5	C11	`printf("%d\n",i);`	0.9118
6	C++17	`cout << i << '\n';`	0.9229
7	Java	`BufferedWriter, bf.write(i + "\n");`	0.9581
8	PyPy	`for i in xrange(1,n+1): sys.stdout.write(str(i)+'\n')`	0.9847
9	C++17	`s += to_string(i) + '\n';를 이용해 문자열 하나로 만든 다음, 마지막에 cout << s << '\n';`	1.1507
10	Java	`StringBuilder를 이용해 문자열 하나로 만든 다음, System.out.println(sb);`	1.1881
11	Java	`BufferedWriter, bf.write(Integer.toString(i)); bf.newLine();`	1.2556
12	PyPy3	`for i in range(1,n+1): sys.stdout.write(str(i)+'\n')`	1.3722
13	PyPy	`print '\n'.join(map(str,xrange(1,n+1)))`	1.3738
14	PyPy	`sys.stdout.write('\n'.join(map(str,xrange(1,n+1))))`	1.3772
15	PyPy	`for i in xrange(1,n+1): print i`	1.4968
16	Python 2	`print '\n'.join(map(str,xrange(1,n+1)))`	1.7621
17	Python 2	`sys.stdout.write('\n'.join(map(str,xrange(1,n+1))))`	1.7658
18	Java	`PrintWriter`	1.954
19	Python 3	`print('\n'.join(map(str,range(1,n+1))))`	2.3312
20	Python 3	`sys.stdout.write('\n'.join(map(str,range(1,n+1))))`	2.337
21	PyPy	`sys.stdout.write(''.join(str(i)+'\n' for i in xrange(1,n+1)))`	2.3935
22	PyPy	`print ''.join(str(i)+'\n' for i in xrange(1,n+1))`	2.3974
23	Python 2	`sys.stdout.write(''.join(str(i)+'\n' for i in xrange(1,n+1)))`	2.536
24	Python 2	`print ''.join(str(i)+'\n' for i in xrange(1,n+1))`	2.5372
25	PyPy3	`for i in range(1,n+1): print(i)`	3.051
26	Python 2	`for i in xrange(1,n+1): print i`	3.069
27	C# 6.0	`StreamWriter`	3.0959
28	PyPy3	`sys.stdout.write('\n'.join(map(str,range(1,n+1))))`	3.5625
29	PyPy3	`print('\n'.join(map(str,range(1,n+1))))`	3.566
30	Python 3	`sys.stdout.write(''.join(str(i)+'\n' for i in range(1,n+1)))`	3.6766
31	Python 3	`print(''.join(str(i)+'\n' for i in range(1,n+1)))`	3.6836
32	PyPy3	`print(''.join(str(i)+'\n' for i in range(1,n+1)))`	3.8326
33	PyPy3	`sys.stdout.write(''.join(str(i)+'\n' for i in range(1,n+1)))`	3.8339
34	C# 6.0	`StringBuilder를 이용해 문자열 하나로 만든 다음, Console.Write(sb);`	3.8562
35	Python 2	`for i in xrange(1,n+1): sys.stdout.write(str(i)+'\n')`	4.3475
36	Python 3	`for i in range(1,n+1): sys.stdout.write(str(i)+'\n')`	5.3699
37	Python 3	`for i in range(1,n+1): print(i)`	5.8186
38	PyPy	`for i in xrange(1,n+1): os.write(1,str(i)+'\n')`	10.4553
39	C++17	`cout << i << endl;`	11.5322
40	PyPy3	`for i in range(1,n+1): os.write(1,(str(i)+'\n').encode('utf-8'))`	12.0509
41	Python 2	`for i in xrange(1,n+1): os.write(1,str(i)+'\n')`	14.8269
42	Python 3	`for i in range(1,n+1): os.write(1,(str(i)+'\n').encode('utf-8'))`	18.2189
43	Java	`System.out.println(i);`	30.013
44	C# 6.0	`Console.WriteLine(i);`	30.1438

순위	언어	입력 방법	평균 (초)
1	C11	`mmap`	0.043
2	C11	`fread`	0.0799
3	C11	`getchar`	0.3496
4	C++17	`ios_base::sync_with_stdio(false); cin.tie(NULL);`	0.5938
5	C++17	`ios_base::sync_with_stdio(false);`	0.6348
6	Java	`BufferedReader, Integer.parseInt`	0.6585
7	C11	`scanf`	0.9206
8	PyPy	`int(sys.stdin.readline())`	0.9229
9	PyPy	`map(int,os.read(0, 100000000).split('\n'))`	1.1169
10	PyPy3	`map(int,os.read(0, 100000000).decode('utf-8').split('\n'))`	1.5408
11	PyPy	`int(raw_input())`	1.925
12	C++17	`cin.tie(NULL);`	2.059
13	C++17	`cin`	2.1742
14	C# 6.0	`int.Parse(Console.ReadLine())`	2.9635
15	Python 3	`map(int,os.read(0, 100000000).decode('utf-8').split('\n'))`	4.4033
16	Python 3	`int(sys.stdin.readline())`	4.4394
17	Java	`Scanner`	4.8448
18	Python 2	`map(int,os.read(0, 100000000).split('\n'))`	4.8553
19	Python 2	`int(sys.stdin.readline())`	5.7471
20	PyPy3	`int(sys.stdin.readline())`	6.6291
21	Python 2	`int(raw_input())`	8.9765
22	Python 3	`int(input())`	12.4443
23	PyPy3	`int(input())`	17.3772
24	Python 2	`input()`	37.7823
25	PyPy	`input()`	110.3676

BOJ 101

2018년 1월 9일
jh05013
댓글 (24개)

BOJ 질문 게시판에서 활동하면서 "이건 모두가 알아야 할 것 같다"라고 생각한 것들을 적어 보려 합니다.

BOJ 작동 원리

채점 서버에는 한 쌍 이상의 입력 파일과 출력 파일이 있습니다.코드를 제출하면 그 코드에 입력 파일에 적힌 대로 입력하고 나타나는 출력을 출력 파일과 비교합니다. 모든 입력/출력 파일에 대해 코드가 문제 없이 올바른 출력을 내야 합니다. 여기서 "올바름"이란 것은 단순히 정답과 같은 값이 아니라 같은 출력을 의미합니다. 예를 들어 45.0을 출력해야 하는데 45나 45.00을 출력하면 오답입니다.

스페셜 저지가 있는 문제에는 출력이 올바른지 검사하는 채점 코드가 따로 있습니다. 그러므로 "올바른 출력"은 여러 가지가 될 수 있고, 그 중 하나만 출력하면 됩니다. 예를 들어 10^-2 이하의 오차를 허용하는 문제라면 출력과 정답의 오차가 10^-2 이하인지 검사하는 코드가 있습니다. 그런 문제에서 정답이 45.0이라면 45나 45.00을 출력해도 정답을 받을 수 있습니다.

더 읽기 댓글 쓰기