파이썬 채점 방식에 대해 문의드립니다

  • vio
    vio

    메일로 문의드리려는데 메일이 안나와있어 글로 남깁니다

    https://algospot.com/judge/problem/read/FESTIVAL

    이 문제를 푸는데 Python과 C++ 두가지를 이용해 풀어보았는데요
    C++은 복잡도가 N^2일 때 150ms, N^3이여도 2000ms가 나오는 반면
    Python은 N^2일 경우에도 CPython의 경우 TLE, PyPy는 8500ms가 나왔습니다.
    조금은 그 간극이 큰 것 같아 알아보고 싶습니다.
    Python을 채점할 때 어떤 방식으로하시나요?
    실제 Input과 Output을 받아 제가 테스트해보고 싶은 욕심도 있지만
    만약 그게 불가능하시다면 정말 로직 자체의 수행시간이 저정도 걸리는지, 아니면 Python이 띄워지는 시간 등 까지 포함된 시간인지 문의드립니다


    6년 전
4개의 댓글이 있습니다.
  • JongMan
    JongMan

    파이썬은 기본적으로 루프에 대부분의 시간을 잡아먹는 코드에서는 쥐약이라고 생각하시면 됩니다 ㅜ.ㅜ 테스트를 해보고 싶으시면 랜덤 데이터를 생성해서 로컬에서 해보셔도 될 것 같네요.

    파이썬 뜨는 시간의 오버헤드도 시간 제한에 들어가긴 합니다.


    6년 전 link
  • vio
    vio

    https://gist.github.com/viobo/e4bca47b1e0243264e32

    이 입력으로 해보았습니다

    vio@~/algorithm catfestivalinput.txt| /Downloads/pypy−2.3.1−osx64 2/bin/pypyfestival.py
    357.6451612900
    0.310971975327
    vio@ /algorithm cat festival_input.txt | python festival.py
    357.6451612900
    0.82701921463

    오버헤드 등을 제외한 로직부분 수행시간만 측정했을 시 pypy는 0.310, python2.7은 0.827초가 나왔습니다.
    채점 결과와 수행시간이 다른건 input 개수의 영향인가요 오버헤드등 다른 고려사항이 끼치는 영향이 큰건가요?


    6년 전 link
  • 꿀호떡
    꿀호떡

    채점 결과와 다른 건 머신(중에서도 CPU)의 성능이 다르니까 당연한 문제가 아닌가 싶어요. C++도 한번 같은 데이터로 돌려보시고 스케일 차이를 보시면 될 것 같아요.

    저도 간단히 N^2 코드를 구현해서 올려봤는데 CPython의 경우 4583ms, PyPy의 경우 429ms 정도 나오네요. 일반적으로 C++의 상수배(?) 차이 정도 까지는 끌어올릴 수 있어요. 그 이상은 Python 구동 오버헤드 (PyPy의 경우 JIT 예열 시간까지..) 때문에 무리인 것 같지만요.

    코드를 보고 조언을 좀 드리면,

    1. 우선 range 대신 xrange를 꼭 사용하셔야 합니다. range는 (0, 1, 2, ...., N) 이라는 tuple을 명시적으로 생성한 후 iteration을 수행하고, xrange는 위치만 가지고 만들어진 generator 구문입니다. for(i=0;;) 하는 꼴의 for문에 더 가까운 셈이죠.

    2. C에서의 Array, 즉 size가 고정된 형태의 list를 생성할 때에는 미리 [0]*size 형태의 list를 생성한 후 대입하는 것이 빠릅니다. append는 가능하면 사용하지 않도록 해야 합니다.

    3. 이 문제에서 round는 굳이 필요하지 않죠. (필요하다면 출력할 때만 해주면 되는데, 사실 이 문제 조건에선 그것도 필요하지 않습니다)

    4. float 캐스팅을 위해 / 1.0 을 수행하셨는데 이것보다는 float( ) 이 성능이나 가독성이나 낫지 않나 싶습니다.

    vio님 코드에서 이 부분을 고치고 나서 https://algospot.com/judge/submission/detail/214025 을 돌려봤더니 291ms가 찍히네요.


    6년 전 link
  • vio
    vio

    조언 감사드립니다.
    xrange, 전역변수 사용 안함 등 여러가지 해본 후에도 차이가 심해 익숙하지 않은 cpp로 해야하나 걱정했는데
    말씀해주신 round함수가 굉장히 시간을 많이 잡아먹네요
    이 정도면 충분히 Python으로도 할 수 있을 것 같습니다.
    감사합니다


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