Big-O 표기법에 대한 Rubyists 가이드

저는 컴퓨터 공학 학위가 없습니다. 많은 루비스트들은 그렇지 않습니다. 그래서 오랫동안 나는 big-O 표기법에 대해 배우는 것을 피했습니다. 좀 더 고급 수학처럼 보입니다. 내 말은:O(N^2) . 어서 해봐요.

대신 경험 법칙을 배웠습니다.

• 해시에서 특정 항목을 찾는 것이 배열보다 빠릅니다.
• 중첩 루프 방지
• 보기에서 목록을 생성할 때 우발적인 DB 쿼리에 주의하세요.

이 규칙은 훌륭하지만 WHY를 이해하지 못한다면 그들이 작동하면 실수를 하고 설명할 수 없는 성능 문제를 겪고 있는 자신을 발견하게 될 것입니다.

중요한 이유는 무엇입니까?

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

성능은 속도 또는 램 사용량의 두 가지 중 하나를 의미합니다. 컴퓨터 과학 수업에서는 이것을 "시간 복잡성"과 "공간 복잡성"이라고 합니다. Big-O 표기법은 둘 다에 사용되지만 여기서는 속도가 더 일반적으로 사용되는 것 같으므로 여기서는 속도에 중점을 둘 것입니다.

100개 항목의 배열을 처리하는 것이 10개 항목의 배열보다 느릴 것으로 예상할 수 있습니다. 하지만 얼마까지? 10배, 100배? 1000배?

작은 데이터 세트에서는 큰 문제가 아니지만 데이터베이스의 각 행에 대해 앱이 기하급수적으로 느려지면 곧 문제가 됩니다.

세부 사항을 살펴보기 전에 데이터가 확장됨에 따라 어떻게 느끼는지 보여 주는 이모티콘과 함께 일반적인 big-O를 보여주는 빠른 차트를 만들었습니다.

따라서 누군가가 Array#bsearch라고 말하면 Array#find보다 낫습니다. O(log n)이기 때문입니다. 대 O(n) 😁을 😕과 비교하여 무언가에 있을 수 있음을 확인할 수 있습니다.

좀 더 강력한 것을 보려면 Big-O Cheat Sheet를 확인하십시오.

표기법 해독

표기법이 작동하는 방식을 이해하는 한 다양한 Big-O 값을 모두 외울 필요는 없습니다.

예를 들어, 끔찍한 끔찍한 O(2^n) . Ruby로 표현하면 다음과 같을 수 있습니다.

# O(2^n) translated to Ruby
def o(n)
  2 ** n  # This is ruby for 2^n
end

아직 명확하지 않습니까? 메서드와 인수의 이름을 더 사용자 친화적인 것으로 바꾸면 어떨까요?

# O(2^n) translated to prettier 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

...etc

표기법이 어떻게 작동하는지 알았으니 이제 몇 가지 일반적인 루비 코드를 살펴보고 어떤 관계가 있는지 살펴보겠습니다.

O(1)

어떤 것이 O(1)라고 말할 때 속도가 데이터 세트의 크기에 의존하지 않는다는 것을 의미합니다.

예를 들어 해시 조회 시간은 해시 크기에 따라 달라지지 않습니다.

# These should all take the same amount of time
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배 더 오래 걸립니다.

배열을 반복하는 많은 코드는 O(n)를 따릅니다. 무늬.

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

# This example is 1/2 the speed of the previous because it contains 2x the items. 
(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 로그 n)

O(n log n) 코드는 종종 O(n^2) 알고리즘은 할 것입니다.

코드 조각을 보고 O(n log n)라고 말할 수는 없습니다. . 이것은 더 높은 수학이 들어오는 곳이며 또한 제가 절하는 곳이기도 합니다.

그러나 O(n log n)에 대해 아는 것이 중요합니다. 많은 일반적인 검색 알고리즘을 설명하기 때문입니다. Ruby의 Array#sort 평균적으로 O(n log n)인 유서 깊은 퀵소트 알고리즘을 사용합니다. 최악의 경우는 O(n^2)입니다.

퀵정렬에 익숙하지 않다면 이 훌륭한 데모를 확인하십시오.

모든 것을 함께:귀하의 데이터베이스

새로운 웹 응용 프로그램의 가장 일반적인 문제 중 하나는 개발자의 컴퓨터에서는 빠르지만 프로덕션 환경에서는 점점 느려진다는 것입니다.

이는 데이터베이스의 레코드 양이 시간이 지남에 따라 증가하기 때문에 발생하지만 코드가 DB에 확장성이 좋지 않은 작업을 수행하도록 요청하기 때문에 발생합니다. 즉. O(n) 또는 더 나쁜.

예를 들어, postgres에서 count 쿼리는 항상 O(n) ?

# This makes the DB iterate over every row of Users
# ...unless you're using a Rails counter cache. 
Users.count

postgres explain를 사용하여 이를 확인할 수 있습니다. 명령. 아래에서는 카운트 쿼리에 대한 쿼리 계획을 가져오는 데 사용합니다. 보시다시피 테이블의 모든 104,791개 행에 대해 순차 스캔(루핑을 의미함)을 수행할 계획입니다.

# 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)

많은 커먼 레일 관용구는 의도하지 않은 순차 스캔을 유발할 수 있습니다. 특별히 이를 방지하기 위해 데이터베이스를 최적화하지 않는 한.

# This asks the DB to sort the entire `products` table
Products.order("price desc").limit(1)

# If `hobby` isn't indexed, the DB loops through each row of Users to find it. 
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)

이 모든 문제에 대한 답은 물론 인덱싱입니다. 데이터베이스에 인덱스를 사용하도록 지시하는 것은 Ruby에서 해시 조회 O(1)를 사용할 때와 약간 비슷합니다. 배열 대신 O(n) 찾기 .

그게 다야, 여러분

이것이 Big-O 표기법에 대한 유용한 소개이자 루비 개발자로서 당신에게 어떤 영향을 미쳤기를 바랍니다! 질문이 있으면 @StarrHorne에 핑을 보내주세요.