JLab : Instruction Profile Examples

สิ่งที่นำเสนอข้างล่างนี้ได้มาจากการทำงานแบบใหม่ใน JLab ที่อยู่ในเมนู Run -> Run+Profile (หรือจะใช้ปุ่ม Ctrl+Shift+F5). ถ้าเราอยากรู้ว่าแต่ละคำสั่งในโปรแกรมทำงานกี่ครั้ง Run+Profile จะนับให้ โดยระบบจะแทรกคำสั่งนับไว้ข้าง ๆ แต่ละคำสั่งในโปรแกรม แปลโปรแกรมที่ถูกเปลี่ยนแปลง แล้วก็สั่งทำงานตามปกติ พอทำงานเสร็จ ระบบจะนำผลการนับมาสรุป หาค่าเฉลี่ย และนำเสนอดังแสดงข้างล่างนี้ การนำเสนอมีสองแบบ ทางขวาเป็นตัวโปรแกรมต้นฉบับแต่ละบรรทัดมีสีแสดงโดยความยาวของแถบสีแปรตามสัดส่วนที่คำสั่งนั้นทำงาน (นั่นคือแสดงฮิสโตแกรมของจำนวนครั้งที่คำสั่งในโปรแกรมทำงาน แต่แสดงฮิสโตแรกมในแนวนอน) สิ่งนี้ช่วยให้เรารู้ว่าส่วนใดในโปรแกรมการทำงานมากหรือน้อยเท่าใด

ส่่วนทางซ้ายแสดงกราฟเส้นของจำนวนครั้งที่คำสั่งทำงานกับปริมาณข้อมูลที่โปรแกรมรับไปประมวลผล โดยคำสั่งที่สนใจก็คือคำสั่งต่าง ๆ ที่เราเลือกทางขวา (เลือกโดยกดที่ checkbox ข้าง ๆ หมายเลขปบรรทัดของคำสั่ง จะเห็นสีของบรรทัดที่เลือกต่างจากบรรทัดที่ไม่ได้เลือก) เราสามารถใช้กราฟนี้เพื่อศึกษาอัตราการเติบโตของฟังก์ชันเวลาการทำงานของโปรแกรมได้ การทดลองแปรเปลี่ยนปริมาณข้อมูลที่ส่งให้โปรแกรมทำงานนั้น อาศัยการเขียน @Profile กำกับหน้าเมท็อดที่สนใจ จากตัวอย่าง bubbleSort ข้างล่างนี้ เราใช้ตัวสร้างข้อมูลแบบอาเรย์ของจำนวนเต็มที่มีข้อมูลสุ่ม RandomIntArray โดยให้ส่งอาเรย์ที่มีขนาดตั้งแต่ 0 ถึง 100 ช่อง (เพิ่มขนาดครั้งละ 2) และสั่งทำงานเมท็อด bubbleSort เพื่อทำงานของข้อมูลแต่ละขนาดเป็นจำนวน 30 ครั้งซ้ำๆ (โดยข้อมูลภายในอาเรย์มีการเปลี่ยนแปลง) เพื่อเก็บรวบรวมผลแล้วหาค่าเฉลี่ย

ผมเองใช้ระบบนี้เป็นตัวช่วยในการสอนการวิเคราะห์อัลกอริทึม (ลองกด checkbox ต่าง ๆ ในรูปข้างล่างนี้ดู)

Fibonacci Numbers

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

FindMax

เราเขียนเมท็อดหาค่ามากสุดได้ง่ายด้วยการไล่เปรียบเทียบข้อมูลไปเรื่อยจนครบทุกตัว ถ้ามีข้อมูล n ก็ต้องเปรียบเทียบข้อมูลเป็นจำนวน n – 1 ครั้ง แต่ถ้าเราสนใจอยากรู้ว่า แล้วตัวแปร max ที่มีไว้เก็บค่ามากสุดระหว่างการเปรียบเทียบนั้น มีการเปลี่ยนแปลงค่ากี่ครั้ง ตรงนี้จะตอบได้ไม่ค่อยชัดเจน เพราะขึ้นกับลักษณะของข้อมูลขาเข้า (ถ้าเรียงจากน้อยไปมาก ก็เปลี่ยนทุกครั้ง ถ้าเรียงจากมากมาน้อย ก็เปลี่ยนครั้งเดียว) ผลการทดลองข้างล่างนี้แสดงว่า ค่าของ max เปลี่ยนเป็นจำนวนครั้งที่เป็นฟังก์ชันในลักษณะ ........................ ของปริมาณข้อมูล (ดูจากกราฟเส้นแล้วลองเติมคำในช่องว่างเอง) แล้วก็ลองวิเคราะห์ด้วยคณิตศาสตร์ดู

HeapSort

การทำงานของ heapsort ประกอบด้วยขั้นตอนการสร้างฮีป (บรรทัดที่ 11 – 12) และขั้นตอนการลบตัวมากเพื่อสลับกับตัวหลังสุดในกลุ่ม (บรรทัดที่ 13 – 16) ขั้นตอนทั้งสองอาศัยการปรับฮีปในเมท็อด heapify การทำงานของทั้งสองขั้นตอนที่ลักษณะคล้ายกันมาก แต่หากดูจากภาระการทำงาน (จากฮิสโตแกรม) จะต่างกันมาก ถ้าไปดูที่กราฟเส้นจะพบว่าขั้นตอนทั้งสองใช้เวลาที่คล้าย ๆ กับว่าจะแปรผันโดยตรง (เป็นเชิงเส้น) กับปริมาณข้อมูล ต่างกันแค่ความชันเท่านั้น แต่ถ้าเราให้ระบบช่วยคำนวณค่าของแกน y ให้ใหม่ คือแทนที่จะนำจำนวนครั้ง (ให้ชื่อว่า c) ที่คำสั่งทำงานมาใช้ตรง ๆ ก็ลองให้หารด้วยปริมาณข้อมูล (n) ดู คือให้เป็น c/n โดยป้อนในช่องทางซ้ายล่างที่แสดงข้อความ f(n,c) = c ให้เป็น f(n,c) = c/n จะได้ผลที่เปลี่ยนไป โดยเส้นล่างจะเป็นเส้นตรงขนานกับแกน x แสดงว่า c/n เป็นค่าคงตัว นั่นคือ c แปรตาม n แบบเชิงเส้น ให้ขณะที่เส้นจะเปลี่ยนเป็น ........ ลองทำดู แล้วสรุปคร่าว ๆ ว่า c แปรเป็นฟังก์ชันอะไรของ n

Linear Search

เท่าที่เคยถาม ๆ มา พบว่า หากให้เขียนเมท็อดค้นข้อมูลว่า x ปรากฏที่ตำแหน่งใดในอาเรย์ d (โดยที่ค่าใน d เป็นอะไรก็ได้ ไม่จำเป็นต้องเรียงลำดับ) ก็มักจะเขียนให้ค้นแบบลำดับ วิ่งค้นจากซ้ายไปขวา ถ้าโชคดีก็ค้นเจอตัวแรก โชคร้ายก็ต้องค้นไปถึงตัวท้าย โดยเฉลี่ยก็น่าจะค้นไปประมาณครึ่งหนึ่งของอาเรย์ ผลการทดลองข้างล่างนี้ก็ยืนยันตามที่กล่าวมาในกรณีเฉลี่ย (สังเกตค่าของแกน x และ y ในกราฟ มีความชันประมาณ 0.5 แกน x มีค่ามากสุดที่ 100 ในขณะที่แกน y มีค่ามากสุดที่ 50)

Randomized Linear Search

จากเมท็อดการค้นข้างบนแบบลำดับ น่าจะเกิดคำถามว่า ทำไมต้องค้นจากซ้ายไปขวา ทำไมไม่ค้นจากขวามาซ้าย หรือว่าทำไมไม่ลองโยนเหรียญก่อนแล้วค่อยตัดสินใจว่าจะค้นจากซ้ายไปขวา หรือจากขวามาซ้าย (ดังเมท็อด rand ที่เขียนข้างล่างนี้) หากคิดดูจะพบว่า ข้อมูลตัวที่จะทำให้วิธีการค้นแบบโยนเหรียญนี้ทำงานข้าสุดแน่ ๆ ก็คือข้อมูลที่จะค้นแล้วพบอยู่ตรงกลางอาเรย์ ไม่ว่าจะค้นซ้ายไปขวา หรือขวามาซ้ายก็ต้องค้นครึ่งอาเรย์เท่ากัน หากฟังเผิน ๆ อาจรู้สึกว่า วิธีนี้น่าจะดี ตัวแย่สุด ๆ ใช้การค้นแค่ครึ่งอาเรย์ กรณีเฉลี่ย ๆ ก็น่าจะค้นน้อยกว่า การทดลองข้างล่างนี้ชี้ให้เห็นว่า ไม่จริงหรอก ภาระการทำงานของทั้งเมท็อดหลาย ๆ ครั้ง ต้องรวมทั้งกรณีค้นซ้ายไปขวา กับค้นขวามาซ้าย สำหรับกราฟเส้นที่แสดงทางขวานั้น เพื่อให้การตีความที่ถูกต้องเราต้องเลือกทั้งเส้น 12 และ 15 และเลือกให้รวมผลทั้งสองเส้นแล้วมาแสดง (คือเลือก checkbox ที่เขียน &Sigma(lines) ข้างล่างกราฟเส้น) จะเห็นว่ามีความชันเป็น 0.5 เช่นกัน

MinMax

วิธีหาทั้งค่าน้อยสุดและมากสุดทำได้ง่ายโดยวิ่งในอาเรย์จากซ้ายไปขวา แล้วก็เปรียบเทียบหาทั้งค่ามากและน้อยสุดได้ บางคนก็อาจคิดแบบ divide and conquer โดยแบ่งสองส่วนส่วนละครึ่ง ไปหาน้อยสุดและมากสุดของทั้งสองฝั่ง แล้วค่อยนำน้อยสุดซ้ายเทียบน้อยสุดขวา กับมากสุดซ้ายเทียบมากสุดขวา ก็จะได้น้อยและมากสุดของทั้งหมด การทดลองข้างล่างนี้เปรียบเทียบกรณีที่เราแบ่งสองส่วนส่วนละครึ่ง กับแบ่งสองส่วน ส่วนซ้าย 2 ตัวและส่วนขวา n - 2 ตัว เส้นซิกแซกคือผลของการแบ่งแบบครึ่ง ๆ ส่วนเส้นเกือบตรงด้านล่างเป็นของการแบ่งแบบหลัง ผลที่ได้รู้สึกจะขัดกับที่เห็น divide and conquer ว่ามักจะแบ่ง 50%-50% เรื่อย ๆ ลองคิดต่อได้ว่าทำไมถึงได้ผลเช่นนี้

String Concatenation

เมท็อดข้างล่างเขียนวนต่อสตริงไปเรื่อย ๆ จำนวน n ครั้ง ครั้งละตัว ซึ่งก็แน่นอนว่ามีการต่อสตริง n ครั้ง ตรงไปตรงมาตามจำนวนรอบของ for แต่ถ้าเราไป click ที่ checkbox times เพื่อแสดงเวลาการทำงานในการต่อสตริงแบบนี้ (ลองคลิกตอนนี้เลย) จะพบว่าได้ผลไม่เป็นฟังก์ชันของ n ทำไมจึงเป็นเช่นนั้น (ข้อแนะนำ : อย่าลิมว่า สตริงในจาวาเป็น immutable object จึงไม่มี operation ใดในจาวาที่กระทำกับสตริงเปลี่ยนแปลงสตริงได้ จึงต้องสร้างสตริงใหม่เสมอ)

ยังมีอีก ...

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