Swift를 통해서 PS를 한 지도 오래 된 것 같다. 항상 할 때마다 heap, deck등 직접 구현해주어야 하는 부분이 많아서 힘들 때도 있지만, 괜찮.. 지 않고(??) 가장 힘든 부분은 입출력 시간초과가 날 때이다.
분명 시간복잡도도 똑같고 C++, Python이랑 똑같은 코드임에도 시간초과가 난다. 이런 상황에서 99%는 입출력이 오래걸려서 시간초과가 나는 경우가 많다. (10-20만줄 입력값이면 무조건 터진다고 보면 된다.)
정답인 코드를 두고 문제를 실패로 두기도 찝찝해서 예전부터 알고 있던 라이노님의 FileIO class, 그리고 readLine()에 대해서도 추가적으로 알아보기로 하자.
사실 정리할 생각은 없었는데 거의 모든 FileIO관련 포스팅들이 사용법만 설명해주고 왜 이렇게 하는 것이 더 빠른지, 어떤 개념들로 만들어져있는지 설명해준 글이 정말 거의 없어서 포스팅을 하게 되었다….
readLine()
func readLine(strippingNewline: Bool = true) -> String?strippingNewline라는 인자는 개행문자(= 줄바꿈문자 - \n)의 제거 여부를 나타낸다.
디폴트는 true로 설정되어 있어서, readLine()을 했을 때 개행문자를 제외한 optional(입력값)이 나오게 된다.
EOF(end of file)처리는 엔터(\n)로 처리한다.
FileIO
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)]
// 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[index]
}
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}
@inline(__always) func readString() -> String {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
}
@inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return Array(buffer[beginIndex..<(index-1)])
}
}주의해야할 점은, readLine()과는 다르게 EOF(end of file)처리는 ctrl+D로 처리한다.
하나씩 해석을 해보자.
자 먼저, 맨 처음 나오는 buffer는 무엇일까? 이미 우리는 알고 있는 개념이다. 동영상을 볼 때, 우리가 자주 하는 말인 ‘버퍼링에 걸렸다’ ← 여기서 나오는 buffering의 buffer가 버퍼이다.
정의적으로는, ‘데이터를 전송할 때 데이터의 전송 속도의 차이를 완화하는 목적으로 사용하는 기억장치’ 이다.
말 그대로 ‘임시 저장공간’ 이라고 보면 된다.
앞서 말한 동영상 영상 스트리밍에서, 서버에서 영상 파일을 여러 조각으로 쪼개서 데이터로 보낸다. 버퍼는 이 조각들을 차곡차곡 쌓고, 사용자가 시청할 수 있는 최소한의 크기가 만들어지면 사용자에게 전달이 되는 것이다.
입출력(FileIO)에서도 비슷하다.
버퍼를 사용하지 않는 입력에서는, 문자 하나하나 입력을 받을 때마다 그대로 프로그램에 전달이 된다. 이렇게 되면, 프로그램이 한 번에 처리할 수 있는 작업량이 있는데, 이에 턱없이 작은 하나의 입력만을 담당하게 되므로 성능이 떨어지게 된다.
버퍼를 사용하게 되면, 버퍼의 끝에 도달할 때까지 입력을 쌓아두고, 한 번에 처리되기 때문에 사용하지 않을 때보다 굉장히 효율적으로 시간과 메모리를 사용하게 된다.
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)]
// 인덱스 범위 넘어가는 것 방지
}그렇다면, 왜 buffer의 자료형이 UInt8일까? → 바로 아스키 코드(Ascii code) 때문이다.
입력값이 숫자, 영어 소문자, 대문자 뿐 아니라 기호까지 올 수 있는 상황에서 이를 모두 대응하는 것 보다 아스키코드로 입력값을 받고, 이를 활용하는 방향이 가장 효율적이기 때문이다.
→ 사실 FileHandle.standardInput.readToEnd()!의 출력값이 애초에 Ascii code로 받아진다.
let input = Array(try! FileHandle.standardInput.readToEnd()!)+[UInt8(0)]
print(input)
//[50,10,0]그렇기 때문에, 127번까지 있는 아스키 코드의 입력을 저장하려면 UInt8.max = 256인 UInt8자료형이 가장 효율적이기 때문에 UInt8자료형이 사용된다.
이 정도의 배경지식만 이해를 하면, 나머지는 그냥 자연스럽게 이해할 수 있었다.
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}read()를 통해 읽어온 값이 Ascii 10(줄바꿈), 혹은 Ascii 32(space)일 때는 무시한다.
Ascii 45(음수 -)일 때는 toggle()을 통해 음수처리를 해준다.
또한, Ascii 48~57(숫자)값이 들어올 때는 while문을 돌면서 자릿수에 따라 10을 곱해주고 Int값으로 만들어준다.
readString()또한 다른 점은 거의 없으니 생략한다.
세부적인 것들을 조금 더 알아보고 마무리한다.
@Inline
함수를 그냥 인스턴스 함수로 정의하면 그 함수를 정의되어 있는 곳에 가서 보고, 다시 본래 코드로 와서 적용하는 과정을 거친다. 하지만 @Inline으로 선언하면 함수 호출 오버헤드(부가적인 비용)를 줄이고 성능향상을 이룰 수 있다.
(__always)가 붙으면 ‘항상’ inline으로 확장되도록 강제한다.
(그런데 현대 컴파일러에서는 자동으로 적절하게 인라인화 한다는 소리도..?)
private
함수 접근제어자는 이미 알고 있었는데, 접근제어자로 인해 속도 차이가 난다는 사실은 처음 알았다.
open, 또는 접근 제어자가 없는 함수의 경우 2-3배 차이의 시간차이가 발생한다고 한다 (?!)
(static dispatch 내용 추가 예정)
예전부터 한 번 뜯어보고싶다고 생각한 FileIO를 뜯어보면서 새롭게 알게 된 내용, CS적인 부분도 많이 있는 것 같아서 흥미로웠다.
참조
