ทำไม Big-O จึงสำคัญสำหรับ Ruby Developers: คู่มือปฏิบัติจริง

ผมไม่มีปริญญา computer science หลาย Rubyists ไม่มี นานๆ ผมหลีกเลี่ยม Big-O notation ดูเหมือน higher math เกินไป O(N^2) อ่อ ไม่

แทนที่จะเรียนรู้ rules of thumb:

• หา item ใน Hash เร็วกว่า Array
• หลีกเลี่ยง nested loops
• ระวัง accidental DB queries ตอน generate lists ใน views

กฎเหล่านี้ดี แต่ห้าไม่เข้าใจ WHY มันทำงาน จะทำ mistakes และ performance problems ที่อธิบายไม่ออก

ทำไมมันสำคัญ?

Big-O notation แค่ fancy way อธิบายว่า performance ของโค้ดขึ้นกับปริมาณ data ที่ประมวลผลอย่างไร

Performance หมายถึงสองอย่าง: speed หรือ ram usage ใน CS class เรียกว่า "time complexity" และ "space complexity" Big-O ใช้ได้ทั้งคู่ แต่เน้น speed เพราะพบบ่อยกว่า

คาดว่า process array 100 items ช้ากว่า 10 items แต่ช้ากว่าเท่าไหร่? 10x, 100x? 1000x?

ไม่ใช่ปัญหา newbie datasets แต่ถ้า app ช้าลง exponentially ต่อแถวใน database เร็วๆ จะเป็นปัญหา

ก่อนรายละเอียด ผมทำ chart แสดง common big-Os พร้อม emoji แสดงความรู้สึกตอน data scales

ตอนใครบอก Array#bsearch ดีกว่า Array#find เพราะ O(log n) vs O(n) เปรียบเทียบ 😁 กับ 😕 เห็นว่าพวกเขาอาจถูก

อะไร solid กว่า ดู Big-O Cheat Sheet

ถอดรหัส Notation

ไม่ต้องจดทุก Big-O values แค่เข้าใจ notation ทำงานยังไง

เช่น O(2^n) แย่มาก แปลงเป็น Ruby อาจแบบนี้:

# O(2^n) แปลงเป็น Ruby
def o(n)
  2 ** n # Ruby สำหรับ 2^n
end

ยังไม่ชัด? ลอง rename method และ argument ให้ user-friendly

# 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
...etc

ตอนรู้ notation มาดู typical ruby code ว่าเกี่ยวข้องยังไง

O(1)

พูดว่า O(1) หมายถึง speed ไม่ขึ้นกับขนาด dataset

เช่น hash lookup times ไม่ขึ้นกับ hash size:

# ทั้งหมดควรใช้เวลาเท่ากัน
hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]

นี่คือเหตุที่บอกว่า hashes เร็วกว่า arrays สำหรับ larger datasets

O(n)

ในทางกลับกัน Array#find เป็น O(n) หมายถึงขึ้น linear กับจำนวน items array 100 items ใช้เวลา 100x array 1 item

โค้ด iterate arrays มากพอ follows O(n) pattern

(0..9).each do |i|
  puts i
end
# ตัวอย่างนี้ช้าครึ่งของก่อนหน้า เพราะมี items 2x
(0..19).each do |i|
  puts i
end

O(n^2)

โค้ด O(n^2) มักเกี่ยว nested loops ถ้าคิดจะเข้าใจ loop หนึ่งให้ O(n) nested loop ที่สองให้ O(n^2) ถ้า — เพราะเหตุผลอันร้ายแรง — มี 5-level nested loop จะเป็น 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) algorithm อย่างฉลาด

มองโค้ดงี้บอกว่าเป็น O(n log n) ไม่ได้ higher math ตรงนี้ และผมยอมแพ้

แต่รู้จัก O(n log n) สำคัญ เพราะอธิบาย common search algorithms มาก Ruby Array#sort ใช้ quicksort ซึ่ง average O(n log n) worst-case O(n^2)

ไม่รู้จัก quicksort ดู demonstration ยอดเยี่ยม

รวมกัน: Database ของคุณ

ปัญหา common ของ web apps ใหม่: เร็วบนเครื่อง developer แต่ production ช้าลงเรื่อยๆ

เพราะ records ใน database เพิ่มขึ้น ตอนโค้ดขอ DB ทำ operations ที่ไม่ scale ดี คือ O(n) หรือแย่กว่า

เช่น รู้ไหมใน postgres count queries เสมอ O(n)?

# ทำให้ DB iterate ทุก row ของ Users
# ...เว้นแต่ใช้ Rails counter cache
Users.count

เห็นได้ด้วย postgres explain ด้านล่าง query plan สำหรับ count query เห็นว่าวางแผน sequential scan (loop) ทั้ง 104,791 rows

# 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 idioms หลายอย่าง trigger unintentional sequential scans เว้นแต่ optimize database อย่างเฉพาะเจาะจง

# ขอให้ DB sort ทั้ง `products` table
Products.order("price desc").limit(1)
# ถ้า `hobby` ไม่ได้ indexed DB loop ทุก row ของ Users หา
User.where(hobby: "fishing")

用 explain ดูได้ ตัวอย่าง sort ทั้ง table (อาจ quicksort) หาก memory constraints อาจเลือก sorting algorithm อื่นที่มี performance characteristics ต่างกัน

# 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 บอก database ใช้ index คล้ายใน Ruby 用 hash lookup O(1) แทน array find O(n)

That's all, folks

หวังว่าเป็น intro Big-O notation ที่มีประโยชน์และ impact ให้คุณ as a ruby developer! Ping me @StarrHorne หากมีคำถาม