เรื่องวุ่น ๆ ของการคูณ Matrix
ไม่ได้เขียน Blog มาประมาณชาติเศษ พอดีงานหลวงเข้าเยอะมาก งานราษฎร์เลยพักไว้ก่อน ผมลอง list หัวข้อเกี่ยวกับ C#, Programming และคณิตศาสตร์ที่น่าเขียนออกมา ได้ตั้ง 50-60 กว่าหัวข้อ !!! แล้วหลังยาวอย่างผมจะเขียนต่อไปได้อีกกี่น้ำเนี่ย...
ก่อนเข้าเรื่อง ขอเกริ่นนิดนึงก่อนนะครับว่า สิ่งที่ผมเขียนเนี่ย เป็นส่วนหนึ่งของการจัดการความรู้ของผม ซึ่งเป็นไปได้ว่ามีจุดบกพร่องใด ๆ ทั้งด้านความรู้และงานเขียน ดังนั้นกรุณาติชมเต็มที่เลยครับ เพื่อจะได้ปรับปรุงต่อไป
หรือถ้าคุณสงสัย อยากให้ผมอธิบายอะไร request ได้เต็มที่เลยครับ เพราะมันจะเป็นการต่อยอดความรู้
และถ้าคุณผ่านมาอ่านเฉย ๆ กรุณาสละเวลาเขียน Comment สั้น ๆ เพื่อที่ Effort ของคุณ จะเป็น Effort ของผมในการเขียนต่อไป
มีผู้อ่านท่านหนึ่ง Comment ว่าให้ช่วยอธิบายเรื่อง Matrix Multiplication (ไม่รู้ว่าเจ้าของ Comment ลืมไปรึยัง)
Matrix คือ ชุดตารางตัวเลข เพื่อใช้ศึกษา System of Linear Equations (สมการเชิงเส้นหลายตัวแปร) Matrix สามารถ บวก ลบ คูณ กันเองได้ นอกจากนี้มันยังมีคุณสมบัติอีก มากมาย เพื่อที่จะเปลี่ยนรูปมัน
(ตัวอย่างของ Matrix รูปจาก Wikipedia)
การนำ Matrix ไปใช้งานในชีวิตจริงก็มี มายมาย เช่น - การแก้ปัญหาสมการเชิงเส้น - การประมวลผล Graphics - การเข้ารหัส - หรือแม้แต่การวิเคราะห์การสูญพันธุ์ของนกเค้าแมว
การบวก Matrix การบวก Matrix, Matrix ที่จะนำมาบวก 2 ตัว ต้องมี Dimension ที่เหมือนกัน เวลาบวกกันก็แค่เอาตัวเลขในแต่ละ Element มาบวกกัน ตัวอย่าง สมมติว่ามี Matrix ชุดหนึ่งขนาด 2 x 3 แทนด้วย S1 ซึ่งเป็นยอดขายของร้านอาหารแห่งหนึ่ง Matrix นี้มี 2 แถว แทนสาขา คือ ร้านอาหารนี้มี 2 สาขา A และ B Matrix มี 3 Columns แทนเมนูอาหาร คือ ร้านนี้มี 3 เมนู (Food1, Food2, Food3)
Food1 Food2 Food3 S1 = A [ 4 2 5] B [ 1 2 3]
และมี Matrix อีกชุด ขนาด 2 x 3 เช่นกัน แทนด้วย S2 ซึ่ง เป็นยอดขายของร้านอาหารเดิมนั่นแหละ แต่เป็นยอดขายในวันต่อมา
Food1 Food2 Food3 S2 = A [ 3 3 1] B [ 3 2 0]
ถามว่ารวมยอดขาย 2 วัน ร้านนี้ขายได้เท่าไหร่
Food1 Food2 Food3 S1 + S2 = A [4 + 3 2 + 3 5 + 1] B [1 + 3 2 + 2 3 + 0]
Food1 Food2 Food3 = A [ 7 5 6] B [ 4 4 3]
ก็แค่เอาตัวเลขในแต่ละช่องมาวางให้ตรงกัน แล้วบวกกัน เช่น ช่อง S1(Food1,A) ก็ต้องบวกกับ S2(Food1,A) เท่านั้น
การคูณ Matrix การคูณ Matrix, Matrix ที่จะมาคูณกันจำนวน Column ของตัวตั้งต้องเท่ากับ จำนวนแถวของตัวคูณ เช่น Matrix ขนาด a x b จะสามารถคูณกับ Matrix ขนาด b x c ได้ และผลลัพธ์ จะเป็น Matrix ขนาด a x c
การคูณของ Matrix จะแตกต่างกับการคูณโดยทั่วไปคือ ไม่มีคุณสมบัติในการสลับที่ คือ X * Y != Y * X
อย่างไรก็ตาม การคูณ Matrix ยังคงมีคุณสมบัติในการเปลี่ยนหมู่อยู่ คือ (X * Y) * Z == X * (Y * Z)
ตัวอย่าง ณ ร้านอาหารแห่งเดิมจากตัวอย่างข้างต้น มียอดขายคือ
Food1 Food2 Food3 S = A [ 7 5 6] B [ 4 4 3]
และร้านอาหารนี้ต้องการคำนวนวัตถุดิบที่ใช้ไป เพื่อนำมาซื้อคืนให้กับร้านอาหารทั้ง 2 สาขา โดยสูตรของอาหารเป็น Matrix ขนาด 3 x 2 แทนด้วย T แถว 3 แถวแทนเมนูทั้ง 3 (Food1, Food2, Food3) Column ทั้ง 2 แทนวัตถุดิบ 2 ชนิด (Raw1, Raw2)
Raw1 Raw2 T = Food1 [ 1 0] Food2 [ 1 1] Food3 [ 3 2]
เพื่อที่จะเอาสาขา มา Map กับวัตถุดิบเราต้องเอา Matrix ทั้ง 2 มาคูณกัน
Raw1 Raw2 S * T = A [7*1 + 5*1 + 6*3 7*0 + 5*1 + 6*2] B [4*1 + 4*1 + 3*3 4*0 + 4*1 + 3*2]
Raw1 Raw2 = A [ 30 17] B [ 17 10]
จากข้างบนวิธีคูณคือ ในแต่ละช่องจะเอาผลคูณของ Food ทั้ง 3 มาบวกกัน เช่น ช่อง ST(Raw1,A) จะมาจาก S(Food1,A)*T(Raw1,Food1) + S(Food2,A)*T(Raw1,Food2) + S(Food3,A)*T(Raw1,Food3)
เอาล่ะครับจบเลข ม.ปลายแล้วครับ มาเริ่ม C# ระดับนักศึกษากัน ผมได้เขียน Class Matrix ไว้แล้วนะครับ Download ได้ที่นี่
ข้างล่างนี้เป็น Code ที่ใช้ในการคูณ Matrix นะครับ
public static Matrix operator *(Matrix a, Matrix b) { //เช็คคุณสมบัติของ Matrix ที่จะมาคูณกัน Column ของตัวตั้งต้องเท่ากับ จำนวนแถวของตัวคูณ if (a.Cols != b.Rows) throw new InvalidOperationException('Illegle matrix dimensions.');
//ประกาศ variable ชื่อ data เป็น Jagged Array //data จะมีขนาดเท่ากับ แถวของตัวตั้ง และ Column ของตัวคูณ double[][] data = empty(a.Rows, b.Cols);
//แต่ละแถวของผลลัพธ์ for (int i = 0; i < a.Rows; i++)
//แต่ละ Column ของผลลัพธ์ for (int j = 0; j < b.Cols; j++)
//เท่ากับผลบวกของ แต่ละ Column ของตัวตั้งคูณกับแต่ละแถวของตัวคูณ for (int k = 0; k < a.Cols; k++) data[i][j] += a[i, k] * b[k, j];
//แปลง Jagged Array เป็น Class Matrix return new Matrix(data, false); }
ยังไม่จบนะครับ Highlight ของวันนี้ไม่ใช่การคูณ Matrix แค่นี้ เราจะมาคูณ Matrix แบบต่อเนื่องกันนะครับ มันมีชื่อว่า Matrix Chain Multiplication
เรื่องของเรื่องคือ อย่างที่กล่าวไว้ว่าคุณสมบัติการคูณของ Matrix มันมีคุณสมบัติในการเปลี่ยนหมู่อยู่ เช่น (X * Y) * Z == X * (Y * Z) เชื่อไหมครับว่าการเปลี่ยนหมู่แม้จะไม่ทำให้ผลลัพธ์เปลี่ยนไป แต่ทำให้ประสิทธิภาพในการคูณเปลี่ยนไป
จำนวนครั้งในการคูณสามารถคำนวนได้โดย แถวของตัวตั้ง * Column ของตัวตั้ง * Column ของตัวคูณ เช่น ถ้า X มีขนาด 10 x 3 Y มีขนาด 3 x 5 Z มีขนาด 5 x 6
จำนวนครั้งของการคูณแบบ (X * Y) * Z คือ (10*3*5 + 10*5*6) = 450 ครั้ง
ส่วนจำนวนครั้งของการคูณแบบ X * (Y * Z) คือ (3*5*6 + 10*3*6) = 270 ครั้ง
จะเห็นว่าหมู่การคูณเปลี่ยนจะทำให้ประสิทธิภาพของการคูณเปลี่ยน โดยอาจจะดีขึ้นหรือแย่ลง ดังนั้น มันเป็นการดีที่เราจะหาว่าเราควรจัดหมู่แบบไหนก่อนการคูณ Matrix
แต่เดี๋ยวก่อนครับ เรื่องมันยังไม่ง่ายแค่นี้ ถ้าคูณซ้อนกัน 3 ตัว มีการจัดหมู่แค่ 2 แบบ ถ้าคูณซ้อนกันซัก 10 ตัวล่ะ มีการจัดหมู่กี่แบบ คำตอบนี้แก้ได้โดยใช้ Binary Bracketing สูตรคือ
(2n-2)! --------- n! (n-1)!
คูณซ้อนกัน 10 ตัว มีการจัดหมู่ 4,896 วิธี!! และจำนวนวิธีเพิ่มขึ้นเรื่อย ๆ อย่างน่ากลัวถ้ายิ่งมีตัวคูณเพิ่มขึ้น เผลอ ๆ ตอนคุณกำลังหาวิธีคูณที่ดีที่สุดอยู่ คนที่ใช้วิธีคูณ Matrix ตามลำดับธรรมดาคูณเสร็จไปนานแล้วก็ได้
ทุกปัญหามีทางแก้ครับ เราสามารถหาวิธีคูณที่ดีที่สุดโดยใช้หลักการของ Dynamic Programming (DP) ผมจะเขียนหลักในการแก้ปัญหาของ DP ทีหลังนะครับ อย่างไรก็ตาม เราได้อ่านเกี่ยวกับ DP คร่าว ๆ และรู้จักกับ Method ชื่อ Memoize ใน Post นี้ แล้วนะครับ
ข้างล่างนี้เป็น Function สำหรับหาวิธีการคูณที่ดีที่สุด
//ประกาศ Matrix Array Matrix[] m;
//ประกาศการทำ Recusive function Func<int, int, KeyValuePair<int, int>> func = null;
//จากลำดับที่ l ถึงตัวที่ r func = (l, r) => (from i in l.To(r - 1)
//สร้าง KeyValuePair, Key คือลำดับที่, Value คือจำนวนครั้งการคูณ select new KeyValuePair<int, int>(i, func(l, i).Value + func(i + 1, r).Value + (m[l].Rows * m[i].Cols * m[r].Cols)) into kvp
//เรียงลำดับตามจำนวนครั้งการคูณ orderby kvp.Value
//เอาแค่ตัวแรกที่มีจำนวนครั้งการคูณที่น้อยที่สุด select kvp).First();
//ถ้าเหลือแค่ลำดับเดียว จำนวนครั้งการคูณเป็น 0 func = func.When((l, r) => l == r, (l, r) => new KeyValuePair<int, int>(l, 0));
//จำคำตอบ func = func.Memoize();
Function นี้มี Input 2 ตัวคือ ลำดับที่เริ่มต้น กับลำดับที่สิ้นสุด และมี Output 2 ตัว ซึ่งผูกเป็น KeyValuePair ตัวเดียว (เพราะ Function มีได้แค่ Output เดียว) Key จะเป็นลำดับที่ดีที่สุดในการคูณ Value จะเป็นจำนวนครั้งการคูณที่ดีที่สุด
การทำงานของ Function เช่น มี Matrix A, B, C, D Function จะแบ่งกลุ่ม 3 แบบ คือ A (B C D) , (A B) (C D), และ (A B C) D จากนั้นก็เอาในวงเล็บไปหาย่อยลงไปอีก เช่น (B C D) ก็จะแบ่งเป็นอีก 2 แบบ คือ B (C D) และ (B C) D เมื่อได้คำตอบที่ดีที่สุดก็ส่งต่อไปเรื่อย ๆ จนถึงระดับบนสุด ได้เป็นคำตอบ
คราวนี้มาลองประสิทธิภาพกัน ก่อนอื่นต้องเขียน Function สำหรับเอาคำตอบที่ได้ไปทำ Chain Multiplication ก่อน
//ประกาศการทำ Recusive function Func<int, int, Matrix> chain = null;
//ทำ Matrix Chain Multiplication chain = (l, r) => chain(l, func(l, r).Key) * chain(func(l, r).Key + 1, r);
//ถ้าเหลือแค่ Matrix เดียว ก็ return Matrix นั้นเลย chain = chain.When((l, r) => l == r, (l, r) => m[l]);
เสร็จแล้วก็ random Matrix สัก 7 ตัว ไปใส่ใน Array
m = new[] { Matrix.Random(1000, 300), Matrix.Random(300, 300), Matrix.Random(300, 500), Matrix.Random(500, 100), Matrix.Random(100, 50), Matrix.Random(50, 300), Matrix.Random(300, 100), };
เริ่มทำการทดสอบ
Matrix n; Stopwatch sw = new Stopwatch();
sw.Start(); n = chain(0, m.Length - 1); sw.Stop(); Console.WriteLine(sw.Elapsed); //2 วินาที
sw.Reset(); sw.Start(); n = m[0] * m[1] * m[2] * m[3] * m[4] * m[5] * m[6]; sw.Stop(); Console.WriteLine(sw.Elapsed); //20 วินาที
จะเห็นว่าถ้าใช้ Function Chain Multiplication จะเร็วกว่าการคูณตามลำดับถึง 10 เท่า จบล่ะครับ
Create Date : 20 พฤศจิกายน 2551 |
Last Update : 20 พฤศจิกายน 2551 1:42:30 น. |
|
10 comments
|
Counter : 4076 Pageviews. |
|
|
ง่วงซะก่อน 55+ เดี๋ยวกลับมาอ่านอีกรอบนะค๊ะ
เผื่อได้ใช้ ขอบคุณที่แบ่งปันค่ะ