Cでは、バイトバッファを管理する「クラス」に取り組んでおり、任意のデータを最後に追加できます。の呼び出しを使用して基になる配列がいっぱいになると、自動サイズ変更を検討していますrealloc。これは、JavaまたはC＃を使用したことがある人なら誰でも理解できるはずStringBuilderです。サイズ変更の方法を理解しています。しかし、サイズ変更ごとにバッファをどれだけ増やすかについて、理論的根拠を示した提案はありますか？
明らかに、無駄なスペースと過剰なrealloc呼び出し（過剰なコピーにつながる可能性があります）の間にはトレードオフがあります。倍増を提案するチュートリアル/記事を見てきました。ユーザーが適切な初期推測を提供することができれば、それは無駄に思えます。プラットフォームのアライメントサイズの2倍または倍数に丸めてみる価値はありますか？
JavaやC＃が内部で何をしているのか知っている人はいますか？
C＃では、StringBuilderによって使用される内部バッファーを拡張するために使用される戦略が時間の経過とともに変更されました。
この問題を解決するための3つの基本的な戦略があり、それらには異なるパフォーマンス特性があります。
最初の基本戦略は次のとおりです。
この戦略には多くの問題がありますが、最も明白なのは、構築される文字列が非常に大きい場合、時間内にO（n 2 ）になることです。kが1000文字で、最後の文字列が100万文字だとします。最終的に文字列を1000、2000、3000、4000、...に再割り当てするため、1000 + 2000 + 3000 + 4000 + ... + 999000文字をコピーします。これは、合計で5,000億文字のコピーになります。
この戦略には、「無駄な」メモリの量がkによって制限されるという優れた特性があります。
実際には、このn-squared問題のため、この戦略はめったに使用されません。
2番目の基本戦略は
k％は通常100％です。その場合、これは「フル時のダブル」戦略と呼ばれます。
この戦略には、償却原価がO（n）であるという優れた特性があります。ここでも、最後の文字列が100万文字で、1000文字から始めるとします。1000、2000、4000、8000、...でコピーを作成し、最終的に1000 + 2000 + 4000 + 8000 ... + 512000文字をコピーします。これは、合計で約100万文字がコピーされます。ずっといい。
この戦略には、選択したパーセンテージに関係なく、償却原価が線形であるという特性があります。
この戦略には、コピー操作に非常にコストがかかる場合があり、未使用のメモリで最終的な文字列の長さの最大k％を浪費する可能性があるという多くの欠点があります。
3番目の戦略は、サイズkの各配列の配列のリンクリストを作成することです。既存の配列をオーバーフローさせると、新しい配列が割り当てられ、リストの最後に追加されます。
この戦略には、特にコストのかかる操作がなく、無駄なメモリの合計がkで制限され、ヒープ内の大きなブロックを定期的に見つける必要がないという優れた特性があります。リンクリスト内の配列の局所性が低い可能性があるため、最終的に文字列に変換するとコストがかかる可能性があるという欠点があります。
.NET Frameworkの文字列ビルダーは、フルの場合は2倍の戦略を使用していました。現在、リンクリストオブブロック戦略を使用しています。
あなたは一般的に成長因子を中庸（〜1.6）より少し小さく保ちたいです。中庸よりも小さい場合、破棄されたセグメントは、互いに隣接している限り、後の要求を満たすのに十分な大きさになります。あなたの成長因子が中庸よりも大きい場合、それは起こり得ません。
係数を1.5に減らすことは、それでも非常にうまく機能し、整数演算で簡単に実装できるという利点があることがわかりました（size = (size + (size << 1))>>1;-まともなコンパイラを使用する(size * 3)/2と、それをとして記述でき、高速コードにコンパイルできるはずです）。
数年前のUsenetでの会話を思い出しているようです。そこでは、DinkumwareのPJ Plauger（またはPete Becker）が、これまでよりもかなり広範なテストを実行し、同じ結論に達したと述べています（つまり、たとえば、std::vectorC ++標準ライブラリでの実装は1.5を使用します）。
バッファの拡張と縮小を操作する場合、必要な重要なプロパティは、一定の差ではなく、サイズの倍数だけ拡大または縮小することです。
16バイトの配列がある場合を考えてみましょう。そのサイズを128バイト増やすのはやり過ぎです。ただし、代わりに4096バイトの配列があり、それを128バイトだけ増やした場合、大量のコピーが発生することになります。
私は常にアレイを2倍または半分にするように教えられました。サイズや最大値についてのヒントが本当にない場合は、2を掛けることで、長期間にわたって多くの容量を確保できます。リソースに制約のあるシステムで作業している場合を除き、最大で2倍のスペースを割り当てることはできません。ひどすぎる。さらに、物事を2の累乗に保つと、ビットシフトやその他のトリックを使用できるようになり、基本的な割り当ては通常2の累乗になります。
JavaやC＃が内部で何をしているのか知っている人はいますか？
次のリンクを見て、JDK11のJavaのStringBuilder、特にensureCapacityInternalメソッドでどのように実行されるかを確認してください。 https://java-browser.yawk.at/java/11/java.base/java/lang/AbstractStringBuilder.java#java.lang.AbstractStringBuilder%23ensureCapacityInternal%28int%29
ドキュメントによると、これは実装固有ですが、16から始まります。
この実装のデフォルトの容量は16で、デフォルトの最大容量はInt32.MaxValueです。
StringBuilderオブジェクトは、インスタンスの値が拡大されたときに文字を格納するためにより多くのメモリを割り当てることができ、それに応じて容量が調整されます。たとえば、Append、AppendFormat、EnsureCapacity、Insert、およびReplaceメソッドは、インスタンスの値を拡大できます。
割り当てられるメモリの量は実装固有であり、必要なメモリの量が最大容量を超えると、例外（ArgumentOutOfRangeExceptionまたはOutOfMemoryExceptionのいずれか）がスローされます。
他のいくつかの.NETFrameworkに基づいて、現在の容量に達するたびに1.1を掛けることをお勧めします。余分なスペースが必要な場合は、それと同等のものEnsureCapacityを用意して、手動で必要なサイズに拡張します。
これをCに変換します。
私はおそらくList<List<string>>リストを維持します。
class StringBuilder
{
private List<List<string>> list;
public Append(List<string> listOfCharsToAppend)
{
list.Add(listOfCharsToAppend);
}
}
このようにすると、リストのリストを維持し、メモリを事前に割り当てるのではなく、オンデマンドでメモリを割り当てることができます。
.NET Frameworkのリストはこのアルゴリズムを使用します。初期容量が指定されている場合、このサイズのバッファーが作成されます。それ以外の場合、最初のアイテムが追加されるまでバッファーは割り当てられません。これにより、追加されたアイテムの数に等しいスペースが割り当てられますが、 4以上。より多くのスペースが必要な場合は、以前の2倍の容量の新しいバッファーを割り当て、すべてのアイテムを古いバッファーから新しいバッファーにコピーします。以前のStringBuilderは同様のアルゴリズムを使用していました。
.NET 4では、StringBuilderはコンストラクターで指定されたサイズの初期バッファーを割り当てます（デフォルトのサイズは16文字です）。割り当てられたバッファが小さすぎる場合、コピーは行われません。代わりに、現在のバッファーをリムに埋めてから、StringBuilderの新しいインスタンスを作成します。これにより、サイズ* MAX（length_of_remaining_data_to_add、MIN（length_of_all_previous_buffers、8000））*のバッファーが割り当てられ、少なくとも残りのすべてのデータが新しいバッファーとすべてのバッファーの合計サイズに収まります。少なくとも2倍になります。新しいStringBuilderは古いStringBuilderへの参照を保持するため、個々のインスタンスはバッファのリンクリストを作成します。