wwibul - ใบไม้ผลิ - ฝึกวิเคราะห์ algorithm ด้วยตะแกรงร่อน Palindrome (3)

อ่าน: 475

ฝึกวิเคราะห์ algorithm ด้วยตะแกรงร่อน Palindrome (3)

ดังตัวอย่างที่ยกไปเมื่อตอนที่แล้ว คือ

ฝึกวิเคราะห์ algorithm ด้วยตะแกรงร่อน Palindrome (2)

ผมทึกทักว่า ตัวเลข palindrome ใหญ่สุด น่าจะเป็น 9x xxx xx9 ซึ่งโอกาสที่จะผิด มีเพียง 0.0514 ยกกำลัง 1000 (โอกาสผิดราว 2 ใน 10 ยกกำลังหนึ่งพันเศษ ๆ)

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

เอาให้ตึงขึ้นมาอีกล่ะ คือทึกทักว่า ตัวเลข palindrome ใหญ่สุด น่าจะเป็น 99 9xx 999 ซึ่งโอกาสที่จะผิด มีเพียง 0.0514 ยกกำลัง 10 (โอกาสผิดราว 1 ใน 10 ยกกำลัง 13) ซึ่งในที่นี้ ขอเรียกว่า เป็นกรณีที่ 3

กรณีที่ 3 ซึ่งเป็นกรณีหลังสุด มีความเสี่ยงสูงไปนิดนึง เห็นแล้วไม่สบายใจที่จะใช้

ดังนั้น ผมจะรู้สึกว่า กรณีที่ 2 น่าจะลงตัว คือ ทึกทักว่า ตัวเลข palindrome ใหญ่สุด น่าจะเป็น 99 xxx x99

คราวนี้ผมจะใช้งานอย่างไรต่อล่ะ ?

ใช้การสังเกตุครับ

จากการสังเกตุ 99 xxx x99 จะต้องเกิดจากการคูณกันระหว่าง 99xx กับ 99yy (ดูตรงนี้ให้ดี ๆ นะครับ เพราะผมพลาดตรงนี้ !)

ดังนั้น กฎย่อยข้อแรกของเราคือ ใช้วิธีบังคับคูณแบบหักโหม แต่เลือกค่าตั้งต้นให้เหมาะสม ในที่นี้ เริ่มจาก 9900 ถึง 9999 มาคูณกันเองแบบพบกันหมด ซึ่งก็เป็นไปได้เพียง 1 หมื่นคู่เท่านั้นเอง

แล้วอันที่จริง ผมไม่ต้องคูณทุกรายการด้วย เพราะการที่ผลคูณลงท้ายด้วย 9 เกิดจากความเป็นไปได้เพียง 4 แบบ จาก 100 แบบเท่านั้นเอง

คือ

ลงท้ายด้วย 1 เจอกับลงท้ายด้วย 9

ลงท้ายด้วย 3 เจอกับลงท้ายด้วย 3

ลงท้ายด้วย 7 เจอกับลงท้ายด้วย 7

ลงท้ายด้วย 9 เจอกับลงท้ายด้วย 1

กฎข้อสองคือ กรองด้วยการดูเลขลงท้ายดังกล่าว ก็จะทำให้ 1 หมื่นคู่ ลดลงมาอีก เหลือเพียง 4 ร้อยคู่

ยังไม่หนำใจ ลองนึกถึงว่า การคูณแบบพบกันหมด มีความสมมาตรหน้าหลัง เลขมากคูณเลขน้อย ก็คือเลขน้อยคูณเลขมาก เวลาคูณ ก็อาจบังคับว่า ตัวหน้าใหญ่กว่าตัวหลังเสมอ จะได้ไม่ต้องคูณซ้ำซาก

เกิดเป็นกฎข้อสาม คือ ไม่ต้องคูณซ้ำคู่ที่เคยคูณไปแล้ว เพราะผมสามารถเลือกแต่กรณีที่ตัวเลขตัวหลัง ไม่ต่ำกว่าตัวเลขตัวแรก ก็พอ (เช่นถ้ารู้ 9953 x 9933 ก็ไม่ต้องหา 9933 คูณ 9953)

ทำแบบนี้ ก็จะลดฮวบ คูณทดสอบแค่สองร้อยคู่โดยประมาณเท่านั้นเอง (ผลคือ ความอืด จะลดจาก 8 ลงมาได้เหลือ 2.3 ซึ่งเยอะโขอยู่)

เขียนเป็น pseudocode ดังนี้ (ยืมคำศัพท์ภาษา Basic มาใช้ ... ก็เขียนเป็นอยู่ภาษาเดียวนิ -_-!)

for x=9901 to 9999
for y=x to 9999
z=multiply if ended with {1,9} or {9,1} or {3,3} or {7,7}
check for palindrome and keep the new-high
next y
next x

ลองรันดูจริง ต้องคูณกันทั้งหมด 210 ครั้ง

และได้ 9901 x 9999 = 99000099

ใน 210 ครั้งของการคูณ น่าจะมี palindrome ราว 95 % คือราวเกือบ 200 ครั้ง

แต่มี palindrome แค่ตัวเดียวเท่านั้น

เอ๊ะ ที่เหลือหายไปไหน ?

palindrome = ต้องแยก factor ได้

prime = แยก factor ไม่ได้

มี prime ราว 5 % จึงควรมี palindrome ราว 95 % สิ

ไม่ใช่ครับ

palindrome ต้องแยก factor ได้ แต่แยก factor ได้ไม่จำเป็นต้องเป็น palindrome

แถม palindrome ที่มีอยู่ชุกชุม ก็ไม่จำเป็นต้องเกิดจากเลข 4 หลักคูณเลข 4 หลักด้วย

หน้าแตกครับ แหกเป็นริ้วเลย !

ดังนั้น ในกรณีนี้ ต้องถือว่า algorithm นี้ ให้คำตอบแบบบังเอิญเฉียดฉิวมาก

ชัณสูตรแล้วเดาได้ไหมว่า ทำไมเจอแค่ 1 รายการที่เป็น palindrome ที่เป็นผลจากการที่ใช้เลข 4 หลักคูณเลข 4 หลัก ?

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

แต่ตอนนี้ ยังคิดไม่ค่อยลงตัว ไว้โอกาสหน้าถ้าคิดออก และไม่ลืมซะก่อน ค่อยมาต่อภาค 4 (อิ อิ อิ...)

ลองมาสรุปปฎิบัติการกันหน่อยดีไหม ?

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

แล้วตามด้วยการพลิกแพลงแนวคิดในการเขียนโปรแกรม (optimize algorithm)

หลังจากนั้น ค่อยตามด้วยการเขียนโปรแกรมจริง

ในกรณีนี้ ปัญหามีลักษณะเฉพาะ บังเอิญว่ามองเชิงวิเคราะห์ออกก่อนเขียนโปรแกรม โดยใช้ความเข้าใจเรื่องเลข prime มาช่วย "ฟันธง" ถางทางไว้

แต่การใช้เทคนิคแบบนี้ ก็มีข้อจำกัด คืออาจมีกรณีที่มองไม่รอบด้าน ทำให้ล้มเหลวได้ ดังที่ผมสาธิตให้ดู (ทั้งที่ถูก และที่ผิด)

(ในที่นี้ ผมคาดว่า จะเจอ palindrome เยอะ จากการใช้เลข 4 หลักคูณเลข 4 หลัก ทั้ง 210 ครั้ง แต่เจอจริงแค่ 1 รายการ ซึ่งแม้ไม่ล้มเหลว แต่ถือว่าเป็นความสำเร็จที่ฟลุ้คไปหน่อย)

อย่างไรก็ตาม ปัญหาในสเกลใหญ่จริง ๆ ที่เกิดประโยชน์มาก ๆ มักต้องใช้ความพลิกแพลงเข้าช่วย เลี่ยงไม่ได้ เช่น ใน bioinformatics

เช่น การใช้ mass spectroscopy หา amino acid sequence ที่ยาวสัก 100 ตัวต่อกัน ระดับปัญหาที่คำนวณแบบหักโหม ต้องทำถึง 100! ครั้ง ซึ่งยังไม่มีฮาร์ดแวร์ที่ไหนรองรับได้ในบัดเดี๋ยวนี้ ต้องใช้วิธีพลิกแพลงด้วยการตั้งกฎย่อย ๆ มากระหนาบ กรองทิ้งหย่อมใหญ่ที่ไม่ต้องเสียเวลาตรวจสอบ

แต่ขนาดกรองแล้วเร็วขึ้นล้านล้านล้านเท่า ก็ยังช้ามากๆๆๆๆ ในกรณีเช่นนี้

algorithm จึงสำคัญสุด ๆ ในปัญหาโหด ๆ เช่นนั้น

แต่ใช่ว่า เราต้องพลิกแพลงคิดเสมอไป

ในบางงาน เขาอาจใช้วิธีที่ทื่อ ตรงดิ่ง แบบขวานผ่าซาก เช่น การเขียนโปรแกรมให้ใช้กำลังแบบหักโหม (brute force) เพื่อใช้ประเมินสมรรถนะของ hardware เช่น ในการแข่งขันหมากรุกระหว่างคนกับคอมพิวเตอร์

หรือในงานที่เล็กมาก หรือดูแล้วว่า ต่อให้ brute force ใช้เวลานานแค่ไหน ก็รอได้สบาย ๆ

แบบนั้น ไม่ต้องคิดให้เมื่อยก็ได้ เอาเวลาไปเขียนบล็อกซะดีกว่า

"การเลือกใช้ algorithm จึงต้องนับเป็นส่วนหนึ่งของตัว algorithm เองเสมอ"

สร้าง: จ. 01 ต.ค. 2550 @ 18:58 แก้ไข: พ. 03 ต.ค. 2550 @ 08:40 ขนาด: 13451 ไบต์

ความคิดเห็น

1. वीर
เมื่อ จ. 01 ต.ค. 2550 @ 20:50
404634 [ลบ]

ต้องกลับไปดูตอนก่อนๆ ก่อน. (ผมพลาดไปได้อย่างไร :-P)

2. wwibul
เมื่อ อ. 02 ต.ค. 2550 @ 23:56
406404 [ลบ]

คุณบ่าวพลาดเรื่องการมอง
ผมพลาดเรื่องการคิด
...เสมอกันครับ...
(ได้ทีเชียวแฮะ)

3. वीर
เมื่อ พ. 03 ต.ค. 2550 @ 00:53
406482 [ลบ]

ย้อนกลับไปอ่านก็เจอแล้วครับว่า 0.0514 คืออะไร :-P.

ดู psudo code แล้วก็แอบสงสัยครับว่าถ้า ตัด "z=multiply if ended with {1,9} or {9,1} or {3,3} or {7,7}" ออกไป โปรแกรมจะช้าลงหรือเปล่า. แต่พอย้อมกลับไปอ่านตอนแรก ก็พบว่านอกประเด็น เพราะว่าโจทย์ไม่ได้บอกว่าให้หาวิธีที่ใช้เวลาน้อย.

4. เม้ง สมพร ช่วยอารีย์
เมื่อ อ. 15 ม.ค. 2551 @ 23:02
519710 [ลบ]

สวัสดีครับ อาจารย์

น่าสนใจดีครับ ผมยังไม่เคยเขียนการหาตัวเลขนี้เลยครับ

ต้องการหาตัวที่มากสุดด้วยใช่ไหมครับ

ผมเลยคิดว่า น่าจะปรับอัลกอฯ อาจารย์นิดหน่อยครับ แบบเทคนิคสวนทางครับ

จาก

for x=9901 to 9999
for y=x to 9999
z=multiply if ended with {1,9} or {9,1} or {3,3} or {7,7}
check for palindrome and keep the new-high
next y
next x

เป็น

for x=9999 downto 9901
for y=9999 downto x
z=multiply if ended with {1,9} or {9,1} or {3,3} or {7,7}
check for palindrome and keep the new-high
if palindrome is found, then break the LOOP
next y
next x

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

ขอบพระคุณมากครับ

แต่สำหรับคนที่เค้ามีเครื่อง supercomputer เค้าคงไม่ต้องมานั่งคิดมากเหมือนเราๆ เนอะครับ แต่สาเหตุนี้หล่ะครับที่ทำให้คนอินเดียเขียนโปรแกรมได้ฉลาดนัก เครื่องมือช้าให้หัวมากๆ ครับ

5. wwibul
เมื่อ พ. 16 ม.ค. 2551 @ 09:11
519906 [ลบ]

สวัสดีครับ น้องเม้ง สมพร ช่วยอารีย์

เยี่ยมเลยครับ ผมมองข้ามไปได้ยังไงนี่ !
ที่ผมชอบใจมาก คือคำพูดที่บอกว่า

"แต่สำหรับคนที่เค้ามีเครื่อง supercomputer เค้าคงไม่ต้องมานั่งคิดมากเหมือนเราๆ เนอะครับ แต่สาเหตุนี้หล่ะครับที่ทำให้คนอินเดียเขียนโปรแกรมได้ฉลาดนัก เครื่องมือช้าให้หัวมากๆ ครับ "

เห็นด้วยมาก ๆ เลยครับ ว่าสถานการณ์บีบบังคับให้ใช้'หมอง ทำให้คนฉลาด
นักศึกษาจำนวนมาก คิดเลขในใจไม่เป็นกันแล้ว อาจเพราะชีวิตสะดวกเรื่องเครื่องคิดเลข ซึ่งมือถือ อำนวยให้ได้หมด
คอมพิวเตอร์เร็ว อาจจูงใจให้คนรู้สึกว่า ทุกปัญหา คำนวณหักโหม (brute force) ได้ ง่ายจะตาย ทำให้ไม่สามารถพัฒนาฝีมือให้ถึงที่สุด
ดูกรณีตัวอย่างคือ เกมส์
สมัยเครื่อง 8088 (อือม์ เผยความลับเรื่องอายุซะแร้ว 555) เวลาเครื่องทำงานคำนวณ ผมเห็นทำช้ามาก
แต่บางเกมส์ ทำงานเร็วมหาศาล เพราะลงไประดับภาษาเครื่อง และคงใช้ algorithm ที่ดีมาก ๆ
แสดงว่า ระบบที่เราใช้ ๆ กันอยู่ เราอาจรีดพลังออกมาได้แค่ 1 ในร้อย หรือเผลอ ๆ เพียง 1 ในพัน ที่เหลือ โดนระบบปฎิบัติการเอาไปกินซะมาก
แถมด้วยการใช้ algorithm ที่ไม่ดี อาจหน่วงไปได้อีกเยอะ ตั้งแต่ไม่กี่เท่า ไปจนถึงมากจนประมาณไม่ถูก
ทำอย่างไร เราจะสู้อินเดียได้ในเรื่องนี้ ? ผมเคยอ่านชีวิตของ รามานุจัน ของเขานั่น อย่าว่าแต่ซูเปอร์คอมพ์ไม่มีเลยครับ แค่ตำรา ยังแทบไม่มีเลย
แสดงว่า ระบบการศึกษาของเขา ต้องมีอะไรดี ที่เราไม่มี...?

6. वीर
เมื่อ พ. 16 ม.ค. 2551 @ 10:05
519947 [ลบ]

คนอินเดียก็ไม่ได้มีชีวิตเหมือนรามานุจันไปเสียหมดหรือเปล่าครับ? ดูจากคอมฯที่นักเรียน/อาจารย์วิทยาการคอมพิวเตอร์ที่อินเดียใช้ ก็คล้ายๆกับที่คนไทยใช้ แต่ว่ามักจะลง GNU/Linux พ่วงมากับ Windows ด้วยเท่านั้นเอง :-P.

ผมคิดว่าต่อให้ใช้ super computer หรือแม้แต่ cpu ใหม่ก็ไม่ได้ทำให้เรื่องที่ต้องคิดน้อยลง ถ้าต้องการจะ optimize กันจริงจัง. ส่วนตัวแล้วผมคิดว่า cpu ใหม่ๆอาจจะต้องคิดมากขึ้นด้วยซ้ำ ถ้ามีคำสั่งเรียงกันมา.

ใน 8088 ผมเข้าใจว่าเวลาที่ใช้ในแต่ละคำสั่งมาบวกกัน ก็น่าจะได้เวลารวมแล้ว. แต่ใน CPU ที่ใหม่ขึ้นมาหน่อย บางคำสั่งอาจจะทำงานไปพร้อมๆกันได้ ถ้าไม่มีคำสั่งที่ทำให้โปรแกรมต้องกระโดดไปมา ซึ่งส่วนมากจะเกิดจากการเพิ่มเงื่อนไขเข้าไปในโปรแกรม. นี่ก็อาจจะเป็นไปได้ว่าเราเขียนโปรแกรมหลายๆคำสั่งแต่ไม่มี IF ก็อาจจะทำงานออกมาเร็วกว่าที่คาดไว้. นี่อาจจะเป็นอีกเหตุผลหนึ่งที่ทำให้โปรแกรมที่พยายามจะเขียนออกมาให้ฉลาด แต่ทำให้ทำงานช้าลง!!!. (ผมก็เสียเวลาทำอะไรแบบนี้บ่อยๆ :-P )

ใน super computer ก็ใช้หลักการทำงานแบบขนานเหมือนกัน? ถ้าเรานำ cpu เดี่ยวๆของ super computer ออกมา บางเครื่องอาจจะช้ากว่า cpu ที่เราใช้งานกันเดี๋ยวนี้ด้วยซ้ำ. ถ้าเราใส่โปรแกรมไปแบบไม่ค่อยได้คิดอะไรเท่าไหร่ ก็อาจจะเป็นไปได้ว่าใช้ super computer แล้ว โปรแกรมทำงานช้าลง.

เครื่องใหม่ๆเดี๋ยวนี้มักจะมี GPU ติดว่าด้วย เราอาจจะนำมาช่วยคำนวณอะไรได้บ้าง แต่วิธีใช้งาน วิธีคิดก็อาจจะเปลี่ยนไปพอสมควร. ก็ไม่ใช่ว่าเราเอา GPU มาแล้วเอาโปรแกรมเดิมไปให้ GPU รันแล้วก็จะเร็วขึ้นไปหมดอีกเหมือนกัน.

เหมือนที่อาจารย์ wwibul เคยเขียนเรื่อง multi-core cpu หละครับ. ของพวกนี้บางทีมันก็ไม่ได้เร็วโดยที่เราไม่ได้ออกแรงอะไร.

7. wwibul
เมื่อ พ. 16 ม.ค. 2551 @ 11:02
519989 [ลบ]

สวัสดีครับ คุณบ่าวवीर

เห็นด้วยครับ ว่าเรื่อง optimize ระบบ ต้องว่ากันใหม่เมื่อเปลี่ยนเครื่อง เปลี่ยนระบบ ไม่งั้น ก็เป็นการย่ำยีของดีไป
โปรแกรมฉลาด แต่ทำงานช้าลง ไม่ใช่เรื่องแปลก ถ้ายังไม่ optimize ระบบ ผมมองว่า ช้าลง ชอบด้วยเหตุผล

ส่วนเรื่องการศึกษา เรื่องหนังสือ เรื่องทรัพยากรรองรับ...

ยุคนี้กับยุคนั้น คงไม่เหมือนกันแล้ว
ถ้ามองที่อัจฉริยะ ว่ากันเป็นคน ๆ เราอาจมีสู้เขาได้ในยุคนี้
แต่ถ้ามองแบบภาพรวมทั้งระบบ ผมไม่ค่อยแน่ใจ
ประเด็นที่ผมยังรู้สึกตะหงิด ๆ อยู่ในใจ คือ การเรียนการสอนคณิตศาสตร์ เราอาจเป็นรองเขา และอาจเป็นมานานแล้ว
กรณีตัวอย่าง คือ Satyendra Nath Bose ที่เสนอแนวคิดทางฟิสิกส์ในปี พ.ศ. 2467 (ที่มาทางทฤษฎีของ Bose-Einstein Condensate) แสดงว่า ระบบการศึกษาของเขา สามารถตั้งคำถามพื้นฐานที่ลึก ๆ ได้ตั้งแต่ก่อนนั้นนานพอสมควร
เราอยู่ที่ไหนตอนนั้น ? เราอยู่ที่ไหนตอนนี้ ?

8. เม้ง สมพร ช่วยอารีย์
เมื่อ พ. 16 ม.ค. 2551 @ 16:48
520221 [ลบ]

สวัสดีครับ อ.วิบุล และบ่าววีร์

ดีจังครับผม วันนี้มาดูได้อ่านคำตอบ และมีน้องบ่าววีร์มาร่วมด้วยครับ ฝากหวัดดีน้องบ่าววีร์ด้วยครับ
ผมมีตัวอย่างหนึ่งครับ ตอนนั้น เรียนวิชาการออกแบบอัลกอริทึม อ.ให้ออกแบบการบวกตัวเลขจำนวนเต็มกันจาก A ถึง B โดยที่ A<B
หากเราเล่นกันดื้อๆ เลยเจอตัวเลขระหว่างนั้นซักพันล้านตัว นี่ก็จุกครับ
แต่หากประยุกต์ใช้ N(N+1)/2 เข้าไป นี่แทบไม่ทันได้หายใจสุดอัลวีโอลัส คำตอบก็ออกมาแล้วครับ
นี่หล่ะครับ ข้อดีของคณิตศาสตร์และสูตรต่างๆ
อย่างวิธีการหาค่า Prime number นี่ก็สนุกที่สุดครับ โดยศึกษาพื้นฐาน แล้วให้เด็กคิดต่อยอดจากพื้นฐานง่ายๆ ก่อน จากนั้นค่อยเสริมวิธีการอื่นๆ ที่คนอื่นคิดมา แล้วให้เทียบกับเราที่คิดใหม่ได้ แล้วเพิ่มมาเรื่อยๆ ว่าใครเร็วกว่า จะเป็นการแข่งขันแบบเสริมเกื้อกูลปัญญาให้กับเด็กครับ
การเขียนโปรแกรม ผมพบหลายๆ กรณีเพราะผมก็เขียนโปรแกรมแบบจะหาทางทำให้โปรแกรมเร็วเช่นกันครับ พอไปใช้โปรแกรมคนอื่นเขียน ทำงานคล้ายๆ กัน แต่เอ ทำไมมันเร็วขนาดนั้นหนอทำให้คิดถึงโปรแกรมที่ตนเคยเขียน หันไปอีกทีหมักๆ ปัญหาเอาไว้วันหนึ่งก็อาจจะได้คำตอบ โดยอาจจะหาทางในการใช้พวกฟังก์ชันหรือวิธีการต่างๆ ที่สอดคล้องกับระบบปฏิบัติการนั้นๆ ด้วยครับ
แม้แต่บางที่ ตัวภาษาเองก็อำนวยการคำนวณภายในช้าเร็วแตกต่างกันด้วยครับ
บางครั้ง การโหลดไลบรารี่มาใช้ในโปรแกรมนั้น ก็สำคัญ หากเราเรียกใช้ไม่กี่ตัวเราอาจจะเขียนฟังก์ชันเอาเองก็ได้ ลดขนาดแฟ้มโปรแกรมและยังอาจจะทำให้เร็วกว่าด้วยในบางกรณี เพราะเราไม่รู้หรอกคับ ว่าที่เคยเขียนและใช้ภายในนั้นเค้าใช้แบบฉลาดขนาดไหน
อีกอย่างคือ การทำงานซ้ำๆ อย่างตัวอย่างด้านบนของอาจารย์นะครับ มีการวนทำ้ำซ้ำจำนวน 2 loops ข้างในนะครับ ผมพบว่า หากมีการเช็คเงื่อนไขภายใน จะทำให้โปรแกรมช้าลงกว่ามาก หากเทียบกับการมีเงื่อนไขภายนอก Loop (กรณีที่มีทางเลี่ยง)
บางครั้ง เราต้องยอมเขียนโปรแกรมแบบ source code ยาวๆ เพื่อให้เงื่อนไข IF Then Else อยู่นอก Loop ยาวกว่าก็ยอมครับ เพราะมันเร็วกว่าต่างกันจริงๆ ครับ
มีตัวอย่างหนึ่งให้ลองคิดลับสมองครับ
ผมมีภาพขนาด M x N มองเป็น Array ก็ได้ครับเก็บค่าสีโดยมีค่าเป็นไบต์ 0-255 ตามแบบ 8 bits นะครับ
ผมอยากจะหยิบ จุดใดๆ ใน Array ขึ้นมาแล้วอ่านค่านั้น เช่น มีค่าเป็น a
สิ่งที่ผมอยากได้คือ ต้องการระบายค่า โดยแทนที่สีหรือค่าไบต์ต่างๆ ที่อยู่ใกล้ชิดหรือติดกันกับจุดที่หยิบที่ขึ้นในช่วงของเงื่อนไข

[a - b, a +b] โดยที่ b คืำำำำอค่าจำนวนเต็มที่คร่อมค่าที่หยิบที่มาในตำแหน่งเริ่มต้น
หากเข้าเงื่อนไขนั้นก็ให้แทนที่จุดเหล่านั้น ด้วยสีดำ หรือแทนด้วยค่า 0 หรือ 255 ที่แตกต่างจากสีหรือค่าพื้นหลัง
หากจะให้มองเห็นปัญหาแบบทั่วไปนะครับ ให้มองว่าเรามีภาพใหญ่ภาพหนึ่ง ในภาพมีต้นไม้ สีเทา ต้นใหญ่ โครงสร้างซับซ้อน
สิ่งที่ต้องการคือ เอาเม้าส์ไปดับเบิ้ลคลิกบนตำแหน่งใดๆ ในต้นไม้ แล้วให้โปรแกรมระบายสีต้นไม้ให้เร็วที่สุด ในทางคอมพ์ อาจจะเรียกว่า flooding region หรือว่า growing region ครับ
อิๆๆๆ คิดกันเล่นๆ นะครับ หาเราสามารถ flooding ได้ภายในเวลาอันรวดเร็วก็นับว่าเราจะไปใช้เครื่องรุ่นเก่าๆ หากโปรแกรมทำงานได้ ก็นับว่าเร็วประหลาดใจเช่นกันครับ
ขอบคุณมากครับผม พูดคุยในเรื่องเหล่านี้ ก็สนุกดีเหมือนกันครับ
จะเอาคณิตศาสตร์ไปช่วยคิดแก้ปัญหาการเมืองได้อย่างไรบ้างครับ เห็นยุ่งเหยิงจริงๆ ครับ

9. wwibul
เมื่อ พ. 16 ม.ค. 2551 @ 17:50
520246 [ลบ]

สวัสดีครับ น้อง เม้ง สมพร ช่วยอารีย์

ถ้าถามมาเร็วกว่านี้สักสัปดาห์นึง ผมคงสลัดโจทย์ข้อนี้ออกจากหัวไม่ได้
บังเอิญมาก เมื่อไม่กี่วันก่อน ผมปรับเนื้อหาในหัวข้อ "ฟองน้ำหิน" และหารูปประกอบ เป็นรูปเกี่ยวกับ cluster & percolation แล้วไปเจออัลกอริธึมที่ตรงกับที่น้องเม้งถามมาพอดี ชื่อ Hoshen-Kopelman Algorithm
ฟองน้ำหิน คือการที่ภูเขาทั้งลูก มีความพรุนในนั้น และมีการต่อเชื่อมถึงกัน ทำให้น้ำไหลผ่านเนื้อหินได้ ซึ่งอัลกอริธึมนี้
คงคล้าย ๆ กับโจทย์ที่น้องเม้งว่ามา
อ่านแล้วพบว่า เป็นอัลกอริธึมที่น่าสนุกครับ
แต่ที่น่าสนุกกว่าคือ ผมกำลังนึกถึงโจทย์ทางปฎิบัติ ที่สวมเข้าพอดีกับอัลกอริธึมนี้ ว่ามีไหม
ซึ่งโจทย์แบบนี้ คิดไปเรื่อย ๆ สบาย ๆ สิบปีก็ไม่สายครับ

ส่วนเรื่องที่ว่า

"จะเอาคณิตศาสตร์ไปช่วยคิดแก้ปัญหาการเมืองได้อย่างไรบ้างครับ เห็นยุ่งเหยิงจริงๆ ครับ..."

คิดว่า ใช้แค่ + กับ - ก็น่าจะพอนะครับ
ิbrute force algorithm ธรรมดาครับ
(หาว ...)

10. वीर
เมื่อ พ. 16 ม.ค. 2551 @ 19:04
520295 [ลบ]

wwibul: อาจจะเป็นไปได้ว่าอินเดียระบบก็ดีกว่า เครื่องไม้เครื่องมีก็อาจจะดีกว่าประเทศไทยด้วย.

11. เม้ง สมพร ช่วยอารีย์
เมื่อ พ. 16 ม.ค. 2551 @ 19:36
520341 [ลบ]

สวัสดีครับ อ.วิบุล และบ่าววีร์

ผมทราบมาว่าอินเดีย มีหนังสือเยอะครับ และหนังสือราคาถูกครับ
ที่น่าสนใจเพิ่มคือ เค้าใช้อังกฤษเยอะด้วยครับ (หากจำไม่ผิดจะใช้เป็นภาษาราชการด้วยครับ อันนี้อาจจะเป็นประตูหนึ่งในการให้เค้าอ่านหนังสือแพร่หลายขึ้นได้)
ตอนนี้ทราบว่า จะใช้การแพร่ความรู้ผ่านทีวีด้วย ซึ่งเป็นสื่อที่ดีอยู่แล้ว เพียงแต่บ้านเราอาจจะให้ความสนใจไปในทางอื่นมากไปหน่อย

เรื่องอัลกอริทึมนี้ Hoshen-Kopelman Algorithm น่าสนใจดีครับ

ผมเคยนำแนวคิดที่ตั้งโจทย์กับอาจารย์ เอาไปประยุกต์กับการไหลของน้ำในภาพครับ หรือการค้นหาโครงสร้างต่างๆ จากภาพ ได้น่าสนใจครับ แต่ผมแก้สมการโดยใช้หลักการน้ำไหล เป็น Parabolic PDE, heat equation หรือจะใช้แบบ wave equation ก็ได้ครับแต่เปลืองกว่า heat equation ครับ

มีภาพเคลื่อนไหวตัวอย่างให้ดูครับผม คลิกที่นี่ครับ เป็นโครงสร้างเส้นใบไม้ นะครับ

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

ขอบคุณมากๆ ครับผม

12. wwibul
เมื่อ พ. 16 ม.ค. 2551 @ 21:50
520432 [ลบ]

น้องเม้ง สมพร ช่วยอารีย์

ปรากฎการณ์เหล่านี้ ใช้แบบมหภาค มีข้อดีคือ แม่นยำสูง และใช้ algorithm รีดพลังเครื่องได้ แต่ต้องลงทุนเขียนโปรแกรมเยอะ ถ้าเจองานเล็กมาก ๆ บางงาน อาจไม่คุ้ม
ผมมองว่า ในงานบางแบบ วิธีแบบจุลภาค เช่น cellular automaton หรือเป็น stochastic modeling ไปเลย อาจเขียนโปรแกรมง่ายกว่า แม้ว่า จะช้ากว่ามาก
แต่ผมมองว่า เวลาที่ใช้รวม = เวลาเครื่อง + เวลาคน ดังนั้น การ optimize รวม ต้องนำเรื่องคนเข้ามาคิดด้วย ไม่งั้นถือว่า มองไม่ครบทุกด้าน
ลองนึกถึง grid volume ของน้ำจำนวน grid มาก ๆ ต่างก็"ไหล"ตามกฎของตัวเอง แสวงหาเส้นทางการไหลไปตามทางของตนเอง แล้วประมวลพฤติกรรมมหภาค ซึ่งมีข้อดีคือ ไม่ต้องคำนวณโยงใยทั้งโลกเหมือน PDE แต่คำนวณแบบจำกัดอาณาเขตเล็ก ๆ ของแต่ละชิ้นย่อย สามารถลัดเลาะไปตามผิวไม่เรียบในสามมิติ โดยไม่ต้อง solve แต่ใช้วิธีตามรอยแทน ก็จะทำให้สามารถได้ค่าเฉลี่ยพฤติกรรมระบบได้คร่าว ๆ ดีพอสมควร
ตัวอย่างเช่น กรณีของ biochemical kinetics มี Gillespie's Algorithm ที่ผมเคยเขียนเล่าไว้ ก็ใช้แบบนี้ คือแทนที่จะใช้ RKF5 ก็มาใช้ stochasic modeling รายโมเลกุลไปเลย ทำให้กำหนดเวลาได้เลย ว่า จะรอได้นานแค่ไหน รอได้เดี๋ยวเดียว ก็ simulate ไม่กี่โมเลกุล รอได้นาน ก็เพิ่มจำนวนโมเลกุล ซึ่งเพิ่มความแม่นยำขึ้น เห็นพฤติกรรมได้ดีพอสมควร ไม่แพ้การแก้เต็มรูปแบบเหมือนกัน

13. wwibul
เมื่อ พ. 16 ม.ค. 2551 @ 22:00
520443 [ลบ]

คุณบ่าวवीर

"ระบบดีกว่า" เห็นภาพไม่ชัดเท่าไหร่
...ครูสอนดีกว่า ?
...การสนับสนุน จริงจังกว่า คือ พูดกับทำ สอดคล้องกัน ?
...การประกันคุณภาพการศึกษา หลุดจากโลก surreal ได้ ?
...หลักสูตร เนื้อหาดีกว่า ?

เป็นประเด็น ที่ยังต้องรอข้อมูลเพิ่ม

แต่อย่างน้อย ประเทศที่เคยเป็นอาณานิคมอังกฤษ เรื่องที่ค่อนข้างจะแน่ใจได้ คือ เรื่องภาษา และเรื่องส่งเสริมหนังสือแพร่หลายและราคาถูกนี่ ผมเชื่อว่า เป็นไปได้สูง

เรื่องอื่น ไม่รู้เหมือนกันครับ

กลับขึ้นข้างบน

ชื่อ:
อีเมล:
IP แอดเดรส:	38.103.63.56
	เรียกใช้งานตัวจัดการข้อความ
ข้อความ:

รหัสสุ่ม:	(ใส่รหัสสุ่มที่แสดงไว้ด้านบน)
	ยกเลิก