วงแหวนเว็บ

neizod's speculation

insufficient data for meaningful answer

Swap ตัวแปร

Saturday, March 2, 2013, 06:57 PM

โปรแกรมที่เล็กและง่ายรองจาก hello world ที่โปรแกรมเมอร์หลายคนต้องผ่านตามาบ้าง คือโปรแกรม (ฟังก์ชัน) สำหรับสลับค่าตัวแปรนั่นเอง

แต่ก่อนจะลงลึกที่รายละเอียด มาดู simple yet best practice ใน Pyhton กันก่อน :P

a, b = b, a

อธิบายก่อนว่าการเข้าถึง data ในคอมพิวเตอร์ จะคล้ายๆ กับคนที่มีแขนข้างเดียว คือหยิบของได้ทีละ 1 อย่าง ไม่สามารถหยิบของพร้อมกัน 2 อย่างแล้ววางสลับที่กันทันทีได้เหมือนในชีวิตจริง

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

จะอธิบายให้คอมพิวเตอร์เข้าใจได้ ก็ต้องบอกด้วยว่าที่ว่างนั้นคือตรงไหน (พูดลอยๆ ไม่ได้ เดี๋ยวกลับไปหาไม่เจอ) เช่นนี้

int t;

t = a;
a = b;
b = t;

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

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

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

a = a + b;
b = a - b;
a = a - b;

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

ถ้าจะมองให้เป็นไปในทางคอมพิวเตอร์จริงๆ ต้องเปลี่ยนการดำเนินการ +, - ไปใช้ xor แทน เช่นนี้

a ^= b;
b ^= a;
a ^= b;

ซึ่งสามารถลดรูปได้อีกขั้นจนเหลือเพียงบรรทัดเดียวว่า

a ^= b ^= a ^= b;

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

process [1, 2]:
  goto address [a, b]
  read into process memory
  sync with process [2, 1]
  goto address [b, a]
  write from process memory

ส่วนภาษาเชิง functional ที่ไม่ยอมให้มี mutable อย่างการสลับเปลี่ยนค่าตัวแปร ก็ยังสามารถทำท่านี้ได้โดยใช้เทคนิคตั้งชื่อตัวแปรสลับที่กันใน environment ที่ต่างกัน (ภาษาเค้าเรียกว่า Monad) ต่อไปนี้คือตัวอย่างใน Haskell

do (a,b) <- return (b,a)
   someMagic a b
   ...

หรือแบบนี้ใน Lisp (สังเกตการใช้คำสั่ง let เพื่อสลับตัวแปร)

(let ([a b]
      [b a])
  (magic-happens a b ...))

สุดท้ายนี้กลับไปดู Python ที่เรียบง่ายอีกรอบ แท้จริงแล้วมันคือการสั่ง

container = b, a
a, b = container

แปลได้ว่า แรกสุดมันจะเก็บค่าตัวแปร b และ a ตามลำดับลง container ชนิดหนึ่ง (ใน Python มันคือ tuple) แล้วหลังจากนั้นจึงดึงตัวแปรออกจาก container นี้มาให้ตัวแปร a และ b ตามลำดับ แนวคิดแบบนี้ค่อนข้าง general มาก และสามารถนำไปใช้กับกรณีที่มีตัวแปรให้สลับเยอะกว่านี้ได้ด้วย เช่น

a, b, c, d = d, -b, -c, a

neizod

author