Wall of Text #9: Tree

น้องที่โรงเรียนให้ช่วยติวไปแข่งขันรายการหนึ่ง ซึ่งเราก็เคยไป จำได้ว่าคำถามที่เคยถามมีเกี่ยวกับ Data Structure เลยเล่าเรื่อง Tree ให้ เพราะในมัธยมไม่มีสอน

Tree Data Structure

โครงสร้างข้อมูลแบบ Tree แปลตรงตัวก็คือต้นไม้

แต่ละวงกลมในภาพ มีชื่อเรียกว่า Node แต่ละ Node จะมีตัวพ่อของมันเสมอ ยกเว้นด้านบนสุดของต้นไม้ ซึ่งดันเรียกว่าราก (Root)

Tree ที่อยากจะเล่าถึงเป็นพิเศษวันนี้คือ Binary Tree ซึ่งก็คือ Tree ที่มีลูก 0-2 กิ่ง

Math statement as a tree

การใช้งาน Binary Tree รูปแบบหนึ่งที่น่าสนใจคือเราสามารถแทนสมการคณิตศาสตร์เป็น Tree ได้ เช่น (1 +3) x 5 เขียนได้ดังนี้

ข้อสังเกตอย่างหนึ่งคือการเขียนเป็น Tree ช่วยลดการสับสนได้โดยไม่ต้องใส่วงเล็บ เช่น ถ้าเราเขียนสูตรด้านบนเป็น 1+3 x 5 แล้ว ตามลำดับความสำคัญของ operator เราจะต้องทำคูณหารก่อน คือ 1 + (3×5) ความหมายไม่เหมือนกัน

เมื่อเราแทนสูตรเป็น Tree แล้วก็ทำให้ประโยคไม่กำกวมเช่นเดียวกับการใส่วงเล็บ

Tree traversal

ยังอยู่กันที่ 1+(3×5)
(บทความนี้เผยแพร่ครั้งแรกเขียนว่าใช้ (1×3)+5 แต่รูปผิด เลยขอแก้สูตรให้ถูกต้อง)

เวลาเราไล่ Tree เราสามารถไล่ได้ 2 แบบดังนี้ (สมมุติว่ามองจากซ้ายไปขวา)

Depth first

แปลว่าไล่เอาด้านลึกลงก่อน เราจะได้

  • + จากด้านบนสุดก่อน
  • 1 เกาะด้านซ้าย ไม่มีลูกต่อกลับไปด้านบน
  • x จากด้านขวา
  • 3 จากด้านซ้าย
  • 5 จากด้านขวา

ส่วนมากที่จะพูดถึงต่อไปจะใช้ Depth first เป็นหลัก

Breath first

แปลว่าไล่เอาด้านกว้างก่อน เราจะได้

  • + จากแถวบนสุด
  • 1, x จากแถวที่สอง
  • 3, 5 จากแถวที่สาม

Project อันนึงที่เราเคยทำคือสำรวจความสัมพันธ์ของสองคนบน Steam ใช้ Breath first search เพื่อหาเส้นทางที่สั้นที่สุดระหว่างคนสองคนบน Steam (แต่นี่ไม่ใช่ Tree มันคือ Graph) เช่น

  • เราเป็นเพื่อนกับ A, B, C, …
  • A เป็นเพื่อนกับ A1, A2, A3, A4, …
  • B เป็นเพื่อนกับ B1, B2, B3, B4, …
  • C เป็นเพื่อนกับ C1, C2, C3, C4, …
  • ในชั้นแรกยังไม่เจอเป้าหมาย เราจะดูว่า A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4 เป็นเพื่อนกับใครบ้าง
  • A1 เป็นเพื่อนกับ A11, A12, A13, …
  • A2 เป็นเพื่อนกับ A21, A22, A23, …
  • ก็ยังไม่เจอ เราจะดูเพื่อนของ A11, A12, A13, A21, A22, A23, …
  • เราพบว่า A12 เป็นเพื่อนกับเป้าหมาย
  • สรุปว่า เส้นทางที่ใกล้ที่สุดคือ เรา -> A -> A1 -> A12 -> เป้าหมาย

ตอนที่ทำ ใช้สูตรโกงเล็กน้อยคือเราใช้ algorithm นี้สองข้างพร้อมกันเพื่อให้เร็วขึ้น

  • เราเป็นเพื่อนกับ A, B, C, …
  • เป้าหมายเป็นเพื่อนกับ ก, ข, ค, …
  • เอา set {A, B, C}, {ก, ข, ค} มา Intersect เพื่อดูว่าทับซ้อนหรือเปล่า
  • ถ้าไม่มีให้เปิดเพิ่มอีก 1 ชั้นของทั้งสองฝั่ง แล้วเอา set เพื่อนของเพื่อน ทั้งสองคนมา intersect กัน

Notation

นอกจากว่าเราจะไล่ลงด้านลึกก่อนหรือด้านกว้างก่อนแล้ว เรายังสามารถเลือกได้ด้วยว่าหัวของ tree จะอยู่ตรงไหน

กลับมาที่ (1+3)x5

Prefix

สมมุติว่าเราจะไล่ Depth first, Prefix เราจะเขียนหัวก่อนเสมอ ได้ว่า x + 1 3 5

ถ้าย้อนกลับไปอ่านหัวข้อ Depth first จะสังเกตว่าวิธีที่เราไล่ตอนนั้นคือแบบ Prefix

Infix

Infix จะเขียนหัวไว้ตรงกลาง เขียนได้ว่า 1 + 3 x 5

สังเกตว่าวิธีนี้จะเหมือนที่เราใช้เขียนสูตรตามปกติ เพื่อความชัดเจนทุกครั้งเราอาจจะใส่วงเล็บคร่อมเป็น ((1+3)x5) เพื่อไม่ให้กำกวมว่าต้องอ่านจากซ้ายไปขวา

Postfix

วิธีสุดท้ายคือเอาหัวไว้ด้านหลัง เขียนได้ว่า 1 3 + 5 x

Calculation

ประโยชน์อย่างหนึ่งของ Postfix คือเราสามารถหาคำตอบได้ง่ายๆ โดยไม่ต้องใส่วงเล็บ

วิธีการคือ เอาตัวเลขทีละตัวจากซ้ายไปขวามาทดไว้ ถ้าเจอเครื่องหมายให้ดึงตัวทด 2 ตัวล่าสุดมาทำตามเครื่องหมาย แล้วใส่เฉพาะคำตอบคืน

เช่นจากด้านบน (1+3) x 5 เขียนเป็น Postfix ได้ว่า 1 3 + 5 x

  • 1 ทดไว้
  • 3 ทดไว้ เป็น 1 3
  • เจอเครื่องหมาย + เอามาบวกกันได้ 4 แล้วใส่คืน
  • 5 ทดไว้ เป็น 4 5
  • เจอเครื่องหมายคูณ เอามาคูณกันได้ 20 เป็นคำตอบสุดท้าย

ถ้าเป็นรูปนี้ 1+(3×5) เราจะเขียน Postfix ได้ว่า 1 3 5 x +

  • 1 3 5 x ทดไว้ เจอเครื่องหมาย x เอาสองตัวล่าสุดคูณกัน 3 x 5 = 15 ใส่คืน
  • ตอนนี้ที่ทดอยู่คือ 1 15
  • 1 15 + เจอเครื่องหมายเอามาบวกกันได้ 16

ข้อสังเกตเวลาเราใช้เครื่องคิดเลขที่รองรับการป้อนข้อมูลแบบ Postfix

  • เราไม่ต้องทดเลขไว้ในใจ เช่นถ้าจะกด (1+3) x (2+5) เราต้องกด 1+3, 2+5 แล้วเอาคำตอบมาคูณกัน (อาจจะใช้ระบบ MS ของเครื่องคิดเลข) แต่ถ้าเป็น Postfix เราสามารถกด 1 3 + 2 5 + x ได้เลย
  • เราไม่ต้องกดเครื่องหมาย = เพื่อหาคำตอบสุดท้าย เพราะตัวสุดท้ายเป็นเครื่องหมายคณิตศาสตร์เสมอ

Tree ใช้ตอนไหน

นอกเหนือจาก Binary Tree ที่มีแค่สองขาแล้ว Tree ธรรมดาก็มีประโยชน์หลายอย่าง เช่น

Abstract Syntax Tree

เวลาเขียนโปรแกรมแล้ว Compile ตัว Compiler จะสร้าง Tree จากโปรแกรมของเรา

เช่นโปรแกรมนี้

if (x == 0) {
   x = x + 1;
}
print("%d", x);

เขียนเป็น Tree ได้ว่า

ซึ่งถ้าเราลองคิดตาม Tree แบบ Depth first ดูก็จะพบว่าได้ลำดับการทำงานเหมือนกับโปรแกรมเดิมเลย ซึ่งช่วยให้ compiler สามารถแปลงโค้ดโปรแกรมต่อเป็นภาษาเครื่องได้ง่าย

หาข้อมูล

เราสามารถใช้ Tree เก็บข้อมูลเพื่อให้หาข้อมูลได้ง่ายๆ เช่น

จากภาพนี้ถ้าเราต้องการหาคำว่า bag ว่ามีหรือไม่ เราก็ไล่ไปทีละตัว คือ b, a, แล้วชั้นสุดท้ายพบว่าไม่มี g แสดงว่าไม่มีคำนี้

เมื่อเทียบกับการเขียนทุกคำคือ app, apt, ape, ace, act, bad, ban, bat แล้วไล่จากซ้ายไปขวา การใช้ tree ไวกว่ากันเยอะ

Wall of Text #6: When O(1) doesn’t matter

ไม่แน่ใจว่าเปิดประเด็นนี้มาได้ยังไง

ตอนเรียนปีสองจะมีวิชา Data Structure ซึ่งเราจะได้เรียนว่า Data Structure ต่างๆ มี Time complexity เท่าไร ทวนให้อีกครั้งหนึ่งคือ

ArrayList (Vector) คือการสร้าง Array ขึ้นมาเก็บข้อมูล ดังนั้นการเข้าถึงสมาชิกใดๆ ใน Array เป็น O(1) แปลว่าไม่ว่าจะเข้าตัวไหนก็ใช้เวลาเท่ากันหมด

แต่ถ้าหากต้องการเพิ่มสมาชิกของ Array แล้ว มีโอกาสที่ Array เต็มซึ่งจะต้องสร้าง Array ใหม่ที่ใหญ่ขึ้นแล้ว copy ข้อมูลเก่าลงไป ดังนั้นเวลาที่ใช้คือ O(n) หรือแปลผันตามจำนวนสมาชิกของ Array

LinkedList เป็นการสร้างระเบียนข้อมูล 1 ชุด ในระเบียนจะเก็บข้อมูล, ที่อยู่ (Pointer) ของระเบียนถัดไป และถ้าเป็น Doubly Linked List จะมีที่อยู่ของระเบียนก่อนหน้าด้วย

การเข้าถึงสมาชิกใน LinkedList จึงต้องกระโดดจากระเบียนหนึ่งไปอีกระเบียนหนึ่ง ถ้าหากต้องการเข้าถึงระเบียนสุดท้ายก็ต้องใช้เวลา O(n) คือกระโดดผ่านทุกสมาชิก

วิธีที่จะทำให้เร็วขึ้นคือ เก็บทั้งตัวแรกและตัวสุดท้ายไว้ ตัวที่จะเข้าถึงช้าสุดก็คือตัวตรงกลางแทน วิธีนี้ก็ยังเขียนสัญกรณ์ Big O เป็น O(n) อยู่ดี

แต่ถ้าต้องการเพิ่มสมาชิกเข้าไป เราเพียงแค่สร้างช่องใหม่และเพิ่มตัวชี้เข้าไปยังระเบียนสุดท้ายของเดิม เป็นอันเรียบร้อย แบบนี้จะเป็น O(1)

จากข้อสรุปนี้เราก็จะทราบว่า ถ้าข้อมูลที่ต้องการเพิ่มต่อท้ายบ่อยๆ ใช้ LinkedList จะเร็ว นอกเหนือจากนั้นแล้วใช้ ArrayList ดีกว่า


แต่ตอนปีสามผมได้ฟัง Talk ของ James Gosling ผู้สร้างภาษา Java (เสียดายที่หาไม่เจอแล้ว) เค้าบอกว่าคุณไม่ควรใช้ LinkedList เลย ให้ใช้ ArrayList เสมอ

เพราะอะไร? คำตอบสั้นๆ คือ CPU Cache

ตอนนั้นผมได้ยินแล้วรู้สึกตื่นเต้นมาก เพราะมันคือศึกระหว่างวิชา Data Structure กับวิชา Computer Architecture เลยทีเดียว

Benchmark

เว็บไซต์ DZone ได้ทดลองวัดผลดูแล้ว (แนะนำให้ดูกราฟจากต้นทาง) พบว่าการแทรกสมาชิกใหม่ที่เราทราบดีว่า LinkedList เป็น O(1) นั้นกลับช้ากว่า ArrayList!

สิ่งที่เกิดขึ้น เค้าอธิบายว่าเนื่องจากว่า RAM ทำงานได้ช้า CPU จึงจะนำข้อมูลบางส่วนใน RAM เข้ามาพักบน Memory ที่อยู่บน CPU หรือเรียกว่า CPU Cache

แล้วการเลือกข้อมูลที่จะมาพักทำอย่างไร? วิธีที่ CPU ทำคือเมื่อมีการเข้าถึงข้อมูลที่ไม่อยู่บน Cache แล้ว CPU จะดึงข้อมูลนั้นจากใน RAM เข้ามา และข้อมูลที่อยู่โดยรอบด้วย

ดังนั้น Array ซึ่งเก็บข้อมูลเป็นชุดติดกันจึงได้ประโยชน์จากกระบวนการนี้มาก เพราะเมื่อเราเข้าถึงสมาชิกตัวหนึ่งแล้ว CPU จะดึงตัวติดกันมาด้วย ถ้าเราวนไล่สมาชิก Array ก็จะทำงานได้เร็วมาก สมบัตินี้เรียกว่า Locality

ในขณะเดียวกัน ถึงแม้ว่าการหาสมาชิกตัวถัดไปของ LinkedList จะเป็น O(1) เช่นกัน แต่จะใช้เวลานานกว่ามาก เพราะแต่ละระเบียนไม่ได้อยู่ติดกัน CPU จะต้องดึงข้อมูลจาก RAM ใหม่ทุกครั้ง

จากการทดสอบแล้วก็จะพบว่า overhead ตรงนี้ของ LinkedList แค่จะเปิดหาตัวสุดท้ายมาเพิ่มระเบียนใหม่ก็ช้ากว่า Copy Array แล้ว

ทั้งนี้ถ้า Array มีข้อมูลใหญ่มากๆ ก็ยังอาจจะแพ้ LinkedList อยู่ดีเพราะประสิทธิภาพของ LinkedList ไม่ได้ขึ้นอยู่กับขนาดของข้อมูลเลย ขึ้นอยู่กับจำนวนข้อมูลเท่านั้น

Don’t Premature Optimize

คำแนะนำหนึ่งที่ผมชอบคือ “Premature optimization is the root of all evil” อย่ามัวพะวงว่าโปรแกรมเราช้าเพราะเรื่องเล็กๆ แบบนี้ เพราะบางทีเรา optimize ตรงนี้เป็นอย่างดีแล้วอาจจะเร็วขึ้นแค่ 3% ก็ได้แต่เสียเวลาทำไปหลายวัน

ถ้าอยากจะ optimize ควรจะต้องวัดผลจากการใช้งานจริงให้รู้แน่เสียก่อนว่าตรงไหนช้า ถึงจะ optimize ได้ถูกจุด