1708번 문제
23642141 (Swift)
23642165 (C++)
2075번 문제
C++ : 31448953
Swift : 31448940
2075번은 문제는 기본 입출력 함수를 사용하면 시간 초과가 나고, 빠른 입출력 함수를 사용하면 통과가 됩니다.
Swift에서 기본 입력 함수는 readLine()이고, 기본 출력 함수는 print()입니다.
두 함수는 느려서 많은 입출력이 요구되는 경우 해당 빠른 입출력 소스코드를 사용하고 있습니다. ( Fread 방식 )
백준에서 거의 모든 Swift 소스코드는 해당 빠른 입출력 소스 코드를 사용하고 있습니다.
-
11003번 문제
C++ : 31450594
Swift : 31450143 (시간 초과)
11003번 문제는 빠른 입출력을 사용해도 시간 초과가 나는 것 같습니다.
문제 | C++ | Swift | 비고 |
---|---|---|---|
1708 | 32, 2808 | 480, 82296 | |
11054 | 4, 2020 | 20, 62232 | |
10989 | 1980, 2020 | 2864, 280416 | Swift: Fast IO |
2467 | 76, 2680 | 80, 71476 | |
11048 | 264, 9832 | 376, 77976 | |
5582 | 64, 64432 | 468, 187556 | |
11049 | 52, 3864 | 144, 64212 | |
9252 | 4, 5940 | 40, 70112 | |
12015 | 180, 12072 | 232, 110484 | Swift: Fast IO |
11659 | 52, 2288 | 68, 84684 | Swift: Fast IO |
2075 | 468, 10808 | 568, 165964 | Swift: Fast IO |
11003 | 1672, 41084 | 5536, 353580 | Swift: Fast IO |
2805 | 196, 9712 | 212, 106300 | Swift: Fast IO |
13977 | 264, 33272 | 196, 114452 | Swift: Fast IO |
14003 | 296, 29876 | 492, 258916 | Swift: Fast IO |
8892 | 52, 2156 | 1044, 79164 |
현재 Swift는 추가 메모리로 512MB를 받고 있는걸로 알고 있습니다.
Swift는 빠른 입출력을 사용하기 위해 입력 데이터와 출력 데이터를 통째로 메모리에 저장해두는 방식을 사용하고 있는데
입출력 데이터가 무겁고, 메모리 제한 넉넉하지 않게 있는 경우 해결할 수 없는 문제가 됩니다.
해당 표에서는 10989번 문제가 해당됩니다.
그래서 추가 메모리 +512MB에 대해서는 현행 유지가 좋을 것 같습니다.
추가 시간은 필요하다고 느끼나, 어떤 연산이 느린지 파악하지 못한 상태입니다.
Swift는 특정 연산에 대해서 느린 것 같습니다.
확실하게 이야기할 수 있는 부분은 입출력량에 민감한 것 같습니다.
빠른 입출력에서는 입력을 한 줄의 문자열로 통째로 받아서 영문자, 공백과 개행 문자를 포함하여 한 글자씩 전부 아스키코드 배열로 변환 합니다. (O(N))
해당 표에서 11003번 문제에서는 최악의 경우 5000000개의 숫자가 들어갑니다.
그 각 숫자가 -10^9로 “-1000000000” 최악의 경우 모두 10글자씩 오므로, 10(글자) * 5000000(개 숫자) + 5000000(개의 공백) = 약 5.5 * 10^7번 연산을 해야합니다.
Swift 연산이 느리다고 가정하면 치명적인 수치라고 생각합니다.
그래서 입력에서 연산하는 시간 때문에, 실질적으로 문제를 풀기 위한 알고리즘의 제한 연산 시간이 줄어듭니다.
개인적인 의견으로는 문제를 풀면서 Go 연산 수행 시간과 많이 비교해왔는데, Go 언어보다 느렸던 경우가 많았습니다.
그래서 Go 언어의 추가 시간보다 더 많이 추가 시간을 받았으면 좋겠습니다.
1987 https://www.acmicpc.net/proble...
C++: 31090927
Swift(시간초과): 31888235
Swift(BitMask, 통과): 31888141
C++ 코드와 동일한 로직을 사용한 Swift 코드는 시간초과가 납니다.
추가로 의견을 제시합니다.
메모리 부분에서는 만약 빠른 입출력을 사용하지 않았을 때 readLine() 기본 내장 함수를 사용하게 됩니다.
readLine()은 공백 단위가 아닌 개행 문자 단위로 입력을 받아들입니다. ( = 한 줄씩 입력을 받습니다. )
표에서 14003번 문제처럼 1줄 입력이면 1줄짜리 문자열을 통째로 읽고 파싱하는 작업이 필요합니다.
1줄 입력이 긴 경우 그만큼 문자열 변수에 할당되는 메모리가 증가하므로, 빠른 입출력을 사용하지 않아도 메모리를 많이 쓰는 상황이 발생합니다.
시간 부분에서는 여러 자료를 조사해보니 Swift가 그래도 그렇게 느리지 않은 언어네요.
앞 댓글에서 Go 보다 느리다고 Go 보다는 더 많은 추가 시간을 요청했었는데, 그럴 필요는 없다는 생각이 들어 비슷하게 +2~3초 정도면 좋을 것 같습니다.
11003번 문제처럼 입출력이 과도한 경우 문제의 Swift 언어 시간 제한 조정을 하면 좋을 것 같습니다.
그 이후로 Swift 언어로 문제를 풀면서 겪었던 경험을 작성합니다.
1. Swift는 Python처럼 함수 호출이 느리며 이는 오버헤드와 관련 있는 것 같습니다.
1-1. 함수 호출이 느림
백트래킹 문제 N-Queen (9663번 문제)입니다.
재귀 함수 호출 로직으로 작성한 C++ / PyPy3 / Swift 프로그램의 연산 시간을 비교해보았습니다.
C++ : 1692ms (34750410)
PyPy3 : 5324ms (34751758)
Swift : 4564ms (34750350)
파이썬 보다는 빠른 퍼포먼스를 보여주지만, C++와 비교한다면 느린 퍼포먼스를 보여주고 있습니다.
보통 백트래킹 문제에서 재귀 함수를 사용할 경우 시간 초과를 보이는 경향이 큽니다.
그 예시로 jwonylee님이 달아주신 댓글에서 1987번 문제와 12094번, 15651번 문제등이 있습니다.
그리고 또한, 다른 알고리즘 (DP, 분할정복, DFS등)에서도 재귀 함수 사용시 느리다라는 부분을 파악할 수 있었습니다.
11066번 파일 합치기 문제입니다.
Swift (Top-Down) : 시간 초과 (35407977) [재귀 함수]
Swift (Bottom-Up) : 520ms (35408479)
1493번 박스 채우기 문제입니다.
Swift (재귀 함수) : 1568ms (34774884) [재귀 함수]
Swift (스택) : 1032ms (34775167)
1-2. 오버헤드
보통 프로그래밍에 있어 코드를 모듈화하여 코딩을 하면 편리합니다.
그래서 보통 함수나 클래드 단위로 묶어 함수지향/객체지향 프로그래밍을 진행하게되는데,
Swift에서는 그렇게 코드를 작성 했을 경우, 오버헤드 현상이 일어나 소요시간이 길어졌습니다.
3954번 Brainf**k 인터프리터 문제입니다.
Swift (모듈화 X) : 2580ms (35607290)
Swift (모듈화 O) : 시간 초과 (35607138) [함수]
11003번 최솟값 찾기 문제 입니다.
이 문제는 4달전 제가 많은 입출력량으로 인해 Swift로 풀기 불가능한 문제라고 언급한 적이 있습니다.
하지만 입출력량이 문제가 아니라, 덱 자료구조 오버헤드로 인한 소요시간 증가가 문제였습니다.
Swift (모듈화 X) : 2032ms (35898370)
Swift (모듈화 O) : 시간 초과(5536ms) (31450143) (함수)
2. Swift에서 기본적으로 제공하는 입출력 함수는 느립니다.
이는 위에 제가 댓글로 달아서 언급한 부분입니다.
사실 Swift 빠른 입출력 코드를 커스텀 할 줄 안다면, 입출력 때문에 못 푸는 문제는 거의 없었습니다.
입출력 속도와 별개로 입출력 양이 많으면 연산량이 많아지는데, 연산량이 많을 수록 연산 시간 느린 모습을 보여주었던적이 많았습니다.
3. 그 외 정확한 이유를 파악하지 못 했지만 시간 초과로 인해 Swift로 풀 수 없었던 문제들입니다.
1325번 효율적인 해킹
2820번 자동차 공장
16235번 나무 재테크
12094번 2048 (Hard)
18015번 어려운 계단 수
19998번 스도쿠 (Hard)
4. 기타
최근에 시간 초과 관련 의견 게시판을 올려주셨는데,
거기서 언급해주신 1번 의견인
'1. 시간 초과지만 min(TL*2, TL+5) 이내에 수행이 완료된 “맞았습니다!!” 제출의 경우 소요 시간을 보여줌 (대회 제출 제외)'
기능은 Swift 언어 유저 입장에서는 긍정적인 의견입니다. ( 시간 초과한 소요 시간에 따라 재귀 함수 / 오버 헤드 / 빠른 입출력을 고려할 수 있기 때문입니다. )
그러나 이 문제를 겪는건 다른 언어도 마찬가지일테고, 보통 다른 PS 사이트에서 시간 초과(TLE)의 코드 소요 시간은 보여주지 않는다는 점에서 반대하는 입장도 공감합니다.
+ Swift 추가 시간 적용하기에 아직 의견이 부족한 것인지 혹은 추가 시간 적용 예정인지 궁금합니다.
댓글을 작성하려면 로그인해야 합니다.
startlink 3년 전 9
Swift의 시간 보너스 조정을 위해 정해로 구현한 Swift 소스를 구합니다.
최소 O(N)정도의 시간 복잡도를 갖는 문제에 제출한 Swift의 소스 번호를 적어주세요.
같은 방식으로 구현한 C++ 소스도 있으면 그 소스의 소스 번호도 적어주세요.