Sviluppare programma c per determinare 2 array uguali

[cronos80]

Infatti, perciò chiedevo lumi
Anche perché inizialmente l'OP aveva parlato di due cicli..

[TardoFreak]

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.

[Nunziox]

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.

[fairyvilje]

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 :)

[fairyvilje]

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.

[Nunziox]

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.

[fairyvilje]

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.









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

[fairyvilje]

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.

[Nunziox]

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.

[fairyvilje]

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 .
Banalmente il mio discorso sono abbastanza sicuro regga per le moderne architetture 80x86.