public
Last active

Beust Challenge - Sliding window map

  • Download Gist
SlidingWindowMap.java
Java
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
package com.mainaud.slidingwindow;
 
import java.util.Set;
 
public class SlidingWindowMap {
private long periodMs;
private SlidingWindow[] keyWindow;
 
public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs) {
keyWindow = new SlidingWindow[keys.size()];
int i = 0;
for (String key : keys) {
keyWindow[i++] = new SlidingWindow(key, maxCount);
}
}
 
public String getNextKey() {
String key = null;
// Change i initialization to change key usage distribution
for (int i = 0; key == null && i < keyWindow.length; ++i) {
key = keyWindow[i].getKey(periodMs);
}
return key;
}
 
/*
* Keep the last maxCount usage timestamp and test the oldest one. Use an array as a round buffer because it is easy an
* efficient.
*/
private static class SlidingWindow {
private final String key;
private final long[] timestamp;
private int next;
 
SlidingWindow(String key, int maxCount) {
this.key = key;
this.timestamp = new long[maxCount];
/*
* works when periodMs < currentTimestamp. if paranoid uncomment next line:
*/
// java.util.Arrays.fill(timestamp, Long.MIN_VALUE);
}
 
synchronized String getKey(long periodMs) {
long now = System.currentTimeMillis();
if (now > timestamp[next] + periodMs) {
timestamp[next] = now;
next = (next + 1) % timestamp.length;
return key;
} else {
return null;
}
}
}
}

Many thanks for this, it's really helpful. However, what does 'String key' represent (e.g. line 31)? I can't work it out from your code?

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.