Just algorithm!
เรื่องวุ่น ๆ ของการคูณ Matrix

ไม่ได้เขียน Blog มาประมาณชาติเศษ Smiley
พอดีงานหลวงเข้าเยอะมาก งานราษฎร์เลยพักไว้ก่อน
ผมลอง list หัวข้อเกี่ยวกับ C#, Programming และคณิตศาสตร์ที่น่าเขียนออกมา
ได้ตั้ง 50-60 กว่าหัวข้อ !!! Smiley
แล้วหลังยาวอย่างผมจะเขียนต่อไปได้อีกกี่น้ำเนี่ย...Smiley

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

หรือถ้าคุณสงสัย อยากให้ผมอธิบายอะไร
request ได้เต็มที่เลยครับ
เพราะมันจะเป็นการต่อยอดความรู้

และถ้าคุณผ่านมาอ่านเฉย ๆ
กรุณาสละเวลาเขียน Comment สั้น ๆ
เพื่อที่ Effort ของคุณ จะเป็น Effort ของผมในการเขียนต่อไป Smiley

มีผู้อ่านท่านหนึ่ง Comment ว่าให้ช่วยอธิบายเรื่อง Matrix Multiplication
(ไม่รู้ว่าเจ้าของ Comment ลืมไปรึยัง)

Matrix คือ ชุดตารางตัวเลข เพื่อใช้ศึกษา System of Linear Equations (สมการเชิงเส้นหลายตัวแปร)
Matrix สามารถ บวก ลบ คูณ กันเองได้
นอกจากนี้มันยังมีคุณสมบัติอีก มากมาย เพื่อที่จะเปลี่ยนรูปมัน


(ตัวอย่างของ Matrix รูปจาก Wikipedia)

การนำ Matrix ไปใช้งานในชีวิตจริงก็มี มายมาย เช่น
- การแก้ปัญหาสมการเชิงเส้น
- การประมวลผล Graphics
- การเข้ารหัส
- หรือแม้แต่การวิเคราะห์การสูญพันธุ์ของนกเค้าแมว Smiley

การบวก 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# ระดับนักศึกษากัน Smiley
ผมได้เขียน 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 Smiley

เรื่องของเรื่องคือ อย่างที่กล่าวไว้ว่าคุณสมบัติการคูณของ 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 ตามลำดับธรรมดาคูณเสร็จไปนานแล้วก็ได้ Smiley

ทุกปัญหามีทางแก้ครับ
เราสามารถหาวิธีคูณที่ดีที่สุดโดยใช้หลักการของ 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+ เดี๋ยวกลับมาอ่านอีกรอบนะค๊ะ

เผื่อได้ใช้ ขอบคุณที่แบ่งปันค่ะ


โดย: ChocolateStory วันที่: 20 พฤศจิกายน 2551 เวลา:2:28:45 น.  

 
ผ่านมาเจ๋ยๆ น๊า

อ่านแระตะมะรู้เรื่อง หุหุ


โดย: ถุง (ถุงก๊อปแก๊ป ) วันที่: 20 พฤศจิกายน 2551 เวลา:20:48:54 น.  

 
อ่านแล้วคับ

แล้วจะ apply ไงดีเนี่ย ???


โดย: kongthong วันที่: 21 พฤศจิกายน 2551 เวลา:14:15:29 น.  

 
ตอนนี้ผมกำลังทำโปรเจ็ค c# เกี่ยวกับ matrix พอดี

มีปัญหาเกี่ยวกับการโปรแกรมเชิงเส้นครับ

การวิเคราะห์หาค่าประสิทธิภาพใช้ matrix row operation
ครับ



โดย: phanthawatt@hotmail.com IP: 124.121.7.247 วันที่: 27 มกราคม 2552 เวลา:19:09:28 น.  

 
^
|
|
มีอะไรให้ช่วย หรือครับ?

ถ้าต้องการ code Matrix สำหรับแก้ปัญหาเชิงเส้น
แนะนำ JAMA เป็น Matrix Package ค่อนข้างสมบูรณ์
//math.nist.gov/javanumerics/jama/
ถ้าต้องการเป็น C# ลอง search ประมาณ JAMA port C# ดู
น่าจะมีเพียบ


โดย: chaowman วันที่: 29 มกราคม 2552 เวลา:21:57:51 น.  

 
ขอบคุณครับพี่เชาว์

ปล.เน็ตเสียพึ่งซ่อมเสร็จเลยมาช้า
BIG THXs


โดย: phanthawatt IP: 125.25.75.245 วันที่: 17 กุมภาพันธ์ 2552 เวลา:15:49:38 น.  

 
ขอบคุณมาก ๆ เลยคะ สำหรับความรู้ดี ๆ ที่แบ่งปันกัน


โดย: tazz IP: 202.28.78.33 วันที่: 21 กุมภาพันธ์ 2552 เวลา:19:00:18 น.  

 
โหพี่ เทพเกิ๊น ตอนนี้เอามาศึกษาลองเล่นดูค่ะ แล้วจะมาถามนะ ^^



โดย: lovelycute IP: 202.176.113.59 วันที่: 31 มีนาคม 2552 เวลา:9:18:37 น.  

 
สุดยอดมากครับ


โดย: Audna IP: 117.47.11.52 วันที่: 7 เมษายน 2552 เวลา:14:50:30 น.  

 
เข้า lab ภาษาซี เลยแวะมาเยี่ยมครับ


โดย: แวะมาทัก IP: 10.5.103.156, 202.44.8.100 วันที่: 24 สิงหาคม 2552 เวลา:17:22:18 น.  

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]





New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.