4

试图有效地从字符串中提取一些数字并尝试过

  • java.util.regex.Matcher
  • com.google.common.base.Splitter

结果是：

  • 通过正则表达式：24417 毫秒
  • 通过谷歌拆分器：17730 毫秒

您可以推荐另一种更快的方法吗？

我知道之前问过类似的问题，例如如何从 Java 中的字符串中提取多个整数？但我的重点是让它快速（但可维护/简单），因为它经常发生。

编辑：这是我的最终结果，与下面 Andrea Ligios 的结果一致：

  • 正则表达式（不带括号）：18857
  • Google Splitter（没有多余的 trimResults() 方法）：15329
  • Martijn Courteaux 回答如下：4073
import org.junit.Test;

import com.google.common.base.CharMatcher;
import com.google.common.base.Splitter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Sample {

    final static int COUNT = 50000000;
    public static final String INPUT = "FOO-1-9-BAR1"; // I want 1, 9, 1

    @Test
    public void extractNumbers() {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < COUNT; i++) {
            // Output is list of 1, 9, 1
            Demo.extractNumbersViaGoogleSplitter(INPUT);
        }
        System.out.println("Total execution time (ms) via Google Splitter: " + (System.currentTimeMillis() - startTime));


        startTime = System.currentTimeMillis();
        for (int i = 0; i < COUNT; i++) {
            // Output is list of 1, 9, 1
            Demo.extractNumbersViaRegEx(INPUT);
        }
        System.out.println("Total execution time (ms) Regular Expression: " + (System.currentTimeMillis() - startTime));

    }
}

class Demo {

    static List<Integer> extractNumbersViaGoogleSplitter(final String text) {

        Iterator<String> iter = Splitter.on(CharMatcher.JAVA_DIGIT.negate()).trimResults().omitEmptyStrings().split(text).iterator();
        final List<Integer> result = new ArrayList<Integer>();
        while (iter.hasNext()) {
            result.add(Integer.parseInt(iter.next()));

        }
        return result;
    }
    /**
     * Matches all the numbers in a string, as individual groups. e.g.
     * FOO-1-BAR1-1-12 matches 1,1,1,12.
     */
    private static final Pattern NUMBERS = Pattern.compile("(\\d+)");

    static List<Integer> extractNumbersViaRegEx(final String source) {
        final Matcher matcher = NUMBERS.matcher(source);
        final List<Integer> result = new ArrayList<Integer>();

        if (matcher.find()) {
            do {
                result.add(Integer.parseInt(matcher.group(0)));
            } while (matcher.find());
            return result;
        }
        return result;
    }
}
4

2 回答 2

9

这是一个非常快速的算法：

public List<Integer> extractIntegers(String input)
{
    List<Integer> result = new ArrayList<Integer>();
    int index = 0;
    int v = 0;
    int l = 0;
    while (index < input.length())
    {
        char c = input.charAt(index);
        if (Character.isDigit(c))
        {
            v *= 10;
            v += c - '0';
            l++;
        } else if (l > 0)
        {
            result.add(v);
            l = 0;
            v = 0;
        }
        index++;
    }
    if (l > 0)
    {
        result.add(v);
    }
    return result;
}

这段代码在我的机器上运行了 3672 毫秒，用于“FOO-1-9-BAR1”和 50000000 次运行。我在 2.3 GHz 内核上。

于 2012-12-13T15:44:41.287 回答
1

编辑：为了知识，我在同一台（旧）机器上运行了不同的解决方案，迭代了 5000000 次（从 OP 问题中删除了一个零），结果如下：

通过 Martijn Courteaux 算法的总执行时间（毫秒）：2562

通过 Char 比较的总执行时间（毫秒）：6891

总执行时间（毫秒）正则表达式（带括号）：12937

总执行时间（毫秒）正则表达式（不带括号）：12297

这比正则表达式快大约两倍：

   startTime = System.currentTimeMillis();
   for (int i = 0; i < COUNT; i++) {
       // Output is list of 1, 9, 1
       Demo.extractNumbersViaCharComparison(INPUT);
   }
   System.out.println("Total execution time (ms) via Char comparison: " + 
                              (System.currentTimeMillis() - startTime));

[...]

    static List<Integer> extractNumbersViaCharComparison(final String text) {

        final List<Integer> result = new ArrayList<Integer>();
        char[] chars = text.toCharArray();

        StringBuilder sB = new StringBuilder();
        boolean previousWasDigit = false;
        for (int i = 0; i < chars.length; i++) {
            if (Character.isDigit(chars[i])){
                previousWasDigit = true;
                sB.append(chars[i]);
            } else {
                if (previousWasDigit){
                    result.add(Integer.valueOf(sB.toString()));                 
                    previousWasDigit = false;
                    sB = new StringBuilder();
                }                   
            }
        }
        if (previousWasDigit)
            result.add(Integer.valueOf(sB.toString()));

        return result;
    }

顺便说一句，其他解决方案要优雅得多，+1

于 2012-12-13T15:50:01.907 回答