关于StringBuffer实现的思考

type

Post

status

Published

date

Dec 2, 2022

slug

Stringbuffer

summary

复习Java时，习题要求通过ArrayList与Char[]分别简单实现Stringbuffer，于是记录下其分别的性能开销和编写时的思考

背景

在复习Java时，于How2J网站上遇到习题是关于StringBuffer的手动实现，由于对于其在添加和删除的性能上十分感兴趣，和对其动态扩容的方式比较好奇，就跟着实现了一遍，并测试一下用ArrayList和Char[]，进行实现的时间开销和内存开销

代码接口与思考

题目要求的接口

在网站上给出实现接口如下


public interface IStringBuffer {
    public void append(String str); //追加字符串
    public void append(char c);  //追加字符
    public void insert(int pos,char b); //指定位置插入字符
    public void insert(int pos,String b); //指定位置插入字符串
    public void delete(int start); //从开始位置删除剩下的
    public void delete(int start,int end); //从开始位置删除结束位置-1
    public void reverse(); //反转
    public int length(); //返回长度
}

编写过程的思考

一开始编写时犯了比较致命的复杂化错误，其中的append和insert 他们的核心功能是相同，但是由于从上到下的实现，导致花了很多时间纠结于append的实现，其实append完全可以用insert去实现，这样就做到了一个代码多处使用，不用重复造轮子。

以后先通读需求，然后凝练他的核心功能，做到多处复用，降低无需的编写时间

实现代码

变量声明


    private char[] value;
	  private int length = 0;
    private int capacity = 10;

核心功能1

insert 函数的实现图示

char[]中的实现


public void insert(int pos, String b) {
				//关于边界值的判定
        if (pos > length)
            return;
        if (pos < 0)
            return;
        //将String转化为char数组
        char[] B = b.toCharArray();
        //如果超过容量则扩容
        if (length + b.length() > capacity) {
            capacity = (length + b.length()) * 2;
            char[] tmp = new char[capacity];
            //将旧数组复制到新数组
            System.arraycopy(value, 0, tmp, 0, length);
            value = tmp;
        }
        //如果超过容量则扩容
        System.arraycopy(value, pos, value, pos + b.length(), length - pos);
        //先将原字符数组中需要插入位置的元素复制到后方
        System.arraycopy(B, 0, value, pos, b.length());
        //将插入的数组复制到插入位置
        length += b.length();
}

ArraysList中的实现

对于ArrayList就可以直接依赖自身含有的函数进行插入


public void insert(int pos, String b) {
        if (pos < 0)
            return;
        if (pos > value.size())
            return;
        if (null == b)
            return;
        char[] B = b.toCharArray();
        int len = B.length;
        for (int i = 0; i < len; i++) {
            char c = B[i];
            value.add(pos + i, c);
        }
    }

性能比较

通过currentTimeMillis 记录其时间开销

通过Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory() 记录其内存开销

对官方、char[]实现、ArrayList实现，三个数据结构进行尾插测试

分别实验长度为10，长度为5的字符串尾部

代码


				StringBuffer S2 = new StringBuffer("");
        MyStringBuffer_char S3 = new MyStringBuffer_char("");
        MyStringBuffer_ArrayList S4 = new MyStringBuffer_ArrayList("");
        long Mem1=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
        long time1 = System.currentTimeMillis();
        String S = "sssssss";
        for(int i=0;i<1000000;i++)
        {
            S2.append(S);
        }
        long Mem2=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
        long time2 = System.currentTimeMillis();
        for(int i=0;i<1000000;i++)
        {
            S3.append(S);
        }
        long Mem3=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
        long time3 = System.currentTimeMillis();
        for(int i=0;i<1000000;i++)
        {
            S4.append(S);
        }
        long Mem4=Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory();
        long time4 = System.currentTimeMillis();
				System.out.println(time2-time1);
        System.out.println((Mem2-Mem1)/1024/1024);
        System.out.println(time3-time2);
        System.out.println((Mem3-Mem2)/1024/1024);
        System.out.println(time4-time3);
        System.out.println((Mem4-Mem3)/1024/1024);

长度为1，插入10^6次，分别三次取平均(时间ms，内存M)

ㅤ	时间1	时间2	时间3	时间均值	内存1	内存2	内存3	内存均值
官方	23	22	26	23.6	2	3	3	3
Char[]	38	42	41	40.3	1	1	1	1
ArrayList	41	40	37	39.3	40	40	40	40

长度为10，插入10^6次，分别三次取平均(时间ms，内存M)

ㅤ	时间1	时间2	时间3	时间均值	内存1	内存2	内存3	内存均值
官方	50	40	41	43.6	40	40	40	40
Char[]	65	55	55	58.3	21	21	21	21
ArrayList	781	595	598	658	28	28	28	28

长度为1，插入10^7次，分别三次取平均(时间ms，内存M)

ㅤ	时间1	时间2	时间3	时间均值	内存1	内存2	内存3	内存均值
官方	155	165	139	153	40	40	40	40
Char[]	38	37	38	38	-35	-35	-35	-35
ArrayList	39	34	33	36	40	40	40	40

由上述数据可以粗劣得出结论

选用Runtime库测量内存并不是很准确

高长度，低频率的插入，官方库有优势

任意长度，任意频率的插入，char[]的实现都有优势

高频率，低长度的常茹，ArrayList有优势

核心代码2

Delete 删除功能，待测试….