คู่มือนักทับทิมสำหรับสัญลักษณ์ Big-O

ฉันไม่จบปริญญาวิทยาการคอมพิวเตอร์ พวกเราหลายคน Rubyists ไม่ทำ ดังนั้นฉันจึงหลีกเลี่ยงการเรียนรู้เกี่ยวกับสัญกรณ์ big-O เป็นเวลานาน มันดูคล้ายกับคณิตศาสตร์ที่สูงกว่าเล็กน้อย ฉันหมายถึง:O(N^2) . มาเร็ว.

แต่ฉันได้เรียนรู้กฎทั่วไป:

การค้นหารายการเฉพาะใน Hash นั้นเร็วกว่าใน Array
หลีกเลี่ยงการวนซ้ำซ้อน
ระวังการสืบค้นฐานข้อมูลโดยไม่ได้ตั้งใจเมื่อสร้างรายการในมุมมองของคุณ

กฎเหล่านี้ดี แต่ถ้าคุณไม่เข้าใจ WHY มันใช้งานได้ คุณจะพบว่าตัวเองทำผิดพลาดและมีปัญหาด้านประสิทธิภาพที่อธิบายไม่ได้

เหตุใดจึงสำคัญ

สัญกรณ์ Big-O เป็นเพียงวิธีการที่สวยงามในการอธิบายว่าประสิทธิภาพของโค้ดของคุณนั้นขึ้นอยู่กับปริมาณข้อมูลที่ประมวลผลอย่างไร

ประสิทธิภาพหมายถึงหนึ่งในสองสิ่ง:ความเร็วหรือการใช้แรม ในชั้นเรียนวิทยาการคอมพิวเตอร์ คุณจะเรียกสิ่งเหล่านี้ว่า "ความซับซ้อนของเวลา" และ "ความซับซ้อนของอวกาศ" สัญกรณ์ Big-O ใช้สำหรับทั้งคู่ แต่เราจะเน้นที่ความเร็วที่นี่ เนื่องจากดูเหมือนว่าจะเป็นการใช้งานทั่วไปมากกว่า

คุณคาดหวังว่าการประมวลผลอาร์เรย์ 100 รายการจะช้ากว่าอาร์เรย์ 10 รายการ แต่เท่าไหร่? 10 เท่า 100 เท่า? 1000x?

ไม่ใช่เรื่องใหญ่สำหรับชุดข้อมูลขนาดเล็ก แต่ถ้าแอปของคุณทำงานช้าลงอย่างมากในแต่ละแถวในฐานข้อมูล ในไม่ช้าก็จะกลายเป็นปัญหา

ก่อนที่เราจะลงรายละเอียด ฉันได้สร้างแผนภูมิสั้นๆ ที่แสดง Big-O ทั่วไปพร้อมอิโมจิที่แสดงให้เห็นว่าสิ่งเหล่านี้จะทำให้คุณรู้สึกอย่างไรเมื่อข้อมูลของคุณมีขนาดเท่ากัน

บิ๊กโอ	อันดับ	ความหมาย
O(1)	😎	ความเร็วไม่ได้ขึ้นอยู่กับขนาดของชุดข้อมูล
O(ล็อก n)	😁	ข้อมูล 10 เท่า มีเวลาเพิ่มขึ้น 2 เท่า
O(n)	😕	ข้อมูล 10 เท่า มีเวลามากขึ้น 10 เท่า
O(n บันทึก n)	😖	ข้อมูลเพิ่มขึ้น 10 เท่า มีเวลาเพิ่มขึ้นประมาณ 20 เท่า
O(n^2)	😫	ข้อมูล 10 เท่าใช้เวลามากขึ้น 100 เท่า
O(2^n)	😱	ผลึกดิลิเธียมกำลังแตก!

ดังนั้นเมื่อมีคนพูดว่า Array#bsearch ดีกว่า Array#find เพราะมันคือ O(log n) vs 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 รายการจะใช้เวลาค้นหานานกว่าอาร์เรย์ที่มีรายการเดียว 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) โปรไฟล์มักจะเกี่ยวข้องกับการวนซ้ำซ้อน มันสมเหตุสมผลถ้าคุณคิดเกี่ยวกับมัน One loop ให้ 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) เพราะมันอธิบายอัลกอริธึมการค้นหาทั่วไปจำนวนมาก Array#sortของ Ruby ใช้อัลกอริธึม Quicksort ที่น่ายกย่อง ซึ่งโดยเฉลี่ยแล้วคือ O(n log n) และกรณีที่เลวร้ายที่สุดคือ O(n^2)

หากคุณไม่คุ้นเคยกับ Quicksort ลองดูการสาธิตที่ยอดเยี่ยมนี้

รวมทุกอย่างเข้าด้วยกัน:ฐานข้อมูลของคุณ

ปัญหาที่พบบ่อยที่สุดอย่างหนึ่งของเว็บแอปพลิเคชันใหม่คือมันเร็วบนคอมพิวเตอร์ของนักพัฒนา แต่ในการใช้งานจริงจะช้าลงและช้าลง

สิ่งนี้เกิดขึ้นเนื่องจากจำนวนเร็กคอร์ดในฐานข้อมูลของคุณเพิ่มขึ้นเมื่อเวลาผ่านไป แต่โค้ดของคุณขอให้ DB ดำเนินการที่ปรับขนาดได้ไม่ดี เช่น. O(n) หรือแย่กว่านั้น

ตัวอย่างเช่น คุณทราบหรือไม่ว่าใน postgres การนับข้อความค้นหาจะเป็น 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 และผลกระทบต่อคุณในฐานะนักพัฒนาทับทิม! โปรด ping ฉัน @StarrHorne หากคุณมีคำถามใด ๆ