เจาะลึกเทคนิค Two Pointers: วิธีเขียนโค้ดให้เร็วและมีประสิทธิภาพสำหรับมือใหม่

ทำความเข้าใจเทคนิค Two Pointers คืออะไรและทำไมต้องใช้

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

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

การใช้เทคนิคนี้มักเปลี่ยนความซับซ้อนของโค้ดจากแบบ O(n^2) (เวลาที่ใช้เพิ่มขึ้นเป็นทวีคูณตามขนาดข้อมูล) ให้เหลือเพียง O(n) (เวลาที่ใช้เพิ่มขึ้นตามจำนวนข้อมูลแบบเส้นตรง) ซึ่งถือว่าเร็วมากในการจัดการกับ Array (ชุดข้อมูลที่เก็บค่าไว้ต่อเนื่องกัน) หรือ String (ข้อความ) ที่มีจำนวนมาก การฝึกใช้เทคนิคนี้จะทำให้โค้ดของน้องๆ ดูเป็นมืออาชีพและมีประสิทธิภาพสูงขึ้นทันที

เมื่อไหร่ที่ควรหยิบเทคนิค Two Pointers มาใช้

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

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

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

# ตัวอย่างการเช็ก Palindrome (ข้อความที่อ่านหน้าหลังเหมือนกัน)
def is_palindrome(s):
    left = 0 # จุดเริ่มต้นจากซ้าย
    right = len(s) - 1 # จุดเริ่มต้นจากขวา
    while left < right:
        if s[left] != s[right]:
            return False # ถ้าไม่เท่ากันแสดงว่าไม่ใช่
        left += 1 # ขยับซ้ายไปทางขวา
        right -= 1 # ขยับขวาไปทางซ้าย
    return True # ถ้าผ่านหมดแสดงว่าเป็น

คำอธิบายโค้ด: บรรทัดที่ 3-4 คือการกำหนดจุดชี้สองจุดที่หัวและท้าย บรรทัดที่ 6 คือการเปรียบเทียบตัวอักษรที่ตำแหน่งนั้นๆ ถ้าไม่เท่ากันให้หยุดทันที บรรทัดที่ 8-9 คือการขยับตัวชี้เข้าหากันเพื่อตรวจสอบคู่ถัดไป

ผลลัพธ์ที่ควรเห็น: หากป้อนค่า "level" โปรแกรมจะคืนค่าเป็น True แต่ถ้าป้อนค่า "hello" โปรแกรมจะคืนค่าเป็น False ทันทีเพราะตัวอักษรตัวแรกและตัวสุดท้ายไม่ตรงกัน

กลยุทธ์การเคลื่อนที่ของตัวชี้แบบต่างๆ

การเดินตัวชี้ไม่ได้มีแค่แบบเดียว แต่มันขึ้นอยู่กับลักษณะของโจทย์ที่เราเจอ โดยกลยุทธ์แรกคือ Opposite Direction (การเคลื่อนที่สวนทางกัน) แบบที่ใช้ในตัวอย่างก่อนหน้านี้ คือการวางตัวชี้ไว้สองฝั่งแล้ววิ่งเข้าหากัน ซึ่งเหมาะมากสำหรับการหาผลรวมในรายการที่เรียงลำดับแล้ว หรือการตรวจสอบข้อความว่าเป็นแบบ Palindrome หรือไม่

กลยุทธ์ที่สองคือ Same Direction (การเคลื่อนที่ไปในทิศทางเดียวกัน) มักใช้ตัวชี้ตัวหนึ่งวิ่งนำไปก่อนเพื่อสำรวจข้อมูล ส่วนอีกตัวคอยจัดการหรือบันทึกค่าที่ถูกต้องไว้ด้านหลัง วิธีนี้มีประโยชน์มากในงานจำพวกการกรองข้อมูลที่ไม่ต้องการออก เช่น การลบตัวเลขซ้ำในรายการ หรือการย้ายเลขศูนย์ไปไว้ท้ายรายการโดยไม่เปลี่ยนลำดับเลขอื่น

กลยุทธ์สุดท้ายคือ Fast and Slow Pointers (ตัวชี้แบบเร็วและช้า) ซึ่งเป็นเทคนิคระดับสูงขึ้นมาหน่อย โดยให้ตัวชี้ตัวหนึ่งวิ่งเร็วกว่าอีกตัว เช่น ตัวหนึ่งวิ่งทีละหนึ่งก้าว อีกตัววิ่งทีละสองก้าว วิธีนี้มักใช้ในการหาจุดกึ่งกลางของข้อมูลหรือตรวจจับวงจรในรายการที่เชื่อมโยงกัน (Linked List - ข้อมูลที่เก็บเป็นโหนดต่อกันเหมือนโซ่) ซึ่งจะช่วยให้เราแก้ปัญหาซับซ้อนได้โดยไม่ต้องใช้หน่วยความจำเพิ่ม

ขั้นตอนการฝึกฝนจากโจทย์สู่โค้ด

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

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

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

จุดที่มือใหม่มักพลาดและวิธีป้องกัน

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

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

สุดท้ายคือการเข้าถึงข้อมูลนอกขอบเขต (Index Out of Bounds) เช่น พยายามอ่านข้อมูลในตำแหน่งที่ไม่มีอยู่จริง ให้ตรวจสอบขนาดของข้อมูลให้ดีก่อนเสมอ โดยเฉพาะในภาษาที่ไม่มีการจัดการความปลอดภัยของตำแหน่งข้อมูลอัตโนมัติ การใช้ if หรือ while เช็กขอบเขตให้ดีจะช่วยให้โปรแกรมทำงานได้อย่างราบรื่นและไม่พังกลางคัน

สรุป: เปลี่ยนความรู้เป็นทักษะด้วยการลงมือทำ

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

ลองนำไปใช้กับโจทย์จริง เช่น การทำ Two Sum (การหาคู่ตัวเลขที่บวกกันได้ค่าที่กำหนด) โดยกำหนดให้รายการเรียงลำดับไว้แล้ว ถ้าบวกกันแล้วได้น้อยกว่าเป้าหมายให้เลื่อนตัวชี้ซ้ายขึ้น ถ้าได้มากกว่าเป้าหมายให้เลื่อนตัวชี้ขวาลง ทำแบบนี้ซ้ำๆ จนกว่าจะเจอคำตอบ การทำโจทย์เหล่านี้บ่อยๆ จะทำให้ทักษะการคิดแบบอัลกอริทึมของน้องๆ พัฒนาขึ้นอย่างก้าวกระโดด

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

ที่มา: Mastering Two Pointers: A Step-by-Step Guide to Solving Sequence Problems — DEV Community