ギャップがないようにC配列に要素を配置する

Question

私は毎秒実行され、構造体内のすべてのデータを更新するプログラムで、Cで構造体の規則的な配列を持っています。条件が満たされると、要素の1つがクリアされ、任意の点に入る可能性のある新しい要素（この場合はタイマー）の空きスロットとして使用されます。

私は、更新が必要なアクティブな要素を探している配列のすべての要素を解析するだけです。しかし、要素の量が小さい（< 2000）場合でも、これは非アクティブなものを通過する時間を無駄にしていると感じます。私は配列をギャップフリーに保つことができるので、現在割り当てられている要素の数を反復するだけでいいですか？

Answer 1

要素の特定の順序が重要でないと仮定すると、非常に簡単に行うことができます。

あなたは、アレイAと能動素子Nの数を持っている場合は、その要素このようなE追加することができます。

A[N++] = E; 

と、次のようにインデックスIにある要素を削除します。

A[I] = A[--N]; 

を

これはどのように機能しますか？まあ、それはかなり簡単です。配列にはアクティブな要素だけを格納したいので、これらのいずれかをやってみると配列がそうであると仮定します。

要素を追加すると、最後に配置されます。現在配列内のすべての要素と新しく追加された要素がアクティブになるため、末尾に追加することができます。

要素を削除するには、削除する要素の配列インデックスを引き継ぐために最後の要素を移動します。したがって、A[0..I-1]はアクティブなだけでなく、A[I+1..N]あり、そしてA[I]にA[N]を移動することで、全体の範囲A[0..N-1]がアクティブになって、それはもう存在しないので（A[N]が、アクティブではないではありません - 私たちはA[I]にそれを移動し、私たちは1でNを減らす理由です）。

要素を反復処理している間に要素を削除して更新する場合は、が削除されない要素を処理した後でループカウンタを増やすことができます。が削除されます。 。これを達成する

Answer 2

比較的簡単な方法：

void remove(struct foo *foo_array, int *n) 
{ 
    struct foo *src = foo_array, *dst = foo_array; 
    int num_removed = 0; 

    for (int i=0; i<*n; ++i) 
    { 
     // Do we want to remove this? (should_remove() left as exercise for reader.) 
     if (should_remove(src)) 
     { 
     // yes, remove; advance src without advancing dst 
     ++src; 
     ++num_removed; 
     } 
     else if (src != dst) 
     { 
     // advance src and dst (with copy) 
     *dst++ = *src++; 
     } 
     else 
     { 
     // advance both pointers (no copy) 
     ++src; 
     ++dst; 
     } 
    } 

    // update size of array 
    *n -= num_removed; 
} 

アイデアは、あなたが、配列の要素数を追跡することである（ここでは*n）有効であり、そして「イン/アウトとしてそのポインタを渡しますパラメータ "となる。 remove()は、削除する要素を決定し、適切でない要素をコピーします。削除される要素の数に関係なく、これはO（n）であることに注意してください。

Answer 3

1秒あたり2,000エントリの移動は無視できます。それは本当に最適化する価値はありません。本当に必要があると思われる場合は、非アクティブなエントリを最後のアクティブなエントリと入れ替えます。

Answer 4

あなたの構造体にリンクリストの動作を追加すると、次のアクティブな要素を指すポインタメンバーですか？

要素の有効化と無効化でこれらのポインタを更新する必要があります。

EDIT：それはリストが使用するポインタを無効に、メモリオブジェクトのアドレスを変更する可能性があるためこの方法は、動的にリサイズ配列には適していません..です

Answer 5

あなたは素晴らしいを持っているようにそれは聞こえませんリンクされたリストを使用しない理由。実装をうまく実行すると、O（1）の挿入、O（1）の削除が発生し、アクティブな構造体を保持する（繰り返し処理する）必要があります。いくつかのメモリオーバヘッドがあるでしょう...しかし、中規模の構造体でさえ、二重リンクリストでさえかなり効率的です。このアプローチの良い点は、余分な計算上のオーバーヘッドなしに要素を挿入順に保持できることです。あなたには、いくつかのパフォーマンスの問題を有するかまたはスケールアップする必要がありますされていない限り、そのまま

1）は、それを残す：

Answer 6

いくつかの選択肢は、あなたのニーズに合わせてお選び、気にしています。

2）各構造体に "next"ポインタを追加して、二重リンクリストの要素として使用します。 2つのリストをアクティブなものと未使用のものに分けてください。支柱の使い方によっては、リストを二重にリンクすることも検討してください。 （構造体を索引付けする必要がある場合は、配列内の要素を引き続き使用することもできます。そうでない場合は配列の使用を停止することもできます）。3）構造体の索引を必要としない場合は、配列内で定数になるように、未使用のエントリを配列の末尾に移動します。その後、最初から配列全体を反復すると、最初に使用されていないものに到達するたびに停止することができます。 （最後のアクティブな構造体のインデックスを格納できるので、構造体が非アクティブ化されたときは直近のアクティブな構造体の場所を切り替えてから最後のアクティブな構造体のインデックスを減らすことができます）