Il modo più veloce per rimuovere un numero enorme di elementi da una matrice in C

Question

Ho una matrice dinamica che contiene migliaia di elementi o anche di più, per non consumare una grande dimensione di memoria, posso rimuovere elementi indesiderati da essa (cioè elementi sono stati utilizzati e non è più necessario per loro), quindi fin dall'inizio posso allocare una dimensione di memoria più piccola stimando la dimensione massima richiesta dopo aver rimosso gli elementi ogni volta.

Io uso in questo modo, ma ci vuole molto molto tempo per finire, a volte ci vogliono 30 minuti!

int x, y ; 
for (x = 0 ; x<number_of_elements_to_remove ; x++){ 
    for (y = 0 ; y<size_of_array; y++){ 
      array[y] = array[y+1]; 
    } 
} 

C'è un modo più veloce di questo?

Answer 1

Invece di rimuovere gli elementi uno alla volta, con due cicli che costituiscono una soluzione O (n), è possibile creare un singolo ciclo, con una singola lettura e un singolo indice di scrittura. Passare attraverso la matrice, la copia di oggetti, come si va:

int rd = 0, wr = 0; 
while (rd != size_of_array) { 
    if (keep_element(array[rd])) { 
     array[wr++] = array[rd]; 
    } 
    rd++; 
} 

Alla fine del ciclo wr è il numero di elementi conservati nella array.

Answer 2

vi pare essenzialmente fare

int y; 
for (y = 0; y<size_of_array; y++){ 
    array[y] = array[y+numbre_of_elements_to_remove]; 
} 

Quanto sopra dovrebbe essere più veloce, ma ci sono ancora alcune avvertenze/problemi con il codice (ad esempio, l'accesso oltre la fine od dell'array).

Answer 3

come ho notato che si desidera eliminare solo gli elementi fin dall'inizio della matrice, provate questo:

int x; 
     for(x = 0 ; x< size_of_array - number_of_elements_to_remove; x++) 
      array[x] = array[number_of_elements_to_remove + x]; 

questo modo si sta utilizzando uno per il ciclo che riduce la complessità sacco

Answer 4

Ecco il codice per deframmentare la matrice.

int sparse_to_compact(int*arr, int total, int*is_valid) { 
     int i = 0; 
     int last = total - 1; 
     // trim the last invalid elements 
     for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements from last 

     // now we keep swapping the invalid with last valid element 
     for(i=0; i < last; i++) { 
       if(is_valid[i]) 
         continue; 
       arr[i] = arr[last]; // swap invalid with the last valid 
       last--; 
       for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements 
     } 
     return last+1; // return the compact length of the array 
} 

Ho copiato il codice this risposta.

Penso che il modo più efficiente sia utilizzare un elenco di collegamenti di bucket. E i bucket sono gestiti da un gestore di memoria bit-string. E 'come il seguente,

struct elem { 
    uint32_t index; /* helper to locate it's position in the array */ 
    int x; /* The content/object kept in the array */ 
} 

Supponiamo, i contenuti in array è int ed è incapsulato in una struttura di nome struct elem.

enum { 
    MAX_BUCKET_SIZE = 1024, 
    MAX_BITMASK_SIZE = (MAX_BUCKET_SIZE + 63) >> 6, 
}; 

struct bucket { 
    struct bucket*next; /* link to the next bucket */ 
    uint64_t usage[MAX_BITMASK_SIZE]; /* track memory usage */ 
    struct elem[MAX_BUCKET_SIZE]; /* the array */ 
}; 

Un secchio è definito come un array di struct elem e maschera utilizzo.

struct bucket_list { 
    struct bucket*head; /* dynamically allocated bucket */ 
}container; 

E un elenco di bucket è un elenco collegato contenente tutti i bucket.

Quindi abbiamo bisogno di scrivere il codice gestore della memoria.

All'inizio abbiamo bisogno di un nuovo bucket da allocare quando necessario.

struct bucket*bk = get_empty_bucket(&container); 
if(!bk) { /* no empty bucket */ 
    /* allocate a bucket */ 
    struct bucket*bk = (struct bucket*)malloc(sizeof(struct bucket)); 
    assert(bk); 
    /* cleanup the usage flag */ 
    memset(bk->usage, 0, sizeof(bk->usage)); 
    /* link the bucket */ 
    bk->next = container.head; 
    container.head = bk; 
} 

Ora come abbiamo il bucket, è necessario impostare il valore nell'array quando necessario.

for(i = 0; i < MAX_BITMASK_SIZE; i++) { 
    uint64_t bits = ~bk.usage[i]; 
    if(!bits) continue; /* no space */ 
    /* get the next empty position */ 
    int bit_index = _builtin_ctzl(bits); 
    int index = (i<<6)+bit_index; 
    /* set the array value */ 
    bk->elem[index].index = index; 
    bk->elem[index].x = 34/* my value */; 
    bk.usage[i] |= 1<<bit_index; /* mark/flag the array element as used */ 
} 

Eliminare gli elementi di matrice è facile da contrassegnarli inutilizzati. Ora, quando tutti gli elementi di un bucket non sono utilizzati, è possibile eliminare il bucket dall'elenco dei collegamenti.

A volte possiamo deframmentare i bucket o ottimizzarli per adattarli a spazi più piccoli. Altrimenti, quando assegniamo nuovi elementi, possiamo selezionare secchi più affollati su uno meno affollato. Quando cancelliamo possiamo scambiare l'elemento di quello meno affollato in quello più affollato.

È possibile eliminare elementi di matrice in modo efficiente,

int remove_element(int*from, int total, int index) { 
     if(index != (total-1)) 
       from[index] = from[total-1]; 
     return total; // **DO NOT DECREASE** the total here 
} 

Si è fatto scambiando l'elemento con l'ultimo valore.