การโปรแกรมแบบไม่มีวันตาย

posted on 27 May 2015 23:51 by kimballlegates

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

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

ลองดูโปรแกรมที่มีการวนซ้ำต่อไปนี้นะครับ

            for i=1 to10

                        for j=1 to 20

                                    print i,j

                                    work for the case i,j

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

วิธีการที่มันจะไม่ให้ค่า i และ jต้องเริ่มต้นเป็น 1 และ 1  แต่ยังคงสามารถเพิ่มค่าจนถึงค่ามากสุดของแต่ละตัว ก็ด้วยการใช้คำสั่งwhile ดังต่อไปนี้

            i=8

            j=3

            while i<=10

                        while j<=20

                                    print i,j

                                    work for the case i,j

                        i=i+1

                        j=1

แค่นี้ก็จะสามารถทำงานต่อไปได้โดยไม่เสียเวลาทำซ้ำของเดิม

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

            ระหว่างที่ให้ผู้อ่านได้ลองคิดหาคำตอบ  ตอนนี้ก็ขอพักโฆษณาตัวเองก่อน  เพื่อเพิ่มความศรัทธาของผู้อ่านต่อการใช้งานโปรแกรมแบบเรียกตัวเอง   ผมได้เขียนโปรแกรมหลายอย่างเกี่ยวกับการแก้ปัญหาเฉพาะต่าง ๆ  ซึ่งส่วนใหญ่ก็เป็นเกมส์ต่าง ๆ  เช่น ไม้พับลูกบาศก์ ว่ามันมีแค่ 2 คำตอบซึ่งคล้ายกันเพราะเป็นภาพสะท้อนกันเอง  เหมือนกำมือซ้ายกับกำมือขวานั่นแหละ

p1 p2

เคยหาคำตอบตัวต่อวิศวกรน้อย ซึ่งแบบพิเศษที่ผู้ประดิษฐ์ท้าไว้มันไม่มีคำตอบ   เคยหาคำตอบตัวต่อตาราง 8x8 ด้วย 13 ชิ้น  

p3

ซึ่งเป็นผลงานเก่าย้อนไปปี 2536 สมัยที่คอมพิวเตอร์ยังเร็วแค่ 35MHz (ตอนนี้ก็ปาเข้าไปเป็น GHz กันแล้ว)   เก่าน้อยกว่านั้นหน่อยก็มีโปรแกรม tetris สู้กันผ่านอินเตอร์เน็ต   ช่วงหลังก็ลองแก้ Sudokuแต่ไม่สมบูรณ์เพราะมันซับซ้อนมาก   และก็แก้ bloxorz เกมที่ฝึกสมองได้ดีจนผมเชียร์ให้ลูกเล่น

p4

เอาหละ มาต่อกันว่าเราจะทำยังไงในกรณีที่เป็นโปรแกรมเรียกตัวเอง  ซึ่งผมก็ขอกำหนดเป็นการทำงานวนแบบ for ซ้อนกัน 500 ชั้น  ซึ่งก็คงไม่มีใครสวมเขาควายเขียนซ้อนกัน 500 ชั้นแบบ

            for i1=1 to max_i1

                        for i2=1 to max_i2

                                    …

                                                for i500=1 to max_i500

                                                            work for the case i1,i2,...,i500

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

            recursive_work(n)=

                        for i[n]=1 to max_i[n]

                                    if n=500

                                                work for the case i1,i2,...,i500

                                    else

                                                recursive_work(n+1)

โดยขยายความว่า i และ max_i เป็นตัวแปร array ขนาด 500 ช่อง  และเราก็จะเรียกโปรแกรมให้เริ่มทำงานด้วยคำสั่ง

recursive_work(1)

เราจะเขียนส่วนเรียกตัวเองได้อีกแบบหนึ่งว่า

            recursive_work(n)=

                        if n>500

                                    work for the case i1,i2,...,i500

                        else

                                    for i[n]=1 to max_i[n]

                                                recursive_work(n+1)

ก็จะไม่ต้องตรวจสอบค่า n บ่อย ๆ  แต่ต้องเรียกตัวเองต่อไปถึงขั้น 501

และหากต้องการแบบรันต่อได้ก็ต้องเขียนเป็น

            recursive_work(n)=

                        while i[n]<=max_i[n]

                                    if n=500

                                                work for the case i1,i2,...,i500

                                    else

                                                recursive_work(n+1)

                                                i[n]=i[n]+1

                                                for k=n+1 to 500

                                                           i[k]=1

เพียงแต่ก่อนเริ่มรันต่อ ต้องมีการให้ค่า i ต่าง ๆ จากค่าเก่า เช่น

            i[1]=8

            i[2]=3

            i[3]=6

           

            i[500]=14

หรือถ้าเป็นการรันครั้งแรกก็ใช้คำสั่ง

            for k=1 to 500

                        i[k]=1

สำหรับโปรแกรมเรียกตัวเองที่มีการจบด้วยเงื่อนไขอื่นก็ทำได้ในทำนองเดียวกัน

            ผมก็ขอทิ้งท้ายไว้ว่าเมื่อสมัยที่ยังไม่มี Microsoft Windowsนั้น  ผู้คนส่วนใหญ่ก็ใช้ระบบปฏิบัติการ DOS  ตอนนั้นผมก็มีความคิดจะเก็บสภาพเครื่องโดยให้เมื่อเปิดใหม่มันจะกลับมารันต่อ   ตอนนั้นก็วางแนวคิดไว้ว่าให้โปรแกรมมันไปอยู่ในตำแหน่งเฉพาะของหน่วยความจำแล้วเก็บทุกส่วนของหน่วยความจำลงดิสค์  เมื่อเปิดเครื่องใหม่ก็ให้มันอ่านข้อมูลมายัดใส่หน่วยความจำให้เหมือนเดิม  โปรแกรมต่าง ๆ ก็จะทำงานต่อเหมือนไม่ได้ปิดเครื่องพักเลย   แต่ก็ไม่ได้ลงมือทำ   ในปัจจุบันความสามารถนี้ถูกเรียกว่าการจำศีล (hibernation)   ซึ่งมีความจำเป็นมากในการทำงาน   มันเปิดโอกาสให้เราปิดเครื่องดับไฟได้เลย (ไม่ใช่แค่ standby  แต่ก็ควรเซฟทุกอย่างก่อน)  แล้วเมื่อเปิดใหม่ตื่นขึ้นมาก็เหมือนทำงานต่อได้เลย  ไม่ต้องมาเปิดโปรแกรมต่าง ๆ ใหม่   ไม่ต้องมานึกว่าลืมทำอะไรต่อบ้าง   โดยเฉพาะอย่างยิ่งเมื่อโน้ตบุคเราแบ็ตจะหมดก็ควร hibernate แล้วจะทำงานต่อได้ด้วยความสะดวก เอย

 

Comment

Comment:

Tweet