3

Cで文字列のリストを読み込んで保存する最もメモリ効率の良い方法を知りたい.

各文字列の長さは異なる場合があるため、大きな 2D 配列を事前に割り当てるのは無駄です。また、多くの文字列が存在する可能性があるため、文字列ごとに個別の malloc を回避したいと考えています。

文字列は、私が求めているこのリストのデータ構造に大きなバッファから読み込まれます。

正確に適切なサイズの単一の割り当てで、すべての文字列を個別に格納することは可能ですか?

私が持っている1つのアイデアは、それらをバッファに連続して保存し、バッファ内のさまざまな部分を指すchar *配列を作成することです。これには、区切りのために「\ 0」が含まれます。もっと良い方法があることを願っています。

struct list {
  char *index[32];
  char buf[];
};

データ構造と文字列は厳密に読み取り専用になります。

4

5 に答える 5

2

以下は、すべての文字列の長さが事前にわかっていると仮定した場合の、やや効率的な形式です。

|| total size |  string 1 | string 2 | ........ | string N | len(string N) | ... | len(string 2) | len(string 1) ||

長さは固定幅整数または可変幅整数のいずれかで格納できますが、ポイントは、最後までジャンプしてすべての長さを比較的効率的にスキャンできることです。長さの合計から、文字列のオフセットを計算できます。 . 残りのスペースがないときに、最後の文字列にいつ到達したかがわかります。

于 2014-03-12T11:38:06.553 に答える
0

すべての文字列の数と全長を求めます。

int num = 0;
int len = 0;
char* string = GetNextString(input);
while (string)
{
    num += 1;
    len += strlen(string);
    string = GetNextString(input);
}
Rewind(input);

次に、次の 2 つのバッファーを割り当てます。

int*  indexes = malloc(num*sizeof(int));
char* strings = malloc((num+len)*sizeof(char));

最後に、次の 2 つのバッファーを埋めます。

int index = 0;
for (int i=0; i<num; i++)
{
    indexes[i] = index;
    string = GetNextString(input);
    strcpy(strings+index,string);
    index += strlen(string)+1;
}

その後strings[indexes[i]]、i 番目の文字列にアクセスするために単純に使用できます。

于 2014-03-12T11:53:43.267 に答える
0

単一のバッファーを作成して連続して保存し、必要に応じて を使用してバッファーを拡張できますrealloc()。ただし、文字列の位置を格納するための 2 つ目の配列が必要になる場合がありますrealloc()。そのため、動的に割り当てられた配列とmalloc()各文字列を個別に作成するだけです。

于 2014-03-12T11:37:55.127 に答える
0

説明したように厳密に読み取り専用の場合は、文字列のリスト全体とそのオフセットをメモリの単一のチャンクに格納し、1 回の読み取りで全体を読み取ることができます。

1 つ目sizeof(long) bytesは、文字列の数を格納しますn。次のlong は、位置 (n+1)*sizeof(long) から始まるnオフセットを各文字列に格納します。string buffer各文字列の末尾のゼロを格納する必要はありませんが、格納する場合は、&str_buffer[offset[i]] を使用して各文字列にアクセスできます。末尾の '\0' を保存しない場合は、一時バッファーにコピーして自分で追加する必要があります。

于 2016-12-28T12:36:47.303 に答える
0

最も効率的でメモリ効率の良い方法は、2 パス ソリューションです。最初のパスでは、すべての文字列の合計サイズを計算してから、合計メモリ ブロックを割り当てます。2 番目のパスでは、大きなバッファーを使用してすべての文字列を読み取ります。

文字列のポインター配列を作成し、ポインター間の差を計算して文字列のサイズを取得できます。このようにして、null バイトを終了マーカーとして保存します。

ここに完全な例があります:

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

struct StringMap
{
    char *data;
    char **ptr;
    long cPos;
};


void initStringMap(StringMap *stringMap, long numberOfStrings, long totalCharacters)
{
    stringMap->data = (char*)malloc(sizeof(char)*(totalCharacters+1));
    stringMap->ptr = (char**)malloc(sizeof(char*)*(numberOfStrings+2));
    memset(stringMap->ptr, 0, sizeof(char*)*(numberOfStrings+1));
    stringMap->ptr[0] = stringMap->data;
    stringMap->ptr[1] = stringMap->data;
    stringMap->cPos = 0;
}


void extendString(StringMap *stringMap, char *str, size_t size)
{
    memcpy(stringMap->ptr[stringMap->cPos+1], str, size);
    stringMap->ptr[stringMap->cPos+1] += size;
}


void endString(StringMap *stringMap)
{
    stringMap->cPos++;
    stringMap->ptr[stringMap->cPos+1] = stringMap->ptr[stringMap->cPos];
}


long numberOfStringsInStringMap(StringMap *stringMap)
{
    return stringMap->cPos;
}


size_t stringSizeInStringMap(StringMap *stringMap, long index)
{
    return stringMap->ptr[index+1] - stringMap->ptr[index];
}


char* stringinStringMap(StringMap *stringMap, long index)
{
    return stringMap->ptr[index];
}


void freeStringMap(StringMap *stringMap)
{
    free(stringMap->data);
    free(stringMap->ptr);
}


int main()
{
    // The interesting values
    long numberOfStrings = 0;
    long totalCharacters = 0;

    // Scan the input for required information
    FILE *fd = fopen("/path/to/large/textfile.txt", "r");
    int bufferSize = 4096;
    char *readBuffer = (char*)malloc(sizeof(char)*bufferSize);
    int currentStringLength = 0;
    ssize_t readBytes;
    while ((readBytes = fread(readBuffer, sizeof(char), bufferSize, fd))>0) {
        for (int i = 0; i < readBytes; ++i) {
            const char c = readBuffer[i];
            if (c != '\n') {
                ++currentStringLength;
            } else {
                ++numberOfStrings;
                totalCharacters += currentStringLength;
                currentStringLength = 0;
            }
        }
    }

    // Display the found results
    printf("Found %ld strings with total of %ld bytes\n", numberOfStrings, totalCharacters);

    // Allocate the memory for the resource
    StringMap stringMap;
    initStringMap(&stringMap, numberOfStrings, totalCharacters);

    // read all strings
    rewind(fd);
    while ((readBytes = fread(readBuffer, sizeof(char), bufferSize, fd))>0) {
        char *stringStart = readBuffer;
        for (int i = 0; i < readBytes; ++i) {
            const char c = readBuffer[i];
            if (c == '\n') {
                extendString(&stringMap, stringStart, &readBuffer[i]-stringStart);
                endString(&stringMap);
                stringStart = &readBuffer[i+1];
            }
        }
        if (stringStart < &readBuffer[readBytes]) {
            extendString(&stringMap, stringStart, &readBuffer[readBytes]-stringStart);
        }
    }
    endString(&stringMap);
    fclose(fd);

    // Ok read the list
    numberOfStrings = numberOfStringsInStringMap(&stringMap);
    printf("Number of strings in map: %ld\n", numberOfStrings);
    for (long i = 0; i < numberOfStrings; ++i) {
        size_t stringSize = stringSizeInStringMap(&stringMap, i);
        char *buffer = (char*)malloc(stringSize+1);
        memcpy(buffer, stringinStringMap(&stringMap, i), stringSize);
        buffer[stringSize-1] = '\0';
        printf("string %05ld size=%8ld : %s\n", i, stringSize, buffer);
        free(buffer);
    }

    // free the resource
    freeStringMap(&stringMap);
}

この例では、非常に大きなテキスト ファイルを読み取り、それを行に分割して、行ごとに文字列を含む配列を作成します。必要なのは 2 回のmalloc呼び出しだけです。1 つはポインター配列用で、もう 1 つは文字列ブロック用です。

于 2014-03-12T12:36:42.497 に答える