• 배열을 뒤지면서 특정 원소를 찾아지우는 연산을 생각해보자.
    • 앞에서 부터 지우면, 지울때 마다 원소 수가 바뀌면서 out-of-index 문제가 생긴다.
    • 그렇다고 while문으로 바꾸면 직관적이지도 않고, 인덱스를 잘못 스킵하는 문제가 생길 수 있다. 그걸 해결해도 코드가 길어진다.
    • 더 쉬운 방법이 있다. 뒤에서 부터 탐색하면 for문으로도 문제없이 탐색이 가능하다.
  • 하지만 이런 코드는 원소가 많아지면 너무 느려진다.
    • 이는 배열의 삭제 연산이 O(n)이기 때문이다. 실제로는 O(n^2)이나 다름없다.
  • 좋은 프로그래머는 아키텍처만 잘 짜면 된다고?
    • 실제 컴퓨터가 어떻게 도는지도 모르면서 좋은 프로그래머라고 할 수 없다.
  • 위의 방법을 해결하는 것. O(n)인 removeAll(where:)을 쓰는 것!
  • Linear vs Quadratic
  • removeAll의 구현

    • halfStablePartition을 한다.

      • 삭제할 첫번째 원소를 찾는다.

      • 이후 루프를 돌면서 다음 삭제할 원소를 찾는다.

        extension MutableColleciton {
	mutating func halfStablePartition(isSuffixElement: (Element) -> Bool) -> Index {
		guard var i = firstIndex(where: isSuffixElement) else { return endIndex }
		var j = index(after: i)
		while j != endIndex {
			if !isSuffixElement(self[j]) { swapAt(i, j); formIndex(after: &j) }
			formIndex(after: &j)
		}
		return i
	}
}

    • 뒷부분을 자른다.

  • standard Libray를 알면, 이러한 최적화된 코드를 쉽게 짤 수 있다 -> 물론 제공해주는 한도 내에서…
  • 게다가 의미도 쉽게 알 수 있다.
  • 여기서 순서를 자유자재로 바꾸는 코드가 필요하다고 해보자.
    • 게다가 여러개를 선택하면, 그 순서를 유지하면서 움직여야 한다.
    • 정직하게 짜면 O(n^2)
  • 필요한 알고리즘을 최대한 일반적으로 짜도록 하자
  • 테스트와 문서화를 잊지 말 것!
    • 우리는 수많은 추상화 위에 건물을 짓고 있고, 앱 개발자는 그 최상위에서 논다.
  • stablePartition 알고리즘
    • divide and conquer
    • 베이스 케이스
      • 원소 0개: startIndex 그대로 반환
      • 원소 1개: 조건을 만족하면 startIndex, 아니면 endIndex
    • 반 잘라서 알고리즘 수행
      • 이후 앞쪽과 뒷쪽에서 파티셔닝된 인덱스범위만큼 다시 알고리즘 수행