Mlog2-统计词频

Author Avatar
Emily Chen 7月 03, 2019

2019-4-8

文章目录：

  1. 题目要求–分析
  2. 具体实现–动手
  3. 源码分析–知其然，知其所以然
  4. 优化–创新
  5. 总结

1. 题目要求–分析

写一个脚本以统计一个文本文件 words.txt 中每个单词出现的频率。
为了简单起见，你可以假设：
words.txt只包括小写字母和 ‘ ‘ ;
每个单词只由小写字母组成。
单词间由一个或多个空格字符分隔。
示例:
假设 words.txt 内容如下：
the day is sunny the the the sunny is is
你的脚本应当输出（以词频降序排列）：
the 4
is 3
sunny 2
day 1

2. 具体实现–动手

1.输入，读取文件，使用 FileInputStream、BufferedReader读取文件；
2.分割字符串，采用StringTokenizer进行字符分割；
3.用 HashMap 保存统计数据；
4.统计词频，降序排序输出，采用Comparator用来实现按value排序
5.输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package algorithm;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class WordFrequency {
	
	public static void main(String[] args) {
		
		long startTime=System.nanoTime();   //获取开始时间
		
		String string = "";
		Map<String, Integer> map = new HashMap<String,Integer>();
		try {
			//[1] 读取 2.txt 文本
			FileInputStream fis = new FileInputStream("/Users/sweetgirl/Documents/MyCode/2.txt");
			BufferedReader br = new BufferedReader(new InputStreamReader(fis));
			String temp = "";
			try {
				while((temp = br.readLine()) != null) {
					string = string + temp;
				}
			} catch (IOException e) {
				// TODO: handle exception
				e.printStackTrace();
			}
			
		} catch (Exception e) {
			// TODO: handle exception
			e.printStackTrace();
		}
		
		//[2] 分割字符串
		StringTokenizer st = new StringTokenizer(string); //用于切分字符串
		int count;
		String word;
		while(st.hasMoreTokens()) {
			 word = st.nextToken(",?.!:\"\"' '\n");
			 if (map.containsKey(word)) {
				//[3] HashMap 保存数据
				 count = map.get(word);
				 map.put(word, count + 1);
				
			}else {
				map.put(word, 1);
			}
			}
		
		 //[4] 排序
		Comparator<Map.Entry<String, Integer>> valueComparator = new Comparator<Map.Entry<String,Integer>>() {
		public int compare(Map.Entry<String, Integer> o1,Map.Entry<String, Integer> o2) {
			return o2.getValue()-o1.getValue();
		}
		};
		//[5] 输出结果
		List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String,Integer>>(map.entrySet());
		Collections.sort(list,valueComparator);
		
		System.out.println("---------------------map 按照 value 降序排序----------");
		for(Map.Entry<String, Integer> entry:list) {
			System.out.println(entry.getKey() + ":"+ entry.getValue());
		}
		
		long endTime=System.nanoTime(); //获取结束时间
		System.out.println("程序运行时间： "+(endTime-startTime)+"ns");
		
	}

}

测试文本：

Photo sphere panoramic camera function; keyboard gesture input function; improved lock screen function, including support for desktop pendant and direct opening camera function in lock screen state; expandable notification, allowing users to directly open the application; Gmail mail zoom display; Daydream screen saver Program; the user can zoom in on the entire display three times, and can also rotate and zoom display with two fingers, as well as voice output and gesture mode navigation designed for blind users; support Miracast wireless display sharing function; Google Now is now available Allow users to use Gamail as a new source of data, such as improved flight tracking, hotel and restaurant reservations, and music and movie recommendations.Photo sphere panoramic camera function; keyboard gesture input function; improved lock screen function, including support for desktop pendant and direct opening camera function in lock screen state; expandable notification, allowing users to directly open the application; Gmail mail zoom display; Daydream screen saver Program; the user can zoom in on the entire display three times, and can also rotate and zoom display with two fingers, as well as voice output and gesture mode navigation designed for blind users; support Miracast wireless display sharing function.

测试结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
---------------------map 按照 value 降序排序----------
and:11
screen:6
as:6
display:6
zoom:6
the:6
function:5
function;:5
lock:4
in:4
support:4
for:4
gesture:4
can:4
camera:4
improved:3
users:3
to:3
voice:2
rotate:2
mail:2
state;:2
panoramic:2
Photo:2
entire:2
fingers:2
three:2
output:2
mode:2
notification:2
navigation:2
saver:2
users;:2
directly:2
Miracast:2
including:2
sharing:2
input:2
application;:2
Daydream:2
blind:2
display;:2
expandable:2
direct:2
pendant:2
two:2
times:2
desktop:2
sphere:2
designed:2
on:2
keyboard:2
Gmail:2
also:2
allowing:2
opening:2
with:2
Program;:2
well:2
wireless:2
user:2
open:2
Gamail:1
data:1
movie:1
use:1
available:1
source:1
tracking:1
recommendations:1
music:1
Google:1
new:1
is:1
Now:1
flight:1
now:1
of:1
hotel:1
a:1
restaurant:1
Allow:1
such:1
reservations:1
程序运行时间： 13034950ns

###3. 源码分析–知其然，知其所以然

Hashmap [1] 存值

1
2
3
4
5
6
1  public static void main(String[] args) {
2 
3          HashMap<String, Integer> map=new HashMap<>();
4          System.out.println(map.put("1", 1));//null
5          System.out.println(map.put("1", 2));//1
6      }

Hashmap [2] 取值

1
2
3
4
5
6
1 public static void main(String[] args) {
2         HashMap<String, Integer> map=new HashMap<>();
3         map.put("DEMO", 1);
4         System.out.println(map.get("1"));//null
5         System.out.println(map.get("DEMO"));//1
6     }

2019-04-16

4. 优化–创新

分割字符串 方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package algorithm;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;


public class WordFrequency {
	
	public static void main(String[] args) {
		
		long startTime=System.nanoTime();   //获取开始时间
		
		String string = "";
		Map<String, Integer> map = new HashMap<String,Integer>();
		try {
			//[1] 读取 2.txt 文本
			FileInputStream fis = new FileInputStream("/Users/sweetgirl/Documents/MyCode/2.txt");
			BufferedReader br = new BufferedReader(new InputStreamReader(fis));
			String temp = "";
			try {
				while((temp = br.readLine()) != null) {
					string = string + temp;
				}
			} catch (IOException e) {
				// TODO: handle exception
				e.printStackTrace();
			}
			
		} catch (Exception e) {
			// TODO: handle exception
			e.printStackTrace();
		}

		//[2] 分割字符串
		
		 String[] spit = string.split(" ");
		 for(int i = 0; i < spit.length; i++) {
			if (map.get(spit[i]) == null) {
				map.put(spit[i], 1);
			}else {
				//[3] HashMap 保存数据
				int frequency = map.get(spit[i]);
				map.put(spit[i], ++frequency);
			}
		}
		
		 //[4] 排序
		Comparator<Map.Entry<String, Integer>> valueComparator = new Comparator<Map.Entry<String,Integer>>() {
		public int compare(Map.Entry<String, Integer> o1,Map.Entry<String, Integer> o2) {
			return o2.getValue()-o1.getValue();
		}
		};
		
		List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String,Integer>>(map.entrySet());
		Collections.sort(list,valueComparator);
		
		System.out.println("---------------------map 按照 value 降序排序----------");
		for(Map.Entry<String, Integer> entry:list) {
			System.out.println(entry.getKey() + ":"+ entry.getValue());
		}
		
		long endTime=System.nanoTime(); //获取结束时间
		System.out.println("程序运行时间： "+(endTime-startTime)+"ns");
		
	}


}

测试文本：

同上

测试结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
---------------------map 按照 value 降序排序----------
and:11
screen:6
as:6
display:6
zoom:6
the:6
function;:5
lock:4
in:4
support:4
for:4
gesture:4
can:4
camera:4
improved:3
users:3
to:3
voice:2
rotate:2
mail:2
state;:2
panoramic:2
entire:2
three:2
output:2
mode:2
navigation:2
function:2
saver:2
users;:2
directly:2
Miracast:2
including:2
sharing:2
input:2
application;:2
Daydream:2
blind:2
display;:2
expandable:2
direct:2
times,:2
function,:2
pendant:2
two:2
desktop:2
sphere:2
designed:2
on:2
keyboard:2
Gmail:2
also:2
allowing:2
opening:2
with:2
fingers,:2
notification,:2
Program;:2
well:2
wireless:2
user:2
open:2
Gamail:1
movie:1
use:1
available:1
Photo:1
source:1
music:1
Google:1
new:1
is:1
Now:1
flight:1
function.:1
now:1
of:1
hotel:1
tracking,:1
a:1
recommendations.Photo:1
restaurant:1
data,:1
Allow:1
such:1
reservations,:1
程序运行时间： 9878808ns

5. 总结

当文本为 1 KB 时，方法一 （使用 StringTokenizer ）程序运行时间： 13034950ns；方法二 （使用 spit ）程序运行时间： 9878808ns .

StringTokenizer > spit

当文本为 24 KB 时，方法一 （使用 StringTokenizer ）程序运行时间： 25411294ns；方法二 （使用 spit ）程序运行时间： 28782200ns .

StringTokenizer < spit

综上可知，当你需要统计词频的文本较大时，例如一本长篇小说，那么 StringTokenizer 的效率更高。