1) Java의 System.in/out 은 굉장히 느리다. 얼마나 느리냐고? 다음은 10,000,000 정수를 읽는데 걸리는 수행시간이다:
Input Method | Time (sec) |
C scanf("%d", &arg) | 3.78 |
Scanner.parseInt() | 29.52 |
BufferedReader + inline Integer.parseInt | 2.89 |
BufferedReader + Reader.nextInt method | 3.01 |
단순히 2 ~ 3배 느린게 아니라 10배 가까이 차이가 난다. 이 때문에 BufferedReader 그리고, 출력에 있어서는 StringBuilder를 사용해야만 시간 초과를 피할 수 있다. 9935번 문자열 폭발이 대표적인데 알고리즘이 문제가 아니라 System.out.print 속도가 느려서 해결하기 쉽지 않다.
2) 최적화된 C/C++ 프로그램 속도는 빠르지만 역시나 코드는 더러워서 볼 수 가 없다 :/ 빠른게 능사가 아니란 말이다. 아래는 내 코드 (수행속도: 70 ms) 와 속도로 1위한 사람의 C++ 코드 (수행속도: 0 ms) 다. 물론 개발자 차이가 있을 수 있는데 ㅋ 일반적으로 Java나 함수형 언어에 익숙한 개발자는 대게 코드가 수식과 같고, C/C++은 무슨 연유인지 알 수 없으나 네이밍도 그렇고 코드가 대게가 지저분. 이 때문에 알고리즘 구현과 수행속도는 개발자의 평가기준이 절대 될 수 없다고 생각한다. Jeff Dean께서 그리 말씀하셨다니 나도 한마디 거들면 C++은 혐오스럽다.
한번 직접보시라:
import java.util.Scanner; public class Main { static int[] a; static int[] memo; private static int calculate(int i) { if (i == 0) memo[i] = a[i]; else memo[i] = Math.max(a[i], memo[i - 1] + a[i]); if (i == a.length - 1) { return memo[i]; } else { return Math.max(calculate(i + 1), memo[i]); } } public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); a = new int[n]; memo = new int[a.length]; for (int i = 0; i < n; i++) a[i] = sc.nextInt(); System.out.println(calculate(0)); sc.close(); } }vs.
#include#include namespace my { struct istream{}; istream cin; inline bool is_num( char c ){ return ( c >= '0' && c <= '9' ); } inline bool is_negative( char c ){ return c == '-'; } inline istream& operator>>( istream& in, int& out ) { char c; out = 0; bool neg = false; while( c = getchar() ){ if( is_negative(c) ){ neg = true; break; } if( is_num(c) ){ out += (c-'0'); break; } } while( c = getchar() ){ if( !is_num(c) ) break; out *= 10; out += (c-'0'); } if( neg ) out *= -1; return in; } inline void calc_max( int& max, int value ){ if( max < value ) max = value; } inline void calc_min( int& min, int value ){ if( min > value ) min = value; } } int main( int argc, char** argv ) { int N; my::cin >> N; int curr_max = std::numeric_limits ::min(); int curr_min = 0; int temp_min = 0; int n, accum = 0; for( int i = 0; i < N; ++i ) { my::cin >> n; accum += n; if( accum > curr_max ) { curr_max = accum; } if( accum - temp_min > curr_max - curr_min ) { curr_max = accum; curr_min = temp_min; temp_min = 0; } if( accum < temp_min ) { temp_min = accum; } } printf("%d\n", curr_max-curr_min); return 0; }
No comments:
Post a Comment