-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRandomSurfer.java
More file actions
50 lines (41 loc) · 1.69 KB
/
Copy pathRandomSurfer.java
File metadata and controls
50 lines (41 loc) · 1.69 KB
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
/*************************************************************************
* Compilation: javac RandomSurfer.java
* Execution: java RandomSurfer T
* Data files: http://introcs.cs.princeton.edu/16pagerank/tiny.txt
* http://introcs.cs.princeton.edu/16pagerank/medium.txt
*
* % java Transition < tiny.txt | java RandomSurfer 1000000
* 0.27297 0.26583 0.14598 0.24729 0.06793
*
*************************************************************************/
public class RandomSurfer {
public static void main(String[] args) {
int T = Integer.parseInt(args[0]); // number of moves
int M = StdIn.readInt(); // number of pages - ignore since M = N
int N = StdIn.readInt(); // number of pages
// Read transition matrix.
double[][] p = new double[N][N]; // p[i][j] = prob. that surfer moves from page i to page j
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
p[i][j] = StdIn.readDouble();
int[] freq = new int[N]; // freq[i] = # times surfer hits page i
// Start at page 0.
int page = 0;
for (int t = 0; t < T; t++) {
// Make one random move.
double r = Math.random();
double sum = 0.0;
for (int j = 0; j < N; j++) {
// Find interval containing r.
sum += p[page][j];
if (r < sum) { page = j; break; }
}
freq[page]++;
}
// Print page ranks.
for (int i = 0; i < N; i++) {
StdOut.printf("%8.5f", (double) freq[i] / T);
}
StdOut.println();
}
}