尽管我很喜欢C和c++,但我还是忍不住对空结尾字符串的选择抓耳挠脑:
Length prefixed (i.e. Pascal) strings existed before C
Length prefixed strings make several algorithms faster by allowing constant time length lookup.
Length prefixed strings make it more difficult to cause buffer overrun errors.
Even on a 32 bit machine, if you allow the string to be the size of available memory, a length prefixed string is only three bytes wider than a null terminated string. On 16 bit machines this is a single byte. On 64 bit machines, 4GB is a reasonable string length limit, but even if you want to expand it to the size of the machine word, 64 bit machines usually have ample memory making the extra seven bytes sort of a null argument. I know the original C standard was written for insanely poor machines (in terms of memory), but the efficiency argument doesn't sell me here.
Pretty much every other language (i.e. Perl, Pascal, Python, Java, C#, etc) use length prefixed strings. These languages usually beat C in string manipulation benchmarks because they are more efficient with strings.
C++ rectified this a bit with the std::basic_string template, but plain character arrays expecting null terminated strings are still pervasive. This is also imperfect because it requires heap allocation.
Null terminated strings have to reserve a character (namely, null), which cannot exist in the string, while length prefixed strings can contain embedded nulls.
其中一些东西比C语言出现得更晚,所以C语言不知道它们是有道理的。然而,在C语言出现之前,有些语言就已经很简单了。为什么会选择空终止字符串,而不是明显更好的长度前缀?
编辑:因为有些人问了关于我上面提到的效率点的事实(他们不喜欢我已经提供的事实),他们源于以下几点:
使用空结尾字符串的Concat需要O(n + m)时间复杂度。长度前缀通常只需要O(m)。
使用空结尾字符串的长度需要O(n)时间复杂度。长度前缀为O(1)。
Length和concat是迄今为止最常见的字符串操作。在一些情况下,以空结尾的字符串可能更有效,但这种情况发生的频率要低得多。
从下面的答案,这些是一些情况下,空终止字符串更有效:
When you need to cut off the start of a string and need to pass it to some method. You can't really do this in constant time with length prefixing even if you are allowed to destroy the original string, because the length prefix probably needs to follow alignment rules.
In some cases where you're just looping through the string character by character you might be able to save a CPU register. Note that this works only in the case that you haven't dynamically allocated the string (Because then you'd have to free it, necessitating using that CPU register you saved to hold the pointer you originally got from malloc and friends).
上面这些词都没有length和concat常见。
下面的答案中还有一个断言:
你需要把绳子的一端剪掉
但这个是不正确的——对于以null结尾的字符串和有长度前缀的字符串,它的时间是相同的。(以Null结尾的字符串只是在你想要的新结尾的地方插入一个Null,长度前缀只是从前缀中减去。)
懒惰、寄存器节俭和可移植性考虑到任何语言的汇编核心,尤其是C语言,它比汇编高出一步(因此继承了大量汇编遗留代码)。
你会同意null字符在那些ASCII的日子里是无用的,它(可能和EOF控件字符一样好)。
让我们看看伪代码
function readString(string) // 1 parameter: 1 register or 1 stact entries
pointer=addressOf(string)
while(string[pointer]!=CONTROL_CHAR) do
read(string[pointer])
increment pointer
共使用1个寄存器
案例2
function readString(length,string) // 2 parameters: 2 register used or 2 stack entries
pointer=addressOf(string)
while(length>0) do
read(string[pointer])
increment pointer
decrement length
共使用2个寄存器
这在当时似乎是短视的,但考虑到代码和寄存器的节俭(这在当时是PREMIUM,那时你知道,他们使用穿孔卡)。因此,更快(当处理器速度可以以kHz计),这个“黑客”是相当不错的,可轻松移植到无寄存器处理器。
为了便于讨论,我将实现2个常见的字符串操作
stringLength(string)
pointer=addressOf(string)
while(string[pointer]!=CONTROL_CHAR) do
increment pointer
return pointer-addressOf(string)
复杂度O(n),在大多数情况下PASCAL字符串是O(1),因为字符串的长度是预先挂起的字符串结构(这也意味着该操作必须在更早的阶段进行)。
concatString(string1,string2)
length1=stringLength(string1)
length2=stringLength(string2)
string3=allocate(string1+string2)
pointer1=addressOf(string1)
pointer3=addressOf(string3)
while(string1[pointer1]!=CONTROL_CHAR) do
string3[pointer3]=string1[pointer1]
increment pointer3
increment pointer1
pointer2=addressOf(string2)
while(string2[pointer2]!=CONTROL_CHAR) do
string3[pointer3]=string2[pointer2]
increment pointer3
increment pointer1
return string3
复杂度O(n)和预先设置字符串长度不会改变操作的复杂性,而我承认它会减少3倍的时间。
另一方面,如果你使用PASCAL字符串将不得不重新设计您的API来考虑在长度和bit-endianness注册,帕斯卡字符串的众所周知的限制255字符(0 xff)因为中存储的长度是1个字节(8位),而且你想要更长的字符串(16位- >任何)你必须考虑在一层的架构代码,这意味着在大多数情况下不相容的字符串API如果你想要更长的字符串。
例子:
One file was written with your prepended string api on an 8 bit computer and then would have to be read on say a 32 bit computer, what would the lazy program do considers that your 4bytes are the length of the string then allocate that lot of memory then attempt to read that many bytes.
Another case would be PPC 32 byte string read(little endian) onto a x86 (big endian), of course if you don't know that one is written by the other there would be trouble.
1 byte length (0x00000001) would become 16777216 (0x0100000) that is 16 MB for reading a 1 byte string.
Of course you would say that people should agree on one standard but even 16bit unicode got little and big endianness.
当然,C也有它的问题,但它不会受到这里提出的问题的影响。
与长度前缀相比,null终止的一个优点是字符串比较的简单性,这一点我没有看到任何人提到过。考虑比较标准,它返回小于、等于或大于的有符号结果。对于长度前缀,算法必须遵循以下几行:
Compare the two lengths; record the smaller, and note if they are equal (this last step might be deferred to step 3).
Scan the two character sequences, subtracting characters at matching indices (or use a dual pointer scan). Stop either when the difference is nonzero, returning the difference, or when the number of characters scanned is equal to the smaller length.
When the smaller length is reached, one string is a prefix of the other. Return negative or positive value according to which is shorter, or zero if of equal length.
将其与null终止算法进行对比:
扫描两个字符序列,在匹配的索引处减去字符[注意,移动指针处理得更好]。当差值非零时停止,返回差值。注意:如果一个字符串是另一个字符串的PROPER前缀,减法中的一个字符将为NUL,即零,比较将自然地停止在那里。
如果差值为零,-only then-检查是否有字符为NUL。如果是,则返回0,否则继续到下一个字符。
以null结尾的情况更简单,并且非常容易用双指针扫描高效地实现。带长度前缀的大小写至少做同样多的工作,几乎总是更多。如果你的算法必须做大量的字符串比较[e。编译器!],以null结尾的情况胜出。现在,这可能不那么重要了,但在过去,是的。