在 C 语言中读取和存储字符串列表的最节省内存的方法

Question

我想知道什么是最有效的内存读取方式&在c中存储字符串列表

每个字符串可能有不同的长度，所以预分配一个大的2D数组是浪费的。我还希望避免为每个字符串使用单独的malloc，因为可能有许多字符串。

字符串将从一个大缓冲区中读取到我正在询问的这个列表数据结构中。

是否有可能单独存储所有字符串，并分配正确的大小?

我的一个想法是将它们连续存储在缓冲区中，然后有一个char *数组指向缓冲区中的不同部分，其中将有''来分隔。我希望有更好的办法。

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

数据结构和字符串将严格为只读。

Answer 1

假设您事先知道所有字符串的长度，下面是一种比较有效的格式:

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

可以将长度存储在固定宽度的整数中，也可以存储在可变宽度的整数中，但关键是您可以跳转到末尾并相对有效地扫描所有长度，并且可以从长度总和中计算字符串的偏移量。当到达最后一个字符串时，没有剩余的空间

Answer 2

您可以创建单个缓冲区并连续存储它们，根据需要使用realloc()扩展缓冲区。但是，您需要第二个数组来存储字符串位置，也许realloc()也是如此，所以我可以简单地创建一个动态分配的数组和malloc()每个字符串分别。

Answer 3

查找所有字符串的个数和总长度:

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

然后，分配以下两个缓冲区:

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

最后，填充这两个缓冲区:

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个字符串。

Answer 4

最有效和内存效率最高的方法是两步解决方案。在第一次传递中，计算所有字符串的总大小，然后分配总内存块。在第二遍中，使用大缓冲区读取所有字符串。

您可以为字符串创建一个指针数组，并计算指针之间的差值以获得字符串的大小。这样可以保存空字节作为结束标记。

这里有一个完整的例子:

#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 bytesn", 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: %ldn", 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] = '';
        printf("string %05ld size=%8ld : %sn", i, stringSize, buffer);
        free(buffer);
    }
    // free the resource
    freeStringMap(&stringMap);
}

这个例子读取一个非常大的文本文件，将它分成几行，并创建一个每行一个字符串的数组。它只需要两个malloc调用。一个用于指针数组，一个用于字符串块。

Answer 5

如果它是严格只读的，正如你所描述的，你可以将整个字符串列表和它们的偏移量存储在一个内存块中，并且一次读取就可以读取整个列表。

第一个sizeof(long) bytes存储字符串的数量，n。下一个n long存储从位置(n+1)*sizeof(long)开始的string buffer开始的每个字符串的偏移量。您不必为每个字符串存储末尾的零，但是如果您这样做，您可以使用&str_buffer[offset[i]]访问每个字符串。如果不存储末尾的''，则必须将其复制到临时缓冲区中并自己追加。