Google-Hash-Code-2017---Hash-Bros-Melee/Cache.java at master · KristianBerg/Google-Hash-Code-2017---Hash-Bros-Melee · GitHub

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import java.util.ArrayList;
import java.util.Arrays;

public class Cache {
	int cap, remaining;
	ArrayList<Endpoint> endpoints;
	int[] videoSizes;
	ArrayList<Integer> storedVideos;
	static int nextId = 0;
	int id = 0;

	public Cache(int cap, int[] videoSizes) {
		endpoints = new ArrayList<>();
		this.cap = cap;
		remaining = cap;
		this.videoSizes = videoSizes;
		storedVideos = new ArrayList<>();
		id = nextId;
		nextId++;
	}

	public boolean addVideo(int id) {
		if (videoSizes[id] < remaining) {
			remaining -= videoSizes[id];
			storedVideos.add(id);
			return true;
		}
		return false;
	}

    public ArrayList<Integer> getVideos() {
      return storedVideos;
    }
	public void calcuteMostPopularVideos() {
		int[] requestSum = new int[videoSizes.length];
		for (Endpoint p : endpoints)
			for (int i = 0; i < p.requests.length; ++i)
				requestSum[i] += p.requests[i];
		for(int i = 0; i < videoSizes.length; i++){
			int best = 0;
			for(int k = 0; k < videoSizes.length; k++){
				if(requestSum[k] > requestSum[best]){
					best = k;
				}
			}
			if(!addVideo(best)){
				break;
			}
			requestSum[best] = 0;
		}
	}

	public void calcuteMostPopularVideos2() {
		int[] requestSum = new int[videoSizes.length];
		for (Endpoint p : endpoints)
			for (int i = 0; i < p.requests.length; ++i)
				requestSum[i] += p.requests[i];

		for(int i = 0; i < videoSizes.length; i++){
			int best = 0;
			for(int k = 0; k < videoSizes.length; k++){
				if(requestSum[k] > requestSum[best]){
					best = k;
				}
			}
			if(!addVideo(best)){
				break;
			} else {
				requestSum[best] = 0;
				for(Endpoint e: endpoints){
					e.requests[best] = 0;
				}
			}
		}
	}

	public void calcuteMostPopularVideos3() {
		double[] requestSum = new double[videoSizes.length];
		for (Endpoint p : endpoints)
			for (int i = 0; i < p.requests.length; ++i)
				if (p.cachelatency[id] != 0)
					requestSum[i] += p.requests[i]*Math.pow(p.datalatency - p.cachelatency[id], 0.775)/videoSizes[i];

        ArrayIndexComparator comparator = new ArrayIndexComparator(requestSum);
        Integer[] indexes = comparator.createIndexArray();
        Arrays.sort(indexes, comparator);
        for (int i = indexes.length - 1; i >= 0; --i) {
          int currBest = indexes[i];
          if (addVideo(currBest)){
            for (Endpoint e: endpoints){
              e.requests[currBest] = 0;
            }
          }
        }
		//for(int i = 0; i < videoSizes.length; i++){
		//	int best = 0;
		//	for(int k = 0; k < videoSizes.length; k++){
		//		if(requestSum[k] > requestSum[best]){
		//			best = k;
		//		}
		//	}
		//	if(!addVideo(best)){
        //        requestSum[best] = 0;
		//	} else {
		//		requestSum[best] = 0;
		//		for(Endpoint e: endpoints){
		//			e.requests[best] = 0;
		//		}
		//	}
		//}
	}
}