Swift 속도 높이기 - 안전성과 속도(ex: 백준 11049 행렬 곱셈 순서)
참고
Why are Swift’s UnsafePointer and UnsafeBufferPointer not interchangeable?(StackOverflow)
Safely manage pointers in Swift(WWDC2020)
알고리즘 스터디에서 프로그래머스 문제는 풀만한 것들은 다 풀어서 이제 다시 백준 문제들 풀고 있다
백준은 C++로는 많이 풀었었지만 Swift로는 별로 안 해봄
프로그래머스에 있는 여러 언어를 지원하는 코테 문제들은 시공간 복잡도가 대체로 널널한 편으로 주는데,
백준은 그런 거 없으므로 Swift를 쓰면 같은 알고리즘인데도 컷을 통과 못하는 경우도 있음
Swift는 안전한 언어이기 때문에 생기는 문제인데, 지금 같이 그냥 알고리즘 채점할 때는 배열 크기 정해져 있고 하면 속도가 우선되어야 하는 상황이다.
그래서 이거 어떻게 좀 못하나??! 해서 개선한 과정
백준의 행렬 곱셈 순서(11049)를 예로 들겠습니다
문제
상당히 스탠다드한 dp 문제 입니다… 근데 처음 볼 땐 너무 어려웠음ㅋㅋ
여러 행렬들이 있을 때 곱셈 순서에 따라 연산 횟수가 달라지므로 최소화한 크기 찾기
조건
첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.
둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)
풀이
이차원 배열을 잡고, 시작과 끝의 연산 횟수를 저장해두는 방식
시작과 끝의 연산 횟수는 (시작, 어느 중간 지점)의 연산 횟수, 두 행렬을 곱하는 연산 횟수, (어느 중간 지점 + 1, 끝)의 연산 횟수를 계산해서 다 더해주면 됨
dp[s][e] = min(dp[s][e], dp[s][i] + (s의 행)*(i의 열)*(e의 열) + dp[i+1][e]
1. 재귀(시간 초과)
var mats = [(Int, Int)]()
var dp = [[Int]](repeating: [Int](repeating: Int.max, count: 501), count: 501)
func calc(_ s: Int, _ e: Int) -> Int {
if dp[s][e] != Int.max {
return dp[s][e]
}
if s == e {
dp[s][e] = 0
return 0
}
if s + 1 == e {
dp[s][e] = mats[s].0 * mats[s].1 * mats[e].1
return dp[s][e]
}
for i in s..<e {
dp[s][e] = min(dp[s][e], calc(s, i) + mats[s].0 * mats[i].1 * mats[e].1 + calc(i + 1, e))
}
return dp[s][e]
}
let n = Int(readLine()!)!
for _ in 0..<n {
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
mats.append((arr[0], arr[1]))
}
print(calc(0, n-1))
그래서 재귀로 했는데 시간 초과 남…
1-2. 재귀(C++)
#include <bits/stdc++.h>
using namespace std;
int r[501];
int c[501];
int dp[501][501];
int func(int a, int b){
if( dp[a][b] != INT_MAX ) return dp[a][b];
if( a == b ){
dp[a][b] = 0;
return 0;
}
if( b-a == 1 ){
dp[a][b] = r[a] * c[a] * c[b];
return dp[a][b];
}
for(int i = a; i < b; i++){
dp[a][b] = min(dp[a][b], func(a, i) + func(i+1, b) + r[a]*c[i]*c[b]);
}
return dp[a][b];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> r[i] >> c[i];
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
dp[i][j] = INT_MAX;
}
}
cout << func(0, n-1) << endl;
}
예전에 풀었던 같은 로직(재귀)인 C++은 3004 KB, 148 ms인데 뭐지
2. 재귀 X
var mats = [(Int, Int)]()
var dp = [[Int]](repeating: [Int](repeating: 0, count: 501), count: 501)
let n = Int(readLine()!)!
for _ in 0..<n {
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
mats.append((arr[0], arr[1]))
}
for a in 1..<n {
for s in 0..<n-a {
let e = s + a
dp[s][e] = Int.max
for i in s..<e {
dp[s][e] = min(dp[s][e], dp[s][i] + mats[s].0 * mats[i].1 * mats[e].1 + dp[i+1][e])
}
}
}
print(dp[0][n-1])
그래서 재귀 안 쓰도록 바꿈
71084 KB, 548 ms 나오고 통과
3. 재귀 X(temp 변수 사용)
근데 통과는 하긴 했는데 생각보다 너무 느린 거 같지 않음??
그래서 더 빠른 swift 코드들을 찾아봤는데 로직은 똑같았고, 다른 부분을 딱 하나 찾았는데 min 값 업데이트할 때 temp 변수를 사용함
var mats = [(Int, Int)]()
var dp = [[Int]](repeating: [Int](repeating: 0, count: 501), count: 501)
let n = Int(readLine()!)!
for _ in 0..<n {
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
mats.append((arr[0], arr[1]))
}
for a in 1..<n {
for s in 0..<n-a {
let e = s + a
var temp = Int.max
for i in s..<e {
temp = min(temp, dp[s][i] + mats[s].0 * mats[i].1 * mats[e].1 + dp[i+1][e])
}
dp[s][e] = temp
}
}
print(dp[0][n-1])
그래서 dp[s][e]를 계속 업데이트 안 하고 temp를 업데이트 후에 dp[s][e]에 덮어쓰게 하니까 71084 KB, 100 ms 나옴
테스팅
1. Array와 일반 변수
저게 그렇게 차이 날 일인가??
해서 백준말고 따로 직접 돌려 봄
func testPerformanceTmp() throws {
let n = 100
self.measure {
var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
for i in 0..<n {
for j in 0..<n {
var temp = Int.max
for k in 0..<n {
temp = min(temp, k)
}
dp[i][j] = temp
}
}
}
}
func testPerformanceArr() throws {
let n = 100
self.measure {
var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
for i in 0..<n {
for j in 0..<n {
dp[i][j] = Int.max
for k in 0..<n {
dp[i][j] = min(dp[i][j], k)
}
}
}
}
}
testPerformanceTmp
average: 0.247, relative standard deviation: 4.586%,
values: [0.281306, 0.241937, 0.245725, 0.243498, 0.243551, 0.243469, 0.243383, 0.243448, 0.243913, 0.243491], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
(2.727 seconds).
testPerformanceArr
average: 0.289, relative standard deviation: 4.577%,
values: [0.326845, 0.284971, 0.283706, 0.288736, 0.287529, 0.284505, 0.289616, 0.282690, 0.278838, 0.278799], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
(3.173 seconds).
그러니까 진짜 배열값 업데이트하는 게 더 오래 걸림!!!
이전에 빠르게 병렬 처리하는 코드를 찾아봤던 내용 중 withUnsafeMutableBufferPointer()를 사용하는 코드가 생각나네요
일반 배열은 범위 검사가 있어서 안전한 대신 속도가 느리다고 했었는데, 그 때는 그런갑다 했는데 생각보다 차이가 남ㄷㄷ
2. 스택과 힙
배열은 대표적인 힙을 사용하는 구조체인데,
그럼 혹시 스택이랑 힙 차이도 있을까?? 해서
struct S {
var s = 0
}
class C {
var c = 0
}
이렇게 똑같은 내용의 구조체랑 클래스를 만들어서
func testPerformanceStruct() throws {
self.measure {
let s = S()
for i in 0..<5000000 {
_ = min(s.s, i)
}
}
}
func testPerformanceClass() throws {
self.measure {
let c = C()
for i in 0..<5000000 {
_ = min(c.c, i)
}
}
}
각자 s.s, c.c에 접근하도록 해서 이 둘을 한 번 비교해보니까
n = 5000000
testPerformanceClass
average: 1.261, relative standard deviation: 1.085%,
values: [1.301309, 1.259097, 1.254454, 1.254592, 1.256693, 1.254904, 1.252998, 1.255957, 1.257812, 1.263065], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
(12.892 seconds).
testPerformanceStruct
average: 1.220, relative standard deviation: 0.461%,
values: [1.231718, 1.224455, 1.223466, 1.220644, 1.222473, 1.215172, 1.214919, 1.213395, 1.213834, 1.216764], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
(12.449 seconds).
n = 10000000
testPerformanceClass
average: 2.492, relative standard deviation: 0.946%,
values: [2.533375, 2.510912, 2.506536, 2.490910, 2.455178, 2.464214, 2.465062, 2.484884, 2.495857, 2.510978], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
(25.206 seconds).
testPerformanceStruct
average: 2.449, relative standard deviation: 0.740%,
values: [2.500354, 2.455439, 2.445043, 2.440963, 2.441130, 2.437140, 2.432284, 2.445015, 2.452564, 2.444581], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
(24.748 seconds).
n = 100000000
testPerformanceClass
average: 25.274, relative standard deviation: 0.345%,
values: [25.114033, 25.369771, 25.368506, 25.207563, 25.276780, 25.382416, 25.279062, 25.337830, 25.233618, 25.172490], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
(253.090 seconds)
testPerformanceStruct
average: 24.508, relative standard deviation: 0.197%,
values: [24.550876, 24.493880, 24.505509, 24.458932, 24.478443, 24.460256, 24.506413, 24.600263, 24.571954, 24.451533], performanceMetricID:com.apple.XCTPerformanceMetric_WallClockTime, baselineName: "", baselineAverage: , polarity: prefers smaller, maxPercentRegression: 10.000%, maxPercentRelativeStandardDeviation: 10.000%, maxRegression: 0.100, maxStandardDeviation: 0.100
(245.324 seconds)
클래스가 쪼끔 더 느리다!!
RSD(relative standard deviation)는 평균에 대한 정밀도를 측정한 계수라고 하는데 이것도 struct가 더 안정적
사실 유의미한 수치인지는 모르겠지만, 힙이 할당이 느린 건 알고 있었는데 메모리 접근도 이렇게 어느 정도 느린 줄은 몰랐음…
이거는 힙에서 포인터 한 번 거쳐가서 그런 거로 이해함??
풀이(개선)
4. 재귀 X(포인터 사용)
그래서 배열 접근이 느린 거라면 배열 범위 검사 등을 안 하는 함수로 속도가 빠른 대신 덜 안전한(약간 C 느낌??) withUnsafeMutableBufferPointer()를 사용해보기로 함
지금은 어차피 최대 크기가 500으로 정해져 있고 그거로 init하니까 검사 필요 없음
var mats = [(Int, Int)]()
var dp = [[Int]](repeating: [Int](repeating: 0, count: 501), count: 501)
let n = Int(readLine()!)!
for _ in 0..<n {
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
mats.append((arr[0], arr[1]))
}
dp.withUnsafeMutableBufferPointer { buffer -> UnsafeMutableBufferPointer<[Int]> in
for a in 1..<n {
for s in 0..<n-a {
let e = s + a
buffer[s][e] = Int.max
for i in s..<e {
buffer[s][e] = min(buffer[s][e], buffer[s][i] + mats[s].0 * mats[i].1 * mats[e].1 + buffer[i+1][e])
}
}
}
return buffer
}
print(dp[0][n-1])
해당 UnsafeMutableBufferPointer로 직접 값을 업데이트하면서 해본 결과
71088 KB, 172 ms 나옴
5. 재귀(포인터 사용)
var mats = [(Int, Int)]()
var dp = [[Int]](repeating: [Int](repeating: Int.max, count: 501), count: 501)
let pointer = UnsafeMutableBufferPointer(start: &dp, count: dp.count).baseAddress!
func calc(_ s: Int, _ e: Int) -> Int {
if pointer[s][e] != Int.max {
return pointer[s][e]
}
if s == e {
pointer[s][e] = 0
return 0
}
if s + 1 == e {
pointer[s][e] = mats[s].0 * mats[s].1 * mats[e].1
return pointer[s][e]
}
for i in s..<e {
pointer[s][e] = min(pointer[s][e], calc(s, i) + mats[s].0 * mats[i].1 * mats[e].1 + calc(i + 1, e))
}
return pointer[s][e]
}
let n = Int(readLine()!)!
for _ in 0..<n {
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
mats.append((arr[0], arr[1]))
}
print(calc(0, n-1))
그렇다면 이제 너무 느려서 시간 초과 났던 풀이1(재귀)을 포인터로 사용해봅니다
코드 완전히 같고 dp를 액세스하던 것을 pointer로 액세스하면
71088 KB, 288 ms로 통과!!!
재귀 안 쓰고 dp 배열 직접 업데이트 했던 풀이2보다도 빠르네요
결과
(백준 제출 기준이므로 대략적인 수치이고, 실 사용에서는 상황 따라 다를 수 있음)
| 번호 | 내용 | 시간(ms) |
|---|---|---|
| 1 | 재귀 | 시간 초과 |
| 2 | dp 배열 직접 업데이트 | 544 |
| 3 | temp 변수 사용 | 100 |
| 4 | dp 배열 직접 업데이트(UnsafeMutableBufferPointer) | 172 |
| 5 | 재귀(UnsafeMutableBufferPointer) | 288 |
일단 재귀 풀이인 1과 5를 비교하면 버퍼 포인터 사용한 5번이 훨씬 빠릅니다.
재귀가 아닌 풀이인 2, 3, 4를 비교하면 아무래도 그냥 레지스터를 사용하는 3번 풀이가 제일 빠르긴 하고,
그 다음은 버퍼 포인터 사용해서 배열 read write 하는 4번이 빠르고,
기존 평범한 방식인 배열을 직접 접근하는 2번은 눈에 띄게 제일 느립니다.
결론
withUnsafeMutableBufferPointer얘를 쓰면 속도 개선에 도움이 될 수 있다.- 안전성이 적은 대신 빠른 C 스타일 포인터로 접근할 수 있어 속도가 빨라짐
- Array나 heap 변수를 너무 자주 업데이트 하기 보다는 tmp 변수를 사용하도록 하자
- 당연한 거긴 한데 힙 변수보다는 그냥 레지스터 쓰는 게 훨 빠름
Swift로 백준 풀 때 기준 입니다!!
대체로 속도보다 안전성이 중요한 편이고, 굳이 변수 늘리는 게 코드 스멜 늘리고 별로일 수도 있으므로
실제 개발에서는 상황 따라서 고르기~~
댓글남기기