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 #8: เวลา

จริงๆ ก็หมด content แล้ว เพราะน้องที่ทำให้ผมเริ่มซีรีส์นี้เค้าหนี 100 days of code ไปเที่ยวแล้ว แต่พอดีว่าเจอบั๊ก เลยอยากเล่าเรื่องเวลาสักหน่อยเพราะเป็นเรื่องที่น่าปวดหัวมาก

ถ้าขี้เกียจอ่าน ขอแนะนำให้ดูคลิปนี้ซึ่งคงจะเล่าได้สนุกกว่าที่ผมจะเขียนเยอะ

สมัยนึงผมคิดว่าเวลาเป็นเรื่องง่ายๆ โดยเฉพาะเมื่อมาเขียนโค้ดที่ต้องเก็บเวลาแล้วทุกคนน่าจะเคยคุ้นตากับ UNIX Time ซึ่งเก็บจำนวนวินาทีตั้งแต่ 1 มกราคม 1970

ข้อดีอย่างหนึ่งของ UNIX Timestamp คือเราสามารถหาผลต่างของ 2 เวลาได้ง่าย เพียงแค่เอามาลบกันก็จะได้จำนวนวินาทีในช่วงเวลานั้น

ปัญหามันอยู่ที่ว่า เวลาแต่ละที่ในโลกไม่เหมือนกัน…

Timezone

ครั้งหนึ่งผมก็เคยคิดว่า ลูกค้าเราอยู่ในประเทศไทยเท่านั้น ถ้าอย่างนั้นเราก็ตั้ง Timezone ทุกที่ในโค้ดเป็นบวก 7 ชั่วโมง หรือเขตเวลาของประเทศไทยก็น่าจะจบ

ปรากฏว่า ทำไปพักหนึ่งก็วุ่น เนื่องจากระบบหลายอย่างมักจะอ้างอิงจากเขตเวลาสากล (UTC) อยู่ดี เช่น UNIX Time ตามมาตรฐานนั้นกำหนดให้ใช้เวลาที่เขตเวลา UTC แล้ว Library มันก็จะไม่ถามเราเลยว่าเอาเขตเวลาอะไร

เนื่องจากเราเขียนโค้ดโดย assume เขตเวลาประเทศไทยแล้ว เมื่อ user กรอกข้อมูลมาว่าตั้งเวลาแจ้งเตือน 2019-07-06 14:00:00 เราเอาเข้า function convert เป็น UNIX Time มันก็คืนให้เราเป็น 1562421600 ซึ่งก็เป็นเวลาที่ถูกต้องแต่เขตเวลาเป็น UTC พอแปลงเป็นเวลาไทยคือ 3 ทุ่ม แทนที่จะเป็นบ่ายสองตามที่ตั้งใจไว้

สองคือการเก็บวันอย่างเดียวก็ยุ่งยากและมีปัญหา… เพราะถ้าเราเก็บเป็น UNIX Timestamp โดยกำหนดให้เวลาเป็น 0 หมด (เช่น 2019-07-16 00:00:00) ถ้าเราดันไปใช้ค่าเวลานั้นในฟังค์ชั่นที่รับข้อมูลเป็น Date + Time แล้ว มันอาจจะแปลงเขตเวลากลับเป็น UTC ทำให้กลายเป็นวันก่อนหน้าเวลา 17:00น. พอเราแปลงกลับเป็นวันที่อย่างเดียว ก็ผิดวันซะอย่างนั้น

Always use Timezone

Django สอนผมไว้ว่า เปิด Timezone เหอะ สมัยนึงมันเคยปิดได้ ตอนนี้ปิดไม่ได้แล้ว แล้วมันจะเตือนเสมอถ้าเราใส่เวลาไปโดยไม่บอกเขตเวลา

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

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

Birthday

ปัญหาถัดมาคือวันเกิด ซึ่งปวดหัวมาก เพราะคน Gen Y วันเกิดสามารถแทนด้วย UNIX Timestamp ได้เป็นเรื่องปกติ เราก็ออกแบบโปรแกรมไปอย่างนั้น พอไปใช้จริงเจอคนคนยุคก่อนหน้านี้ซึ่งเกิดก่อน 1 มกราคม 1970 แล้วจะแทนอย่างไร?

ผมก็ยังไม่เคยหาคำตอบ เพราะส่วนมากภาษาจะมีไลบรารีที่เกี่ยวข้องกับวันเวลาไว้ให้แล้ว เราก็ให้มันเก็บข้อมูลให้เลย ไม่ได้สนใจว่าด้านหลังจะทำงานอย่างไร

แต่ที่ร้ายไปกว่านั้นคือบางคนไม่ทราบวันเกิดตัวเอง ทราบเพียงแต่ปีเกิด (บางทีก็ไม่ทราบ ไปประมาณเอา) ยิ่งแล้วใหญ่ แทนในระบบไม่ได้เลย ส่วนมากผู้ใช้งานก็จะแก้ขัดโดยระบุวันที่เป็นวันที่ 1 มกราคมของปีนั้นๆ ไป แต่บางระบบก็อาจจะจำเป็นจะต้องเพิ่มช่องให้ระบุได้ว่าไม่ทราบวันที่

History is Hard

อันนี้เพิ่งเจอมาสดๆ ร้อนๆ คือเราก็คิดว่าระบุเวลา 2019-07-06 14:00:00 เขตเวลา Asia/Bangkok เราก็คิดว่ามั่นใจไม่มีทางหลุดหรอก

แต่ปรากฏว่าเวลาที่ได้จริงกลับใช้เขตเวลา +06:42 ไม่ใช่ +07:00 แล้วทำให้การประมวลผลข้อมูลที่เหลื่อมกันผิดพลาดไปซะอย่างนั้น

เอ๊ะ ยังไง เวลาประเทศไทยเป็น +07:00 ไม่ใช่หรอ ใครๆ ก็รู้??

ปรากฏว่าในประเทศไทยก่อนวันที่ 31 มีนาคม 2463 ใช้เขตเวลา +06:42 ส่วนตั้งแต่เวลา 1 เมษายนเป็นต้นไปจะใช้เขตเวลา +07:00

โอ้พระสงฆ์

ทีนี้พอเราระบุเขตเวลาเฉยๆ มันไม่ทราบว่าเราหมายถึงเขตเวลาตอนไหน เพราะถ้าเราระบุวันที่ก่อนปี 2463 จะต้องใช้เขตเวลาเดิม แต่ถ้าหลังจากนั้นต้องใช้เขตเวลาใหม่

วิธีแก้ใน Python ก็คือ ไลบรารี pytz จะมีฟังค์ชั่น localize ที่รับเวลาเข้าไปพร้อมเขตเวลา เสร็จแล้วมันจะไปคิดเอาเองว่าวันที่และเวลานี้ สถานที่นี้ควรจะใช้เขตเวลาอะไร

Astronomy is Hard

อันนี้ยังไม่เคยเจอ แต่อยากเล่าให้ฟัง

นักดาราศาสตร์ได้สังเกตว่าโลกเริ่มหมุนช้าลง จึงมีการกำหนดให้เพิ่มเวลาไปอีก 1 วินาทีตามเวลาที่กำหนด ก็คือในวันนั้น นาฬิกาจะเดิน

  • 23:59:58
  • 23:59:59
  • 23:59:60
  • 00:00:00

1 นาทีมี 61 วินาที!

ใน UNIX Time ก็จะใช้วิธีคือย้ำเวลาเดิม คือเวลาจะเดิน 1 2 3 3 4 5 .. ทำให้เวลา UNIX ไม่ตรงกับเวลาสากล

พอเวลาซ้ำแบบนี้ได้แล้ว ก็อาจเกิดปัญหาขึ้น เช่น ถ้ามีรายการหนึ่งที่ทำที่เวลา 3.98 แล้วอีกรายการทำทีหลังแต่วินาทีที่ 3 วนซ้ำ เลยได้ timestamp เป็น 3.14

เมื่อเราเอารายการมาเรียงกัน รายการทำทีหลังกลับ timestamp อยู่ก่อน และถ้าเอาเวลามาลบกันก็จะทำ leap second ตกหายไปอีกด้วย

วิธีที่ Google แก้ปัญหานี้คือ Leap Smear เนื่องจาก Google ต้องการให้รายการที่ทำทีก่อนอยู่ก่อนรายการที่ทำที่หลังเสมอ จึงกำหนดให้วันที่มีการแทรก Leap second นั้นเวลาบน Server จะเดินช้าลงเล็กน้อยตลอดทั้งวันแทน เมื่อ Leap second ผ่านไปแล้วเวลาก็จะกลับมาตรงกันอีกครั้ง วิธีนี้ทำให้เราไม่ต้องมีวินาทีซ้ำ 2 ครั้ง

ถ้าใครใช้เครื่อง Google Compute Engine เวลาบนเครื่องก็จะถูก Leap Smear อัตโนมัติ หรือถ้าอยู่ข้างนอกก็สามารถใช้ NTP Server ของ Google ได้

Monotonic Time

ปัญหานี้ใกล้ๆ กันกับปัญหาข้างบน แต่อันนี้อาจจะเจอได้ด้วยตัวเอง

คือเวลาเรา Benchmark โปรแกรม ท่าที่เราคิดก็คือ Read unix time ที่ละเอียดที่สุดเท่าที่เป็นไปได้มาเก็บไว้, ทำงานบางอย่าง แล้วเอา Unix time ตอนสุดท้ายมาลบออกกับเวลาแรกก็จะได้เวลาที่ใช้ทำงานนั้น

ฟังดูดีไม่มีปัญหา แต่ท่านี้ก็ไม่รอด…

เพราะนาฬิกาในคอมพิวเตอร์มันตั้งเวลาได้ ดังนั้นระหว่างการวัด 2 ครั้งนั้น NTP อาจจะทำงานแล้ว sync เวลาเครื่องถอยหลังกลับไป อาจจะมากถึง 1-2 วินาที พอเราอ่านค่าเวลาใหม่มันก็จะถอยหลังไปตามนั้นด้วย

ปัญหานี้อาจจะเห็นผลยิ่งชัดถ้าหาก operation นั้นใช้เวลานาน เช่น test เรื่อง Network call โปรแกรมบางตัวก็ไม่ชอบเท่าไรนักหากเวลาเดินย้อนหลัง เช่น Dovecot

วิธีแก้ไขคือ ระบบปฏิบัติการต่างๆ จะมีเวลาที่เรียกว่า Monotonic timer ซึ่งจะนับตลอดตั้งแต่เปิดเครื่องคอมพิวเตอร์ โดยการันตีว่าเดินไปข้างหน้าอย่างเดียว ตั้งเวลาถอยหลังไม่ได้

แต่มีข้อแม้คือ Monotonic timer ไม่ได้อ้างอิงกับเวลาใดๆ ทั้งสิ้น เราจึงไม่สามารถแปลงเป็นเวลาตามนาฬิกา (เรียกว่า Wallclock timer) หรือเอาไปเทียบกันระหว่างเครื่องคอมพิวเตอร์ 2 เครื่องได้ ทำได้อย่างเดียวคือใช้เปรียบเทียบระหว่าง 2 ช่วงเวลาบนคอมพิวเตอร์เครื่องนั้น

Use a Library

สุดท้ายนี้คงต้องใช้ประโยคคลาสสิค จำได้ว่าเคยพูดนานมากแล้วในเรื่อง Web Framework ซึ่งก็ยังใช้ได้กับเรื่องนี้เหมือนกัน

ถ้าจะทำ Date time manipulation เนี่ย ไปใช้ Library เถอะครับ ไปนั่งทำเองปวดหัวแน่นอน มันอาจจะเจอกับดักอื่นๆ ที่ผมยังไม่ได้เจอแล้วไม่ได้เล่าในบล็อคนี้ก็ได้

เท่าที่สังเกตดู ภาษายุคใหม่ๆ ก็จะเริ่มบังคับให้ใช้ Library มากขึ้น เช่น Rust หรือ Go ถ้าอยากทราบเวลาปัจจุบันต้องเรียกใช้ time.Now() และมันไม่ได้คืนค่าเป็น UNIX Time แล้ว ถ้ายังอยากใช้ต้องแปลงเอง