2

我有空格分隔的字符串，其中包含数字，例如：

"abc123 ws32wd3 y3tg43 5tga89 a1a"

我必须解析字符串以从每个标记中获取数字，然后总结从标记中提取的所有数字。我已经写了下面的代码，但我认为，如果有很大的字符串，那么可能会出现性能问题。

所以，我的问题是：

  1. 我们如何提高以下代码的性能？

  2. 我们是否有另一种方法来编写以下代码来解决问题？

代码：

public class TestSum {

    public static int doSum(String str){
        String[] sArray = str.split(" ");
        char[] chr = null;
        String temp;
        String number = "";
        int sum=0;
        for(String s : sArray){
            chr = s.toCharArray();
            for(char c : chr){
                temp = String.valueOf(c);
                if(isNum(temp)){
                    number = number + temp;
                }           
            }
            sum = sum + Integer.parseInt(number);
            number="";
        }       
        return sum;
    }

    public static boolean isNum(String nStr){   
        try{
            Integer.parseInt(nStr);
            return true;
        }catch(NumberFormatException nfe){
            return false;
        }       
    }

    public static void main(String[] args) {
        System.out.println("Sum is "+ TestSum.doSum("abc123 ws32wd3 y3tg43 5tga89 a1a"));
    }
}
4

6 回答 6

5

这是我能想到的最快的：

public static int getSum(String str) 
{
    int sum = 0;
    int exp = 1;      
    for (int i = str.length() - 1; i >= 0; i--) 
    {
        final char c = str.charAt(i);
        if (c >= '0' && c <= '9')
        {
            sum += (c - '0') * exp;
            exp *= 10;
        }
        else
        {
            exp = 1;
        }
    }
    return sum;
}

它从右到左遍历字符串。多亏了这一点，当它“看到”一个数字时，它可以添加适当的值，具体取决于数字中“看到”的小数位。

使用Caliper进行基准测试

结果与davecom 的基准不同：

AUTHOR       RUNTIME (NS)   HOW MANY TIMES FASTER THAN JUNS
-----------------------------------------------------------
Adam              66.221                                600
Old              579.873                                 70
Prabhakaran   20,012.750                                  2 (2x faster than Juns)
Juns          39,681.074                                  1
于 2013-10-08T15:10:49.497 回答
4

您可以通过消除您的 isNum() 方法并使用内置的 Character.isDigit() 方法来开始提高代码的速度。

您可以通过使用正则表达式从每个标记中提取数字而不是使用循环来进一步提高速度。

祝你好运。

编辑

比较这里一些答案的表现，似乎@Prabhakaran 的答案比原来的要慢，而@OldCurmudgeon 的更快，@Adam Stelmaszczyk 的最快：

import java.util.*;

public class TestSum {

    public static int doSum(String str){
        String[] sArray = str.split(" ");
        char[] chr = null;
        String temp;
        String number = "";
        int sum=0;
        for(String s : sArray){
            chr = s.toCharArray();
            for(char c : chr){
                temp = String.valueOf(c);
                if(isNum(temp)){
                    number = number + temp;
                }           
            }
            sum = sum + Integer.parseInt(number);
            number="";
        }       
        return sum;
    }

    public static boolean isNum(String nStr){   
        try{
            Integer.parseInt(nStr);
            return true;
        }catch(NumberFormatException nfe){
            return false;
        }       
    }

    public static void testSum1(){
        String str = "abc123 ws32wd3 y3tg43 5tga89 a1a";      
        str = str.replaceAll("[^0-9]+", " ");
        List<String> asList = Arrays.asList(str.trim().split(" "));
        int sum=0;      
        for (String string : asList) {
            sum+=Integer.parseInt(string);
        }
        System.out.println(sum);
    }

    public static int doSum2(String str) {
        int sum = 0;
        // -1 means not started.
        int start = -1;
        for ( int i = 0; i < str.length(); i++ ) {
            char ch = str.charAt(i);
            if ( Character.isDigit(ch)) {
                if ( start == -1 ) {
                    // Start of a number.
                    start = i;
                }
            } else {
                if ( start != -1 ) {
                    // End of a number.
                    sum += Integer.parseInt(str.substring(start, i));
                    start = -1;
                }
            }
        }
        if ( start != -1 ) {
            // A number at the end of the string.
            sum += Integer.parseInt(str.substring(start, str.length()));
        }
        return sum;
    }

    public static int getSum(String str) {
        int sum = 0;
        int exp = 1;      
        for (int i = str.length() - 1; i >= 0; i--) {
            final char c = str.charAt(i);
            if (c >= '0' && c <= '9'){
                sum += (c - '0') * exp;
                exp *= 10;
            }
            else{
                exp = 1;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        TestSum.testSum1();
        long endTime = System.nanoTime();
        System.out.println("testSum1 took " + (endTime - startTime) + " nanoseconds");

        startTime = System.nanoTime();
        System.out.println(TestSum.doSum("abc123 ws32wd3 y3tg43 5tga89 a1a"));
        endTime = System.nanoTime();
        System.out.println("doSum took " + (endTime - startTime) + " nanoseconds");

        startTime = System.nanoTime();
        System.out.println(TestSum.doSum2("abc123 ws32wd3 y3tg43 5tga89 a1a"));
        endTime = System.nanoTime();
        System.out.println("doSum2 took " + (endTime - startTime) + " nanoseconds");

        startTime = System.nanoTime();
        System.out.println(TestSum.getSum("abc123 ws32wd3 y3tg43 5tga89 a1a"));
        endTime = System.nanoTime();
        System.out.println("getSum took " + (endTime - startTime) + " nanoseconds");
    }
}

这是输出

Davids-MacBook-Air:desktop dave$ javac TestSum.java
Davids-MacBook-Air:desktop dave$ java TestSum
299
testSum1 took 1790000 nanoseconds
1379
doSum took 373000 nanoseconds
299
doSum2 took 173000 nanoseconds
299
getSum took 45000 nanoseconds
于 2013-10-08T14:47:45.913 回答
3

为了获得最佳性能，您可以尝试以下操作：

public static int doSum(String str) {
  int sum = 0;
  // -1 means not started.
  int start = -1;
  for ( int i = 0; i < str.length(); i++ ) {
    char ch = str.charAt(i);
    if ( Character.isDigit(ch)) {
      if ( start == -1 ) {
        // Start of a number.
        start = i;
      }
    } else {
      if ( start != -1 ) {
        // End of a number.
        sum += Integer.parseInt(str.substring(start, i));
        start = -1;
      }
    }
  }
  if ( start != -1 ) {
    // A number at the end of the string.
    sum += Integer.parseInt(str.substring(start, str.length()));
  }
  return sum;
}

我的计算器确认的打印299是 123+32+3+3+43+5+89+1

于 2013-10-08T14:55:26.030 回答
3 
    String str = "abc123 ws32wd3 y3tg43 5tga89 a1a";      
    str = str.replaceAll("[^0-9]+", " ");
    List<String> asList = Arrays.asList(str.trim().split(" "));
    int sum=0;      
    for (String string : asList) {
        sum+=Integer.parseInt(string);
    }
    System.out.println(asList);
    System.out.println(sum);

输出

str = [123, 32, 3, 3, 43, 5, 89, 1]

总和 = 299

于 2013-10-08T14:52:59.123 回答
0

更简单的解决方案是使用正则表达式查找数字来解析该字符串\d，然后遍历新字符串（仅包含数字）并总结该字符串中的每个符号（数字）。

您甚至不必检查是否对数字求和，因为正则表达式会为您完成。

于 2013-10-08T14:51:03.977 回答
0

我认为为了加快转换速度，您可以使用以下技巧：
数字的 int 表示 = 数字的字符表示 - '0'

所以 int 5 = char 5 - '0'
或者换句话说
int 5 = '5' - '0'

这是因为 ASCII 表的索引方式。

我写的一些（未经测试的）代码超级快来说明：

for(int i=0; i<str.length(); i++){
  if (!(str.charAt(i).isDigit()) continue;

  do {
    //now handle digit parsing into a number
    crtNumber= crtNumber*10 + str.charAt(i)-'0'
    i++
  } while(str.charAt(i).isDigit());

  queue.push(crtNumber);//save the number somewhere
  crtNumber= 0; //prepare for next round
}
于 2013-10-08T15:06:09.620 回答