Cの配列から膨大な数の要素を削除する最速の方法

Question

私は、何千もの要素を含む動的配列を持っています。大きなサイズのメモリを消費しないように、使用されており、それらの必要はもうありません）。最初から、毎回要素を削除した後に必要な最大サイズを見積もることで、より小さなメモリサイズを割り当てることができます。

私はこの方法を使用しますが、それは非常に非常に長い時間がかかり、時には30分かかります！

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

これより速い方法がありますか？

Answer 1

O（n ）ソリューション用の2つのループを使用して、一度に1つずつ要素を削除する代わりに、単一の読み取りと単一の書き込みインデックスを使用してループを作成できます。あなたが行くように項目をコピーし、配列を通過します：

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

ループwrの終わりにarrayに保持要素の数です。あなたが本質的に上記

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

を行うようだ

Answer 2

は速くなるはずですが、あなたのコードといくつかの注意点/問題が（例えば、エンドを越えてのアクセスは、アレイをOD）残っています。

Answer 3

私はあなただけの配列の先頭から要素を削除するに気づいたとして、これを試してみてください。

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

あなたは

Answer 4

たくさんの複雑さを軽減ループのための1つを使用しているこの方法はこちら配列をデフラグメントするコード。

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 
} 

私はthis答えからコードをコピーしました。

私はより効率的な方法は、バケットのリンクリストを使用することだと思います。バケットはビットストリングメモリマネージャによって管理されます。それは私たちの配列の内容は、intあり、それはstruct elemという名前の構造の中にカプセル化され、

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

と仮定、次のようなものです。

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

バケットは、struct elemと使用マスクの配列として定義されます。

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

バケットリストは、すべてのバケットを含むリンクリストです。

私たちはメモリマネージャーコードを書く必要があります。

まず、必要に応じて新しいバケットを割り当てる必要があります。

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

バケットがあるので、必要に応じて配列の値を設定する必要があります。

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

アレイ要素を削除するのは、未使用のマークとして簡単です。バケット内のすべての要素が使用されていない場合、バケットをリンクリストから削除できます。

バケットを最適化したり、小さい領域に収まるようにバケットを最適化することがあります。それ以外の場合は、新しい要素を割り当てるときに、混雑していないバケットよりも混雑したバケットを選択することができます。削除すると、あまり混雑していない要素をより混雑した要素に入れ替えることができます。

最後の値を持つ要素を交換することによって行われ、効率的な方法で配列の要素を削除する

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 
} 

可能です。