المقدمة
أساس العمل مع المصفوفات (في هذه المقالة سننظر فقط في المصفوفات ثنائية الأبعاد) هو نظرية رياضية قوية من مجال الجبر الخطي. يتبع تعريف أو إجراء من آخر ؛ وظيفة واحدة تستدعي أخرى. لذلك ، من أجل التنفيذ الوظيفي لوظيفة العمليات الحسابية على المصفوفات ، تتناسب اللغات الوظيفية بشكل جيد للغاية. في هذه المقالة ، سنلقي نظرة على أمثلة محددة في F # وسنقدم تعليقات مفصلة حول كيفية عمل ذلك. نظرًا لأن F # جزء من عائلة .NET ، يمكن استخدام الوظيفة الناتجة دون أي مشاكل في اللغات الحتمية الأخرى ، على سبيل المثال C #.تعريف المصفوفة وتنفيذها في F #
المصفوفات هي الجزء الأساسي والأهم من الجبر الخطي. غالبًا ما تستخدم المصفوفات في البرمجة ، على سبيل المثال ، في النمذجة ثلاثية الأبعاد أو تطوير الألعاب. بالطبع ، تم اختراع الدراجة لفترة طويلة والأطر اللازمة للعمل مع المصفوفات جاهزة بالفعل ، ويمكن ويجب استخدامها. لا تهدف هذه المقالة إلى اختراع إطار عمل جديد ، ولكنها توضح تنفيذ العمليات الحسابية الأساسية للعمل مع المصفوفات بأسلوب وظيفي باستخدام لغة البرمجة F #. عندما نفحص المادة ، سننتقل إلى النظرية الرياضية للمصفوفات ونرى كيف يمكن تنفيذها في التعليمات البرمجية.أولاً ، دعنا نتذكر ما هي المصفوفة؟ تقول لنا النظرية ما يلييسمى جدول مستطيل من الأرقام التي تحتوي على صفوف m وأعمدة n مصفوفة بحجم mxn
المصفوفات عادة ما يرمز لها بأحرف كبيرة من الأبجدية اللاتينية وتكتب باسمأو قريبًاA=(aij)
للعمل مع المصفوفات في F # ، سننشئ سجلاً بناءً على جدول ثنائي الأبعاد ، والذي سنقوم بتوسيعه بطرق مفيدة لإجراء العمليات الحسابية اللازمة عليه.type Matrix = { values: int[,] }
with
//
end
أضف طريقة مساعدة لتهيئة التسجيل بمصفوفة ثنائية الأبعادstatic member ofArray2D (values: int [,]) =
{ values = values }
وسيطة إدخال الدالة ستكون مصفوفة ثنائية الأبعاد ، وفي مخرجاتها ، سجل من نوع Matrix . فيما يلي مثال على تهيئة السجل.let a = array2D [[1;0;2]
[3;1;0]]
let A = Matrix.ofArray2D a
المصفوفتان A = (aij) و B = (bij) تسمى متساوية إذا تزامنت مع عنصر ، أي aij = bij للجميع i = 1،2 ...، m و j = 1،2 ... n
لتطبيق هذه القاعدة ، سنستخدم عامل تجاوز == وسنضيف بعض الوظائف المفيدة ، والتي سنحتاجها أيضًا في المستقبل.static member sizes matrix =
let rows = matrix.values.[*,0].Length
let cols = matrix.values.[0,*].Length
(rows, cols)
static member isEquallySized matrix1 matrix2 =
let dim1 = Matrix.sizes matrix1
let dim2 = Matrix.sizes matrix2
(dim1 = dim2)
static member (==) (matrix1, matrix2) =
if not (Matrix.isEquallySized matrix1 matrix2) then false
else
not (matrix1.values
|> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
|> Seq.cast<bool>
|> Seq.contains false)
دعونا نلقي نظرة فاحصة على الرمز أعلاه. كما ترون ، هناك ثلاث وظائف. تُرجع دالة الأحجام الأولى بُعد المصفوفة كمجموعة. نظرًا لأننا نعمل فقط مع المصفوفات المستطيلة ، للحصول على عدد الصفوف ، فإننا نأخذ شريحة كاملة من العمود الأول ونعيد طوله.let rows = matrix.values.[*,0].Length
تحديد عدد الأعمدة يعمل بطريقة مماثلة - نحصل على شريحة كاملة من الصف الأول ونعيد طولها. تقارنالدالة isEquallySized التالية أبعاد المصفوفتين وترجع القيمة الصحيحة إذا كانت متساوية. للقيام بذلك ، يستخدم وظيفة الأحجام الجاهزة ويقارن النتائج ببساطة.يبدو العامل == لمقارنة مصفوفتين بشكل أكثر تعقيدًا ، ولكن الآن سترى أنه بسيط أيضًا.قبل مقارنة مصفوفتين ، نقارن أبعادها. إذا لم تكن متساوية ، فلا توجد نقطة أخرى في التحقق ، حيث من الواضح بالفعل أن المصفوفات لن تكون متساوية.if not (Matrix.isEquallySized matrix1 matrix2) then false
علاوة على ذلك ، على أساس المصفوفات الأصلية matrix1 و matrix2 ، نشكل مصفوفة جديدة مليئة بالصواب أو الخطأ ، اعتمادًا على ما إذا كانت الخلايا المقابلة لكل من المصفوفات تتزامن.matrix1.values
|> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true
و Array2D.mapi وظيفة بالتكرار على كل عناصر matrix1 ويمر ثلاثة المعلماتاكس إلى معالج - مؤشر الصفذ - مؤشر العمودالخامس - خليةمحتويات قارنا محتويات الخلية الخامس مع الخلية المقابلة matrix2 وإذا كانت تساوي، ثم أكتب صحيحا ، وإلا كاذبة .إذا كانت هناك خلية واحدة على الأقل تحتوي على عنصر خاطئ ، فهذا يعني أن المصفوفات ليست متساوية مع بعضها البعض.نظرًا لأن Array2D لا يحتوي على طرق للتصفية أو البحث ، فسنطبق ذلك بأنفسنا. للقيام بذلك ، نقوم بتحليل المصفوفة إلى قائمة خطية|> Seq.cast<bool>
والعثور على عدم تطابق واحد على الأقل|> Seq.contains false
و Seq.contains وظيفة سيعود صحيح إذا واحد على الأقل كاذبة وجدت قيمة في القائمة الموسعة . لذلك ، نحتاج إلى عكس النتيجة بحيث يعمل عامل == بالطريقة التي نريدهاelse
not (matrix1.values
|> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
|> Seq.cast<bool>
|> Seq.contains false)
المصفوفة O تسمى مصفوفة صفرية أو صفرية إذا كانت جميع عناصرها تساوي الصفر.
static member O rows cols =
let array2d = Array2D.zeroCreate rows cols
{ values = array2d }
مثال على استخدام هذه الوظيفةlet AO = Matrix.O 5 5
أعتقد أنه لا يوجد شيء معقد يتطلب التفسير ، لذلك نستمر.المصفوفة التي يساوي عدد صفوفها عدد الأعمدة ويساوي n تسمى مصفوفة مربعة من الترتيب n
وهكذا ، فإن المصفوفة المربعة لها الشكل.A=[a11a12...a1na21a22...a2n............an1an2...ann]
كجزء من هذه القاعدة ، سننشئ وظيفة تحول مصفوفة مستطيلة إلى مصفوفة مربعة عن طريق قطع جميع العناصر التي لا تقع في المربع.static member toSquare matrix =
//
let dim = Matrix.sizes matrix
//
let colCount: int = snd dim
//
let rowCount: int = fst dim
//
let length = System.Math.Min (colCount, rowCount)
//
//
let zero = Array2D.zeroCreate length length
//
let square = zero |> Array2D.mapi (fun x y _ -> matrix.values.[x, y])
//
{ values = square }
تشرح التعليقات في شفرة المصدر كيفية عمل الوظيفة ، لذا دعنا نواصل.تسمى المصفوفة المربعة مثلثة إذا كانت جميع عناصرها تحت القطر الرئيسي تساوي صفر ، أي المصفوفة المثلثة لها الشكل
T=(a11a12...a1n0a22...a2n............00...ann)
يوجد أدناه رمز الوظيفة الذي يحول المصفوفة الأصلية إلى مصفوفة مثلثة. ولكن في وظيفتنا ، سنعمل مع مصفوفة مستطيلة ، أي أنها قد لا تكون مربعة. يمكن للقارئ بسهولة تعديل رمز الوظيفة بحيث يرجع مصفوفة مثلثة مربعة باستخدام الوظيفة التي فحصناها سابقًا.static member T matrix =
let values = matrix.values |> Array2D.mapi (fun x y v -> if y < x then 0 else v)
{ values = values }
تحوّل الدالة Array2D.mapi الصفيف ثنائي الأبعاد الأصلي إلى صفيف جديد باستخدام معالج يأخذ ثلاث معلمات رقم الصفx رقم العمودy العمودالخامس محتويات الخليةif y < x then 0 else v
هنا نتحقق مما إذا كان العنصر أسفل القطر الرئيسي وإذا كان الأمر كذلك ، فاملأ الخلية 0. وإلا ، فإن القيمة الأولية من مصفوفة الإدخال.فيما يلي مثال على استخدام هذه الوظيفة.let a = array2D [[1;2;3]
[4;5;6]
[7;8;9]
[10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.triangular A
printfn "origin = \n %A" A.values
printfn "triangular = \n %A" R.values
نحصل على النتيجة التاليةorigin =
[[1; 2; 3]
[4; 5; 6]
[7; 8; 9]
[10; 11; 12]]
triangular =
[[1; 2; 3]
[0; 5; 6]
[0; 0; 9]
[0; 0; 0]]
تسمى المصفوفة المربعة قطريًا إذا كانت جميع عناصرها الموجودة خارج القطر الرئيسي تساوي الصفر
static member D matrix =
let diagonal = matrix.values |> Array2D.mapi (fun x y v -> if x <> y then 0 else v)
{ values = diagonal }
هذه الوظيفة تشبه إلى حد كبير الوظيفة السابقة ، فقط شرط التحقق مختلف. فيما يلي مثال للاستخدامlet a = array2D [[1;2;3]
[4;5;6]
[7;8;9]
[10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.D A
printfn "origin = \n %A" A.values
printfn "diagonal = \n %A" R.values
origin =
[[1; 2; 3]
[4; 5; 6]
[7; 8; 9]
[10; 11; 12]]
diagonal =
[[1; 0; 0]
[0; 5; 0]
[0; 0; 9]
[0; 0; 0]]
المصفوفة القطرية هي وحدة ويشار إليها بالرمز E إذا كانت جميع عناصرها الموجودة على القطر الرئيسي تساوي الوحدة
E=(10...001...0............00...1)
تنفيذ مثل هذه المصفوفة على F # يبدو هكذاstatic member E rows cols =
let array2d = Array2D.init rows cols (fun x y -> if x = y then 1 else 0)
{ values = array2d }
عمليات المصفوفة مع F #
يمكن تنفيذ عدد من الإجراءات على المصفوفات ، وكذلك على الأرقام ، وبعضها مشابه للعمليات على الأرقام ، وبعضها محدد.مجموع المصفوفتين Amn = (aij) و Bmn = (bij) من نفس الحجم هو مصفوفة من نفس الحجم A + B = Cmn = (cij) ، والتي تساوي عناصرها مجموع عناصر المصفوفات A و B الموجودة في الأماكن المقابلة
cij=aij+bij,i=1,2,...,m,j=1,2,...,n
على سبيل المثال ، بالنسبة للمصفوفتين A و B ، نجد المجموع A + BA=(231−506),B=(−331720),A+B=(−162226)
خذ بعين الاعتبار الرمز لإضافة مصفوفتينstatic member (+) (matrix1, matrix2) =
if Matrix.isEquallySized matrix1 matrix2 then
let array2d = matrix1.values |> Array2D.mapi (fun x y v -> matrix2.values.[x, y] + v)
{ values = array2d }
else failwith "matrix1 is not equal to matrix2"
قبل إضافة المصفوفات ، تحتاج إلى التأكد من أن أبعادها تتزامن ، وإلا فإن الوظيفة تستثني. فيما يلي مثال على استخدام هذه الوظيفةlet a = array2D [[2;3]
[1;-5]
[0;6]]
let A = Matrix.ofArray2D a
let b = array2D [[-3;3]
[1;7]
[2;0]]
let B = Matrix.ofArray2D b
let R = A+B
printfn "A+B =\n %A" R.values
A+B =
[[-1; 6]
[2; 2]
[2; 6]]
ناتج المصفوفة A = (aij) بالرقم k هو المصفوفة kA = (kaij) من نفس حجم المصفوفة A التي تم الحصول عليها عن طريق ضرب جميع عناصر المصفوفة A في الرقم k
سبيل المثال، لإعطاء مصفوفة A نجد مصفوفة 3AA=(230154),3A=(69031512)
static member (*) (value, matrix) =
let array2d = matrix.values |> Array2D.mapi (fun _ _ v -> v * value)
{ values = array2d }
مصفوفة -A = (- 1) * A وسوف يطلق على العكس مصفوفة A . من هذا التعريف ، ننتقل بسلاسة إلى التاليالفرق بين المصفوفات A و B ذات الأحجام المتساوية هو مجموع المصفوفة A والمصفوفة المقابلة لـ B
static member (-) (matrix1: Matrix, matrix2: Matrix) =
if Matrix.isEquallySized matrix1 matrix2 then
matrix1 + (-1)*matrix2
else failwith "matrix1 is not equal to matrix2"
تسمى مصفوفتان متسقة إذا كان عدد أعمدة الأول يساوي عدد صفوف الثاني
A=(2103),B=(05211437)
static member isMatched matrix1 matrix2 =
let row1Count = matrix1.values.[0,*].Length
let col2Count = matrix2.values.[*,0].Length
row1Count = col2Count
مطلوب التحقق من اتساق المصفوفة لمضاعفتهم.المصفوفة المتماسكة AB للمنتج Amn = (aij) و Bnp = (bjk) هي المصفوفة Cmn = (cik) ، يتم احتساب العنصر cik كمجموع الصفوف i -th من المصفوفة A والعناصر المقابلة في العمود k من المصفوفة B
احسب منتج المصفوفاتA=(102310),B=(−1051−20)
قرار تحديد منتج المصفوفاتAB=(1(−1)+0∗5+2(−2)1∗0+0∗1+2∗03(−1)+1∗5+0(−2)3∗0+1∗1+0∗0)=(−5021)
ضع في اعتبارك كود ضرب مصفوفتينstatic member (*) (matrix1, (matrix2: Matrix)) =
if Matrix.isMatched matrix1 matrix2 then
let row1Count = matrix1.values.[*,0].Length
let col2Count = matrix2.values.[0,*].Length
let values = Array2D.zeroCreate row1Count col2Count
for r in 0..row1Count-1 do
for c in 0..col2Count-1 do
let row = Array.toList matrix1.values.[r,*]
let col = Array.toList matrix2.values.[*,c]
let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col
values.[r,c] <- cell
{ values = values }
else failwith "matrix1 is not matched to matrix2"
دعونا نلقي نظرة على الرمز بمزيد من التفصيل.قبل الضرب ، عليك التأكد من أن المصفوفات متناسقةif Matrix.isMatched matrix1 matrix2 then
المصفوفة الناتجة سيكون لها بعد حيث يكون عدد الصفوف هو نفسه المصفوفة الأولى وعدد الأعمدة هو نفس المصفوفة الثانيةlet row1Count = matrix1.values.[*,0].Length
let col2Count = matrix2.values.[0,*].Length
//
let values = Array2D.zeroCreate row1Count col2Count
بعد ذلك ، ننتقل عبر جميع الصفوف وجميع أعمدة المصفوفات الأصليةfor r in 0..row1Count-1 do
for c in 0..col2Count-1 do
let row = Array.toList matrix1.values.[r,*]
let col = Array.toList matrix2.values.[*,c]
نحسب القيمة الإجمالية لكل خليةlet cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col
تتلقى الدالة List.fold2 قائمتين عند الإدخال (الصف والعمود) وتمرر المعلمات التالية إلى المعالجacc - المجمع الذي يحتوي على نتيجة الحساب السابق1 - محتويات الخلية من الصفيف الأول. في حالتنا ، هذا هو الصف من المصفوفة الأولىval2 - محتويات الخلية من المصفوفة الثانية ، أي أعمدة المصفوفة الثانية.بما أن المصفوفات متناسقة ، فنحن على يقين من أننا لن نتجاوز الصفائف.يضيف المعالج إلى المركم منتج خلايا من الصفوف والعمود ، وسيتم تمرير القيمة الناتجة إلى التكرار التالي. وبالتالي ، فإن النتيجة النهائية للدالة List.fold2ستكون القيمة النهائية لمنتجات مصفوفتين. يبقى فقط لملئها بالمصفوفة الفارغة التي تم إنشاؤها مسبقًاvalues.[r,c] <- cell
الذي سيعود نتيجة لذلك{ values = values }
فيما يلي مثال على استخدام هذه الوظيفةlet a = array2D [[1;0;2]
[3;1;0]]
let A = Matrix.ofArray2D a
let b = array2D [[-1;0]
[5;1]
[-2;0]]
let B = Matrix.ofArray2D b
let R = A*B
printfn "A*B =\n %A" R.values
A1*B1 =
[[-5; 0]
[2; 1]]
إذا كانت k ∈ N ، فإن القوة kth للمصفوفة المربعة A هي نتاج المصفوفات k
Ak=A∗A∗...A(k−)
ضع في اعتبارك الرمز على F # لمنتج مصفوفة إلى قوة. سيتم استخدام عائد الذيل هنا حتى لا يتم تجاوز المكدس بقوة كبيرة. عودية الذيل هي عودية يحولها المترجم في النهاية إلى حلقة. إذا كان ذلك ممكنًا ، فمن المستحسن أن تستخدم دائمًا العود الذيل بدلاً من المعتاد ، ولكن لهذا تحتاج إلى كل إطار عائد لإرجاع القيمة المحسوبة النهائية. تسمى هذه القيمة عادةً المركم ويتم تمريرها إلى إطار العودية التالي. هذا ، على عكس العودية المنتظمة ، التي تُرجع القيمة المحسوبة في المكدس ، يعيد العائد الذيل القيمة المحسوبة إلى أسفل المكدس. يقوم كل إطار جديد للإعادة بحساباته الخاصة ويضيفها إلى القيمة المحسوبة سابقًا ، والتي يتم تخزينها في البطارية. بعد ذلك،بما أن الإطار الأخير من العودية يعمل ، فإن للمراكم بالفعل قيمة محسوبة ، والتي تعود ببساطة نتيجة لذلك.وبالتالي ، يمكن للمترجم تحسين الكود وتحويله إلى حلقة عادية.
//
// matrix -
// value -
static member (^^) (matrix, value) =
// ,
// m -
// p =
let inRecPow m p =
//
// acc - . Matrix
// p -
//
let rec recPow acc p =
//
match p with
| x when x > 0 ->
//
// ,
let nextAcc = acc*m
//
recPow nextAcc (x-1)
// ,
| _ -> acc
// ,
let dim = Matrix.sizes matrix
let colCount = snd dim
let rowCount = fst dim
let u = Matrix.E rowCount colCount
//
recPow u p
// ,
let powMatrix = inRecPow matrix value
//
{ values = powMatrix.values }
يحتوي الرمز على تعليقات تفصيلية حول كيفية عمله. يتطلب شرحا قليلا ، لماذا يتم استخدام مصفوفة الوحدة؟ وهو ضروري للإطار الأول من العودية ويعمل كقيمة أساسية للمركم ، حيث سيتم تجميع النتيجة النهائية.فيما يلي مثال على استخدام وظيفتناA=(102−1)
A2=AA=(102−1)(102−1)=(1001)
A3=AA2=(102−1)(1001)=(102−1)
نحن نحسب المنتج التاليf(A)=2A3−4A2+3E
حيث E هي مصفوفة الهوية. نظرًا لأنه لا يمكننا إضافة رقم إلى المصفوفة ، يجب أن نضيف 3E .2(102−1)−4(1001)+3(1001)=(104−3)
//
static member (+) (matrix, (value: int)) =
let dim = Matrix.sizes matrix
let r = fst dim
let c = snd dim
//
let unit = Matrix.E r c
//
value*unit + matrix
let a = array2D [[1;0]
[2;-1]]
let A = Matrix.ofArray2D a
let R = 2*(A^^3) - 4*(A^^2) + 3
printfn "2*A^3 - 4*A^2 + 3 =\n %A" R.values
2*A5^3 - 4*A5^2 + 3 =
[[1; 0]
[4; -3]]
المصفوفة A T التي تتكون أعمدتها من صفوف المصفوفة A مع نفس الأرقام ونفس تسلسل العناصر تسمى المنقولة إلى المصفوفة A
static member transpose matrix =
let dim = Matrix.sizes matrix
let rows = fst dim
let cols = snd dim
//
let tMatrix = Matrix.O cols rows
//
matrix.values |> Array2D.iteri(fun x y v -> tMatrix.values.[y, x] <- v)
//
tMatrix
مثال للاستخدامlet a = array2D [[1;2;3]
[4;5;6]
[7;8;9]
[10;11;12]]
let A = Matrix.ofArray2D a
let R6 = Matrix.T A
printfn "origin = \n %A" A.values
printfn "transpose = \n %A" R.values
origin =
[[1; 2; 3]
[4; 5; 6]
[7; 8; 9]
[10; 11; 12]]
transpose =
[[1; 4; 7; 10]
[2; 5; 8; 11]
[3; 6; 9; 12]]
ملخص
في هذه المقالة ، درسنا أمثلة على تنفيذ واستخدام المصفوفات من نظرية الجبر الخطي. وكذلك العمليات الحسابية الأساسية عليها ، باستخدام نهج وظيفي في F #. آمل أن يتمكن القارئ من تقدير المرونة التي توفرها اللغات الوظيفية.الكود المصدر الكامل لوحدة المصفوفة ، التي تم النظر في أجزاء منها في إطار المقالة ، يمكنك العثور عليها على جيثب.جيثب ماتريكس