루비 개발자를 위한 Big-O 표기법 완벽 가이드

저는 컴퓨터 공학 학위가 없습니다. 루비(Rubyist) 개발자 중에는 저처럼 학위가 없는 사람이 많죠. 그래서 한동안 Big-O 표기법을 배우는 것을 피해 다녔습니다. 너무 고등 수학 같아 보였거든요. O(N^2)이라니, 말이 안 되잖아요.

대신 저는 이런 경험 법칙들을 익혔습니다:

• Hash에서 특정 항목을 찾는 것이 Array에서 찾는 것보다 빠르다
• 중첩 루프는 피하라
• 뷰(View)에서 목록을 생성할 때 의도치 않은 DB 쿼리가 발생하지 않도록 주의하라

이런 규칙들도 좋지만, 왜 그렇게 작동하는지 이해하지 못하면 실수를 반복하게 되고, 원인을 알 수 없는 성능 문제에 부딪히게 됩니다.

왜 중요한가?

Big-O 표기법은 코드의 성능이 처리하는 데이터의 양에 따라 어떻게 달라지는지 설명하는 방법입니다.

여기서 성능은 두 가지 중 하나를 의미합니다. 바로 속도 또는 RAM 사용량이죠. 컴퓨터 과학 수업에서는 각각 "시간 복잡도(time complexity)"와 "공간 복잡도(space complexity)"라고 부릅니다. Big-O 표기법은 둘 다에 사용되지만, 이 글에서는 더 일반적으로 쓰이는 속도에 초점을 맞추겠습니다.

항목이 100개인 배열을 처리하는 것이 10개짜리 배열보다 느릴 것이라고 예상할 수 있습니다. 하지만 얼마나 느릴까요? 10배? 100배? 아니면 1000배?

작은 데이터셋에서는 큰 문제가 되지 않지만, 앱이 데이터베이스의 행(row)이 늘어날 때마다 기하급수적으로 느려진다면 곧 심각한 문제가 됩니다.

세부 내용으로 들어가기 전에, 일반적인 Big-O 복잡도를 데이터가 커질 때의 기분과 함께 이모지로 표현한 차트를 준비했습니다.

그래서 누군가 Array#bsearch가 Array#find보다 낫다고 말할 때, O(log n) vs O(n)이니 😁와 😕를 비교해 보면 그 사람이 무슨 말을 하는지 감이 잡힙니다.

좀 더 체계적인 자료가 필요하다면 Big-O Cheat Sheet를 참고해 보세요.

표기법 해독하기

모든 Big-O 값을 통째로 외울 필요는 없습니다. 표기법이 어떻게 작동하는지만 이해하면 됩니다.

예를 들어 끔찍하고도 끔찍한 O(2^n)을 살펴보겠습니다. 이걸 Ruby로 표현하면 다음과 같습니다:

# O(2^n)를 Ruby로 옮긴 코드
def o(n)
  2 ** n  # Ruby에서 2^n을 나타내는 방식
end

아직 잘 와닿지 않나요? 메서드와 인수 이름을 좀 더 직관적으로 바꿔 보겠습니다.

# O(2^n)를 더 읽기 쉬운 Ruby로 옮긴 코드
def execution_time(size_of_dataset)
  2 ** size_of_dataset
end

다른 복잡도도 마찬가지 방식으로 표현할 수 있습니다:

# O(1)
def o1_execution_time(size_of_dataset)
  1
end

# O(n)
def on_execution_time(size_of_dataset)
  size_of_dataset
end

# O(n^2)
def on2_execution_time(size_of_dataset)
  size_of_dataset * size_of_dataset
end

# ... 등등

이제 표기법이 어떻게 작동하는지 알았으니, 실제 Ruby 코드가 이 개념과 어떻게 연결되는지 살펴보겠습니다.

O(1)

어떤 코드가 O(1)이라는 것은, 실행 속도가 데이터셋의 크기에 영향을 받지 않는다는 의미입니다.

예를 들어 해시(hash) 조회 시간은 해시의 크기와 무관합니다:

# 아래 세 코드는 모두 거의 같은 시간이 걸립니다
hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]

바로 이런 이유로 대용량 데이터셋에서는 해시가 배열보다 빠르다고 말하는 것입니다.

O(n)

반면 Array#find는 O(n)입니다. 즉, Array#find의 실행 시간은 배열의 항목 수에 선형적으로 비례합니다. 항목이 100개인 배열은 항목이 1개인 배열보다 검색에 100배 더 오래 걸립니다.

배열을 순회(iterate)하는 대부분의 코드가 O(n) 패턴을 따릅니다.

(0..9).each do |i|
  puts i
end

# 아래 예제는 항목이 2배이므로 위 예제의 절반 속도입니다.
(0..19).each do |i|
  puts i
end

O(n^2)

O(n^2) 패턴에 해당하는 코드는 대개 중첩 루프를 포함합니다. 생각해 보면 당연합니다. 루프 하나면 O(n), 여기에 루프가 하나 더 중첩되면 O(n^2)가 됩니다. 만약 — 어느 미친 이유로든 — 5단계 중첩 루프를 만들었다면 O(n^5)가 되겠죠.

data = (0..100)
data.each do |d1|
  data.each do |d2|
    puts "#{ d1 }, #{ d2 }"
  end
end

O(n log n)

O(n log n) 코드는 흔히, 원래 O(n^2)일 알고리즘이 수행해야 할 작업량을 줄이는 영리한 방법을 찾아낸 결과물입니다.

코드만 눈으로 보고 O(n log n)이라고 판단하기는 어렵습니다. 여기서부터 고등 수학이 등장하고, 솔직히 저는 여기서 물러나겠습니다.

그래도 O(n log n)에 대해 알아두는 것이 중요한데, 수많은 일반적인 정렬·검색 알고리즘이 이 복잡도에 해당하기 때문입니다. Ruby의 Array#sort는 오랜 역사를 지닌 퀵소트(quicksort) 알고리즘을 사용하며, 평균적으로는 O(n log n), 최악의 경우에는 O(n^2)입니다.

퀵소트가 낯설다면 이 훌륭한 시연 자료를 확인해 보세요.

종합하기: 데이터베이스

새 웹 애플리케이션에서 가장 흔히 발생하는 문제 중 하나는, 개발자 컴퓨터에서는 빠르게 돌아가던 앱이 프로덕션 환경에서는 점점 느려진다는 것입니다.

원인은 이렇습니다. 데이터베이스의 레코드 수는 시간이 지나며 계속 늘어나는데, 코드는 DB에 확장성이 떨어지는 작업, 즉 O(n) 이상의 작업을 계속 요청하고 있는 것입니다.

예를 들어, PostgreSQL에서 count 쿼리는 항상 O(n)이라는 사실을 알고 계셨나요?

# 이 코드는 DB가 Users 테이블의 모든 행을 순회하게 만듭니다
# ... Rails의 카운터 캐시(counter cache)를 사용하지 않는 한요.
Users.count

PostgreSQL의 explain 명령으로 이를 직접 확인할 수 있습니다. 아래는 count 쿼리의 실행 계획(query plan)을 조회한 결과입니다. 보시다시피 테이블의 104,791행 전체에 대해 순차 스캔(sequential scan, 즉 루핑)을 수행할 계획입니다.

# explain select count(*) from users;
                           QUERY PLAN
-----------------------------------------------------------------
 Aggregate  (cost=6920.89..6920.90 rows=1 width=0)
   ->  Seq Scan on users  (cost=0.00..6660.71 rows=104701 width=0)
(2 rows)

데이터베이스를 별도로 최적화하지 않는 한, 흔히 쓰이는 Rails 관용구(idiom)들이 의도치 않은 순차 스캔을 유발할 수 있습니다.

# 이 코드는 DB에게 `products` 테이블 전체를 정렬하도록 요청합니다
Products.order("price desc").limit(1)

# `hobby` 컬럼에 인덱스가 없다면, DB는 Users의 모든 행을 순회하며 찾습니다.
User.where(hobby: "fishing")

이 경우에도 explain 명령으로 확인할 수 있습니다. 아래 결과에서는 전체 테이블에 대한 정렬(아마도 퀵소트)이 수행됩니다. 메모리 제약이 있는 환경이라면 성능 특성이 다른 다른 정렬 알고리즘이 선택되었을 수도 있습니다.

# explain select * from users order by nickname desc limit 1;
                               QUERY PLAN
-------------------------------------------------------------------------
 Limit  (cost=7190.07..7190.07 rows=1 width=812)
   ->  Sort  (cost=7190.07..7405.24 rows=104701 width=812)
         Sort Key: nickname
         ->  Seq Scan on users  (cost=0.00..6606.71 rows=104701 width=812)

이 모든 문제에 대한 해답은 당연히 인덱싱(indexing)입니다. 데이터베이스에 인덱스를 활용하도록 하는 것은, Ruby에서 배열 탐색 O(n) 대신 해시 조회 O(1)를 사용하는 것과 같은 원리입니다.

그럼, 여기까지!

이 글이 Big-O 표기법의 기본 개념과, 루비 개발자로서 이것이 실무에 어떤 영향을 주는지 이해하는 데 도움이 되었기를 바랍니다! 궁금한 점이 있다면 @StarrHorne으로 연락해 주세요.