Java статистика по словам в длинной строке

Question

Я пишу программу в java, чтобы получить статистику по словам в очень большой строке (строка s < = 100000). Это займет менее 1 секунды и использует менее 16 МБ памяти.

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 Но для больших строк у меня есть время или/и ограничение памяти.

Помоги мне, пожалуйста, чтобы оптимизировать свою программу

Answer 1

Если обеспокоенный с памятью вы хотите, чтобы попытаться поток настолько, насколько это возможно.

См 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 прав, что вы, вероятно, должны использовать Map<String,Integer>, который даст вам O(1), а не ваш массив RecString. Я не собираюсь исправлять вашу музыку на этом, так как я думаю, что это хорошее упражнение.