15 September 2015
在看过雨痕大神的Golang学习笔记和《Redis设计与实现》之后,在这里总结一下。另外,雨痕大神啥时候更新1.5版本的学习笔记呀。

C语言中的字符串

C语言的字符串是通过字符数组实现的,每个字符串以'\0'结束。C语言字符串的三大操作函数也是常见笔试题。

int strlen(char *s) {
	char *p = s;
	while (*p != '\0')
		p++
	return p -s;
}

void strcpy(char *s, char *t) {
	int i;
	i = 0;
	while ((s[i] = t[i]) != '\0')
		i++;
}

void strcmp(char *s, char *t) {
	for ( ; *s == *t; s++, t++)
		if (*s == '\0')
			return 0;
	return *s - *t;

}

具体实现的方式为就不说了,主要说说这里的问题。

  • 在计算字符串长度的时候,每次都是需要遍历整个数组,直到'\0'为止,时间复杂度是O(n),如果字符串较长,性能还是会受到影响;
  • 在字符串复制的时候,有可能会导致越界。如果此时的内存结构是:
  a   \0   b   \0  

要给前面的一个字符串a赋值abc,那么结果就是后面紧跟着的字符串b也会被修改;

  • 字符串相加的时候,也有可能会引起越界的问题。

Golang的字符串

在Golang1.5之前,底层代码是用C语言写的。Golang1.5实现了自举,这个我还不懂是怎么具体实现的,就说1.4的。字符串不再像C语言那样用比较简易的字符数组实现,而是封装了字符串类型string

struct String
{
	byte* str;
	intgo len;
}
  • 这里定义了一个结构体,包含str和len字段。新增的len字段用于保存字符串长度。这样计算字符串长度的时间复杂度就是O(1),用空间换取了时间性能。
  • 字符串数据依然是用数组存储,但是由于有了len字段存储长度,所以不再需要'\0'来表示结束了。
  • 字符串的赋值就是指针指向对象的变化,不会有赋值操作,这样就不会导致越界问题了。
  • 如果两个字符串相加,操作方案是重新申请内存,保存相加的两个字符串相加的结果,这样也不会导致越界。
  • 但是还不是很完美,字符串是常量,不能通过数据下标的方式访问和修改。每次修改字符串,需要将字符串转换成[]byte数组。这样修改完之后,再转成字符串,这个字符串和之前的字符串已经不是同一个变量了。
  • 字符串相加操作也是,任何修改都会导致重新申请内存,时间复杂度是O(m+n)。Golang字符串修改一般是用copy或者bytes包的bytes.WriteString实现。

Redis的字符串

Redis是用C语言开发的,Redis支持字符串保存数据。它肯定不会用字符数组来做字符串实现。。。它开发了一个叫做简单动态字符串(simpledynamic string,SDS)的类型来实现字符串。定义的结构体如下:

struct sdshdr {    
	// 记录buf数组中已使用字节的数量    
	// 等于SDS所保存字符串的长度,用空间解决时间问题
	int len;    
	// 记录buf数组中未使用字节的数量。用于避免缓冲区溢出,如果当前空间不够,则再分配一个符合大小的空间  
	int free;   
	// 字节数组,用于保存字符串。用这个是为了和C语言字符串兼容
	char buf[];
};
  • 和Golang的实现相比,除了长度字段len和保存内容的数组buf。计算字符串长度的时间复杂度是O(1)
  • Redis是用C语言开发的,为了和C语言兼容,buf是C语言的字符串,以'\0'结束。
  • 它还增加了free字段表示空闲空间(别的类似实现可能是用容量字段,都差不多)。为了解决像Golang实现那样对于写操作不友好的问题,它会初始化一个较大的内存空间,字符串的增加会写入这些提前准备好的空间里面。一旦用完free的内容,就给buf追加空间。当追加空间的时候,性能会降到和Golang差不多的性能,一般情况还是很好的。

参考文献
  1. How to efficiently concatenate strings in Go? - stackoverflow

原文链接:字符串横向对比:C、Golang、Redis,转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;