0

私は現在、Cで非常に単純なJSONパーサーを実装しています.可変文字列を使用できるようにしたいと考えています. 私の現在の方法は次のとおりです。

char * str = calloc(0, sizeof(char));
//The following is executed in a loop
int length = strlen(str);
str = realloc(str, sizeof(char) * (length + 2));
//I had to reallocate with +2 in order to ensure I still had a zero value at the end
str[length] = newChar;
str[length + 1] = 0;

私はこのアプローチに満足していますが、毎回1文字しか追加していないことを考えると、少し非効率的だと思います（議論のために、文字列の最終的な長さを見つけるために先読みはしていません） . 別の方法は、リンクされたリストを使用することです。

struct linked_string
{
    char character;
    struct linked_string * next;
}

次に、処理が完了したら、長さを見つけ、char *適切な長さを割り当て、リンク リストを反復処理して文字列を作成します。

ただし、各文字と次の文字へのポインターの両方にメモリを割り当てる必要があるため、このアプローチはメモリ効率が悪いようです。したがって、私の質問は 2 つあります。

  • リンクされたリストを作成してからC文字列を作成する方が、毎回C文字列を再割り当てするよりも高速ですか?
  • もしそうなら、得られた速度は、より大きなメモリオーバーヘッドに見合う価値がありますか?
4

4 に答える 4

4

動的配列の標準的な方法は、保存するのがchars であるか他のものであるかに関係なく、拡張するときに容量を2 倍にすることです。(技術的には、複数でも機能しますが、2 倍にするのは簡単で、速度とメモリのバランスが取れています。) また、0 ターミネータを捨てて (0 で終了する文字列を返す必要がある場合は、最後に 1 つ追加してください)、割り当てられたサイズ (容量とも呼ばれます) と実際に格納された文字数。strlenそれ以外の場合、繰り返し使用することにより、ループの時間の複雑さが 2次になります (画家のアルゴリズムのシュレミエル)。

これらの変更により、時間の複雑さは線形になり (追加操作ごとに償却された定数時間)、実用的なパフォーマンスは、さまざまな醜い低レベルの理由から非常に優れています。

理論上の欠点は、厳密に必要な最大 2 倍のメモリを使用することですが、リンクされたリストでは、同じ量の文字に対して少なくとも 5 倍のメモリが必要です (64 ビット ポインター、パディング、および典型的な malloc オーバーヘッドを使用すると、24 のようになります)。または32回）。通常、実際には問題になりません。

于 2013-10-12T19:17:40.193 に答える
1

いいえ、リンクされたリストは間違いなく「高速」ではありません（そのようなことを測定する方法と場所）。これはひどいオーバーヘッドです。

現在のアプローチがボトルネックであることが本当にわかった場合は、いつでも文字列を の累乗のサイズで割り当てまたは再割り当てできます2。次に、配列reallocの合計サイズがそのような境界を超える場合にのみ行う必要があります。char

于 2013-10-12T19:14:48.377 に答える
1

テキストのセット全体を 1 つのメモリ割り当てに読み込んでから、各文字列を NUL で終了することが合理的であることをお勧めします。次に、文字列の数を数え、各文字列へのポインターの配列を作成します。そうすれば、テキスト領域用に 1 つのメモリ割り当てと、ポインターの配列用に 1 つのメモリ割り当てができます。

于 2013-10-12T19:17:27.520 に答える
0

可変長配列/文字列/その他のほとんどの実装には、sizeとcapacityがあります。容量は割り当てられたサイズであり、サイズは実際に使用されているものです。

struct mutable_string {
   char* data;
   size_t capacity;
};

新しい文字列を割り当てると、次のようになります。

#define INITIAL_CAPACITY 10

mutable_string* mutable_string_create_empty() {
   mutable_string* str = malloc(sizeof(mutable_string));
   if (!str) return NULL;

   str->data = calloc(INITIAL_CAPACITY, 1);
   if (!str->data) { free(str); return NULL; }

   str->capacity = INITIAL_CAPACITY;

   return str;
}

文字列に文字を追加する必要があるときはいつでも、次のようにします。

int mutable_string_concat_char(mutable_string* str, char chr) {
   size_t len = strlen(str->data);
   if (len < str->capacity) {
      str->data[len] = chr;
      return 1; //Success
   }

   size_t new_capacity = str->capacity * 2;
   char* new_data = realloc(str->data, new_capacity);
   if (!new_data) return 0;

   str->data = new_data;
   str->data[len] = chr;
   str->data[len + 1] = '\0';
   str->capacity = new_capacity;
}

リンクされたリストのアプローチは、次の理由で悪化します。

  1. キャラクターを追加するたびに割り当て呼び出しを行う必要があります。
  2. それはより多くのメモリを消費します。このアプローチでは、最大で が消費されsizeof(size_t) + (string_length + 1) * 2ます。そのアプローチは消費しstring_length * sizeof(linked_string)ます。
  3. 一般に、連結リストは配列ほどキャッシュに適していません。
于 2013-10-12T19:22:31.157 に答える