Java高效分割字符串

最近优化一段代码的调用时间,发现性能瓶颈居然是io和split!io操作慢情有可原,那么对于split有没有更高效的方法呢?

一般方法

再java里面,一般的split 字符串解决方案有三种:

  1. 直接用split函数
  2. 使用StingTokenizer类
  3. indexOf,subString实现;

在JDK6的实现中,String类的split直接使用了正则表达式;不得不说,真是杀鸡焉用牛刀。

public String[] split(String regex, int limit) {
        return Pattern.compile(regex).split(this, limit);
}

在Android VM(Android 4.0以上系统源码如此)里面,对这个方法做了一定的优化:

public String[] split(String regularExpression, int limit) {
       String[] result = java.util.regex.Splitter.fastSplit(regularExpression, this, limit);
       return result != null ? result : Pattern.compile(regularExpression).split(this, limit);
   }

使用正则的话,效率肯定是有问题的;具体我们看一看就知道了。StringTokenizer是一个流式解析类,虽然JDK已经deprecated很久了,但是还是无法阻止大量的开源库使用这个类,效果自然得到了广泛的认可;另外呢,对于简单的分隔符,比如空格,单个字符等,可以直接使用indexOf得到索引,然后用subString得到字串;在这种情况下,理论上效率比上述两种高出很多;首先indexOf这个查找操作肯定是o(logn),然后,求字串最多也是线性操作。具体效率如何,测试一下就知道了。

测试

我们选择的测试字符串对象,是ps得到的输出,然后,写一个测试类,然后在Android下面运行:

package com.example.test.app;

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class TestSplitter {
		private static final String line =
            "root      1     0     572    436   c014bbc4 00011304 S /init";

    private static final int RUNS = 1000000;// 000000;

    private static final int COLUMNS = 9;

    private static String[] splitBySplit() {
        return line.split("\\s+");
    }

    private static List<String> splitByIndex() {
        List<String> l = new ArrayList<String>(16);

        int[] lp = getPsLinePos(line);
        for (int i1 = 1; i1 < COLUMNS - 1; i1++) {
            l.add(line.substring(lp[i1 - 1], lp[i1]));
        }
        l.add(line.substring(lp[COLUMNS - 1]));
        return l;
    }

    static int[] sPos;

    private static List<String> splitByIndex2() {
        List<String> l = new ArrayList<String>(16);

        if (sPos == null) {
            sPos = getPsLinePos(line);
        }
        for (int i1 = 1; i1 < COLUMNS - 1; i1++) {
            l.add(line.substring(sPos[i1 - 1], sPos[i1]));
        }
        l.add(line.substring(sPos[COLUMNS - 1]));
        return l;
    }

    private static int[] getPsLinePos(String line) {
        // 以下是为了得到每一列的pos;不在循环里面判空,节省调用
        int[] lp = new int[COLUMNS];
        lp[0] = 0; // 第一个起点是开始
        int index = 0;
        char lastChar;
        char curChar;

        int length = line.length();
        for (int j = 1; j < length; j++) {
            lastChar = line.charAt(j - 1);
            curChar = line.charAt(j);

            if (index + 1 >= COLUMNS) {
                break;
            }

            if (lastChar == ' ' && curChar != ' ') {
                // 如果是从空格突变为非空格,那么就是起始点
                lp[++index] = j;
            }
        }
        return lp;
    }

    private static List<String> splitByTokenizer() {
        List<String> l = new ArrayList<String>(16);
        StringTokenizer st = new StringTokenizer(line);
        while (st.hasMoreTokens()) {
            l.add(st.nextToken());
        }
        return l;
    }

    private static void test(Test test) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < RUNS; i++) {
            test.run();
        }
        System.out.println(String.format("%s use time: %s(ms)", test.tag, System.currentTimeMillis() - start));
    }

    public static void main() {
        Test split = new Test("Split") {
            @Override
            void run() {
                splitBySplit();
            }
        };

        Test string = new Test("StringTokenizer") {
            @Override
            void run() {
                splitByTokenizer();
            }
        };

        Test index = new Test("indexOf") {
            @Override
            void run() {
                splitByIndex();
            }
        };

        Test index2 = new Test("indexOf2") {
            @Override
            void run() {
                splitByIndex2();
            }
        };

        test(split);
        test(string);
        test(index);
        test(index2);

    }

    abstract static class Test {

        String tag;

        Test(String tag) {
            this.tag = tag;
        }

        abstract void run();

    }
}

结果

代码有点长,能用lambda就简洁了,这时后话;看一看性能表现如何(以下使用的是Htc x920e 4.4.2系统测试的):

I/System.out﹕ Split use time: 2267(ms)
I/System.out﹕ StringTokenizer use time: 326(ms)
I/System.out﹕ indexOf use time: 218(ms)
I/System.out﹕ indexOf2 use time: 157(ms)

这下体会到split有多么慢了吧!StringTokenizerindexOf时间在一个数量级,优化后的indexOf稍微好点,大致快一倍。

结论

  1. 在split需要被大量调用的场合,在现有的Android VM里面,String类的split方法肯定是不符合要求的
  2. StringTokenizer是最廉价的替换split的方法,简单修改成这个实现之后,花费时间能提升一个数量级;
  3. indexOf结合subString经过充分的优化,对于结构化特别是表格类的数据,效率是最快的,对于特定场合,可以考虑使用这种方法,速度大致提升一倍。

题外话

JDK8

自己的mac上面装的是jdk8,我看了一下String在上面的实现,如下:

public String[] split(String regex, int limit) {
        /* fastpath if the regex is a
         (1)one-char String and this character is not one of the
            RegEx's meta characters ".$|()[{^?*+\\", or
         (2)two-char String and the first char is the backslash and
            the second is not the ascii digit or ascii letter.
         */
        char ch = 0;
        if (((regex.value.length == 1 &&
             ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
             (regex.length() == 2 &&
              regex.charAt(0) == '\\' &&
              (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&
              ((ch-'a')|('z'-ch)) < 0 &&
              ((ch-'A')|('Z'-ch)) < 0)) &&
            (ch < Character.MIN_HIGH_SURROGATE ||
             ch > Character.MAX_LOW_SURROGATE))
        {
            int off = 0;
            int next = 0;
            boolean limited = limit > 0;
            ArrayList<String> list = new ArrayList<>();
            while ((next = indexOf(ch, off)) != -1) {
                if (!limited || list.size() < limit - 1) {
                    list.add(substring(off, next));
                    off = next + 1;
                } else {    // last one
                    //assert (list.size() == limit - 1);
                    list.add(substring(off, value.length));
                    off = value.length;
                    break;
                }
            }
            // If no match was found, return this
            if (off == 0)
                return new String[]{this};

            // Add remaining segment
            if (!limited || list.size() < limit)
                list.add(substring(off, value.length));

            // Construct result
            int resultSize = list.size();
            if (limit == 0) {
                while (resultSize > 0 && list.get(resultSize - 1).length() == 0) {
                    resultSize--;
                }
            }
            String[] result = new String[resultSize];
            return list.subList(0, resultSize).toArray(result);
        }
        return Pattern.compile(regex).split(this, limit);
    }

上面的实现可以看到:对于单个字符或者两个字符(后面限制条件不翻译了)作为分割的时候,JDK对它进行了优化!,看一看在JDK8上面的结论:(需要把那个正则替换成空格)

Split use time: 43(ms)
StringTokenizer use time: 15(ms)
indexOf use time: 14(ms)
indexOf2 use time: 7(ms)

效果惊人!!硬生生拉到了一个数量级!所以说,没事升级下JDK还是很有必要的,免费的午餐不过如此

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1984: 月下“毛景树”

1984: 月下“毛景树” Time Limit: 20 Sec  Memory Limit: 64 MB Submit: 1003  Solved: 324 ...

28130
来自专栏北京马哥教育

深度详解 Python yield与实现

学Python最简单的方法是什么?推荐阅读:Python开发工程师成长魔法 Python yield与实现 yield的功能类似于return,但是不同之处在于...

627120
来自专栏pangguoming

JDBC上关于数据库中多表操作一对多关系和多对多关系的实现方法

我们知道,在设计一个Java bean的时候,要把这些BEAN 的数据存放在数据库中的表结构,然而这些数据库中的表直接又有些特殊的关系,例如员工与部门直接有一对...

87470
来自专栏haifeiWu与他朋友们的专栏

Kotlin:Android开发技巧

Kotlin作为Android开发第一语言,然而身边做Android的大多还是使用java。Android转到Kotlin的趋势是必然的,公司隔壁部门已经全部使...

15530
来自专栏古时的风筝

模拟实现Spring中的注解装配

在Spring中,XML文件中的bean配置是实现Spring IOC的核心配置文件,在早版本的Spring中,只能基于XML配置文件,配置各个对象之间的依赖关...

23350
来自专栏魂祭心

原 荐 NEO VM原理及其实现

43080
来自专栏禁心尽力

反射+自定义注解---实现Excel数据列属性和JavaBean属性的自动映射

简单粗暴,直奔主题。 需求:通过自定义注解和反射技术,将Excel文件中的数据自动映射到pojo类中,最终返回一个List<pojo>集合?   今天我只是通...

52390
来自专栏恰童鞋骚年

剑指Offer面试题:27.最小的k个数

  这道题是典型的TopK问题,其最简单的思路莫过于把输入的n个整数排序,排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度是O(nlogn),但...

16120
来自专栏GIS讲堂

geotools编写shp转sql,实现shp数据入Oracle Spatial库

用到Oracle Spatial就很难避免shp文件的入库问题,虽然有shp2sdo工具,但是用起来不是很习惯,所以,本文讲述如何结合geotools实现shp...

28340
来自专栏云时之间

数据结构(三):栈与队列

3.1❶若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答: ? (1) 如果进站的车厢序列为123,则可能...

37970

扫码关注云+社区

领取腾讯云代金券