Jan 1, 2016

สรุปปี 2014-2015

เพิ่งเห็นว่าลืมเขียนของปี 2014 ตอนแรกก็ว่าจะแยกโพสออกไปแล้วตั้งเวลาย้อนหลัง แต่พอไล่ลิสต์ดูแล้วปีนั้นก็ไม่ค่อยได้ทำอะไรเท่าไหร่ ไม่เป็นไรงั้นรวบทั้ง 2 ปีมาไว้ตรงนี้เลยละกัน จะได้ดูเหมือนได้ทำอะไรเยอะแยะ 555

  • ตีพิมพ์งานวิชาการนานาชาติ งานนี้ทำกับ @lewcpe และ @pruet ตีลง Springer โดยเสนอวิธีการทำให้รหัสผ่านแข็งแรงขึ้นแต่ก็ยังจดจำได้
  • สัมมนาวิชาการนานาชาติ ต่อเนื่องจากอันบนครับ .. โอเคแม้ว่างานสัมมนาจะจัดที่ไทย แต่ก็เป็นระดับภูมิภาคชาวต่างชาติมากันเต็ม แย่หน่อยที่ตอนนั้นยังขี้อายเลยทำให้ไม่ค่อยได้หาเพื่อนใหม่เท่าไหร่ (ถ้าไม่ได้อาจารย์ @dittaya ช่วยไว้คงแย่อะ)
  • เป็นอาจารย์พิเศษ เสียดายอย่างว่าก่อนวันสัมภาษณ์เกิดเหตุการณ์ไม่สงบทางการเมือง จนทำให้การจราจรติดขัดอดได้งานเลย
  • อ่านนิยายสถาบันสถาปนาของอาซิมอฟ รู้สึกว่าเป็นนิยายที่ดีเกือบๆ จะที่สุดเท่าที่เคยอ่านมาเลย
  • ไปฮ่องกง-มาเก๊าครั้งแรก อันฃนี้ไม่มีอะไรมาก เที่ยวขำๆ วันปีใหม่ ได้เห็นอะไรแปลกๆ เยอะดี ชอบสุดคือระบบขนส่งมวลชนที่โคตรจะสะดวกและรวดเร็ว
  • จบป.โท จบตรงตามเวลา น่าจะเป็นเพราะเรียนสายประยุกต์ด้วย งานวิจัยเลยไม่ได้ยากมากเท่าเพื่อนๆ ที่เรียนเพียว ทำให้ยังจบได้ตามกำหนด (ถ้าเรียนเพียวอาจจะช้ากว่านี้ 555)
  • เดินทางเยอะมาก เนื่องจากรับงานกับอาจารย์ @jittat ทำให้ได้ไปเที่ยวมหาวิทยาลัยเกษตรศาสตร์ครบทุกวิทยาเขตเลย พอกลับมาที่บ้านก็เจอพ่อกับแม่พาตะลุยขับรถเที่ยวไทยอีก ทำให้ช่วงนี้เมารถง่ายหน่อยนะ @_@
  • กลับมาสเก็ตช์รูปบ่อยเหมือนก่อนแล้ว หลังจากหันหน้าเข้าหาคีย์บอร์ดมาหลายปี พอได้ปากกาดีๆ มาใช้เลยทำให้มีอาการอยากวาดภาพขึ้นหลายเท่าตัว
  • ไม่ดองเกมแล้ว จริงๆ อันนี้ไม่ค่อยดีเท่าไหร่ (ในแง่เบียดบังเวลาที่ควรจริงจัง) แต่ก็ทำให้ตอนนี้พูดได้อย่างเต็มปากแล้วว่าไม่ได้ซื้อเกมมาดองไว้เฉยๆ นะ 555

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

  • ย้ายบล็อกไปไว้ที่อื่น ขั้นพื้นฐานขอให้แทรกโค้ดโปรแกรมกับสมการได้ง่ายๆ ตอนนี้ดูโปรเจค pagist ของ @dtinth ไว้อยู่ หวังว่าจะดัดแปลงเอามาใช้ได้ไม่ยากเย็นนะ
  • อ่านหนังสือให้จบเดือนละสองเล่ม ดูเหมือนเยอะนะ แต่เพราะว่านี่เป็นคนอ่านแล้วดอง (ตอนนี้ดองไว้ร่วมสิบเล่มแล้ว) อ่านไปได้ซัก 40% ไม่ว่าจะสนุกแค่ไหนจะเริ่มรู้สึกกลัวมันจบ แต่ถ้าพยายามอ่านไปจนซัก 75% จะกลับมามีแรงฮึดอ่านรวดเดียวจบละ
  • เขียนบล็อกให้ได้เดือนละครั้ง อันนี้พังพินาศมานานแล้ว ต้องขยันๆ หน่อย ปัญหาสำคัญคือมีเรื่องที่อยากเขียนแล้วแต่ก็รู้สึกว่ามันสั้นไป (ปัจจุบันมีบล็อกดองอยู่เป็นร้อยตอนแล้ว) ควรจะลดความคาดหวังลงว่าเรื่องที่เอามาเขียนต้องคิดตกตะกอนมาจนสมบูรณ์แบบก่อน คือเขียนๆ ไปเลยถ้าจะมีรายละเอียดที่ผิดนิดผิดหน่อยก็ช่างมัน ตอนนี้พยายามให้ใจความสำคัญชัดเจนไว้เป็นพอ
  • เขียนหนังสือให้เสร็จ อันนี้ก็พังพินาศมานานแล้วเหมือนกัน ยังรอดอยู่ได้ไม่โดน @markpeak เอาไม้ฟาดหัวก็ดีแค่ไหนแล้ว T^T
  • เริ่มมองหางานประจำ/ที่เรียนต่อ โอเคว่ามันต้องเลือกเอาซักอย่าง ภายในครึ่งปีนี้ก็ควรไปนั่งคิดดูดีๆ ว่าจะไปเส้นทางไหนกันแน่
  • ลดน้ำหนัก ปีก่อนๆ มันกลับมาขึ้นอีกแล้ว ว่าจะพยายามดันมันลงไปใหม่อีกที หลังจากกินดีอยู่ดีมาพักใหญ่

ลองดูแค่นี้ก่อน ไม่แน่ใจว่าเยอะเกินไปหรือยัง กลัวว่าพอตั้งเป้าเยอะมากเกินไปเดี๋ยวจะรู้สึก overwhelm แล้วก็พังพินาศทุกอันอีก

เจอกันใหม่ในอีกครึ่งปีครับ

Dec 29, 2015

เจองานจับฉลากแลกของขวัญที่มีคนได้ของตัวเอง ไม่ต้องตกใจไปโอกาสมีสูงเกินครึ่ง

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

แต่ก่อนอื่นต้องเข้าใจกฎการแลกของขวัญ ซึ่งมีขั้นตอนประมาณนี้
  1. ทุกคนซื้อของขวัญมาร่วมสนุกในงานคนละอย่าง โดยเอาของขวัญใส่กล่องไว้ไม่ให้ใครรู้ว่าด้านในเป็นอะไร
  2. พอแต่ละคนไปถึงงาน คนจัดงานจะแปะป้ายชื่อเจ้าของของขวัญไว้กับกล่อง พร้อมหย่อนฉลากรายชื่อของคนนั้นลงไห
  3. เมื่อถึงเวลาแลกของขวัญ ให้ประธานในพิธีหรือใครซักคนที่ใหญ่ที่สุดในงาน เป็นคนเริ่มจับฉลากรายชื่อจากไหเป็นคนแรก
  4. ประธานจับได้ชื่อใครก็เอากล่องของขวัญของคนนั้นไป แล้วก็ให้คนที่โดนจับชื่อเมื่อกี้ เป็นคนเริ่มจับฉลากในไหวนต่อไปเรื่อยๆ
  5. ถ้าเกิดมีคนจับได้ชื่อประธาน จะถือว่าเป็นการแลกของขวัญที่ครบรอบวง ก็ให้คนนั้นเอาของขวัญของประธานไป แล้วผู้จัดงานเลือกใครซักคนจากคนที่ยังไม่ได้จับของขวัญ มาเป็นหัวจับของขวัญรอบต่อไป
  6. การแลกของขวัญจะสิ้นสุดลงเมื่อไม่มีฉลากรายชื่อเหลือในไห
จากกฎนี้เห็นได้ชัดว่า เมื่อถึงตอนใกล้จบการแลกของขวัญที่มีฉลากรายชื่อในไหเหลือแค่ 2 ใบ ใบนึงจะเป็นของคนแรกและอีกใบเป็นของคนที่ยังไม่ได้จับฉลาก ดังนั้นโอกาสที่คนจับก่อนจะจับฉลากได้ชื่อคนแรกและบังคับให้คนสุดท้ายจับชื่อตัวเอง โอกาสนี้จะสูงถึง 50% เลย

ยกตัวอย่างให้ชัดขึ้นไปอีก สมมตินายประธานเป็นคนจับฉลากคนแรก แล้วก็มีคนจับตามๆ กันมาอีกหลายคน จนตอนสุดท้ายเหลือคนที่ยังไม่ได้จับฉลาก 2 คนคือสมศักดิ์กับมานี ถ้าคนก่อนหน้าจับฉลากได้ชื่อสมศักดิ์ แปลว่าสมศักดิ์จะเป็นคนจับฉลากคนต่อไป แต่รายชื่อในไหตอนนี้จะเหลือแค่มานีกับประธานเท่านั้น ที่โอกาสครึ่งๆ ถ้าสมศักดิ์จับได้ชื่อประธาน ก็จะเหลือคนไม่ได้จับฉลากคือมานี และฉลากที่เหลือในไหก็เป็นชื่อมานี นั่นก็คือมานีจะต้องจับฉลากได้ของขวัญของตัวเองแน่นอน

โอกาสที่ในงานแลกของขวัญงานหนึ่ง จะมีคนได้ของขวัญเป็นของตัวเองสูงถึง 50% ซึ่งจริงๆ แล้วโอกาสน่าจะมากกว่านี้อีกนิดหน่อยด้วยซ้ำ เพราะยังไม่ได้คิดโอกาสที่คนกลางๆ จะจับได้ของตัวเองทันทีหลังจากเกิดการจับฉลากครบรอบวงเลย



คิดได้แค่นี้ก็พอใจแล้ว แต่ก็โดน @NungNing ถามต่อว่า ถ้าไม่จับฉลากกันต่อไปเรื่อยๆ แบบนี้หละ แต่เปลี่ยนเป็นให้ทุกคนหยิบฉลากจากไหพร้อมกันเลย แล้วค่อยเปิดดูทีเดียวว่าใครได้ของขวัญจากใคร ยังจะมีโอกาสสูงอยู่มั้ยที่จะมีคนจับฉลากได้ของขวัญของตัวเอง?

ตอนนั้นหมดพลังแล้ว ให้คิดต่ออย่างเดียวคงไม่ออกแน่ๆ เลยเขียนโปรแกรมง่ายๆ มาดูค่าเอาเลยนั่นแหละ
#!/usr/bin/env python3
from random import shuffle
from collections import Counter

shuffled = lambda ls: shuffle(ls) or ls
own_gift = lambda n: [i for i, j in enumerate(shuffled(list(range(n)))) if i == j]
สมมติให้มีคนแลกของขวัญกัน 10 คน ทดลองไปล้านครั้ง พบว่ามีประมาณสามแสนหกหมื่นครั้งเท่านั้น (36%) ที่การแลกของขวัญนั้นจะไม่มีคนได้ของตัวเอง

ตอนนั้นก็ตกใจว่าเลข 36% มาจากไหน นึกว่าโอกาสไม่ได้ของตัวเองมันจะมีค่าสูงกว่า 50% ที่คิดได้จากการแลกของขวัญวนไปเรื่อยๆ ซะอีก นี่กลายเป็นว่าโอกาสไม่ได้ของตัวเองมันยิ่งเหลือน้อย เลยทดลองเพิ่มโดยนับแยกว่า ในแต่ละการทดลองแลกของขวัญนั้น มีคนกี่คนที่ได้ของขวัญของตัวเอง

ทดลองแลกของขวัญกัน 10 คนล้านครั้งเหมือนเดิม แล้วก็ตกใจเพิ่มกับหน้าตาผลลัพธ์ที่ไม่โกหกดังนี้

จำนวนคนที่จับได้ของขวัญของตัวเอง จำนวนครั้งของเหตุการณ์ที่เกิด ข้อคาดการณ์โอกาสการเกิด
0 368,243 1/0! x 1/e
1 367,640 1/1! x 1/e
2 183,800 1/2! x 1/e
3 61,406 1/3! x 1/e
4 15,269 1/4! x 1/e
5 3,014 1/5! x 1/e
6 545 1/6! x 1/e
7 67 1/7! x 1/e
8 16 1/8! x 1/e

ถึงตอนนี้ก็พอจะเข้าใจแล้วว่ามันเกิดอะไรขึ้น



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

เริ่มจากกรณีที่ไม่มีใครจับของขวัญได้ของตัวเองก่อน จะได้ว่า
  • คนแรกมีโอกาสจะจับไม่ได้ของตัวเองที่ (n-1)/n
  • คนที่สองมีโอกาสที่จะจับไม่ได้ของตัวเอง แบ่งได้ 2 แบบ คือ
    • คนแรกจับได้ของคนที่สองไปแล้ว (โอกาส 1/n) ดังนั้นคนที่สองจับไม่ได้ของตัวเองแน่ๆ (โอกาส 1) รวมโอกาสได้เป็น 1/n
    • คนแรกจับไม่ได้ของคนที่สอง (โอกาส (n-1)/n) คนที่สองต้องจับหลบให้ไม่ได้ของตัวเอง (โอกาส (n-2)/(n-1)) รวมโอกาสได้เป็น ((n-1)/n)((n-2)/(n-1))
    • สรุปว่าโอกาสทั้งหมดที่คนที่สองจะจับไม่ได้ของตัวเองคือ 1/n + ((n-1)/n)((n-2)/(n-1))
  • โอกาสคนที่สามจะคล้ายๆ กับของคนที่สอง คือ 2/n + ((n-2)/n)((n-3)/(n-2))
  • คนที่ i มีโอกาส (i-1)/n + ((n-i-1)/n)((n-i)/(n-i-1)) ที่จะจับไม่ได้ของตัวเอง

เนื่องจากเหตุการณ์ทั้งหมด ต้องเกิดขึ้นพร้อมกัน ดังนั้นสรุปได้ว่า
P(n คนไม่มีใครได้ของตัวเอง) = (n-1)/n x (1/n + ((n-1)/n)((n-2)/(n-1))
                                  x ... x ((i-1)/n + ((n-i-1)/n)((n-i)/(n-i-1))
                                  x ... x ((n-n)/n + 0)
                        = (n-1)/n x (1/n + (n-2)/n) x .... x ((i-1)/n + (n-i)/n) x ... x 1
                        = Product  (n-1)/n  for integer i from 1 to n-1
                        = Product  1 - 1/n  for integer i from 1 to n-1
                        = (1-1/n)^(n-1)
จากสมการข้างต้น ถ้าลองแทนตัวเลขน้อยๆ เช่น n=1,2,3,4 เข้าไป จะได้คำตอบเป็น 1, 0.5, 0.445, 0.422 ตามลำดับ แต่เมื่อลองแทนเลขมากๆ แล้ว ผลลัพธ์จะลู่เข้าหาค่าเดียวกันคือ 0.367879... นั่นก็เพราะ
limit  (1-1/n)^(n-1)  when n -> infinity = limit  (1-1/n)^n  when n -> infinity
                                         = limit  ((n-1)/n)^n  when n -> infinity
                                         = limit  (n/(n+1))^n  when n -> infinity
                                         = limit  1/((n+1)/n)^n  when n -> infinity
                                         = 1/(limit  ((n+1)/n)^n  when n -> infinity)
                                         = 1/(limit  (1+1/n)^n  when n -> infinity)
                                         = 1/e
สวยมั้ย อยู่ดีๆ ก็ได้ค่า e ออกมาเฉยเลย

ส่วนการพิสูจน์กรณีมีคนได้ของขวัญของตัวเองแค่คนเดียว จะมีฟอร์มที่ต่างไปเล็กน้อยเนื่องจากเหตุการณ์จะไม่เกิดขึ้นต่อเนื่องกันแล้ว เขียนสมการออกมาได้เป็น
P(n คนมี 1 คนได้ของตัวเอง) = (1/n)P(n-1 คนไม่มีใครได้ของตัวเอง)
                              + ((n-1)/n)(1/(n-1))P(n-2 คนไม่มีใครได้ของตัวเอง)
                              + ...
                              + ((n-(n-1))/n)(1/(n-(n-1)))P(n-n คนไม่มีใครได้ของตัวเอง)
                        = (1/n)P(n-1 คนไม่มีใครได้ของตัวเอง)
                              + (1/n)P(n-2 คนไม่มีใครได้ของตัวเอง)
                              + ...
                              + (1/n)P(n-n คนไม่มีใครได้ของตัวเอง)
                        = (1/n)(Sum  P(n-i คนไม่มีใครได้ของตัวเอง)  for integer i from 1 to n)
สมมติว่ามีคนมาร่วมงานแลกของขวัญเยอะ อาจจะมองว่า P(n-i คนที่ไม่มีใครได้ของตัวเอง) มีค่าไม่แตกต่างกันสำหรับแต่ละค่า i เลยก็ได้ ทำให้เราสามารถยุบผลรวมยุ่งๆ ด้านหลัง ให้เหลือแค่เอาความน่าจะเป็นไปคูณด้วย n ก็พอ ซึ่งมันก็จะโดนหักล้างทิ้งไปกับ (1/n) ด้านหน้าทันที

ดังนั้นจะได้ว่า ค่าความน่าจะเป็นของงานเลี้ยงแลกของขวัญที่จะมีคนหนึ่งคนได้จับได้ของตัวเอง เป็น 1/e เท่ากันกับกรณีไม่มีใครจับได้ของตัวเองเลย

สำหรับกรณีที่มีคนสองคนจับได้ของตัวเอง จะเริ่มพิสูจน์ยุ่งยากมากขึ้นไปอีก แต่ใจความจะคล้ายๆ กับการพิสูจน์คนเดียวได้ของตัวเอง ซึ่งได้แก่การมองแยกกรณี โดยแบบที่หนึ่งจะให้คนแรกจับได้ของตัวเองไปแล้ว หลังจากนั้นจึงหาโอกาสของคนที่เหลือที่จะมีหนึ่งคนจับได้ของตัวเองเป็นเท่าไหร่ กับแบบที่สองที่ให้คนแรกจับไม่ได้ของตัวเอง แล้วหาโอกาสของคนที่เหลือที่จะมีสองคนจับได้ของตัวเองเป็นเท่าไหร่ (ถ้าคิดด้วยวิธีนี้ไม่ผิด จะได้หน้าตาสมการเป็นการหาผลรวมของเทอม ((n-k)/n)((n-k+1)/(n-1))((n-k+2)/(n-2))...(1/(n-k+1))P(n-k คนมี 1 คนได้ของตัวเอง))

กรณีอื่นๆ ที่เหลือเนื่องด้วยพื้นที่กระดาษไม่พอเขี.... เฮ้ย ไม่ใช่แฟร์มาต์! จริงๆ แล้วต้องบอกว่าการพิสูจน์ด้วยท่านี้มันเริ่มยุ่งยากซับซ้อนจนไปต่อไม่ไหวแล้ว แต่ถ้ายังจำกันได้ นี่มันการแจกแจงปัวซองที่มีค่า λ=1 ชัดๆ ก็เอาเป็นว่าใครอยากพิสูจน์ต่อก็ลองใช้ท่านี้ดูนะ อาจจะได้บทพิสูจน์ที่สั้นและสวยงามกว่าด้วย



เห็นแล้วว่าการสุ่มจับฉลากทั้งหมดทีเดียวพร้อมกันมันไม่เวิร์ค กลับไปดูวิธีดั้งเดิมที่ค่อยๆ ให้จับฉลากทีละคน จับได้ชื่อใครก็ให้คนนั้นไปจับฉลากต่อ วิธีนี้เขียนเป็นโค้ดออกมาได้ว่า
from random import randint

def exchange(ls):
    owned = [None for _ in ls]
    current = 0
    while ls:
        if owned[current] is not None:
            current = owned.index(None)
        gone = randint(0, len(ls)-1)
        owned[current] = ls[gone]
        current = ls[gone]
        del ls[gone]
    return owned
เอาฟังก์ชัน exchange ไปแทนที่ฟังก์ชัน shuffled ข้างบนแล้วทดลองใหม่ ก็ได้ผลลัพธ์ที่ไม่ต่างไปจากตารางแรกซักเท่าไหร่เลย



ดังนั้นไม่ว่าจะให้จับฉลากพร้อมกันหมดในทีเดียว หรือจะค่อยๆ จับทีละคน พอจับได้ชื่อใครก็ให้คนนั้นจับต่อ ทั้งสองวิธีนี้ยังไงก็จะมีคนซวยโชคดีอย่างน้อยหนึ่งคน ที่จับได้ของขวัญของตัวเองด้วยโอกาสสูงเท่ากันที่ 1-1/e หรือประมาณ 63.21% ครับ โดยที่(แทบ)ไม่ต้องสนใจด้วยว่ามีคนมาแลกของขวัญกันกี่คน

แต่วิธีแก้ก็ไม่ได้ยากเกินไป ใช้วิธีค่อยๆ ไล่จับฉลากไปทีละคนนั่นแหละ (จะได้เล่นมุกคั่นเวลา ดูรีแอคชันของคนได้ของขวัญด้วย) แล้วเพิ่มกฎเข้าไปสองข้อดังนี้
  1. ถ้าจับได้ชื่อตัวเอง ให้จับฉลากเพิ่มอีกใบเพื่อจะได้เอาของขวัญจากคนนั้น แต่อย่าลืมหย่อนฉลากชื่อตัวเองที่จับขึ้นมาเมื่อกี้ใส่กลับลงไหก่อนเอาไปให้จับฉลากต่อ
  2. ตอนเหลือคนยังไม่ได้จับฉลาก 2 คน ไม่ต้องให้จับฉลากแล้ว ให้คนที่กำลังจะจับฉลากไปเอาของขวัญจากคนสุดท้ายได้เลย ส่วนคนสุดท้ายก็ไปเอาของขวัญจากคนแรก
อย่างไรก็ตาม หากรู้สึกว่ากฎพวกนี้มันวุ่นวายจนทำให้งานกร่อยก็ไม่ต้องไปทำตามหรอก เพราะการมีคนจับได้ของขวัญของตัวเองก็ไม่ใช่เรื่องเลวร้ายแต่อย่างใด หนำซ้ำมันยังเป็นประสบการณ์สุดประหลาดที่หาได้ยาก และเป็นเรื่องขำขันชั้นดีที่สามารถเก็บเอาไว้เล่นได้เรื่อยๆ ยันลูกบวชเลยหละ

สวัสดีปีใหม่ 2016 ล่วงหน้าครับ

Aug 13, 2015

จักรวาลวิทยาและความตาย: YOLO

YOLO เป็นสแลงของวัยรุ่นในแถบประเทศที่พูดภาษาอังกฤษ มันย่อมาจากประโยคที่บอกว่า you only live once ที่แปลว่า "คุณมีชีวิตอยู่แค่ครั้งเดียว" ดังนั้นจะทำอะไรก็ทำไปเถอะ น่าเสียดายว่าหลายคนเอาไปใช้ในทางที่สุดโต่งอย่างการทำผิดกฎหมาย ทำให้คำนี้โดนมองในแง่ลบอย่างหนัก ต่างไปจากวลี carpe diem ในภาษาละตินที่แปลว่า "จงฉกฉวยชั่นขณะนี้ไว้" มันเป็นคำประพันธ์โบราณโดย Horace เมื่อกว่าสองพันปีก่อน และได้รับการเผยแพร่ซ้ำผ่านหนังขึ้นหิ้งอย่าง Dead Poet Society ทำให้วลีนี้ดูสุขุมนุ่มลึกกว่าคำข้างต้นที่เป็นได้เพียงสบถของพวกนอกคอก


แต่บทความนี้ไม่ได้มาเจาะลึกเรื่องทางประวัติศาสตร์ สังคม หรือแม้กระทั่งความหมายของคำนั้นหรอกครับ

เพราะสิ่งที่น่าสนใจยิ่งกว่า คือแนวคิดที่แฝงไว้ว่า "ชีวิตนี้มีแค่ครั้งเดียว"

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

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

พูดง่ายๆ ว่าวิญญาณนั้นอยู่ในมิติอื่นที่เราไม่สามารถสังเกตได้นั่นเอง

และแน่นอนว่า เมื่อไหร่ก็ตามที่วิทยาศาสตร์จะพยายามสังเกตวิญญาณให้ได้ ศาสนาก็จะหลบเลี่ยงไปอธิบายวิญญาณในรูปแบบอื่นแทน ดังนั้นบทความนี้จะยังไม่มาเล่นวิ่งไล่จับกัน แต่จะฟันธงไปก่อนเลยว่าวิญญาณนั้นไม่มี เพื่อที่จะได้สำรวจความคิดที่งอกเงยขึ้นมาอย่างเต็มที่

เมื่อเราปฏิเสธเรื่องวิญญาณไปแล้ว จะเห็นได้ว่าส่วนที่เหลือก็ง่ายทันที ความรู้สึกนึกคิด ความฝัน ความตระหนักในตัวตน (self-awareness) ต่างเป็นกิจกรรมที่เกิดขึ้นในสมองทั้งนั้น เมื่อสมองหยุดทำงานลง ก็หมายถึงความตายที่เราคุ้นเคยกันดี

แต่ความตายนั้นเป็นจุดจบจริงหรือ?

แบบจำลองจักรวาลที่ได้รับการยอมรับอย่างมากที่สุด ณ ขณะนี้ เสนอว่าจักรวาลนั้นมีจุดกำเนิด (big bang) เมื่อสิบสี่พันล้านปีที่แล้ว และขยายตัวมาเรื่อยๆ ด้วยอัตราเร่งที่สูงอย่างน่าใจหายถึงทุกวันนี้

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

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

Aug 6, 2015

ตรวจ 2^n

วันก่อนเห็นทวีตนี้ของ @Methuz


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




ถ้าไม่เชี่ยววิเคราะห์อัลกอริทึม ดูแค่นี้อาจยังมองไม่เห็นว่าปรับปรุงดีขึ้นจริงหรือเปล่า เลย compile เป็น assembly ออกมาแล้วไล่ดูทีละบรรทัดเลย

คำสั่งที่ใช้ compile ให้เป็น assembly (GAS syntax) คือ

$ gcc -S -O3 program.c

อันนี้คือผลลัพธ์แบบแรกที่คุณ @Methuz เสนอ (ตัดมาเฉพาะส่วนฟังก์ชันที่สำคัญนะครับ)

chkpowof2:
        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L42
        movl    %edi, %eax
        negl    %eax
        andl    %edi, %eax
        cmpl    %eax, %edi
        sete    %al
        movzbl  %al, %eax
.L42:
        rep ret

และอันนี้เป็นแบบที่ปรับปรุงแล้ว

chkpowof2:
        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L42
        leal    -1(%rdi), %eax
        testl   %edi, %eax
        sete    %al
        movzbl  %al, %eax
.L42:
        rep ret

โอเค ใครอ่านถึงตรงนี้แล้วไม่งงก็กดปิดได้ เพราะเห็นชัดว่าปรับปรุงให้ดีขึ้นจริง

ส่วนใครงงอยู่ เดี๋ยวมาไล่โค้ดกันทีละบรรทัดกันครับ :D



แต่ก่อนอื่น หากอยากอ่าน assembly รู้เรื่อง ก็ต้องไปทำความคุ้นเคยกับ register เสียก่อน (พวกที่เขียนด้วยเครื่องหมาย % นำหน้า) ซึ่งมันก็คือตัวแปรต่างๆ นั่นเอง เพียงแต่ว่าตำแหน่งในโลกจริงของ register ถูกวางไว้ใน CPU เพื่อให้ทำงานได้อย่างรวดเร็ว ทำให้ register ทั้งหมดนั้นมีอยู่อย่างจำกัด (ไม่กี่สิบตัว)

ในฟังก์ชันที่ตัดมานี้มี register ที่สำคัญอยู่ 2 ตัว คือ %eax และ %edi และยังมี register ตัวอื่นอีก เช่น %al ซึ่งเป็นส่วนย่อยของ %eax โดยอธิบายความสัมพันธ์ได้ดังแผนภาพนี้

sample value:
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

a family register:
                                                            |- %ah -| |- %al -|
                                                            |------ %ax ------|
                                        |--------------- %eax ----------------|
|----------------------------------- %rax ------------------------------------|

di family register:
                                                            |------ %di ------|
                                        |--------------- %edi ----------------|
|----------------------------------- %rdi ------------------------------------|

ดังนั้นหากค่าของ %eax (32 บิต) ถูกตั้งไว้เป็น 0x89ABCDEF เมื่อเรียกดูค่าของ %al (8 บิต) ก็จะว่ามีค่าเป็น 0xEF

ส่วนหน้าที่พิเศษของ register ทั้ง 2 ตัวในที่นี้คือ
  • %eax เก็บค่าที่จะ return จากฟังก์ชัน
  • %edi เก็บค่า argument ของฟังก์ชัน

พอคุ้นเคยกับ register เหล่านี้แล้ว คราวนี้ก็ได้เวลามาดูโค้ดจริงๆ เสียที

บรรทัด 1

xorl    %eax, %eax

บรรทัดแรกนี้สั่งล้างค่า %eax ให้เป็นศูนย์ไว้ก่อน โดยใช้เทคนิคว่า ค่าใดๆ เมื่อนำไป xor กับตัวเองแล้วจะได้ศูนย์เสมอ ท่านี้จะเร็วกว่าการโหลดข้อมูลจาก memory มาถม

บรรทัด 2-3:

testl   %edi, %edi
je      .L42

สองบรรทัดต่อมาเป็นการเช็คว่า %edi (ตัวแปร x) มีค่าเป็นศูนย์หรือเปล่า โดยใช้เทคนิคว่า ค่าใดๆ เมื่อนำไป and กับตัวเองก็จะได้ตัวเองเสมอ หากตรวจแล้วพบว่าเป็นศูนย์ก็ให้กระโดดไปยังจุดจบฟังก์ชัน ซึ่งเมื่อรวมกับข้อมูลก่อนหน้าว่าตอนนี้ %eax เป็นศูนย์อยู่ ก็คือฟังก์ชันนี้ให้คำตอบเป็น false นั่นเอง

บรรทัด 4-8 ของแบบแรก:

movl    %edi, %eax
negl    %eax
andl    %edi, %eax
cmpl    %eax, %edi
sete    %al

บรรทัดต่อๆ มาเป็นชุดคำสั่งในส่วนหลังที่ถามว่า หากมอง x เป็น binary แล้ว จะมีตัวเลข 1 เพียงตัวเดียวเท่านั้นหรือเปล่า? ซึ่งโค้ดชุดนี้ทำงานโดยเริ่มจากการคัดลอกค่า x จาก %edi มาไว้ที่ %eax ก่อน แล้วหาค่าติดลบแบบ two complement ของ %eax และเก็บไว้ที่เดิม (มีค่าเทียบได้กับการคำนวณ ~x+1) แล้วจึงเอาค่าของ %edi ไปทำการ and และเก็บค่าไว้ใน %eax (ตอนนี้ %eax ก็จะเก็บค่าของ x&(~x+1) แล้ว) สุดท้ายถามว่า %eax ลบ %edi ได้ศูนย์หรือเปล่า ถ้าใช่ก็จะตั้งค่า %al ให้เท่ากับหนึ่ง (ซึ่งก็คือ ฟังก์ชันจะคืนค่า true)

บรรทัด 4-6 ของแบบสอง:

leal    -1(%rdi), %eax
testl   %edi, %eax
sete    %al

ชุดบรรทัดพวกนี้มีหน้าที่และผลลัพธ์เหมือนกับชุดบรรทัดในหัวข้อย่อยก่อนเลยครับ สิ่งที่แตกต่างคือวิธีการเท่านั้น โดยโค้ดเริ่มทำงานจากคัดลอกค่า x จาก %rdi มาลบหนึ่งระหว่างทางแล้วเอาผลลัพธ์ไปเก็บไว้ใน %eax (ตรงนี้เนื่องจากมีการคำนวณพื้นฐานอย่างบวกลบ ทำให้ compiler รวบคำสั่งเข้ามาที่เดียว ต่างจากการคำนวณซับซ้อนอย่างการหาค่าติดลบครับ) เรียบร้อยแล้วเอา %edi มา and กับ %eax หากได้ศูนย์ก็จะตั้งค่า %al ให้เท่ากับหนึ่ง (คืน true)

บรรทัดรองสุดท้าย

movzbl  %al, %eax

ถึงตอนนี้การคำนวณหลักๆ ได้เสร็จสิ้นหมดแล้ว ที่ยังไม่เสร็จคือเตรียมค่าที่จะส่งคืน เพราะก่อนหน้านี้เราใช้ %al ยาว 8 บิต แต่ตอนส่งค่าคืนต้องใช้ %eax ที่ยาว 32 บิต บรรทัดนี้จะช่วยแปลงค่าดังกล่าว

บรรทัดสุดท้าย

rep ret

สุดท้ายก็ได้เวลาส่งคืนคำตอบครับ สังเกตว่า compiler เพิ่มความมั่นใจให้คำสั่งนี้ด้วยการเติม rep ไว้ข้างหน้า เพื่อให้โค้ดที่ทำงานมาถึงบรรทัดนี้ทำคำสั่ง ret ซ้ำๆ จนกว่าจะสำเร็จนั่นเอง



สุดท้ายการวิเคราะห์อัลกอริทึม/โค้ดยังไม่พอ นี่คือผลเชิงประจักษ์ของเวลาที่ใช้ไปสำหรับการตรวจว่าเลขดังกล่าวเป็น 2^n หรือไม่ สำหรับจำนวนเต็มบวกทุกตัวที่มีค่าต่ำกว่าสองพันล้านครับ

$ gcc --version
gcc (Ubuntu 4.9.2-10ubuntu13) 4.9.2
$ cat /proc/cpuinfo
...
model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
...


$ time method-1         # ((x != 0) && ((x & (~x + 1)) == x))
real 0m0.234s ~ 0m0.289s
user 0m0.232s ~ 0m0.288s
sys 0m0.000s


$ time method-2         # ((x != 0) && ((x & (x - 1)) == 0))
real 0m0.212s ~ 0m0.262s
user 0m0.208s ~ 0m0.260s
sys 0m0.000s

ก็เร็วต่างกันประมาณ 10%


Jul 10, 2015

จำลอง WYSIWYG ตามแบบคนจนบน HTML5

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

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

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

ทางแก้สำหรับเหล่า geek คงเป็นการ "เลิกฝัน" แล้วกลับไปลุยดะกับโค้ดจัดย่อหน้าเลย (ซึ่งก็ไม่จำเป็นต้องยุ่งกับ HTML ตรงๆ อาจเลือกพวกที่เจ็บปวดน้อยลงอย่าง Markdown ก็ได้)

แต่ถ้าแนะนำแบบนี้กับคนทั่วไปที่ชินกับ MS Word คงไม่เวิร์กแน่

จริงๆ ทางออกสำหรับพวกเขาเหล่านั่น อาจไม่ใช่การแก้ไขทุกรายละเอียดผ่านกล่องข้อความในหน้าเว็บก็ได้

เพราะในเมื่อพวกเขาชินกับการใช้โปรแกรม Word อยู่แล้ว ก็ให้แก้ไขอะไรให้เรียบร้อยบน Word ไปเลย เรียบร้อยแล้วลากคลุมสิ่งที่ต้องการ Ctrl+C Ctrl+V มาวางบนกล่องข้อความหน้าเว็บก็พอ

ส่วนกล่องข้อความก็เปลี่ยนจาก <textarea> ไปเป็น <div contenteditable> แทน เท่านี้ก็เรียบร้อย (แล้วไปหาวิธีเซฟ/โหลดข้อความที่ <div> แทน ซึ่งไม่ยุ่งยากหรอกในโลกที่มี jQuery ให้ใช้ :P)



อยากลองเล่น? ขั้นแรกให้พิมพ์ตามนี้ลงไปใน address bar ของเว็บเบราเซอร์เพื่อสร้าง WYSIWYG ก่อนครับ

data:text/html, <html contenteditable>

ขั้นต่อมาก็ไปเปิดเอกสาร Word ซักอัน (หรือจะสร้างใหม่ก็ได้) แล้วลองคัดลอกข้อความมาวางบนหน้าเว็บนั้นดู

ส่วนอะไรที่เวิร์กไม่เวิร์กบ้าง เท่าที่ลองคร่าวๆ ได้ผลตามตารางนี้ครับ

การจัดรูปแบบ แท็กที่ใช้แทน MS Word LibreOffice Google Docs
Title <p align="center"><font size="6">
Subtitle <p align="center"><font size="5">
Heading 1-3 <h1> - <h3>
Heading <font size="4">
Quotations <blockquote>
Align Left / Center / Right / Justify <p align="left / center / right / justify">
Bold, Italic, Underline, Strikethrough <b> / <i> / <u> / <strike>
Superscript, Subscript <sup> / <sub>
Table <table><tbody><tr><td>
Bullet List <ul><li>
Numbering <ol><li>
Image <img src="data:image/png;base64,...">
Formula <img src="data:image/png;base64,...">

(จากที่สังเกต ผลลัพธ์ตอนนำข้อความมาวางเหมือนจะไม่มีความต่างกันในแต่ละเว็บบราวเซอร์ ดังนั้นจึงสนใจเฉพาะตอนคัดลอกมาจากโปรแกรมแก้ไขเอกสารอย่างเดียวครับ)

Jun 17, 2015

AutoHotKey กับสคริปต์เปลี่ยนภาษา

ลง Windows ใหม่อีกรอบและทำโปรแกรมเปลี่ยนภาษาด้วยปุ่ม CapsLock หายไปแล้ว เลยมาจดไว้ก่อน เผื่อเจอเหตุการณ์ประมาณนี้อีกจะได้ลดเวลาลองผิดลองถูก

  1. เช็คให้แน่ใจว่าการเปลี่ยนภาษาบน Windows ใช้ปุ่ม Alt+Shift เสียก่อน
  2. ดาวน์โหลดและติดตั้งโปรแกรม AutoHotKey
  3. กด Win+R พิมพ์ shell:startup มันจะเปิดแฟ้มเก็บโปรแกรมที่ถูกเรียกอัตโนมัติตอนเปิดเครื่องมาให้
  4. คลิกขวาเลือกสร้างสคริปต์ AutoHotKey (อย่าสร้างไฟล์เปล่าๆ เพราะจะไม่ได้ค่าปริยายมาด้วย) แล้วเพิ่มคำสั่งนี้ต่อท้ายไฟล์
    Capslock:: Send {Alt Down}{Shift}{Alt Up}
    

เรื่องประหลาดคือ ในสคริปต์ถ้าสลับตำแหน่งเป็นกด Shift ค้างไว้ก่อนแล้วค่อยกด Alt มันก็เปลี่ยนภาษาได้นะ แต่พอเปลี่ยนเสร็จเคอร์เซอร์จะหลุดโฟกัสไปเลย ไม่รู้ว่าเกิดอะไรขึ้น :\

May 25, 2015

ลองใช้ Lamy ครั้งแรก

ชีวิตนี้ไม่เคยคิดว่าจะใช้ปากกาด้ามแพงเกินร้อยบาทครับ แต่ก็ได้ Lamy มาฟรีด้ามนึงเป็นของขวัญวันรับปริญญา

ดองไว้เป็นปีแล้วเพราะไม่รู้ว่าใช้ยังไง จนกระทั่งไม่กี่วันก่อนที่ปากกาทุกด้ามจงใจหมึกตัน เลยได้ฤกษ์เอาออกมาลองใช้ซะเลย

ด้ามที่ได้มานี้หัวเป็นขนาด M ครับ โดยรวมแล้วเอาไปเขียนลื่นสนุกดี แม้มีสะดุดบางจังหวะ

แต่ตอนเอามาวาดรูปนี่รู้สึกควบคุมน้ำหนักเส้นไม่ได้เลย (ไม่เหมือนหัวลูกลื่นที่สามารถฝนบางๆ น้อยกว่าขนาดที่บอกไว้ได้) ...





สรุปแล้วไม่ค่อยชอบเท่าไหร่แฮะ นี่ผมแปลกไปเองหรือเปล่าเนี่ย?

May 22, 2015

Voronoi จากภาพ

วันก่อนไปเจอคำถามใน Code Golf มา เค้าให้สร้าง Voronoi เพื่อเลียนแบบภาพต้นฉบับครับ

อ่านแล้วสนุกดี ผลงานของคนอื่นที่ได้ๆ ก็ดูเหมือนงานศิลป์พวก Divisionism/Pointillism ด้วย เลยลองกลับมาเขียนเองแบบมั่วๆ บ้าง 555

import random
from PIL import Image
from PIL.ImageFilter import FIND_EDGES, GaussianBlur, SHARPEN

def coordinate(width, height):
    yield from ((x, y) for y in range(height) for x in range(width))

def normalized(choices):
    lower = min(weight for _, weight in choices)
    upper = max(weight for _, weight in choices)
    norm = lambda weight: (weight-lower) + (upper-lower)//4
    return [((x, y), norm(weight)) for (x, y), weight in choices]

def random_by_weight(choices):
    rand_val = random.uniform(0, sum(weight for _, weight in choices))
    index = 0
    count = 0
    while count < rand_val:
        count += choices[index][1]
        index += 1
    return choices.pop(index-1)[0]

def init_centroids(image, cells):
    width, height = image.size
    edge_img = image.filter(FIND_EDGES).filter(GaussianBlur).filter(SHARPEN)
    weight = lambda x, y: 256 - max(edge_img.getpixel((x, y)))
    choices = [((x, y), weight(x, y)) for x, y in coordinate(width, height)]
    return [random_by_weight(normalized(choices)) for _ in range(cells)]

def init_rgbs(image, centroids):
    rgb_im = image.convert('RGB')
    return [rgb_im.getpixel((x, y)) for x, y in centroids]

def simulate_voronoi(image_path, cells=25, scale=None):
    image = Image.open(image_path)
    if scale is not None:
        image.thumbnail((scale, scale), Image.ANTIALIAS)
    centroids = init_centroids(image, cells)
    rgbs = init_rgbs(image, centroids)
    return image.size, list(zip(centroids, rgbs))
ผลลัพธ์ที่ออกมาก็ประมาณนี้ครับ (ที่ 500 เซลล์ Voronoi)

เอาไปสู้เขาไม่ได้หรอก เพราะเขียนไปมั่วแบบคนไม่มีพื้นฐาน image processing อะไรเลย แต่ก็สนุกดีได้ลองใช้ PIL เป็นครั้งแรกด้วย

May 14, 2015

Sexy Love



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

แล้ว YouTube ก็วนเพลง Sexy Love มาให้

รู้ตัวอีกที 2 ชั่วโมงถัดมา ก็ยังกดเล่นซ้ำ ฟังเพลงนี้ซ้ำๆ อยู่ครับ

ท่าเต้นโรบอทนี่มันแจ่มจริงๆ ให้ดิ้นตายสิ :3

May 7, 2015

Entertainment



เพลงนี้เป็นเพลงประกอบเครดิตหนัง Now You See Me (2013) ครับ คือทั้งเรื่องไม่ได้ใช้เพลงนี้มาประกอบเลยนั่นแหละ ถ้าไม่นั่งดูเครดิตหนังก็ไม่รู้ว่ามี

ฟังแล้วสนุกดี ได้กลิ่นหนังจีนสมัยก่อนลอยมาแต่ไกลเลย (ทั้งๆ ที่เป็นวงจากฝรั่งเศส) สงสัยเพราะว่าเมโลดี้อยู่ในกุญแจไดอาโทนิคด้วย แต่มันก็ไม่ได้ออกบลูแจ๊สแม้แต่น้อย กลับเป็นร๊อคมันส์ๆ ให้โยกหัวตามได้

ก็ถือว่าเป็นการผสมผสานที่น่าสนใจดี นั่งฟังได้ทั้งวัน