분류 전체보기53 [WWDC16] Understanding Swift Performance 2부 Protocol Oriented Programming (POP) 상속이나 참조 semantics없이 다형성 구현 protocol Drawable { func draw() } struct Point: Drawable { var x, y: Double func draw() { } } struct Line: Drawable { var x1, y1, x2, y2: Double func draw() {} } var drawables: [Drawable] = [] for d in drawables { d.draw() } class SharedLine: Drawable { var x1, y1, x2, y2: Double func draw() { // ... } } class도 물론 프로토콜을 사용할 수 있지만, re.. 2023. 3. 3. Queue 구현 (feat. Swift) https://github.com/kodecocodes/swift-algorithm-club/tree/master/Queue 해당 문서를 직접 번역하면서 공부한 내용입니다. BFS를 공부하면서 Queue를 쓰고싶었는데, built-in swift에서의 removieFirst()함수는 배열에서 맨 앞단의 요소를 제거하는 것이기 때문에 O(n)의 시간복잡도가 생긴다. 파이썬에서 deque라이브러리를 통해 O(1)로 맨 앞단의 요소를 제거하는 것처럼 하기 위해서 Swift의 Queue에 대해서 공부해보았다. 단순한 Queue의 구현 public struct Queue { fileprivate var array = [T]() public var isEmpty: Bool { return array.isEmpty .. 2023. 2. 7. Heap 구현 (feat. Swift) https://www.kodeco.com/586-swift-algorithm-club-heap-and-priority-queue-data-structure#toc-anchor-001 해당 원문을 공부하면서 직접 번역한 내용입니다. 정확하지 않은 표현과 필자가 본인의 이해를 위해 추가로 적은 내용들이 있으니 그 점 유의하시기 바랍니다. 우선순위 큐를 구현하는데 Heap을 더 선호하는 이유: https://codingmon.tistory.com/23 Heap은 binary tree(BST와 유사한)와 닮았다. Heap은 트리이고, 모든 노드는 0, 1, 2개의 자식들을 가지고 있다. Heap의 요소들은 그들의 우선 순위에 따라 부분적으로 정렬돼있다. 트리의 모든 노드는 각 노드의 자식들보다 높은 우선순위를 .. 2023. 2. 5. Priority Queue(우선 순위 큐)에서 Heap을 선호하는 이유 앞서 Priority Queue를 구현할 때, BST보다 heap이 선호되는 이유에 대해서 알아보겠다. 컴퓨터 구조를 간단한 예시로, CPU에는 코어, L1, L2, L3캐시가 있고, 또 메모리가 존재한다. L1에서 L3로 갈수록 속도는 느려지고, 용량은 커진다. 메모리는 L3보다 훨씬 느리지만, 용량은 매우 크다. CPU에서 데이터를 처리하기 위해서 가장 먼저 해야할 작업은 메모리에 있는 데이터를 우선 캐시로 가져와서 코어가 작업할 수 있게끔 하는 것이다. 메모리에서의 속도는 상대적으로 매우 느리다. 만약 메모리 곳곳에 분산되어있는 4군데(linked list)에서 작업을 가져와서 처리해야한다고 친다면, 4번 메모리에서 링크를 타고 이동하며 이동하면서 속도가 굉장히 느릴 것이다. 하지만 만약 한 곳에 .. 2023. 2. 2. 이전 1 ··· 10 11 12 13 14 다음
