Efficiently extracting numbers from a java string (already tried guava and regular expressions)

Question

Trying to efficiently extract some numbers from a string and have tried

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

The results were :

• via Regular Expression: 24417 ms
• via Google Splitter: 17730 ms

Is there another faster way you can recommend ?

I know similar questions asked before e.g. How to extract multiple integers from a String in Java? but my emphasis is on making this fast (but maintainable/simple) as it happens a lot.

---

EDIT : Here are my final results which tie in with those from Andrea Ligios below:

• Regular Expression (without brackets) : 18857
• Google Splitter (without the superflous trimResults() method): 15329
• Martijn Courteaux answer below: 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;
    }
}

Answer 1

EDIT: for the sake of the knowledge, i've run the different solutions on the same (old) machine, with 5000000 iterations (one zero removed from OP question), here are the results:

Total execution time (ms) via Martijn Courteaux algorithm: 2562

Total execution time (ms) via Char comparison: 6891

Total execution time (ms) Regular Expression (WITH parenthesis): 12937

Total execution time (ms) Regular Expression (WITHOUT parenthesis): 12297

---

This is circa two time faster than regex:

   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;
    }

By the way the other solution is a lot more elegant, +1

Answer 2

This is a very quick algorithm:

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;
}

This code took on my machine 3672 milliseconds, for "FOO-1-9-BAR1" and 50000000 runs. I'm on a 2.3 GHz core.