Ima*_*ist 29 c string algorithm performance null-terminated
我正在用C编写语言解释器,我的string类型包含一个length属性,如下所示:
struct String
{
char* characters;
size_t length;
};
因此,我必须花费大量时间在我的解释器中手动处理这种字符串,因为C不包含对它的内置支持.我考虑过切换到简单的以null结尾的字符串只是为了符合底层C,但似乎有很多理由不:
如果使用"length"而不是查找null,则内置边界检查.
您必须遍历整个字符串才能找到它的长度.
你必须做额外的事情来处理以null结尾的字符串中间的空字符.
以空值终止的字符串与Unicode处理不佳.
非空终止字符串可以实习更多,即"Hello,world"和"Hello"的字符可以存储在同一个地方,只是具有不同的长度.使用以null结尾的字符串无法做到这一点.
字符串切片(注意:字符串在我的语言中是不可变的).显然,第二较慢(和更容易出错:考虑增加的错误检查begin和end对两种功能).
struct String slice(struct String in, size_t begin, size_t end)
{
struct String out;
out.characters = in.characters + begin;
out.length = end - begin;
return out;
}
char* slice(char* in, size_t begin, size_t end)
{
char* out = malloc(end - begin + 1);
for(int i = 0; i < end - begin; i++)
out[i] = in[i + begin];
out[end - begin] = '\0';
return out;
}
毕竟,我的想法不再是我是否应该使用以null结尾的字符串:我在考虑为什么C使用它们!
所以我的问题是:我错过了无效的空终止有什么好处吗？
wei*_*ure 30
从乔尔回到基础:
为什么C字符串以这种方式工作？这是因为发明了UNIX和C编程语言的PDP-7微处理器具有ASCIZ字符串类型.ASCIZ的意思是"最后用Z(零)的ASCII".
这是存储字符串的唯一方法吗？不,实际上,这是存储字符串的最糟糕方式之一.对于非平凡的程序,API,操作系统,类库,您应该避免像瘟疫这样的ASCIZ字符串.
Dan*_*ker 17
通常的解决方案是同时执行这两项操作 - 保持长度并保持空终止符.这不是额外的工作,意味着你总是准备将字符串传递给任何函数.
空终止字符串通常会消耗性能,原因很明显,发现长度所需的时间取决于长度.从好的方面来说,它们是用C表示字符串的标准方式,所以如果你想使用大多数C库,你别无选择,只能支持它们.
一个好处是,对于null-termination,以null结尾的字符串的任何尾部也是以null结尾的字符串.如果你需要将一个以第N个字符开头的子字符串(假设没有缓冲区溢出)传递给某个字符串处理函数 - 没问题,只需在那里传递一个被覆盖的地址.以其他方式存储大小时,您需要构造一个新字符串.
以空字符结尾的字符串的一个优点是,如果您逐个字符地遍历字符串,则只需要保留一个指针来处理字符串:
while (*s)
{
*s = toupper(*s);
s++;
}
而对于没有标记的字符串,你需要保持两个状态:指针和索引:
while (i < s.length)
{
s.data[i] = toupper(s.data[i]);
i++;
}
...或当前指针和限制:
s_end = s + length;
while (s < s_end)
{
*s = toupper(*s);
s++;
}
当CPU寄存器是稀缺资源(并且编译器在分配它们时更糟糕)时,这很重要.现在,不是那么多.
长度也存在问题.
长度需要额外的存储空间(现在不是这样的问题,但是30年前的一个重要因素).
每次更改字符串时都必须更新长度,这样就可以全面降低性能.
使用NUL终止的字符串,您仍然可以使用长度或存储指向最后一个字符的指针,因此如果您正在进行大量的字符串操作,您仍然可以使字符串与长度相等.
NUL终止的字符串要简单得多 - NUL终结符只是方法所使用的约定,用于strcat确定字符串的结尾.因此,您可以将它们存储在常规char数组中,而不必使用结构.
略微偏离主题,但有一种更有效的方式来做长度前缀的字符串比你描述的方式.创建这样的结构(在C99及以上版本中有效):
struct String
{
size_t length;
char characters[0];
}
这将创建一个在开始时具有长度的结构,其中'characters'元素可用作char*,就像使用当前结构一样.但是,不同之处在于,您只能在堆上为每个字符串分配一个项目,而不是两个.像这样分配你的字符串:
mystr = malloc(sizeof(String) + strlen(cstring))
例如 - 结构的长度(只是size_t)加上足够的空间来放置实际的字符串.
如果您不想使用C99,也可以使用"char characters [1]"执行此操作,并从要分配的字符串长度中减去1.