الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

مشكله فى برنامج معدل لضرب 2 ماتريكس

بدأه The expendable في 19 نوفمبر 2010 · 8 رد · 1,118 مشاهدة · في JavaSE
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

السلام عليكم ورحمه الله وبركاته

هذا هو برنامج ضرب محددين او 2 Matrix وهما فى هذا البرنامج مربعتين اى 2*2

مثل هذه الأسئله شهيره فى مقابلات الشركات الكبيره مثل ياهوو وجوجل و Hp وغيرها فلا يجب ان نكون بمنأى عنها ..

عدد عمليات الجمع فى البرنامج 8 و المطلوب تقليلهم الى 4 .. وبالتالى تحسين تعقيد البرنامج من n3 الى( n3-n2)

العداد داخل اللوب يخرج الرقم 8 ,, المطلوب اضافه تعديل بسيط بحيث يخرج العدد 4 بدلا من 8 مع الحفاظ على الثلاث لوب 

class MatrixMultiply{
  public static void main(String[] args)  {
	int A[][] = {{2,3},{4,1}};
	int B[][] = {{5,7},{6,8}};
	int C[][] = new int[2][2];
	int x= A.length;
	int count_additions =0;

  	for(int i = 0; i < x; i++) {
  	for(int j = 0; j < x; j++){
      	C[j] = 0;
    	for(int k = 0; k < x; k++){
      	C[j] += A[k] * B[k][j];
      	//C[j] = A[k] * B[k][j] + A[k+1] * B[k+1][j]; // my wrong trial
      	count_additions++;
    	}
  	}
 	}
	System.out.println("Multiply of both matrix : ");
	for(int i = 0; i < x; i++) {
  	for(int j = 0; j < x; j++) {
    	System.out.print(" "+C[j]);
  	}
	System.out.println();
	}
	System.out.println("# of additions is " + count_additions );
  }
}

الناتج الصحيح للمصفوفه

38 28

التعديل 36 26

number of additions is 8 == > number of additions is 4

تم تعديل هذه المشاركة بواسطة The expendable في 20 نوفمبر 2010 في 16:24

no-pain-no-gain.jpg

اذا كنت لا تعلم الى اين تذهب... فكــل الطرق تؤدى الى هناك

#2

يبدو ان اسئلتى تثير الرعب ولا مشاهده واحده ...

no-pain-no-gain.jpg

اذا كنت لا تعلم الى اين تذهب... فكــل الطرق تؤدى الى هناك

#3

هوا اسئلتى صعبه للدرجادى .. فى انتظار المحترفين ..036.gif

no-pain-no-gain.jpg

اذا كنت لا تعلم الى اين تذهب... فكــل الطرق تؤدى الى هناك

#4

الطريقة المناسبة ستكون بوضع مؤشرين كل منهم يسير فى عكس اتجاه الاخر. و التعديل سيكون باضافة مؤشر جديد revIdx و الذى يسير فى الاتجاه المعاكس.

التعديل:

for(int k = 0, revIdx = x -1; k < x / 2; k++, revIdx = x - (k+1)){
  C[j] += A[k] * B[k][j];
  C[j] += A[revIdx] * B[revIdx][j];
  count_additions++;
}

الكود بعد التعديل: 

public class MatrixMultiply {
	public static void main(String[] args)  {
        int A[][] = {{2,3},{4,1}};
        int B[][] = {{5,7},{6,8}};
        int C[][] = new int[2][2];
        int x= A.length;
        int count_additions =0;

        for(int i = 0; i < x; i++) {
        	for(int j = 0; j < x; j++){
        		C[j] = 0;
        		for(int k = 0, revIdx = x -1; k < x / 2; k++, revIdx = x - (k+1)){
        			C[j] += A[k] * B[k][j];
        			C[j] += A[revIdx] * B[revIdx][j];
        			count_additions++;
        		}
        	}
        }
        System.out.println("Multiply of both matrix : ");
        for(int i = 0; i < x; i++) {
        for(int j = 0; j < x; j++) {
        System.out.print(" "+C[j]);
        }
        System.out.println();
        }
        System.out.println("# of additions is " + count_additions );
  }
}

بالتوفيق و السلام ختام.

تم تعديل هذه المشاركة بواسطة Ahmedvc في 20 نوفمبر 2010 في 10:33

1
#5
اقتباس

مربعتين اى 2*2

ليس بالضرورة أن المصفوفة المربعة تكون 2*2 ربما تكون 3*3 أو 4*4 إلخ المهم أن يكون عدد الصفوف يساوي عدد الأعمدة

اقتباس

عدد عمليات الجمع فى البرنامج 8 و المطلوب تقليلهم الى 4 .. وبالتالى تحسين تعقيد البرنامج ..

هذا إشعار خاطئ التعقيد لا يتم تقليله بتقليل عدد العمليات إلى النصف بل بنقل الخوارزمية من أس إلى آخر

بمعنى n تقريباً هي n/2 في حياة الخوارزميات laugh.gif

بينما log n أفضل بمراحل من n^1/2 و n^1/2 أفضل من n و n أفضل من n^2 وهكذا

الموضوع مرتبط بمفهوم big O

على كل لا أقول بأن تقليل العمليات ليس جيد لكن أحاول توضيح بعض الأخطاء الحاصلة هنا

بالنسبة لحل الأخ Ahmedvc ففعلاً يقلل لفات التكرار

لكن العمليات هي نفس العدد لأنه يقوم بالزيادة على k

ربما ستفرق معاك لو استخدمت ذاكرة إضافية

بدون ذلك لا أظن

تحياتي

حزمة المحرك الإصدارة 0.8

أي أحد يجد أني ظلمته فليراسلني

وبإذن الله لو كان له حق سيأخذه

728x90.png

#6

اخى احمد مجهودك ما شاء الله وهو فى الاتجاه الصحيح ولكنه يحتاج الى التعديل ارجو منك الاهتمام ..

اخى علاء اخى احمد ,,

المراد هنا هو تحسين عدد عمليات الجمع من n3 الى (n3 - n2)

اذا قمنا بدمج العمليتان على هذا النحو سوف نحصل على عدد عمليات الجمع يساوى 4 وليس بالضروره العداد فهو يمثل عمليات الجمع

C[j] = A[k] * B[k][j] + A[revIdx] * B[revIdx][j];

2- هذا الكود لا يعمل على أى ماتريكس مربعه جرب البرنامج على هذه الماتريكس 3*3 ستجد ان الناتج خاطىء 

int A[][] = {{2,3,4},{4,1,4},{3,2,4}};
	int B[][] = {{5,7,4},{6,8,4},{4,2,4}};
	int C[][] = new int[3][3];

الناتج الصحيح :

alhnufb9bf9ef08e.jpgzomup.gif

وقد قمت بتجربته يدويا ايضا .. وهو يحقق الشرط (n3 - n2) حيث 8-4 =4

اما ناتج برنامجك بغير صحيح فى هذه الحاله وهو كالاتى :

alhnuf738f4216d8.jpgzomup.gif

ولا يحقق الشرط (n3 - n2) حيث 27-9 = 18

انا اعلم ان هذه الجزئيه لم تكن واضحه بعض الشىء فى السؤال لأنى اردت التبسيط ولكن اتمنى ان تكون وضحت

وفى انتظار ردكم ..

تم تعديل هذه المشاركة بواسطة The expendable في 20 نوفمبر 2010 في 16:14

no-pain-no-gain.jpg

اذا كنت لا تعلم الى اين تذهب... فكــل الطرق تؤدى الى هناك

#7

أود اضافة تعديل حسابى للكود نسيتة و ايضا مع تعديل حساب count_additions لتعكس العدد الحقيقى.

التعديل :

for(int j = 0, midIdx = x / 2; j < x; j++){        		
	C[j] = 0;
	if( x%2 !=0 ) {
		C[j] += A[midIdx] * B[midIdx][j];
		count_additions++;
	}
	for(int k = 0, revIdx = x -1; k < midIdx; k++, revIdx = x - (k+1)){
		C[j] += A[k] * B[k][j] + A[revIdx] * B[revIdx][j];
		count_additions++;
	}
}

الكود كاملا بعد التعديل : 

public class MatrixMultiply {
	public static void main(String[] args)  {
	int A[][] = {{2,3,4},{4,1,4},{3,2,4}};
        int B[][] = {{5,7,4},{6,8,4},{4,2,4}};
        int C[][] = new int[3][3];

        int x= A.length;
        int count_additions =0;

        for(int i = 0; i < x; i++) {
        	for(int j = 0, midIdx = x / 2; j < x; j++){        		
        		C[j] = 0;
        		if( x%2 !=0 ) {
        			C[j] += A[midIdx] * B[midIdx][j];
        			count_additions++;
        		}
        		for(int k = 0, revIdx = x -1; k < midIdx; k++, revIdx = x - (k+1)){
        			C[j] += A[k] * B[k][j] + A[revIdx] * B[revIdx][j];
        			count_additions++;
        		}
        	}
        }
        System.out.println("Multiply of both matrix : ");
        for(int i = 0; i < x; i++) {
        for(int j = 0; j < x; j++) {
        System.out.print(" "+C[j]);
        }
        System.out.println();
        }
        System.out.println("# of additions is " + count_additions );
  }
}

لو نظرنا لبعض الطرق الحالية لضرب المصفوفات و نتائجه على النحو التالى :

الطريقة التقليدية و الوارده فى الموضوع : عدد عمليات الجمع (N^3 - N^2 ) وعدد عمليات الضرب (N^3).

طريقة Winograd : عدد عمليات الجمع ( 3N^3 + 4N^2 - 4N / 2 ) و عدد عمليات الضرب ( N^3 + 2N^2 / 2 )

طريقة Strassen: عدد عمليات الجمع (6N^2.81 - 6N^2) و عدد عمليات الضرب (N^2.81).

لذا السؤال لايطرح اسلوب لتحسين ضرب المصفوفات حيث ان الطرح المقدم هو للطريقة التقليدية. و اغلب المحاولات تكون على تحسين Strassen لتقليل عدد عمليات الجمع و الضرب على قدر الامكان.

بالتوفيق و السلام ختام.

تم تعديل هذه المشاركة بواسطة Ahmedvc في 20 نوفمبر 2010 في 20:57

1
#8

بارك الله فيك اخى ... +2

اقتباس

if( x%2 !=0 ) {

C[j] += A[midIdx] * B[midIdx][j];

count_additions++;

}

ممكن توضح فى الفائده الرياضيه من هذا الشرط ..

اقتباس
الطريقة التقليدية و الوارده فى الموضوع : عدد عمليات الجمع (N^3 - N^2 ) وعدد عمليات الضرب (N^3).

ما اعلمه ان عدد مرات الجمع فى الطريقه التقليديه n3 , ولذلك نحن نحاول تحسينها هنا ..

اقتباس
طريقة Strassen: عدد عمليات الجمع (6N^2.81 - 6N^2) و عدد عمليات الضرب (N^2.81).

انا بحثت كثيرا ولكنى لم اجد كود هذه الطريقه ..

تم تعديل هذه المشاركة بواسطة The expendable في 20 نوفمبر 2010 في 22:04

no-pain-no-gain.jpg

اذا كنت لا تعلم الى اين تذهب... فكــل الطرق تؤدى الى هناك

#9

فى مشكله اخى جرب على هاتين 

int A[][] = {{2,3,4,5},{4,1,4,5},{3,2,4,5},{5,5,5,5}};
      	int B[][] = {{5,7,4,5},{6,8,4,5},{4,2,4,5},{5,5,5,5}};

ستجد عدد عمليات الجمع 32 وليس 46-16=48

انتظر تعقيبك

no-pain-no-gain.jpg

اذا كنت لا تعلم الى اين تذهب... فكــل الطرق تؤدى الى هناك

مواضيع مشابهة

عدد الزوار حالياً

المتواجدون خلال آخر دقيقتين · يتحدّث كل ٣٠ ثانية

—الإجمالي—أعضاء مسجّلون—زوار بدون تسجيل

جارٍ التحقق من المتواجدين…