Effiziente Möglichkeit, Zeilen mit gleichen Elementen in einer 3D-Matrix in C

Question

zu finden Ich habe eine 3D-Matrix mat[100][100][100]. Was ist der effiziente Weg, um eine Zeile mit den gleichen Elementen zu finden, die in mat[0][][], mat[1][][],....,mat[99][][] erscheint? Ein einfacher Ansatz wäre der Vergleich jeder Zeile von mat[0][][] mit allen Zeilen der restlichen 99 Matrizen, aber es wäre nicht sehr effizient (ich denke). Gibt es einen besseren Weg, es zu tun?

Answer 1

Um den Kommentar von @chux zu erweitern, besteht der erste Schritt darin, einen Hash-Wert für jede Zeile jeder Matrix zu berechnen. Das sind insgesamt 10000 Hashwerte. Die Ergebnisse sollten in einem Array von 10000 Strukturen gespeichert werden.

struct info 
{ 
    int m;   // the matrix number 
    int row;  // the row number 
    uint32_t hash; // the hash value for mat[m][row] 
}; 

static struct info hashArray[10000]; 

Nachdem alle 10000 Einträge der hashArray in Füllen sortiert das Array von Hash-Wert. Dann können Sie das Array einfach durchsuchen, um doppelte Hashwerte zu finden. Wenn Sie Dubletten finden, müssen Sie dies durch einen Vergleich der Zeilenelemente bestätigen.

Answer 2

Erstellen Sie eine inhaltsadressierbare Tabelle der ersten Werte in jeder Zeile. Dann gehe durch jede Zeile, nimm den ersten Wert und schaue auf den Tisch. Wenn die Suche mehrere Zeilen zurückgibt, sollten diese Zeilen auf Übereinstimmung überprüft werden. Die gesuchten Zeilen sollten zur Steigerung der Effizienz beibehalten werden, da die geprüften Zeilen nicht erneut überprüft werden müssen. Sie erhalten eine Liste mit identischen Zeilengruppierungen.

Answer 3

Ich fand endlich etwas Zeit, um den Inhalt adressierbaren Code zu schreiben. Es erweist sich als viel schneller als die Verwendung von Hash-Tabellen. Aber der Haken ist, dass der Code viel komplexer ist und das Programm WEISE mehr Speicher braucht. Meine abschließende Meinung ist, dass, wenn Sie nicht wirklich die zusätzliche Geschwindigkeit brauchen, bleiben Sie bei der Hash-Tabelle.

Einige Beispiele für Testläufe sind nachstehend aufgeführt. Das Argument für das Programm gibt die Anzahl der eindeutigen Zeilen an. Das Programm füllt den Rest mit zufällig ausgewählten vorhandenen Zeilen. Dann werden die Reihen gemischt. Das Programm sucht nach allen doppelten Zeilen und meldet die Anzahl der doppelten Zeilen und die Zeit, die es für Hash- und inhaltsadressierbare Tabellen benötigt.

bing@mint5 ~ $ cc -O2 cattest.c -o cattest 
bing@mint5 ~ $ ./cattest 500 
CAT Test  9500 0.0083 
Hash Test  9500 0.0499 
bing@mint5 ~ $ ./cattest 5000 
CAT Test  5000 0.0195 
Hash Test  5000 0.1477 
bing@mint5 ~ $ ./cattest 9000 
CAT Test  1000 0.0321 
Hash Test  1000 0.1092 






/* content addressable table vs hash table */ 
/* written by Bing H Bang */ 
/* I DONOT give permission to any snot-nosed students to copy my work and turn it in 
as their own */ 
#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <sys/types.h> 
#include <sys/stat.h> 
#include <fcntl.h> 
#include <unistd.h> 
#include <time.h> 
#include <pthread.h> 
#include <errno.h> 
#include <string.h> 
#include <sys/time.h> 
#include <sys/sysinfo.h> 

double etime() 
{ 
     struct timeval tv; 
    double dt, df; 

    gettimeofday(&tv, NULL); 
    dt = (double)(tv.tv_sec); 
    df = ((double)(tv.tv_usec))/1000000.0; 
    return(dt+df); 
} 

struct CAT_entry 
    { 
    unsigned fval; 
    unsigned short rows[10000]; 
    unsigned short num; 
    unsigned short used; 
    struct CAT_entry *next; 
    } *CAT[256] = {NULL}; 

struct CAT_entry stmem[10000]; 
int stidx = 0; 

unsigned dat[100][10000]; 
char map[10000]; 
unsigned hasht[10000]; 

#define highbit (1 << ((sizeof(unsigned)*8)-1)) 

unsigned 
rotxor(unsigned sum, unsigned v) 
{ 
    if((sum & highbit) == 0) 
     return ((sum << 1)^v); 
    else 
     return (((sum << 1) | 1)^v); 
} 

unsigned 
compute_hash(int y) 
{ 
    int x; 
    unsigned sum = 0; 

    for(x = 0; x < 100; ++x) 
     sum = rotxor(sum, dat[x][y]); 

    return sum; 
} 

void 
mk_hasht() 
{ 
    int y; 

    for(y = 0; y < 10000; ++y) 
     hasht[y] = compute_hash(y); 
} 

clearmap() 
{ 
    memset((void *)map, 0, 10000); 
} 

comprow(int y, int yd) 
{ 
    int x; 

    for(x = 0; x < 100; ++x) 
     if(dat[x][y] != dat[x][yd]) 
      return 0; 

    return 1; 
} 

struct CAT_entry ** 
srch_CAT(unsigned value) 
{ 
    struct CAT_entry **p = &(CAT[value&255]); 
    static struct CAT_entry *r = NULL; 

    while(*p != NULL) 
     { 
     if((*p)->fval == value) 
      break; 

     if((*p)->fval > value) 
      return &r; 
     else 
      p = &((*p)->next); 
     } 

    return p; 
} 

void 
add_entry(int y, unsigned value) 
{ 
    struct CAT_entry **p = &(CAT[value&255]), *q; 

    while(*p != NULL) 
     { 
     q = *p; 
     if(q->fval == value) 
      { 
      q->rows[q->num] = y; 
      q->num++; 
      return; 
      } 

     if(q->fval > value) 
      break; 

     p = &(q->next); 
     } 

    q = *p; 
    //*p = malloc(sizeof(struct CAT_entry)); 

    *p = &stmem[stidx++]; 

    (*p)->next = q; 
    q = *p; 
    q->fval = value; 
    q->num = 0; 
    q->used = 0; 
} 

void 
mk_CAT() 
{ 
    int x,y; 
    struct CAT_entry **p, *q; 

    for(y = 0; y < 10000; y++) 
     add_entry(y, dat[0][y]); 

    for(x=0; x < 256; ++x) 
     { 
     p = &(CAT[x]); 
     while(*p != NULL) 
      { 
      q = *p; 
      if(q->num == 0) 
       { 
       *p = q->next; 
       //free(q); 
       } 
      else 
       p = &(q->next); 
      } 
     } 
} 

void 
gen_data(int npat) 
{ 
    int x, y, rnum, limit; 
    unsigned r; 

    srandom(time(NULL)); 
    rnum = npat * 100; 

    for(y = 0; y < rnum; ++y) 
     dat[y%100][y/100] = random(); 

    for(y = npat; y < 10000; ++y) 
     { 
     rnum = random() % npat; 
     for(x = 0; x < 100; ++x) 
      dat[x][y]=dat[x][rnum]; 
     } 

    for(y = 0; y < 10000; ++y) 
     { 
     rnum = random() % 10000; 
     if(rnum == y) 
      continue; 

     for(x = 0; x < 100; ++x) 
      { 
      r = dat[x][y]; 
      dat[x][y]=dat[x][rnum]; 
      dat[x][rnum] = r; 
      } 
     } 
} 

int 
do_CATtest() 
{ 
    int y, yd, count = 0, i; 
    struct CAT_entry **p, *q; 

    mk_CAT(); 
    clearmap(); 

    for(y = 0; y < 9999; ++y) 
     { 
     if(map[y] == 0) 
      { 
      map[y] = 1; 
      if(*(p = srch_CAT(dat[0][y])) != NULL) 
       { 
       for(q = *p, i = 0; i < q->num; ++i) 
        { 
        yd = q->rows[i]; 
        if(map[yd] == 0) 
         { 
         if(comprow(y, yd)) 
          { 
          map[yd] = 1; 
          ++count; 
          q->used++; 
          } 
         } 
        } 

       if(q->num <= q->used) 
        *p = q->next; 
       } 
      } 
     } 

    return count; 
} 

int 
do_hashtest() 
{ 
    unsigned h; 
    int x, y, yd, count = 0; 

    mk_hasht(); 
    clearmap(); 

    for(y = 0; y < 9999; ++y) 
     { 
     if(map[y] != 0) 
      continue; 

     map[y] = 1; 
     h = hasht[y]; 
     for(yd = y+1; yd < 10000; ++yd) 
      { 
      if(map[yd] != 0) 
       continue; 

      if(h == hasht[yd]) 
       if(comprow(y, yd)) 
        { 
        map[yd] = 1; 
        ++count; 
        } 
      } 
     } 

    return count; 
} 

main(int c, char *v[]) 
{ 
    int npat = 0, count; 
    double t1, t2; 

    if(c == 2) 
     npat = atoi(v[1]); 

    if(npat <= 0 || npat >= 10000) 
     { 
     puts("input param error"); 
     exit(1); 
     } 

    gen_data(npat); 
    npat = 10000 - npat; 

    t1 = etime(); 

    if((count = do_CATtest()) != npat) 
     { 
     printf("CAT test error, %d matches found, not %d", count, npat); 
     exit(1); 
     } 

    t2 = etime(); 

    printf("CAT Test %d %.4f\n", npat, t2-t1); 

    t1 = etime(); 
    if((count = do_hashtest()) != npat) 
     { 
     printf("hash test error, %d matches found, not %d", count, npat); 
     exit(1); 
     } 

    t2 = etime(); 

    printf("Hash Test %d %.4f\n", npat, t2-t1); 
}