저도 질문 / 건의 (코드 수행시간 관련.. )

  • yoons
    yoons

    안녕하세요.

    얼마전에 여차저차 해서 여기 알고 들어와서 틈틈히 공부 하고 있습니다.
    좋은 곳 마련해주셔서 이렇게 운영해주시는 분들께 감사감사~ ^^

    다름이 아니라 지금까지는 성능을 그리 고민하지 않고, (그렇다고 쓸데없는 중첩 등을 사용하거나 하진 않았..;;;; )
    그냥 솔루션을 만드는 위주로 프로그램을 짜다보니 생각보다 "시간제한" 이라는 것이 힘들더군요..;;;

    나름 linux server 에서 컴파일과, 파일 입력을 이용해서 자동화된 테스트 방법(??) 을 구축하여 제 프로그램의 수행 속도를 측정 해보았는데, 여기서 1000 ms 으로 시간초과 된 프로그램들이 200ms 안에 핑핑 돌아가는 충격적인 결과가...!! ㅠㅠ
    (물론.. 제가 돌린 서버가..;; 컴파일용 리눅서 서버라는 것은;;;
    cpu 가 많이 붙어 있긴 하지만..;;;
    그게 차이가 많이 나려나요..;;; )

    그래서 질문 / 건의 를 좀 드립니다.

    먼저 건의 하는 내용은 "시간초과" 인 경우 자신의 수행 시간을 알 수 있으면 좋겠습니다.

    • 얼마나 시간적 개선을 해야 하는지,
    • 자신의 코드가 얼마나 개선이 되었는지 를 알 수 있다면 많은 도움이 될 것 같습니다.

    질문은..

    • 각자 코드의 속도를 늘리는 방법에 어떤 것을 쓰시는지..
    • 각자 어떤 방법으로 자신의 compile 환경에서 속도 측정을 하는지.. 입니다. 회사에서 간간히 할 때는 linux 환경에서 아래 code 를 이용해서 합니다만, 집에 windows PC 나 MAC (xcode) 에서는 어찌 측정할 지 모르겠네요. 
    .... (includes)
#include <sys/time.h>

using namespace std;
struct timeval start, end;

int main()
{
    gettimeofday(&start, NULL);

............. (codes here. ) 

    gettimeofday(&end, NULL);
    cout << "time consumption : " << (end.tv_sec-start.tv_sec)*1000 + (end.tv_usec-start.tv_usec)  << "ms" << endl;
    return 0;
}

    tutorial 을 읽어보고
    cin 을 scanf 로 바꿨다가 되려 20ms 정도 늘어난 결과가 나오더라고요..;; ㄷㄷㄷ
    (제 시간측정 기준;; )

    많은 분들의 도움 부탁 드립니다. ^^


    11년 전
12개의 댓글이 있습니다.
  • Being
    Being

    시간초과일때 grace time을 주는 온라인 채점 시스템에 대해서는 일단 저는 들어본 적이 없습니다. 사실 시간 초과라는 것은 그야말로 얼마나 더 걸릴 지 모르는 프로그램들이 많기 때문이기도 하고, "실제 대회 환경"에서는 그런 것을 고려하지 않기 때문이기도 합니다 (대회에선 틀린 것은 틀린 것이니까요). 오히려 저는 수행 시간이 부가적인 재미 요소라고 생각하고 있습니다. 수행 시간이 빠른 코드도 의미 있지만, 문제를 해결하는 똑같은 코드라면 수행 시간이 빠른 편이 아니라 프로그래머의 노동력이 적게 든(문제를 푸는데 더 적게 시간이 걸린) 쪽이 보통은 더 바람직하다고 생각합니다.

    그리고 리눅스 환경이시라면 위에서와 같이 복잡하게 하실 것 없고 time(1)을 사용하시면 간단하게 시간을 측정하실 수 있을 것 같습니다. 저희가 사용하는 채점 환경이 별로 좋지는 않아서 로컬에서 돌리시는 것과 차이가 클 수 있고요, 실제 테스트 데이터가 훨씬 커서 그럴 수도 있습니다 :) cin과 scanf의 경우 언뜻 이해가 되지 않는 케이스인데 구체적인 예시를 올려 주시면 도움이 될 것 같습니다.


    11년 전 link
  • Being
    Being

    같은 알고리즘의 다른 구현에 대해 코드의 속도가 달라서 문제되는 경우는 종종 있어서 발목을 붙잡기는 하지만 흔한 문제는 아니고, 일정 수준 이상이 되기 전까지는 고민하실 일이 별로 없으실 것 같습니다. 대체로 알고리즘이 문제가 되기 마련입니다. 속도 벤치마크 역시 빌드를 어떻게 하고 수행을 어떻게 하며 테스트 데이터를 어떻게 넣느냐에 따라 전혀 다른 것이므로 보통은 큰 의미를 가지지 않습니다.


    11년 전 link
  • yoons
    yoons

    저도 완전 low level 에서 성능을 최대로 해야 하는 경우가 아니면 가독성, 재활용성, 유지보수가 좋은 코드가 실행시간을 위해서 나머지를 희생한(??) 것 보다는 더 좋다고 생각 합니다.

    어쩌피 코드 끌어안고 죽을 건 아니잖아요. ㅎ
    (학교나 회사서도 내 코드 다른 사람이 봐야 하는데.. )

    제가 로컬에서 돌렸을 땐 돌아가던 코든데 여기서 시간 초과라고 뜨는건 음.... 모르겠네요..
    일단 제껴야 하나봐요 ㅠㅠ


    11년 전 link
  • JongMan
    JongMan

    채점 데이터와 상관없이 수행 시간이 일정한 코드인가요? 저희 서버가 linode 512 서버 하나라 느릴 가능성은 사실 충분합니다만 올려주시면 확인해 보겠습니다.

    그리고 시간 초과시에는 해당 프로그램을 계속 돌리지 않고 죽이게 됩니다. 끝까지 돌려보고 "시간 제한은 몇초인데 이건 몇초에요"알려드릴 수 있으면 좋겠지만, 해당 프로그램이 종료하지 않을 수도 있고 서버 자원은 제한되어 있기 때문이죠. ^^;


    11년 전 link
  • yoons
    yoons

    저도 사실 로컬 컴파일 / 테스트를 다 해보고 올리기 때문에
    시간초과로 못 푼 문제들이 그런 케이스 들이지요. ㅎㅎ

    서버의 채점이 매 분 정도의 밀도까지는 아닌 것 같아서 문제의 시간제한 보다 좀 더 여유있게 돌리고 하는줄로 생각을 했는데,
    제한시간만 돌리고 kill 한다면 초과시 확인할 길이 없겠네요. ㅎㅎ

    다른 분들도 다 푼 문제인데 제꺼만 느리다면 뭔가 고칠 부분이 있는 거겠죠. ㅎㅎ (worst case target 에서도 잘 돌아가야죠. ㅎㅎ )
    그런데 좀 더 빠르게 할 수 있을 팁도 좀 댓글로 올라오길 기대 했는데..
    아님 helloworld 문제를 이용해서라도 속도가 얼마나 차이 나는지 분석 좀 해야겠네요 ㅎㅎ


    11년 전 link
  • hyunhwan
    hyunhwan

    여담이지만, xcode 상에서는 어차피 *nix 체제니깐 저 코드를 동일하게 사용하면 되지 않을까 싶고, 저 같은경우 windows환경에서는 windows.h 헤더안에 포함되어있는 GetTickCount()를 사용하여 시간을 잽니다.


    11년 전 link
  • hyunhwan
    hyunhwan

    그리고 yoons님께서 이야기 하신 "좀 더 빠르게 할 수 있을 팁"이라는 것은 정말로 경우에 따라서 다르기 때문에 "간단히 이것만 지키면 시간초과는 더이상 만나지 않아요!" 라고 답변을 하기는 어렵다 생각합니다. 그런 쪽으로 도움을 얻고자 하시면 작성하신 코드를 질문 게시판에다가 올리시는 것을 추천합니다. 그리고 답변해주시는 분들이 조금 더 코드를 이해하기 쉽도록 해법에 대한 첨부 설명을 달아주시는것도 필요할꺼 같고요.


    11년 전 link
  • hyunhwan
    hyunhwan

    또한 수행 시간의 경우에는 컴파일 옵션에 따라서도 차이가 날 가능성도 큽니다. 아마 알고스팟 같은 경우에는 -O2같은 옵션을 사용하지 않을까 싶긴합니다만, 그리고 20ms 정도의 속도는 시간을 재는 타이머의 오차로인해서 차이가 날 가능성도 큽니다. 역으로 scanf로 인해 변함이 없거나, 20ms 더 빨라질 수도 있는 것이지요.


    11년 전 link
  • JongMan
    JongMan

    혹시 시간초과가 나는 문제가 KOOGLE이시라면, 알고리즘이 잘못되었네요. 문제를 잘못 이해하신 것 같습니다. 왜 시간 초과가 나는지 확인하시려면, a 1000글자로 구성된 문자열을 한번 입력해 보세요.


    11년 전 link
  • yoons
    yoons

    @ LIBe
    시간 초과에 대한 tip 은 조금의 시간의 save 로 문제를 통과하기 위한 tip 보다는 general 하게 일반적 programming 에서 사용될 수 있는 tip 에 대한 고민이랍니다. ^^

    @ JongMan
    시간 초과가 걸리는 문제가 그 문제가 맞긴 한데,
    power 를 구하는 것을 좀 다르게 생각해서 가수 * 10^ 지수 형태로 보고, 지수 * 10 + 가수 형태를 이용하여 비교를 하는 잔꾀 아닌 잔꾀 (??) 를 부려보려고 한건데,
    우선 원래 알고리즘 부터 제대로 검증을 먼저 해봐야겠네요..;;
    알고리즘을 좀 다르게 짜보려 했던게 되려 worst case 에서 독이 되지 않았을까 하는 생각이 바로 들긴 하네요...
    (생각해보면 득도 없는 결과가 나온거 같은데, 왜 저 짓을 했는지.. ㅎ )
    조언 감사합니다. ^^


    11년 전 link
  • ILyoan
    ILyoan

    @yoons 안녕하세요

    저 같은 경우는 알고리즘 문제를 푸는데 있어서 벤치마크를 하지 않습니다 (물론 프로덕트를 개발하거나 최적화 문제를 푸는 경우엔 벤치마크를 통해 속도 개선을 하려고 노력 합니다.)
    이유인 즉슨 알고리즘 문제로 출제된 문제는 대부분 출제자가 의도한 접근 방법 혹은 그와 동등하거나 더 좋은 해결법을 이용하여 구현한 코드의 경우 채점 환경에서 넉넉하게 실행되도록 실행시간을 설정하여 놓기 때문입니다. (출제자는 관대합니다)

    따라서 채점 서버에서 TLE가 발생한 경우 실행시간을 조금 줄여 보려고 노력하기 보다,
    1. Worst Case 인풋에 대해 제한 시간내에 실행될 것인가?
    2. 알고리즘에 문제가 있어서 얘기치 않게 루프를 더 많이 실행하거나 무한루프에 빠지지는 않는가?
    를 살펴봅니다.

    저 같은 경우 제가 생각한 알고리즘이 Worst Case 입력에 대해 프로그램이 루프 이터레이션 횟수가 1초당 천만회가 넘어가면(루프 내부가 너무 간단한 경우에도 최대 1억) 더 좋은 알고리즘을 생각해 봅니다.

    그래서 결론은.. yoons 님께서도 여기에서 알고리즘 문제를 푸실때에는 (대부분의 문제에서) TLE를 만났을 때, 세부적인 최적화를 통해 실행시간을 줄여보려는 노력보단 제출하신 알고리즘이 맞는지 확인하고 더 좋은 알고리즘을 찾아보는것이 도움이 될 것 같습니다.

    제출하신 Koogle 문제에서 문제가 되는 부분은 JongMan님이 지적해 주셨는데 더 자세히 말씀드리면 2.6^1000을 double에 담을 수가 없기 때문에 inf로 표현되고 다음 루프를 빠져나올 수 없습니다.


    11년 전 link
  • yoons
    yoons

    코드의 위치만 약간 재조합 하니 합격이 되네요...
    도움 주신 분들 감사합니다. ^^

    boundary 부분에 대한 test 를 열심히 해야 한다는...
    SE의 test 방법 들이 막 생각이 나네요..;;;
    부족한 제가 부끄럽습니다. ㅎ


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.