Najszybszy sposób na usunięcie ogromnej liczby elementów z tablicy w C

Question

Mam dynamiczną tablicę zawierającą tysiące elementów lub nawet więcej, aby nie zużywać dużego rozmiaru pamięci, mogę usunąć z niej niepożądane elementy (np. zostały już wykorzystane i nie są już potrzebne), więc od początku mogę przydzielić mniejszy rozmiar pamięci przez oszacowanie maksymalnego wymaganego rozmiaru po usunięciu elementów za każdym razem.

Używam tej metody, ale jej ukończenie zajmuje bardzo dużo czasu, czasami zajmuje 30 minut!

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]; 
    } 
} 

Czy istnieje szybszy sposób niż to?

Answer 1

Zamiast usuwać pojedyncze elementy, z dwiema pętlami tworzącymi rozwiązanie O (n), można utworzyć pojedynczą pętlę, z pojedynczym odczytem i pojedynczym indeksem zapisu. Przejść przez tablicę, kopiowanie elementów jak przejść:

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

Pod koniec pętli wr jest liczba elementów przechowywanych w array.

Answer 2

Wydaje się zasadniczo zrobić

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

Powyższe powinno być szybsze, ale nadal istnieją pewne zastrzeżenia/problemy z kodem (na przykład dostęp poza koniec OD tablicę).

Answer 3

jak zauważyłem chcesz tylko usunąć elementy z początku tablicy, spróbuj tego:

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

ten sposób używasz jednej pętli co zmniejsza złożoność dużo

Answer 4

Oto kod do defragmentacji tablicy.

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 
} 

Skopiowałem kod z odpowiedzi this.

Myślę, że bardziej efektywnym sposobem jest użycie listy odnośników. A zasobniki są zarządzane przez menedżer pamięci bitowej. To jest jak poniżej,

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

Załóżmy, nasze zawartość tablicy jest int i jest zamknięty w strukturze o nazwie 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 */ 
}; 

Wiadro definiuje się jako tablicę o wartości struct elem i maskę użytkowania.

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

Lista wiaderek to połączona lista zawierająca wszystkie wiadra.

Musimy więc napisać kod menedżera pamięci.

Na początku potrzebujemy nowego wiadra, które zostanie przydzielone w razie potrzeby.

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; 
} 

Teraz, gdy mamy wiadro, musimy w razie potrzeby ustawić wartość w macierzy.

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 */ 
} 

Usunięcie elementów tablicy jest łatwe i oznacza, że ​​nie są używane. Teraz, gdy wszystkie elementy w wiadrze są nieużywane, możemy usunąć wiadro z listy linków.

Możemy czasami defragmentować wiadra lub zoptymalizować je, aby zmieściły się na mniejszej powierzchni. W przeciwnym razie, gdy przypiszemy nowe elementy, możemy wybrać bardziej zatłoczone wiadra na mniej zatłoczone. Kiedy usuwamy, możemy zamienić element mniej zatłoczonego na bardziej zatłoczony.

Możliwe jest usuwanie elementów tablicy w sposób efektywny,

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 
} 

Stało się poprzez wymianę elementu na ostatniej wartości.