精华内容
下载资源
问答
  • 我们知道,Redis 支持字符串、哈希、列表、集合和有序集合五种基本类型。那么我们如何把图片、音频、...简单动态字符串 ( SDS ) Redis 是使用 C 语言编写的,但是,Redis 没有直接使用 C 语言自有的字符串类型,而是

    我们知道,Redis 支持字符串、哈希、列表、集合和有序集合五种基本类型。那么我们如何把图片、音频、视频或者压缩文件等二进制数据保存到 Redis 中呢?之前在使用 Memcached 缓存这类数据时是把它们转换成 Base64 字符串后再进行保存的。在 Redis 中也可以使用同样的方式,但是,Redis 中的 字符串是支持直接存储二进制数据的,那么我们就聊聊他是如何实现的?

    简单动态字符串 ( SDS )

    Redis 是使用 C 语言编写的,但是,Redis 没有直接使用 C 语言自有的字符串类型,而是自己构建了一个称为简单动态字符串 ( simple dynamic string, SDS ) 的抽象类型。你可能会有个疑惑,Redis 为什么要构建自己的 SDS,而不适用 C 语言自有的字符串?SDS 长什么样?使用 SDS 又有什么优点呢?

    C 语言中的字符串

    C 语言中传统字符串是使用长度为 N+1 的字符数组来表示长度为 N 的字符串,并且字符串数组的最后一个元素总是空字符 '\0'。如下所示:

    在这里插入图片描述

    C 语言中的这种简单的字符串表示方式,不能满足 Redis 对字符串在安全性、效率以及功能方面的要求,所以 Redis 自己构建了字符串表示方式 SDS。

    SDS 的定义

    在 Redis 源码文件 sds.h 中定义了 SDS 的结构,如下所示:

    struct sdshdr {
        // 记录 buf 数组中已使用的数量
        unsigned int len; 
        // 记录 buf 中未使用的空间数量
        unsigned int free; 
        // 字符数组,用于保存字符串
        char buf[];  
    };
    

    有上面的源码,我们看到 SDS 中也是使用字符数组来存放字符串,但是,它是通过 属性 len 来表示当前字符串的长度。

    SDS 与 C 字符串的区别

    接下来我们就通过对比 SDS 和 C 字符串的区别,来说明为什么 Redis 需要构建 SDS,而不使用 C 字符串?

    1、获取字符串长度的复杂度

    因为 C 字符串不记录自身的长度,所以在获取一个 C 字符串的长度时,需要遍历整个字符数组,对遇到的每个字符进行计数,知道遇到代表字符串结尾的空字符串'\0' 为止,那么,这个操作的复杂度为 O(N)。

    上面的 SDS 结构的源码,我们可知,SDS 字符串通过 len 记录了当前字符串的长度,那么当获取 SDS 的字符串长度的复杂度仅为 O(1)。这就确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈,因为不管字符串多长,其获取长度的复杂度都是O(1)。这或许也是 Redis 快的一个原因吧。

    2、杜绝缓冲区溢出

    我们在日常 Java 开发中,经常会用到字符串的拼接,在 C 语言 和 Redis 中也经常用到字符串的拼接。由于 C 字符串不记录自身长度,这样就带来了一个问题就是,如果在拼接字符串时,如果内存计算不当,就会造成缓冲区溢出。如下所示:

    开始为 相邻着的字符串 “Redis” 和 “Mysql”

    在这里插入图片描述

    假如,我们把 “Redis” 改为 “Redis Client”,但忘记了重新分配内存,就会导致如下所示的结果。
    在这里插入图片描述

    可以看到,我们修改 “Redis” 字符串时,无意导致 把 “Mysql” 字符串的位置给占了,导致数据污染。那么 Redis 的 SDS 字符串是如何解决的呢?

    由 SDS 的结构我们可知,SDS 有 len 存储了当前长度,还有 free 存储了未使用的长度,这样就简单多了,当操作字符串拼接时,可以先判断一下 free 和需要拼接的字符串,是否能够存的下,如放的下则直接执行,如果放不下,则进行扩容操作。

    3、减少修改字符串时带来的内存分配次数

    正如我们前面介绍的,因为 C 字符串底层是字符串数组,每次创建总是一个 N+1 个字符长的数组( 额外的一个字符空间用于保存空字符,这也是一个坑)。

    Redis 是个高性能的内存数据库,如果需要对字符串进行频繁的拼接和截取操作,如果我们忘了重新分配空间,就会造成缓冲区溢出。

    因为内存重分配涉及复杂的算法,并且可能需要执行系统调用,所以它通常是一个比较耗时的操作,在 Redis 这种对于速度要求严苛,数据频繁修改的数据库中,这种耗时操作是应该避免的。

    Redis 为了避免 C 字符串的这种缺陷,SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联,SDS实现了空间预分配和惰性空间释放两种优化策略,去达到性能最大化,空间利用最大化:

    • 空间预分配

      当对 SDS 进行修改,并且需要进行空间扩展操作的时候,Redis 程序不仅会为 SDS 分配修改所必须要的空间,并且根据特定的公式,分配额外的空间,这样就可以避免我们连续执行字符串添加所带来的内存分配消耗。

      比如有如下字符串:
      在这里插入图片描述

      我们执行拼接函数,将SDS的长度修改为13字节,并将SDS的未使用空间同样修改为13字节
      在这里插入图片描述

      如果我们在拼接字符串"abc", 长度为 9 小于 free 的值13,所以无需再次执行空间分配操作。

    在这里插入图片描述

    • 空间惰性释放

      刚才说到了分配空间时,会预分配多余的空间,你可以会问这个会不会导致内存泄露呢?这个无需担心,当我们执行完一个字符串缩减的操作,Redis 并不会马上收回我们的空间,因为可以预防你继续添加的操作,这样可以减少分配空间带来的消耗,但是当你再次操作还是没用到多余空间的时候,Redis 也还是会收回对于的空间,防止内存的浪费的。

      比如我们有如下字符串:

    在这里插入图片描述

    我么截取字符串,删除“ Client”,结果如下,我们注意,删除字符串的空间并没有删除,如果后续还是用就可以继续使用,不用再次分配空间,如果不使用了,调用函数删除即可。

    在这里插入图片描述

    4、二进制安全
    我们上文提的 C 字符串中是以空字符 ‘\0’ 来表示 C 字符串的终止符号。这样字符串里就不能包含空字符,否则最先被读入的空字符将被误认为字符串传结尾,这些限制使得 C 字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件等这样的二进制数据。如下所示:
    在这里插入图片描述

    在 Redis 中 SDS 中就不存在此问题,因为在 SDS 中通过 len 属性保存了字符串的长度,所以,在 SDS 中是通过 len 属性的值而不是空字符来判断字符串的是否结束。上图使用 SDS 存储如下所示:
    在这里插入图片描述

    通过使用二进制安全的 SDS,而不是 C 字符串,使得Redis不仅可以保存文本数据,还可以保存任意格式的二进制数据。

    总结

    Redis 通过自构建 SDS,而不使用 C 字符串,不仅解决了 C 字符串存在的缓冲区溢出问题,同时,还通过减少因修改字符串导致的频繁分配内存空间和获取长度导致的性能消耗。再者,由于 SDS 不再使用空字符 '\0' 标志字符串的结尾,使得 Redis 不但可以存储文本数据,还可以保存任意格式二进制数据。

    参考: 《Redis 设计与实现》

    展开全文
  • 动态拼接字符

    万次阅读 2020-09-14 21:19:51
    工作中有时候需要传入不定个数的字符串,就需要专门写一个函数动态添加字符串,下面看下函数: #include <iostream> #include <cstring> #include "stdarg.h" std::string append(int count,const ...

       ❤️强烈推荐人工智能学习网站❤️    

      工作中有时候需要传入不定个数的字符串,就需要专门写一个函数动态添加字符串,下面看下函数:

    #include <iostream>
    #include <cstring>
    #include "stdarg.h"
    
    std::string append(int count,const char* msg, ...){
        std::string srcStr;
        va_list vaList;
        va_start(vaList, msg);
        char tmp[1024] = {0};
        int n = 0;
        int true_count = count -1;
        strcat(tmp,msg);
    
        while(1)
        {
            strcat(tmp,"_");
            strcat(tmp,va_arg(vaList,char*));
    
            n++;
            if(n == true_count)
            {
                printf("%d\n",n);
                break;
            }
        }
        va_end(vaList);//结束可变参数列表
        std::string stmp(tmp);
        srcStr += stmp;
    
        return srcStr;
    }
    
    int main(){
        //string
        std::string str1 = "12";
        std::string str2 = "34";
        std::string str3 = "56";
        std::string src = append(3,str1.c_str(),str2.c_str(),str3.c_str());
    
        std::cout <<  src << std::endl;
    
        return 0;
    }

    经测试好用。

    展开全文
  • Redis没有直接使用C语言传统的字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示. 在Redis 里面,C字符串只会作为字符串面量(string ...

    引言

    Redis没有直接使用C语言传统的字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示.

    在Redis 里面,C字符串只会作为字符串面量(string literal)用在一些无须对字符串值进行修改的地方。

    在一个可以被修改的字符串值里面,Redis就会使用SDS来表示字符串值,比如:Redis数据库里面,包含字符串值得健值对在底层得实现都是由SDS实现的以及AOF的缓冲区等(注:在一些无需更改的地方字符串是用C字符串)

    基本结构

     

    🤔思考:

    (1)为什么不直接使用C字符串,而要自己实现一个SDS呢?

    肯定是C字符串整体上满足不了需求嘛,因为C语言使用的简单的字符串表示方式,并不能满足Redis对字符串在安全性、效率性以及功能方面的要求

    (2)SDS遵循了C字符串以空格符结尾的惯例,为什么要这样设计呢?

    好处就是SDS可以直接重用一部分C字符串函数,不用自己去实现

     

    获取字符串长度

    C字符串不记录自身的长度信息,所以为了获取一个C字符串的长度,程序必须遍历整个字符串,对遇到的每个字符进行计数,知道遇到代表字符串结尾的空字符为止,时间复杂度为O(N)

    Redis中的SDS因为记录的字符串长度,所以获取长度信息 时间复杂度为O(1),因此,在反复获取长度的时候能大大减少性能消耗

    缓存区溢出问题

    C语言不记录自身长度还可能造成缓冲区溢出(buffer overflow)

    但SDS的空间分配策略考虑到这点,当SDS的API需要对SDS进行操作修改时候,API会先检查SDS的空间是否满足修改需求,如果不满足的话,API会自动将SDS的空间扩展至需要执行修改所需的大小,然后才执行相关操作

    🤔思考

    每次重新分配空间都只是按需分配,那和C语言每次重新分配新空间进行存储没多大区别呀?性能好像也没增加多少呀?

    所以如何减少空间重新分配也在Redis考虑之中

    空间预分配策略

    空间预分配就是用与优化SDS的字符串增长操作:当SDS的API对一个SDS进行修改并需要对SDS进行空间扩展的时候,程序不仅仅会为SDS分配修改所必须的空间,还会为SDS分配额外的使用空间

    额外空间分配数量公式:

    如果SDS进行修改之后

    (1)SDS的长度(也即是len属性的值)将小于1MB,那么程序分配和len属性同样大小的未使用空间,这时len属性的值江河free属性的值相同

    (2)SDS的长度大于等于1MB,那么程序将会分配1MB的未使用空间

    这样将N次字符串所需内存重分配次数从必须N次变为最多N次(注:会用空间浪费,典型的空间换时间策略)

    惰性空间释放(有额外分配空间,那回收怎么办?)

    惰性空间释放用于优化SDS的字符串缩短操作,当SDS的API需要缩短保存的字符串,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量保存起来,并等待将来使用

    当然SDS也提供了相应的API,让我们可以在需要的时候,真正释放SDS的使用空间,所以不用担心惰性空间释放策略造成的内存浪费

    二进制安全

    C中字符串只能保存文本数据,不能保存图片、音频等这样的二进制数据

    Redis的SDS的API都是二进制安全的(binary-safe),所有SDS API都会以处理二进制方式来处理SDS存放在buf数组里面的数据,不进行任何限制、过滤或者假设(这也是为什么buf属性称为字节数组的原因)

    因此Redis 不仅可以保存文本数据,还可以保存任意格式的二进制数据

     

    总结:

    Redis只会使用C字符串作为字面量,大多数情况下,Redis使用SDS(Simple Dynamic String,简单动态字符串)作为字符串表示

    优点:

    (1)获取字符串长度时间复杂度降为O(1)

    (2)减少了缓存区溢出

    (3)额外空间预分配策略减少了内存重分配次数

    (4)二进制安全

    (5)兼容部分C语言字符串函数

     

     

    展开全文
  • Redis之简单动态字符串(SDS)

    万次阅读 2018-04-28 10:06:48
    简单动态字符串SDS(Simple Dynamic String) //SDS数据结构如下 struct sdshdr{ //len用来记录buf数组中已使用字节的数量 //等于SDS所保存字符串的长度 int len; //记录buf数组中未使用字节的数量 int free; ...

    简单动态字符串SDS(Simple Dynamic String)

    //SDS数据结构如下
    struct sdshdr{
        //len用来记录buf数组中已使用字节的数量
        //等于SDS所保存字符串的长度
        int len;
        //记录buf数组中未使用字节的数量
        int free;
        //字节数组,用于保存字符串
        char buf[];
    }

    基于SDS数据结构的定义和一些API规则,SDS相比于C字符串有如下优势
    1. 获取字符串长度的复杂度为O(1),C字符串的复杂度为O(n)
    2. 杜绝缓冲区溢出
    3. 减少修改字符串时带来的内存重分配次数
    4. 二进制安全


    原理分析

    1. 由于结构体中len属性的存在,因此查询字符串长度,只需知道len的值是多少就可以了,而无需遍历整个字符串(C字符串就是这么做的,所以为O(n))。同时,SDS字符串结束不是通过空字符串\0来判断的,也是通过len属性来判断的,通过\0来判断字符串结束,会有诸多限制,如果字符串中本身包含\0,那么\0后面的字符就会丢失,所以SDS可以用来存储任何数据,而C字符串则不能保存图片、音频、视频等二进制数据。
    2. 由于Free属性的存在,以及空间预分配策略和惰性空间释放规则,可以减少内存空间重分配次数,这样会大大提升性能,C字符串内存空间是刚好用来存储字符串,但是当要缩小字符串长度时,如果不进行内存重分配,则会导致内存泄露,当要增加字符串长度时,如果不进行内存重分配,则会导致内存溢出,如果进行内存重分配,在频繁修改字符串长度的场景下,则会导致性能大幅度下降。
    3. SDS同时也会在最后一个位置放\0,这样做的好处是可以兼容部分C字符串函数
    展开全文
  • #include #include using namespace std; int main() { string in_str; cin>>in_str;... size_t len=strlen(in_str.c_str());.../*一定不要忘记创建的字符串数组长度应该比字符个数多1,从而可以在最
  • c++中,动态字符串(char)数组可以采用cin输入流进行多个字符的赋值吗?
  • Redis没有直接使用C语言中的字符串,而是自己构建了SDS这样的一种简单动态字符串,并且将他作为Redis中字符串的默认的表示,个人认为,Redis并未完全抛弃C语言字符串,只不过是在C语言字符串的基础上,通过封装其他...
  • Redis没有直接使用C语言传统的字符串表示(以空字符 \0 结尾的字符数组),而是构建了一种名为简单动态字符串SDS的抽象类型,并将SDS用作Redis的默认字符串表示。 SDS的数据结构 struct sdshdr{ //记录buf数组中已经...
  • C++ 动态字符串二维数组

    千次阅读 2019-09-27 11:25:14
    我定义了一个动态字符串二维数组如下: //定义条件二维动态数组 typedef String TJsxT[1000]; TJsxT *TJsx; TJsx=new TJsxT[TJnum+1]; 这种二维的行与列的理解正确的是:TJsx[TJnum+1][1000],至于为什么,我个人是...
  • 题干:给定一个字符串s,在s中的任意位置添加任意字符,求最少添加多少个字符,可以使s变为回文字符串? 示例1:字符串"ab",最少添加1个字符"b"使其变为回文字符串"bab" 示例2:“a”,最少添加0个字符,使其变为...
  • 视频生成动态字符画 python

    千次阅读 2018-07-25 10:08:59
    看抖音视频类型得字符画比较感兴趣,恰好学习python,就写了下代码。 首先对视频用cv2取一个个得帧,再对帧转换为image,最后将image转换为字符画。并且用python得gui显示出来。 from PIL import Image as im ...
  • js的replace全部替换动态字符

    千次阅读 2018-09-22 21:27:06
    js的replace全部替换动态字符串? 解决方法: 1.全部替换写死的字符串 var str="朋友的朋友"; var new_str="同学"; alert(str.replace(new RegExp(/朋友/g),new_str)); 2.全部替换...
  • C语言字符串的动态操作

    千次阅读 2018-10-26 21:43:23
    C语言中的字符串,相比C++,少了许多动态操作函数,比如没有动态删除字符串开头或末尾元素的函数,也没有动态追加字符串的函数,为了一劳永逸,仿写了C++中的push_back(), push_front(), pop_back(), pop_front(), ...
  • 如标题 c语言中如何动态输入字符串而不需要事先定义字符数组大小或为字符指针分配空间
  • 要用最少的字符操作将字符串A 转换为字符串B。 这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。 将字符串A变换为字符串B 所用的最少字符操作次数也称为字符串A到B ...
  • java向字符串数组中动态添加字符

    万次阅读 2013-11-08 15:23:32
    在向字符串数组中动态添加字符串中遇到了错误。 我已开始是这样做的 String [] result; int n=5; for(int i=0;i { result[0]=String.valueOf(i); }; 最后发现这样确实是有错的。修改成 int n=5; String [] ...
  • 字符串上的简单动态规划

    千次阅读 多人点赞 2018-09-13 14:18:26
    因为数据结构快学串了,以前又做过一些字符串dp的题,今天突然就想把它们写在一起吧。   直接开始 问题1:给两个字符串,求最长公共子串 问题2:给两个字符串,求最长公共子序列 问题3:给一个字符串,求最长...
  • c语言:动态输入字符串数组

    千次阅读 2020-07-12 12:07:42
    一般情况下,字符串数组都以二维数组或指针数组定义,而二维数组不能初始化为空,所以本文动态定义以指针数组为例,代码如下 #include<stdio.h> #include<stdlib.h> //字符串数组默认可以用空格隔开!!...
  • 动态规划——字符串比对问题

    千次阅读 2019-08-02 16:16:25
    字符串比对问题是利用动态规划求解的经典问题之一。 比对问题在实际生活中应用广发,如DNA串的比对。 问题描述 给定两个字符串,对其相同字符的程度及位置进行比对 。求两个字符串的最小错位程度。 错位程度(想要...
  • Js动态HTML字符串拼接法加载数据

    千次阅读 2018-12-01 13:20:21
    js动态加载显示方法有两种。 1. 动态创建元素,配置属性,加入母元素标签(编码量多) 2. HTML字符串拼接,替换为母元素innerHTML(高效) 方法 方法一可以参考 =&amp;gt;Js动态给表格节点tbody添加数据 方法...
  • 目前我的问题是如何在while循环中跳出,尝试了很多方法但是还是没用。 求解。
  • 交错字符串——动态规划

    千次阅读 2015-07-09 10:14:35
    交错构成的意思是,对于字符串C,可以将其每个字符标记为A类或B类,使得我A类的每个字符顺序构成了A字符串,B类的每个字符顺序构成了B字符串。如:对于A=”rabbit” B=”mq”, ”rabmbitq”是由A和B交错构成的,但”...
  • SDS简单动态字符串 数据结构 3.2之前 typedef char *sds struct sdschar { // buf[] 中已使用的字节数 int len; // buf[] 中未使用的字节数 int free; // 字符数组,用于实际存储字符串内容 char buf[]; } ...
  • Problem G: 动态字符串排序

    千次阅读 2014-12-13 13:47:25
    Problem G: 动态字符串排序 Time Limit: 5 Sec Memory Limit: 128 MB Submit: 905 Solved: 154 [Submit][Status][Web Board] Description 把字符串按照ASCII码序的从小到大排列出来。 串的ASCII码...
  • 一个12*12的table里面的td的id为0-0,一直到12-12.我通过点击td穿个id到方法中,方法中我需要用到该td的坐标也就是id中-的前后两个数 ,我该如何截取这个数,因为有0-9和10-12两种情况
  • js 动态替换字符

    千次阅读 2018-03-05 15:53:46
    环境:被替换字符串及替换字符串都是由外面传进来,需要替换满足条件的所有字符串。 例子: var str = “(&amp;[DT])?Utils.strToDate(&amp;[DT])”; 需要将str 转换为 “(getValue(DT))?Utils....
  • Redis中简单动态字符串sds数据结构与API相关文件是:sds.h, sds.c。 转载请注明,本文出自:http://blog.csdn.net/acceptedxukai/article/details/17482611 预备知识 下面介绍有关sizeof...
  • C语言 字符串和字符串数组动态分配及赋值

    万次阅读 多人点赞 2018-10-25 19:25:18
    1、字符串指针一定要开辟空间后在做输入 char * str; str=(char*)malloc(100*sizeof(char)); scanf(&quot;%s&quot;,&amp;amp;str); 2、字符串数组要做初始化的开辟空间后再来存储字符串 char * ...
  • 字符串A变换为字符串B 所用的最少字符操作次数也称为字符串A到B 的编辑距离,记为 D(A,B)。 试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离D(A,B)。 例题分析 先上图:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 958,420
精华内容 383,368
关键字:

动态字符什么意思