1

私は C 言語 (Java から来た) が初めてで、私の状況では何がより良いアプローチなのか疑問に思っています。私はゲームをプログラミングしていますが、動きを生成する関数で、構造体の配列へのポインターを返したいと思っています (Move は構造体によって表されます)。

配列のサイズがどうなるか事前にわからないため、移動を追加するたびにサイズを変更するよりも、空の配列から始めることを考えました (realloc(size+1) による)。しかし、初期サイズを設定する方が最適であり、必要に応じてサイズを2倍にするのが最適かどうか疑問に思います。より良いアプローチのパフォーマンスは何ですか?

ありがとうございました！

4

6 に答える 6

2

何度も電話reallocするのは非効率です。したがって、メモリ サイズを 1 つ追加することはお勧めできません。サイズを 2 倍にし、完了したら、データを格納するために必要な正確なサイズを取得reallocし、そのサイズまで下げることができます。それは無駄なメモリを処理するはずです。ただしrealloc、これ以上増やす必要がないと判断した場合にのみ下げてください。

特定の状況と実装によっては、割り当てられたメモリの合計が大きくなったときに倍増が多すぎると思われる場合は、チェックを追加してメモリを段階的に追加できます。何かのようなもの

if (memory_allocated < 100)
   //realloc to double size
else
  //realloc 10 more

上記の数値は任意であり、より適切なものを選択できます。ただし、メモリを 2 倍にすることが大きな懸念事項である場合は、これを使用してください。それ以外の場合は、倍増して正確に再割り当てするだけで十分な解決策です。

于 2013-08-23T06:11:11.253 に答える
2

割り当てのパフォーマンスを向上させるために配列サイズを 2 倍にすることとは別に、realloc各 Move 項目への O(1) アクセス時間が本当に必要かどうかを尋ねます。そうでない場合は、次のように代わりにリストを使用することもできます。

typedef struct Move Move;
struct Move {
    /* your stuff here */
    Move *next;
};

これを念頭に置いて、新しい Move アイテムを作成するたびに、リストの head または tail に新しい Move アイテムを追加できます。しかし、ここでは、Move アイテムへのランダム アクセスに O(n) アクセス時間がかかります。

于 2013-08-23T06:20:35.697 に答える
1

あなたは倍増することができます。しかし、時間と無駄なスペースが気になる場合は、移動数の分布を知る必要があります。つまり、1 回の移動、2 回の移動などの時間の割合です。そうすれば、方法がより明確になる可能性があります。移動数が 100 以下の場合は 2 倍、100 を超える場合は 20 を追加します。

最初に、これらの統計を追跡するコードをゲームに記述し、それに応じてメソッドを調整します。

于 2013-08-23T06:15:06.913 に答える
0

定数を増やすと、各挿入のコストが O(n) になるため、n 個の要素を挿入すると O(n²) の時間計算量になります。

一定の係数で割り当てを増やした場合の単一要素の挿入の償却コストは O(1) です。これは、n 要素の挿入に対して O(n) を意味します。毎回2 倍にする必要はありません。25 % または 20 % またはせいぜい15 %以上を割り当てると、その 15 % が過剰に割り当てられますが、それでも挿入ごとに O(1) の償却コストが得られます。15% と言うと、O(1) はより高い定数係数を持ちますが、平均して、バッファーがいっぱいになるたびに 100% の増分よりもはるかに少ない過剰割り当てになります。

于 2018-12-28T20:14:04.477 に答える
-1

コンテストなし。任意のサイズを選択し、より多くのメモリを割り当てる必要があるたびにそのサイズを 2 倍にします。realloc()追加する必要がある構造体ごとに関数を呼び出すと、プログラムが遅くなります。

realloc()も高価です。これを呼び出すたびに、ヒープ上の新しいメモリ ブロックを使用することになります。realloc()新しいメモリが正常に割り当てられたときに、最初に割り当てられたブロックを解放します。ただし、これによりヒープの断片化が発生し、空きメモリが十分にある場合でも、割り当てる連続したメモリが不足するリスクがあります。

最後に、 を呼び出すたびrealloc()に、メモリ割り当てが失敗するリスクがあります。呼び出し回数をできるだけ少なくして、リスクを最小限に抑えてみませんか?

于 2013-08-23T06:16:48.617 に答える