April 6, 2016

C/C++ vs. Java

요즘 본의 아니게 알고리즘 공부를 좀 하면서 깨달은 바에 대해 몇 개 적어본다.

1) Java의 System.in/out 은 굉장히 느리다. 얼마나 느리냐고? 다음은 10,000,000 정수를 읽는데 걸리는 수행시간이다:

Input MethodTime (sec)
C scanf("%d", &arg)3.78
Scanner.parseInt()29.52
BufferedReader + inline Integer.parseInt2.89
BufferedReader + Reader.nextInt method3.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