우선 순위 큐
우선순위 큐(Priority queue)는 평범한 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.
우선순위 큐가 힙이라는 것은 널리 알려진 오류이다. 우선순위 큐는 "리스트"나 "맵"과 같이 추상적인 개념이다. 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다.
힙(자료구조)
힙(heap)은 최댓값(최대힙) 및 최솟값(최소힙)을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.
A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 부른다.
힙(최소힙) 구현
import Foundation
class minHeap{
var nodes = [Int]()
init(_ val: Int) {
nodes.append(0) //1부터 사용하기 위한 쓰레기값
nodes.append(val)
}
func up_Rightplace(){ // insert를 위한 새로운 노드가 제자리로 찾아가는 함수
var i = nodes.count-1
var parent = i/2
while nodes[i] < nodes[parent]&&parent>0 {
nodes.swapAt(i,parent)
i = parent
parent = i/2
}
}
func insert(_ k:Int){
nodes.append(k)
up_Rightplace()
}
func down_Rightplace(){ // extract를 위한 바뀐 루트 노드가 제자리로 찾아가는 함수
var idx = 1
var left = idx*2
var right = idx*2+1
while idx<=nodes.count-1&&(nodes[idx]>nodes[left]||nodes[idx]>nodes[right]) {
if left<right{
nodes.swapAt(idx, left)
idx = left
left = idx*2
right = idx*2+1
}
else {
nodes.swapAt(idx, right)
idx = right
left = idx*2
right = idx*2+1
}
}
}
func extract() -> Int {
let extract_Node = nodes[1]
nodes[1] = nodes[nodes.count-1]
nodes.popLast()
down_Rightplace()
return extract_Node
}
}
var heap = minHeap.init(30)
var input = Int(readLine()!)!
heap.insert(input)
while input != 0 {
input = Int(readLine()!)!
heap.insert(input)
print(heap.nodes)
}11279번 최대힙(최대힙으로 풀이 x)
import Foundation
let N:Int = Int(readLine()!)!
var maxHeap:[Int] = []
for _ in 0..<N{
let input = Int(readLine()!)!
if input==0 {
if maxHeap.isEmpty{print(0)}
else{
var max = 0
var maxIndex = 0
var size:Int = maxHeap.count
for i in 0..<size{
if max < maxHeap[i] {
max = maxHeap[i]
maxIndex = i
}
}
print(max)
maxHeap.remove(at: maxIndex)
}
}else{
maxHeap.append(input)
}
}1927번 최소힙(최소힙으로 풀이 x)
import Foundation
let N:Int = Int(readLine()!)!
var minHeap:[Int] = []
for _ in 0..<N{
let input = Int(readLine()!)!
if input==0 {
if minHeap.isEmpty{print(0)}
else{
var min = Int.max
var minIndex = 0
let size:Int = minHeap.count
for i in 0..<size{
if min > minHeap[i] {
min = minHeap[i]
minIndex = i
}
}
print(min)
minHeap.remove(at: minIndex)
}
}else{
minHeap.append(input)
}
}11286 (절댓값 힙 구현)
import Foundation
struct minHeap{
var nodes = [Int]()
init(_ val: Int) {
nodes.append(0) //1부터 사용하기 위한 쓰레기값
nodes.append(val)
}
func comparer(_ a:Int, _ b:Int)->Bool{ // 비교를 위한 함수
if abs(a)==abs(b) {return a<b}
else {return abs(a)<abs(b)}
}
mutating func up_Rightplace(){ // insert를 위한 새로운 노드가 제자리로 찾아가는 함수
var i = nodes.endIndex-1
while i>1&&comparer(nodes[i],nodes[i/2]) {
nodes.swapAt(i,i/2)
i = i/2
}
}
mutating func insert(_ k:Int){
nodes.append(k)
up_Rightplace()
}
mutating func down_Rightplace(idx:Int){ // extract를 위한 바뀐 루트 노드가 제자리로 찾아가는 함수
let left = idx*2
let right = idx*2+1
var isSwap = false
var swapIdx = idx
if left<=nodes.endIndex-1 && comparer(nodes[left],nodes[swapIdx]){
swapIdx = left
isSwap = true
}
if right<=nodes.endIndex-1 && comparer(nodes[right],nodes[swapIdx]){
swapIdx = right
isSwap = true
}
if isSwap{
nodes.swapAt(idx, swapIdx)
down_Rightplace(idx: swapIdx)
}
}
mutating func extract() -> Int {
let extract_Node = nodes[1]
nodes[1] = nodes[nodes.endIndex-1]
nodes.popLast()
down_Rightplace(idx: 1)
return extract_Node
}
}
let N = Int(readLine()!)!
var heap = minHeap.init(0) //인스턴스 생성
heap.extract() // 값 비우기
for _ in 1...N{
let input = Int(readLine()!)!
if input==0 {
if heap.nodes.endIndex==1{print(0)}
else {print(heap.extract())}
}
else{
heap.insert(input)
}
}실패 코드
import Foundation
class minHeap{
var nodes = [Int]()
init(_ val: Int) {
nodes.append(0) //1부터 사용하기 위한 쓰레기값
nodes.append(val)
}
func compare(_ a:Int, _ b:Int)->Bool{ // 비교를 위한 함수
if abs(a)==abs(b) {return a<b}
else {return abs(a)<abs(b)}
}
func up_Rightplace(){ // insert를 위한 새로운 노드가 제자리로 찾아가는 함수
var i = nodes.endIndex-1
while i>1&&compare(nodes[i],nodes[i/2]) {
nodes.swapAt(i,i/2)
i = i/2
}
}
func insert(_ k:Int){
nodes.append(k)
up_Rightplace()
}
func down_Rightplace(idx:Int){ // extract를 위한 바뀐 루트 노드가 제자리로 찾아가는 함수
let left = idx*2
let right = idx*2+1
var isSwap = false
var swapIdx = idx
if left<=nodes.endIndex-1 && compare(nodes[left],nodes[swapIdx]){
swapIdx = left
isSwap = true
}
if right<=nodes.endIndex-1 && compare(nodes[right],nodes[swapIdx]){
swapIdx = right
isSwap = true
}
if isSwap{
nodes.swapAt(idx, swapIdx)
down_Rightplace(idx: swapIdx)
}
}
func extract() -> Int {
let extract_Node = nodes[1]
nodes[1] = nodes[nodes.endIndex-1]
nodes.popLast()
down_Rightplace(idx: 1)
return extract_Node
}
}
var heap = minHeap.init(0) //인스턴스 생성
heap.extract() // 값 비우기
var N = Int(readLine()!)!
for _ in 1...N{
let input = Int(readLine()!)!
if input==0 {
if heap.nodes.endIndex==1{print(0)}
else {print(heap.extract())}
}
else{
heap.insert(input)
}
}결론적으로 class를 struct로만 바꿔 구현했더니 성공했다.
class와 struct의 성능차이가 문제였다.
성능을 정하는 요소 3가지
Allocation: 인스턴스를 생성하면 Stack과 Heap 중 어느 곳에 할당 되는 지
Reference Counting: 인스턴스를 통해 레퍼런스 카운트가 몇개가 발생하는지
Method Dispatch: 인스턴스에서 메소드를 호출했을 때, 메소드 디스패치가 정적인지 동적인지
- Methode Dispatch
Method를 호출 시 어떤 Method를 실행시킬지 결정하는 것
이해를 쉽게 풀면 대부분의 객체 지향 언어들에서는 하위 클래스에서 상위 클래스의 메소드와 프로퍼티들을 오버라이드 할 수 있다. 이렇게 오버라이드를 할 경우, 프로그램은 실제 호출할 함수가 어떤 것인지 결정하는 과정이다.
Allocation
Swift는 C와 같은 Unmanaged Language와는 다르게 사용자 대신 메모리를 자동으로 할당하고 해제해주는 Managed Language이다. (ARC)
stack
함수를 호출할 때 stack pointer를 감소시켜 필요한 메모리를 할당하고, 함수 실행이 다 끝나면 stack pointer를 함수를 호출했던 곳으로 다시 증가시켜 메모리를 간단하게 해제한다.
Stack pointer: stack의 최상단에 있는 pointer를 stack pointer라고 부른다.
Stack은 단순한 구조를 가진만큼 시간복잡도는 O(1)으로 속도가 매우 빠르다.
heap
heap은 stack보다는 더 Dynamic하다.
Heap 영역에서 사용하지 않은 블록을 찾아서 메모리 할당을 처리한다. 할당을 해제하기 위해서는 해당 메모리를 적절한 위치로 다시 삽입한다.
이때, 여러 thread가 동시에 Heap에 메모리를 할당할 수 있기 때문에 locking 또는 기타 동기화 메커니즘을 사용하여 무결성을 보호해야하는데 이것이 heap의 주요 Allocation cost로 작용한다.
heap은 stack과 달리 dynamic lifetime을 가진 메모리를 할당할 수 있다.
dynamic lifetime: 사용자에 의해 동적으로 객체의 lifetime이 결정되는 것을 말합니다.
struct의 할당 구조
Value Semantics-struct(+tuple,enum)
Struct 인스턴스를 생성하여 다른 인스턴스에 할당하면, 전체 값은 그대로 복사가 된다. 복사된 인스턴스는 기존 인스턴스와 구분되어져 stack에 저장되기 때문에 내부 값을 변경해도 원래 값에 영향을 주지 않는다. Heap을 사용하지 않기 때문에 reference counting도 사용하지 않는다.
class의 할당 구조
Reference Semantics-Class(+function)Reference semantics은 stack과 heap을 둘 다 사용한다.
stack - reference인 주소값 할당
heap - 데이터 값 할당
사진을 보면 point1이 struct일 때처럼 point1의 contents를 복사하는 대신, point1의 인스턴스에 대한 참조를 복사한다.
그렇기 때문에 복사된 인스턴스를 수정하면 원래 인스턴스 데이터도 함께 변경된다.
Reference Counting
class의 reference counting
클래스는 힙에 할당되기 때문에 Swift는 heap allocation life time을 관리해야한다. 이것은 reference counting으로 처리하게 된다.
struct의 reference counting
반면 구조체는 기본적으로 레퍼런스를 사용하지 않지만, 구조체가 레퍼런스(example: String)를 가지게 되면 reference counting으로 오버헤드(overhead)를 처리하는 비용이 들게 된다.
즉, 구조체의 reference counting 오버헤드는 구조체에 있는 레퍼런스 개수에 비례하게된다.
Static Method Dispatch
Static method dispatch는 컴파일 시점에 컴파일러가 메소드의 실제 코드 위치를 파악할 수 있어 런타임에 찾는 과정 없이 바로 해당 코드를 실행하는 것을 의미한다.
구현된 코드들이 어디서 실행되는지 알 수 있기 때문에 메소드 인라이닝같은 코드 최적화를 적극적으로 시행합니다.
메서드 인라이닝: 성능 최적화를 위해 메서드 호출을 하지 않고 메서드의 본문을 집어 넣는 것을 말한다.
Dynamic Method Dispatch
Dynamic Dispatch는 다형성과 밀접한 연관이 있다. 대부분의 객체 지향 언어들에서는 하위 클래스에서 상위 클래스의 메소드와 프로퍼티들을 오버라이드 할 수 있다. 이렇게 오버라이드를 할 경우, 프로그램은 실제 호출할 함수가 어떤 것인지 결정하는 과정에서 Dynamic Dispatch가 발생한다.
Dynamic Dispatch는 Static Dispatch와 달리 컴파일 타임에 어떤 메소드를 호출하는지 판단할 수 없어, 런타임에 table에 구현을 참조하여 해당 메소드에 대한 정보를 가져와서 코드를 실행시키게 된다.
사실 dynamic dispatch는 static dispatch보다 그렇게 크게 성능 차이가 나지는 않는다. 레퍼런스 카운팅, 힙 할당과 같은 쓰레드 동기 오버헤드가 없기 때문이다.
결론적인 성능 graph (WWDC 2016 자료)
이런 이유로 class가 꼭 필요하지 않으면 apple에서는 struct를 사용하는 것을 권장한다.
