4

文字列からいくつかの数値を効率的に抽出しようとして、試してみました

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

結果は次のとおりです。

  • 正規表現経由: 24417 ミリ秒
  • Google スプリッター経由: 17730 ミリ秒

あなたが推奨できる別のより速い方法はありますか？

Javaで文字列から複数の整数を抽出する方法など、以前に同様の質問があったことを知っていますか? しかし、私の重点は、これが頻繁に発生するため、これを高速に (ただし保守可能/シンプルに) することです。

編集：以下のアンドレア・リギオスの結果と結びつく私の最終結果は次のとおりです。

  • 正規表現 (括弧なし) : 18857
  • Google スプリッター (不要な 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;
}

このコードは、「FOO-1-9-BAR1」と 50000000 回の実行で、私のマシンで 3672 ミリ秒かかりました。私は 2.3 GHz コアを使用しています。

于 2012-12-13T15:44:41.287 に答える
1

編集：知識のために、同じ（古い）マシンで5000000回の反復（OPの質問から1つのゼロを削除）でさまざまなソリューションを実行しました。結果は次のとおりです。

Martijn Courteauxアルゴリズムによる合計実行時間（ミリ秒）：2562

Char比較による合計実行時間（ms）：6891

合計実行時間（ミリ秒）正規表現（括弧付き）：12937

合計実行時間（ミリ秒）正規表現（括弧なし）：12297

これは正規表現よりも約2倍高速です。

   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 に答える