滑动窗口计数的java实现-循环数组
一、用循环数组实现滑动窗口
1.1、实现思想
文章图片
1.定义一个AtomicInteger array数组,每一个元素记录当前区间的计数
2.定义一个long数组 times,记录对应array下标元素开始的时间.
3.定义一个下标int index 记录当前正在使用的位置.
4.定义每个元素的时间区间大小span = 200 ms
index变化情况如下:
1、如果当前时间now - times[index]>span 说明当前请求计数应当位于下一个位置的元素.
index++,
如果index>=size(当前数组大小),则index=0;
2、如果now-times[index]大于传入的计数时间 如1s,则说明,该时间元素无效,重置:
times[index]=now;
array[index].set(0);
1.2、计数逻辑
1.加锁控制
2.按照上面index逻辑更新index,和对应array和times数组里面的元素信息
1.3、获取当前1s内数量
如果get方法加锁,则会影响滑动窗口性能,所以该方法不加锁,得到的值是一个近似精确的值.
实现逻辑:
【滑动窗口计数的java实现-循环数组】1.获取到当前下标curIndex
2.设定循环次数: time = seconds(滑动窗口统计时间) * 1000 /span
3、开始循环,递减curIndex累加当前array对应的值,
判断条件
1.当前index 对应的times[index] 符合now-times[index]
2、不超过time次循环
二、代码实现
链接:
数组实现
import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;
public class ArraySideWindow {
private final AtomicInteger[] array ;
private final long[] times;
private final int span=200;
private final int size ;
private final int delta = 5;
private final int MILL=1000;
private final int second;
private volatile int index;
private ReentrantLock lock;
public ArraySideWindow(int second){
this.second = second;
this.size=second* MILL / span + delta;
this.array = new AtomicInteger[size];
this.times = new long[size];
this.index=0;
for(int i=0;
ispan){
index++;
index=index=second * MILL){
times[index]=now;
this.array[index].set(0);
}
this.array[index].incrementAndGet();
//测试打印 忽略
printNum(this.array);
}catch (Exception e){}finally {
lock.unlock();
}
}public int get(){
intcurIndex = index;
long now = System.currentTimeMillis();
int count=0;
int sum=0;
while (count<5){
if(now-times[curIndex]>=second * MILL){
break;
}
sum +=array[curIndex--].get();
if(curIndex<0){
curIndex=size-1;
}
count++;
}
return sum;
}/**
* 测试代码
* @param array
*/
private synchronized void printNum(AtomicInteger[] array) {
Random random = new Random();
int r = random.nextInt(10);
if(r>=3){
return;
}
StringBuilder numBuilder = new StringBuilder();
StringBuilder timeBuilder = new StringBuilder();
for(int i=0;
i{
int time = 0;
while (time<100000){
int sumNow = sum.get();
if(sumNow>10000){
System.out.println("**************************************************");
try {
TimeUnit.MILLISECONDS.sleep(400+random.nextInt(30));
} catch (InterruptedException e) {
e.printStackTrace();
}
}
window.count();
try {
TimeUnit.MILLISECONDS.sleep(2+random.nextInt(30));
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Thread:"+Thread.currentThread().getName()+",num:"+window.get());
sum.incrementAndGet();
}
},"thread_"+i);
t.start();
}
try {
TimeUnit.SECONDS.sleep(100000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
推荐阅读
- 幻想的死亡
- SourceTree|SourceTree 教程文档（了解界面）
- 十二种排序（冒泡、插入、归并、快速排序等包含希尔和计数排序）
- android仿抖音上下切换视频|android仿抖音上下切换视频,仿抖音上下滑动切换视频
- cocos2dx下的滑动选择效果
- 【golang】leetcode初级-Fizz|【golang】leetcode初级-Fizz Buzz&计数质数
- 基于Vue实现的侧边栏导航组件,自动居中,上下滑动切换菜单
- [Golang]力扣Leetcode—初级算法—数学—计数质数（厄拉多塞筛法）
- WGCLOUD如何实现隐藏窗口运行和开机启动（windows版本）
- JavaCV的摄像头实战之二（本地窗口预览）