Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Sviluppare programma c per determinare 2 array uguali

Linguaggi e sistemi

Moderatori: Foto UtentePaolino, Foto UtenteMassimoB, Foto Utentefairyvilje

0
voti

[31] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto Utentecronos80 » 12 ott 2015, 17:45

Infatti, perciò chiedevo lumi :mrgreen:
Anche perché inizialmente l'OP aveva parlato di due cicli..
Non cercare di piegare il cucchiaio. È impossibile. Cerca invece di fare l'unica cosa saggia: giungere alla verità. Il cucchiaio non esiste. Allora ti accorgerai che non è il cucchiaio a piegarsi, ma sei tu stesso!
Avatar utente
Foto Utentecronos80
1.546 1 6 12
Expert EY
Expert EY
 
Messaggi: 636
Iscritto il: 17 gen 2012, 10:43

4
voti

[32] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto UtenteTardoFreak » 12 ott 2015, 19:27

Per completezza (e perché magari potrebbe interessare a qualcuno) posto anche la soluzione mediante ricorsione.

Ovviamente, trattandosi di ricorsione, bisogna scrivere una funzione che restituisca un valore vero (diverso da 0) o false (uguale a 0).
Si parte sempre e comunque dalla riga centrale del programma, quella che confronta gli elementi degli array dello stesso indice. Come prima se i due elementi sono diversi dovrà ritornare falso, cioè 0.
Codice: Seleziona tutto
if (A[i] != B[i]) return 0;

Ovviamente dobbiamo racchiudere questa riga di programma in una funzione che, per ora, confronta semplicemente gli elementi degli array A e B alla posizione indicata da i
Codice: Seleziona tutto
char isEqual(int A[], int B[], int i)
{
  if (A[i] != B[i]) return 0;
}

Ora dobbiamo in qualche modo fare scandire tutti gli elementi e per farlo partiamo da un elemento qualsiasi per arrivare fino all' elemento con indice 0.
Il ragionamento è questo: supponiamo che io sia all' i-esimo elemento. Potrei essere arrivato all'ultimo elemento degli array quindi, se non sono ancora uscito dalla funzione è perché tutti gli elementi che ho confrontato prima sono uguali, ed anche quelli che ho appena confrontato sono uguali, altrimenti sarei uscito con risultato 0.
Quindi controllo se sono arrivato all'ultimo elemento. Se si, vuol dire che tutti quelli che ho visto prima sono uguali, quelli che ho visto ora (che sono quelli all'ultimo indice, cioè 0) sono uguali e quindi esco dalla funzione con risultato vero, cioè 1.
Codice: Seleziona tutto
char isEqual(int A[], int B[], int i)
{
  if (A[i] != B[i]) return 0;
  if (i == 0) return 1;
}

Se invece non ero alla fine dovrò confrontare gli elementi che vanno da i-1 fino a 0, e quindi semplicemente lo scrivo.
Codice: Seleziona tutto
char isEqual(int A[], int B[], int i)
{
  if (A[i] != B[i]) return 0;
  if (i == 0) return 1;
  return isEqual(A, B, i-1);
}


Tutto qui.

E questo è un programmino che permette di verificare che tutto funzioni, completo della funziona appena scritta.
Codice: Seleziona tutto
char isEqual(int A[], int B[], int i)
{
  if (A[i] != B[i]) return 0;
  if (i == 0) return 1;
  return isEqual(A, B, i-1);
}

#define ELEMENTI 4
int main(void) {
  int array1[ELEMENTI] = {1,2,3,4};
  int array2[ELEMENTI] = {1,2,3,4};
 
  if (isEqual(array1, array2, ELEMENTI - 1)) printf("Sono uguali");
    else printf("Sono diverse");
  return (EXIT_SUCCESS);
}


Notare che nel main si chiama la funzione isEqual passando come parametri i due array e l'indice del primo elemento da cui iniziare il confronto, confronto che proseguirà fino all'elemento 0.
"La follia sta nel fare sempre la stessa cosa aspettandosi risultati diversi".
"Parla soltanto quando sei sicuro che quello che dirai è più bello del silenzio".
Rispondere è cortesia, ma lasciare l'ultima parola ai cretini è arte.
Avatar utente
Foto UtenteTardoFreak
73,4k 8 12 13
-EY Legend-
-EY Legend-
 
Messaggi: 15764
Iscritto il: 16 dic 2009, 11:10
Località: Torino - 3° pianeta del Sistema Solare

1
voti

[33] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto UtenteNunziox » 6 nov 2015, 21:05

Io aggiungerei pure questa soluzione:


Codice: Seleziona tutto
[...]
#include<stdio.h>

#define VEC_LENGTH 3

int c=0;

int main(){
   
  int vec1[]={1,2,1};
  int vec2[]={1,2,1};   

  int result=0,i=0;
  for(i=0;i<VEC_LENGTH;i++){
   result+=(vec1[i]^vec2[i]);
}

if(!result)
   printf("\n Sono Uguali");
else
   printf("\n Non sono uguali");
 
//Solo Windows   
system("pause");

return 0;
}

[...]


Cosi il codice è molto efficiente, in quanto non fai l'if dentro il ciclo.
Quando il compilatore C genera il codice trasforma l'if in un branch.
L'e istruzioni di branch bloccano l'esecuzione delle istruzioni che vengono dopo, in quanto, il processore prima di eseguire l'istruzione successiva deve scoprire l'esito dell'istruzione di branch.
La latenza introdotta varia da architettura ad architettura.
Ultima modifica di Foto UtenteNunziox il 6 nov 2015, 21:25, modificato 1 volta in totale.
Avatar utente
Foto UtenteNunziox
221 1 9
Frequentatore
Frequentatore
 
Messaggi: 152
Iscritto il: 28 ott 2012, 0:38

0
voti

[34] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto Utentefairyvilje » 6 nov 2015, 21:25

Attenzione questo listato non risolve il problema completo. Se due arrays sono uguali termina sempre correttamente, ma non il viceversa. È molto facile costruire un esempio di fallimento :)
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
11,3k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2444
Iscritto il: 24 gen 2012, 19:23

0
voti

[35] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto Utentefairyvilje » 6 nov 2015, 21:26

Nunziox ha scritto:L'e istruzioni di branch bloccano l'esecuzione delle istruzioni che vengono dopo, in quanto, il processore prima di eseguire l'istruzione successiva deve scoprire l'esito dell'istruzione di branch.


Dipende dall'architettura. Spesso la pipeline viene comunque riempita e risolta in attesa dell'esito, sperando che vada tutto bene, altrimenti si recupera lo stato e si riparte.
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
11,3k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2444
Iscritto il: 24 gen 2012, 19:23

0
voti

[36] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto UtenteNunziox » 6 nov 2015, 21:28

Attenzione questo listato non risolve il problema completo. Se due arrays sono uguali termina sempre correttamente, ma non il viceversa. È molto facile costruire un esempio di fallimento :)


Non ho capito! Fammi un esempio!

Dipende dall'architettura. Spesso la pipeline viene comunque riempita e risolta in attesa dell'esito, sperando che vada tutto bene, altrimenti si recupera lo stato e si riparte.


Si è vero! Ma come dici tu, viene risolta in attesa dell'esito. Se non indovina la predizione deve trasformare tutte le operazioni in NOP e ripartire. Ovvero perdo tempo.
Avatar utente
Foto UtenteNunziox
221 1 9
Frequentatore
Frequentatore
 
Messaggi: 152
Iscritto il: 28 ott 2012, 0:38

0
voti

[37] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto Utentefairyvilje » 6 nov 2015, 21:33

Considera che in caso di overflow l'aritmetica dei numeri non da eccezione, ma il comportamento non è determinato dallo standard. In molte architetture si passa da MAX a MIN.

Immagina ora di avere interi a 4 bit, solo per semplificare, nello stesso modo si può costruire un controesempio con tutte le dimensioni.

a_1=1111
a_2=1

b_1=0
b_2=0

a_1 \bigotimes b_1+a_2 \bigotimes b_2=1111+1

In un modulo 16 vuol dire 0. Hai ottenuto 0 con numeri diversi fra loro. Il programma quindi può fallire.

Chiedo scusa per le continue correzioni ma stasera proprio è un errore dietro l'altro :D
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
11,3k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2444
Iscritto il: 24 gen 2012, 19:23

0
voti

[38] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto Utentefairyvilje » 6 nov 2015, 21:39

Nunziox ha scritto:Si è vero! Ma come dici tu, viene risolta in attesa dell'esito. Se non indovina la predizione deve trasformare tutte le operazioni in NOP e ripartire. Ovvero perdo tempo.


In quell'algoritmo nemmeno troppo. Se fallisce un confronto il flusso nel for deve comunque concludersi. Ergo la penalità di errore se il processore assume come predizione "i valori sono uguali" avverrebbe solo una volta e coinciderebbe con il termine del controllo :).
Se fai un po' di conti vedi che un processore abbastanza intelligente non ha praticamente nessuna penalità da questo tipo di condizione.
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
11,3k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2444
Iscritto il: 24 gen 2012, 19:23

0
voti

[39] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto UtenteNunziox » 6 nov 2015, 21:43

In quell'algoritmo nemmeno troppo. Se fallisce un confronto il flusso nel for deve comunque concludersi. Ergo la penalità di errore se il processore assume come predizione "i valori sono uguali" avverrebbe solo una volta e coinciderebbe con il termine del controllo :).
Se fai un po' di conti vedi che un processore abbastanza intelligente non ha praticamente nessuna penalità da questo tipo di condizione.


Credo di no perché il processore o il compilatore nelle architetture VLIW farebbe loop unrolling.
Comunque nulla toglie che, in alcune architetture, potrebbe riuscire ad eliminare gli stalli.

Considera che in caso di overflow l'aritmetica dei numeri non da eccezione, ma il comportamento non è determinato dallo standard. In molte architetture si passa da MAX a MIN.

Immagina ora di avere interi a 4 bit, solo per semplificare, nello stesso modo si può costruire un controesempio con tutte le dimensioni ...


Si hai ragione. Bisogna gestire questa cosa.
Avatar utente
Foto UtenteNunziox
221 1 9
Frequentatore
Frequentatore
 
Messaggi: 152
Iscritto il: 28 ott 2012, 0:38

0
voti

[40] Re: Sviluppare programma c per determinare 2 array uguali

Messaggioda Foto Utentefairyvilje » 6 nov 2015, 21:48

Certamente, come anteposto è un discorso che dipende moltissimo dall'architettura di riferimento. Non ho esperienze dirette con molte architetture superscalari, quindi mi fido del tuo giudizio :mrgreen: .
Banalmente il mio discorso sono abbastanza sicuro regga per le moderne architetture 80x86.
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
11,3k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2444
Iscritto il: 24 gen 2012, 19:23

Precedente

Torna a PC e informatica

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti