Отпечатай - Задача на C

Титла: Задача на C
Публикувано от: theenemy в May 03, 2010, 19:28

Напишете програма, която умножава две матрици. Съставете два варианта: един с използване на масиви и втори с използване на указатели. Използвайте стандартните функции за време, за да определите кой вариант работи по-бързо.
Трябва ми за сряда. Плс хелп.

Титла: Re: Задача на C
Публикувано от: b2l в May 03, 2010, 19:51

Примерно:
main()
{
nov masiv[n,t] = pyrvi masiv[n,m] * vtori masiv[m,t];

zasechi mi vreme();

return 0;
}

Втори пример с указатели:
main()
{
ukazatel kym nov masiv = ukazatel kym pyrvi masiv * ukazatel kym vtori masiv;

zasechi mi vreme();

return 0;
}

И ти остава само да сравниш двете времена, но мисля, че за това и сам ще се справиш :) Успех в сряда!

Титла: Re: Задача на C
Публикувано от: theenemy в May 03, 2010, 20:09

Аз имам една програм с масиви, но нямам идея другата как ще стане. Ето я и нея:

#include<iostream>

using namespace std;

int main(){

const int N=10;//тука си избираш колко да е N

float A[N][N], B[N][N], C[N][N]; //декларация на трите двумерни масива А, B и С

float max=0;

int i, j, k;

cout<<"Vyvedete masiv A: \n";

for(j=0; j<N;j++){ //Въвеждане на масив А

cout<<" "<<j+1<<" red: \n";

for(i=0; i<N;i++){

cout<<i+1<<"-i element: ";cin>>A[j];

}

}

cout<<"Vyvedete masiv B: \n";

for(j=0; j<N;j++){ //Въвеждане на масив B

cout<<" "<<j+1<<" red: \n";

for(i=0; i<N;i++){

cout<<i+1<<"-i element: ";cin>>B[j];

}

}

for(j=0; j<N;j++) //при всяка итерация се изчислява ред на двумерния масив С

for(i=0; i<N;i++){ //при всяка итерация се изчислява елемент от ред двумерния масив С

C[j]=0;

for(k=0;k<N;k++)//при всяка итерация се прибавя резултат от умножението на елементите на А и Б към стоността на поредния елемент на С

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

if(max<C[j])max=C[j];

}

cout<<" Masiva C: \n";

for(j=0; j<N;j++){ //цикъл за извеждане

for(i=0; i<N;i++)cout<<C[j]<<' ';cout<<endl;

}

cout<<"Maksimalni element na masiva C e: "<<max<<endl;

return 0;

}

Титла: Re: Задача на C
Публикувано от: bop_bop_mara в May 03, 2010, 20:35

Цитат на: theenemy в May 03, 2010, 20:09

Аз имам една програм с масиви, но нямам идея другата как ще стане. Ето я и нея:

Първо това е на C++, уточни за кой от двата езика става въпрос.
Второ, кое не ти е ясно - как се умножават две матрици, как се ползват масиви или как се ползват указатели?

Титла: Re: Задача на C
Публикувано от: theenemy в May 03, 2010, 20:52

Честно казано не съм много на ясно нито с масивите, нито с указателите :(

Титла: Re: Задача на C
Публикувано от: bop_bop_mara в May 03, 2010, 20:56

ОК, а искаш да се научиш или искаш просто програма :)

Титла: Re: Задача на C
Публикувано от: theenemy в May 03, 2010, 21:02

Първо да се науча, а след това да мога сам да си правя програмите, но като се има предвид че досега не съм се занимавал със програмиране, не ми е особено лесно :(

Титла: Re: Задача на C
Публикувано от: task_struct в May 03, 2010, 21:34

По мой изчисления от поне 3 месеца ти го преподават, а че ти през тях не си се занимавал, не ми се струва нормално... но то вече кой ли не не приемат в университетите само и само да съберат хора ...

След около 5 секунди търсене в Google: http://www.google.bg/search?aq=1&oq=martix+multiplication&sourceid=chrome&client=ubuntu&channel=cs&ie=UTF-8&q=matrix+multiplication+in+c

Титла: Re: Задача на C
Публикувано от: gat3way в May 03, 2010, 22:53

Коя работи по-бързо в крайна сметка?

Титла: Re: Задача на C
Публикувано от: b2l в May 03, 2010, 23:05

Няма ли да е тази с указателите.

Титла: Re: Задача на C
Публикувано от: gat3way в May 03, 2010, 23:37

Защо трябва да е решението с указателите?

Титла: Re: Задача на C
Публикувано от: b2l в May 03, 2010, 23:39

Може би заради броя на операциите... (просто предположение).

Титла: Re: Задача на C
Публикувано от: gat3way в May 03, 2010, 23:46

Броят на операциите трябва да е същият, очевидно някъде другаде има уловка.

Титла: Re: Задача на C
Публикувано от: b2l в May 03, 2010, 23:53

Ами предполагам, трябва да мислите ми да се насочат към това - какво е указател? - променливи, които съдържат стойност от паметта. Указателя към масив ще сочи първия елемент на този масив. Аре стига ме мъчи де :).

Титла: Re: Задача на C
Публикувано от: gat3way в May 03, 2010, 23:57

Добре де, тая памет трябва да се dereference-ва, иначе как ще умножаваш и събираш там съдържанието на стойностите, намиращи се на тоя адрес. Нямам никаква идея кое ще е по-бързо, и на мен ми е интересно.

При варианта с указатели, нямаме указатели към масиви а към int или каквито там стойности, идеята е да се прави с pointer аритметика. Демек където ще кажеш a[2][2] примерно ще е *(b+2*length+3).

Някой дето разбира повече да се изкаже, аз нямам идея :)

Грр спи ми се и пиша глупости :)

Титла: Re: Задача на C
Публикувано от: task_struct в May 04, 2010, 00:34

Според мен просто му искат 2 функци - едната с входен параметър указател, а другата с матрица. ;)

Другият вариант е една функция за смятане на статично заделена матрица, а другата с динамично заделена.

Реално погледнато няма разлика между: a[ i ][j] и *((b+i)+j), това би трябвало да са един и същ брой инструкции, дори да се еднакви :) ( не съм го тествал)

i и j ще отидат в регистрите на процесора поради това, че са локални променливи. Остават самите мартици - при данимично създадените не знам как ще е ( пиша за embedded, а там няма динамична памет ), при статичните може да се оптимизира при компилирането и част от матриците също да отидат в регистрите. Също така съвременните процесори поддръжат Very long instruction word ( http://en.wikipedia.org/wiki/Very_long_instruction_word ), така че компилаторът да оптимизира кода и част от него да се изпълнява успоредно. ( Някъде бях намерил 1 pdf за AMD процесори, където беше описано как може да се пише кода така, че компилатора да оптимизира като използва тези инструкции ). Също така който е заинтересован може да прегледа проекта Eigen(http://eigen.tuxfamily.org/index.php?title=Main_Page) той е точно за работа с матрици и вектори и там се използват допълнителните инструкции на процесора. В заключение: Смятам, че няма да има разлика между двата метода :)

Титла: Re: Задача на C
Публикувано от: niakoi в May 04, 2010, 11:11

привет,
не претендирам, че съм гуру в С, обаче винаги съм вярвал, че

Код

GeSHi ():
a[i] е абс. същото като *(a+i)

, дори в някои книги по този начин обясняват работата с масиви и каква е връзката с пойнтерите

поздрави
нас

Титла: Re: Задача на C
Публикувано от: remotex в May 04, 2010, 11:36

Надали ще е само до аритметиката с указатели - според мен дали ще е изписано със квадратни скоби или обикновени за процесора е се тая..

Хе-хе всяко нещо си има предимства и недостатъци... едва ли ще задълбават чак толкова надълбоко в архитектури, процесори и оптимизации за тях. Предполагам "грешният" отговор който обикновено признават за верен в сл. е:
Масивите са по-бързи, но си ограничен до размерността на масива
...а пък с указатели можеш да си направиш динамичен масив/структура от данни (макар и по-бавна заради динамичното заделяне и после търкане на елементите 1 по 1 - т.е. само така си мислят даскалята и карат "децата" да преоткриват топлата вода като прескачат stl, boost etc.)

Титла: Re: Задача на C
Публикувано от: lkr в May 04, 2010, 13:51

Достъпът до индекс е еднакъв откъм инструкции, но динамичните почти винаги ще бъдат по-бавни, task_struct изреди някои причини. Други такива са, че при достатъчно големи масиви може да се получи memory fragmentation, а това води до cache misses, което е една от най-бавните операции при днешните x86.

Титла: Re: Задача на C
Публикувано от: hyankov в May 04, 2010, 15:10

Хахах, тъкмо се готвех, да се изрежа квалитетно, че в C (респективно и в C++) такова животно като масиви няма, когато видях, че niakoi ме е изпреварил ;)

Някой може ли да отговори, ако има "масиви" в С, защо следните две операции при са синтактично верни и при това ще дадат един резултат:

Код:

int array[10];

array[5];
5[array];

Отговорът е написан няколко поста по-нагоре. Не се заяждам, но заданието е доста идиотско "Веднъж с масиви, веднъж с указатели" иначе сигурен съм, че има някакъв замисъл.

Титла: Re: Задача на C
Публикувано от: task_struct в May 04, 2010, 15:32

Защото операцията [] се замества с поинтър аритметика от предпроцесора :)

Титла: Re: Задача на C
Публикувано от: task_struct в May 04, 2010, 15:55

Хъм, излязоха доста интересни резултати на VS 6.0 За съжаление вмомента нямам под ръка GCC за да тествам там как стоят нещата :(

Код

GeSHi (C):
int main()
{
    int arr[5] = { 1, 2, 3, 4, 5 };
    int *p = arr;
 
    arr[2] = 10;
    3[arr] = 11;
 
 
    *(p + 2) = 25;
 
 
    return 0;
}

Генерираният от това асемблер е:

Код:

	TITLE	D:\Opit\main.c
	.386P
include listing.inc
if @Version gt 510
.model FLAT
else
_TEXT	SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT	ENDS
_DATA	SEGMENT DWORD USE32 PUBLIC 'DATA'
_DATA	ENDS
CONST	SEGMENT DWORD USE32 PUBLIC 'CONST'
CONST	ENDS
_BSS	SEGMENT DWORD USE32 PUBLIC 'BSS'
_BSS	ENDS
$$SYMBOLS	SEGMENT BYTE USE32 'DEBSYM'
$$SYMBOLS	ENDS
$$TYPES	SEGMENT BYTE USE32 'DEBTYP'
$$TYPES	ENDS
_TLS	SEGMENT DWORD USE32 PUBLIC 'TLS'
_TLS	ENDS
;	COMDAT _main
_TEXT	SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT	ENDS
FLAT	GROUP _DATA, CONST, _BSS
	ASSUME	CS: FLAT, DS: FLAT, SS: FLAT
endif
PUBLIC	_main
;	COMDAT _main
_TEXT	SEGMENT
_arr$ = -20
_p$ = -24
_main	PROC NEAR					; COMDAT

; 2    : {

	push	ebp
	mov	ebp, esp
	sub	esp, 88					; 00000058H
	push	ebx
	push	esi
	push	edi
	lea	edi, DWORD PTR [ebp-88]
	mov	ecx, 22					; 00000016H
	mov	eax, -858993460				; ccccccccH
	rep stosd

; 3    :     int arr[5] = { 1, 2, 3, 4, 5 };

	mov	DWORD PTR _arr$[ebp], 1
	mov	DWORD PTR _arr$[ebp+4], 2
	mov	DWORD PTR _arr$[ebp+8], 3
	mov	DWORD PTR _arr$[ebp+12], 4
	mov	DWORD PTR _arr$[ebp+16], 5

; 4    :     int *p = arr;

	lea	eax, DWORD PTR _arr$[ebp]
	mov	DWORD PTR _p$[ebp], eax

; 5    : 
; 6    :     arr[2] = 10;

	mov	DWORD PTR _arr$[ebp+8], 10		; 0000000aH

; 7    :     3[arr] = 11;

	mov	DWORD PTR _arr$[ebp+12], 11		; 0000000bH

; 8    : 
; 9    : 
; 10   :     *(p + 2) = 25;

	mov	ecx, DWORD PTR _p$[ebp]
	mov	DWORD PTR [ecx+8], 25			; 00000019H

; 11   : 
; 12   : 
; 13   :     return 0;

	xor	eax, eax

; 14   : }

	pop	edi
	pop	esi
	pop	ebx
	mov	esp, ebp
	pop	ebp
	ret	0
_main	ENDP
_TEXT	ENDS
END

Както виждате arr[2] = 10; и 3[arr] = 11; генерират по 1 инструкция, докато *(p + 2) = 25; генерира 2. Следователно варианта с масиви/матрици би трябвало да е по-бърз. ::)

Титла: Re: Задача на C
Публикувано от: gat3way в May 04, 2010, 17:36

Още по-забавни резултати :)

t1.c:

Код

GeSHi (C):
#include <unistd.h>
 
void main()
{
int a[2][2];
int b;
 
b = a[1][1];
}

t2.c:

Код

GeSHi (C):
void main()
{
int *a;
int b;
b = *(a+4);
}

Асемблерен код на main() функцията, компилираме го без оптимизации:

t1:

Код:

0x08048384 <main+0>:    lea    0x4(%esp),%ecx
0x08048388 <main+4>:    and    $0xfffffff0,%esp
0x0804838b <main+7>:    pushl  0xfffffffc(%ecx)
0x0804838e <main+10>:   push   %ebp
0x0804838f <main+11>:   mov    %esp,%ebp
0x08048391 <main+13>:   push   %ecx
0x08048392 <main+14>:   sub    $0x20,%esp
0x08048395 <main+17>:   mov    0xfffffff4(%ebp),%eax
0x08048398 <main+20>:   mov    %eax,0xfffffff8(%ebp)
0x0804839b <main+23>:   add    $0x20,%esp
0x0804839e <main+26>:   pop    %ecx
0x0804839f <main+27>:   pop    %ebp
0x080483a0 <main+28>:   lea    0xfffffffc(%ecx),%esp
0x080483a3 <main+31>:   ret

t2:

Код:

0x08048384 <main+0>:    lea    0x4(%esp),%ecx
0x08048388 <main+4>:    and    $0xfffffff0,%esp
0x0804838b <main+7>:    pushl  0xfffffffc(%ecx)
0x0804838e <main+10>:   push   %ebp
0x0804838f <main+11>:   mov    %esp,%ebp
0x08048391 <main+13>:   push   %ecx
0x08048392 <main+14>:   sub    $0x10,%esp
0x08048395 <main+17>:   mov    0xfffffff4(%ebp),%eax
0x08048398 <main+20>:   add    $0x10,%eax
0x0804839b <main+23>:   mov    (%eax),%eax
0x0804839d <main+25>:   mov    %eax,0xfffffff8(%ebp)
0x080483a0 <main+28>:   add    $0x10,%esp
0x080483a3 <main+31>:   pop    %ecx
0x080483a4 <main+32>:   pop    %ebp
0x080483a5 <main+33>:   lea    0xfffffffc(%ecx),%esp
0x080483a8 <main+36>:   ret

Или демек 5 инструкции повече. Обаче компилираме ли го с флаг за оптимизация (O1 и нагоре), и двете генерират абсолютно идентичен код:

Код:

0x08048384 <main+0>:    lea    0x4(%esp),%ecx
0x08048388 <main+4>:    and    $0xfffffff0,%esp
0x0804838b <main+7>:    pushl  0xfffffffc(%ecx)
0x0804838e <main+10>:   push   %ebp
0x0804838f <main+11>:   mov    %esp,%ebp
0x08048391 <main+13>:   push   %ecx
0x08048392 <main+14>:   pop    %ecx
0x08048393 <main+15>:   pop    %ebp
0x08048394 <main+16>:   lea    0xfffffffc(%ecx),%esp
0x08048397 <main+19>:   ret

Има една разлика между масивите и указателите обаче - масивите могат да бъдат в стека или data секцията (в зависимост от това дали са локални/глобални променливи), указателите се очаква да сочат към памет в хийпа. Обаче последното не е задължително - примерно ако се ползва alloca() няма да е така.

Обаче и при това положение, не виждам разлика. Паметта би трябвало да се dereference-ва еднакво бързо без значение къде е. Performance драми може да има с TLB misses при големи матрици, но това трябва да е валидно и за двата варианта. Другото което си мисля е дали линукс ядрото не предпочита при нужда да pageout-ва страници памет от хийпа пред страници памет от стека, ама много ме съмнява да (може да) го прави, а и не виждам с какво това би било по-умно от LRU стратегията.

Та все още не мога да се сетя защо едното трябва да е по-бързо от другото.

В хийпа трябва да е по-бавно заради malloc() ама ако е малка матрицата може да го заделим в стека и тва е доста бърза операция (измества се само стек пойнтера). После, не е казано че трябва да ползваме malloc() въобще, може и сaмо с mmap(), което ще е малко по-бързо.

Ако изключим времето за заделяне и освобождаваме, двете трябва да са еднакво бързи.

Linux за българи: Форуми

Програмиране => Общ форум => Темата е започната от: theenemy в May 03, 2010, 19:28