4개의 댓글이 있습니다.
-
-
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 개수의 영향인가요 오버헤드등 다른 고려사항이 끼치는 영향이 큰건가요?
9년 전 link
-
-
-
꿀호떡 -
채점 결과와 다른 건 머신(중에서도 CPU)의 성능이 다르니까 당연한 문제가 아닌가 싶어요. C++도 한번 같은 데이터로 돌려보시고 스케일 차이를 보시면 될 것 같아요.
저도 간단히 N^2 코드를 구현해서 올려봤는데 CPython의 경우 4583ms, PyPy의 경우 429ms 정도 나오네요. 일반적으로 C++의 상수배(?) 차이 정도 까지는 끌어올릴 수 있어요. 그 이상은 Python 구동 오버헤드 (PyPy의 경우 JIT 예열 시간까지..) 때문에 무리인 것 같지만요.
코드를 보고 조언을 좀 드리면,
우선 range 대신 xrange를 꼭 사용하셔야 합니다. range는 (0, 1, 2, ...., N) 이라는 tuple을 명시적으로 생성한 후 iteration을 수행하고, xrange는 위치만 가지고 만들어진 generator 구문입니다. for(i=0;;) 하는 꼴의 for문에 더 가까운 셈이죠.
C에서의 Array, 즉 size가 고정된 형태의 list를 생성할 때에는 미리 [0]*size 형태의 list를 생성한 후 대입하는 것이 빠릅니다. append는 가능하면 사용하지 않도록 해야 합니다.
이 문제에서 round는 굳이 필요하지 않죠. (필요하다면 출력할 때만 해주면 되는데, 사실 이 문제 조건에선 그것도 필요하지 않습니다)
float 캐스팅을 위해 / 1.0 을 수행하셨는데 이것보다는 float( ) 이 성능이나 가독성이나 낫지 않나 싶습니다.
vio님 코드에서 이 부분을 고치고 나서 https://algospot.com/judge/submission/detail/214025 을 돌려봤더니 291ms가 찍히네요.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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이 띄워지는 시간 등 까지 포함된 시간인지 문의드립니다
9년 전