0

我正在用java编写一个程序来获取一个非常大的字符串（字符串s <= 100000）中单词的统计信息。这应该花费不到 1 秒的时间并使用少于 16 MB 的内存。

import java.util.Scanner;
class Main{
 public static void main(String[] args){


  Scanner sc = new Scanner(System.in);
  String t = sc.nextLine();
  int i=0;
  while(t.charAt(i)==' ') i++;
  t = t.substring(i);
  String[] s = t.split(" +");

  RecString[] stat  = new RecString[s.length];
  for(i=0; i<s.length;i++){
    stat[i] = new RecString("");  
  }
  int j=0;
  for(i=0; i<s.length;i++){
    int f=0;
    for(int h =0; h<stat.length; h++){
     if(stat[h].word.equals(s[i])){
       f = 1;
       stat[h].count++;
       break;
     }
    }
    if(f==0){
      stat[j] = new RecString(s[i]);
      j++;
    }
  }
  for(i=0;i<=j;i++){
   if(stat[i].word != ""){
      System.out.println(stat[i].word+" "+(stat[i].count));
   }
  }


 }
}

class RecString{
    public  String word;
    public  int count;

    public RecString(String s){
        word = s;
        count = 1;
    }

}

此代码适用于长度 <=255 的字符串，但对于大字符串，我有时间或/和内存限制。

请帮我优化我的程序

4

1 回答 1

0

如果您关心内存，您将希望尽可能多地进行流式传输。

请参阅http://docs.oracle.com/javase/6/docs/api/java/io/StreamTokenizer.html

StreamTokenizer tokenizer = new StreamTokenizer(new InputStreamReader(System.in));

while(tokenizer.nextToken() != StreamTokenizer.TT_EOF){

    if(tokenizer.ttype == StreamTokenizer.TT_WORD) {
        // found a word.
        System.out.println(tokenizer.sval);
    }
}

当然，如果内存不是问题并且速度是您唯一关心的问题，Hadoop 有一个出色的字数统计示例：http ://wiki.apache.org/hadoop/WordCount 。但是把它留到下雨天的学习。

此外，您计算单词的逻辑也不适合效率（其O(N)）。@DaveNewton 是正确的，您可能应该使用 aMap<String,Integer>这会给您O(1)而不是您的RecString. 我不会纠正你对此的看法，因为我认为这是一个很好的练习。

于 2013-04-14T14:57:18.643 回答