dobbiamo confrontare ogni elemento di una matrice in C?

Question

Ho il seguente codice:

int isUsed[6] = {1,1,1,1,1,1}; 

Come confrontare se tutti gli elementi di questa matrice sono pari a 1? o altro valore? So che possiamo fare il ciclo della matrice e confrontarla una per una, ma abbiamo altri modi per farlo?

Answer 1

Sì, è necessario farlo elemento per elemento.

Se l'array consiste di soli tipi interi puri (ovvero non un array di struct s) e si desidera verificare l'uguaglianza, è possibile utilizzare memcmp().

Questo ciclo ovviamente si esegue internamente, ma è una funzione standard preimpostata che facilita la leggibilità. È potrebbe prestazioni male, dal momento che confronta char s. D'altra parte (dopo i commenti) potrebbe migliorare le prestazioni a causa di una ben nota funzione di libreria che potrebbe essere ottimizzata.

Inoltre, per completezza, il motivo per cui ho avuto l'avvertenza su no struct s sopra è che le strutture spesso contengono pad byte, che saranno "visti" da memcmp() e possono causare un risultato errato.

Ad esempio:

struct { 
    int x; 
    char y; 
    int z; 
} a = { 1, 2, 3 }, b = { 1, 2, 3 }; 

In molti sistemi, quanto sopra struct avranno spaziatura tra y e z, che potrebbe causare un risultato errato da memcmp() poiché i byte di riempimento hanno valori indefiniti.

Answer 2

È necessario confrontare gli elementi di matrice uno per uno.

Answer 3

Non c'è altro modo che confrontare ogni elemento alla volta. Anche se ti rallenta, ma non c'è alternativa. Prova

#define NULL (void*)0 
memcmp(char* source, const char * dest, int count); 

restituisce NULL se String corrisponde.

Answer 4

Per i tipi di dati primitivi (non struct), se si conosce la dimensione della matrice e ciò che si sta cercando di confrontare con: memcmp farà il lavoro:

#include <stdio.h> 
#include <string.h> 

static int allOnes[6] = {1,1,1,1,1,1}; 

int main(int argc, const char* argv[]) { 

    int isUsed[6] = {1,1,1,1,1,1}; 

    if(memcmp(isUsed, allOnes, sizeof allOnes) == 0) 
     printf("Array has only 1's\n"); 
    else 
     printf("At least one element is not 1\n"); 
} 

---

EDIT: sulle prestazioni ...

Alcuni commenti menzionano le prestazioni di memcmp e loop, inclusi i loop srotolati.

Di seguito è riportato un semplice programma di test per misurare le prestazioni. Nella mia macchina (Mac OS X, LLVM compilatore), questo è quello che ottengo:

memcmp: 0.036031 seconds result=1 
loop: 0.097180 seconds result=1 
unrolled loop: 0.075623 seconds result=1 

Prima di fare commenti specifici sui numeri di cui sopra, si ricorda che:

• non sto facendo un affermazione generica, solo mostrando che nel mio ambiente la soluzione memcmp batte gli altri con un ampio margine.
• il ciclo di srotolamento che ho non è la massima implementazione. È solo un tentativo grossolano di avere un numero per lo svolgimento del ciclo sul posto.

Sentitevi liberi di rielaborare il codice e inviare altri numeri.

#include <stdio.h> 
#include <string.h> 
#include <time.h> 

static int allOnes[6] = {1,1,1,1,1,1}; 

bool compareWithMemcmp() 
{ 
     int isUsed[6] = {1,1,1,1,1,1}; 
     return memcmp(isUsed, allOnes, sizeof allOnes) == 0; 
} 

bool compareWithLoop() 
{ 
     int isUsed[6] = {1,1,1,1,1,1}; 
     for(int i = 0; i < sizeof allOnes/sizeof allOnes[0]; i++) 
      if(isUsed[i] != 1) 
       return false; 
     return true; 
} 

bool compareWithUnrolledLoop() 
{ 
     int isUsed[6] = {1,1,1,1,1,1}; 
     // IMPORTANT: doesn't account for odd-length array 
     for(int i = 0; i < sizeof allOnes/sizeof allOnes[0]; i += 2) 
      if((isUsed[i] != 1) || (isUsed[i+1] != 1)) 
       return false; 
     return true; 
} 

int main(int argc, const char* argv[]) { 

    bool result; 

    clock_t begin = clock(); 
    for(int i = 0; i < 10000000; i++) 
     result = compareWithMemcmp(); 
    printf("memcmp: %f seconds result=%d\n", 
      (double)(clock() - begin)/CLOCKS_PER_SEC, result); 

    begin = clock(); 
    for(int i = 0; i < 10000000; i++) 
     result = compareWithLoop(); 
    printf("loop: %f seconds result=%d\n", 
      (double)(clock() - begin)/CLOCKS_PER_SEC, result); 

    begin = clock(); 
    for(int i = 0; i < 10000000; i++) 
     result = compareWithUnrolledLoop(); 
    printf("unrolled loop: %f seconds result=%d\n", 
      (double)(clock() - begin)/CLOCKS_PER_SEC, result); 
} 

Answer 5

è possibile utilizzare assembly inline, prendere da questo esempio:

è possibile scrivere una macro per ripetere questo codice 6 volte, il tuo problema:

#include <stdio.h> 
#include <stdlib.h> 
#include <inttypes.h> 


int64_t isUsed[ 1 ] = { 1 }; 

int main (void) 
{ 

__asm__ 
(
    "\n movq %[a] , %%rax" 
    "\n cmpq $1 , %%rax" 
    : 
    : [ a ] "m" (isUsed[0]) 
); 

__asm__ goto ("jne %l0\n" 
: 
: 
: 
: NotEqual); 


printf ("\n Array Contains 1 in all elements"); 
return 1 ; 

NotEqual: 

printf ("\n Array Not contains 1 in all elements"); 

return 0 ; 
} 

questo è il codice assembly : (piccolo)

movq isUsed(%rip) , %rax 
cmpq $1 , %rax 
jne .L2 

attenzione ai tipi interi che si intende utilizzare (o int32_t int64_t: inttypes.h)

Answer 6

si è possibile estensione GCC:

#include <stdio.h> 
#include <inttypes.h> 

#define VECTOR_SIZE   4 
typedef int v4int __attribute__ ((vector_size(sizeof(int32_t)*VECTOR_SIZE))); 


typedef union f4vector 
{ 
v4int  v; 
__int128_t value ; 
} f4vector; 



int main() 
{ 
union f4vector a, b, c; 

a.v = (v4int) { 1, 1, 1, 2 }; // your vector 
b.v = (v4int) { 1, 1, 1, 1 }; 

c.v = a.v - b.v; 

if (c.value == 0) 
    puts ("array contains all 1"); 
else 
    puts ("array Not contais all 1"); 

return 0 ; 
} 

Answer 7

Beh io non vado insieme a qualsiasi risposta che dice che non c'è altro modo ...

La risposta dipende da come la matrice potrebbe essere modificato .

Dato un array che è stato preimpostato su un valore noto e nessun cambiamento ulteriore, il test è banale e la soluzione è O (1). È tutto 1 perché l'hai fatto così.

Dopo aver iniziato a modificare i valori, se è presente un motivo per il modo in cui vengono modificati, è possibile registrare le informazioni su tale schema e il test può essere eseguito sulla cronologia in meno di O (n).

Ad esempio, quando si modifica un elemento nell'array, è possibile impostare un flag altrove che indica quali parti dell'array devono essere rivalutate. Se tutte le modifiche sono raggruppate in una piccola area, potrebbe essere necessario testare solo una piccola parte dell'array.

Tuttavia, nell'esempio specifico, una piccola serie di isUsed[], è ragionevole supporre che ogni elemento abbia solo due possibili stati. Se si utilizza una maschera di bit per questo, testare l'intero array potrebbe essere un'operazione a numero intero singolo. Visita ogni elemento implicitamente, ma è molto più efficiente di un ciclo.