关于java:滑动窗口计数的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 办法加锁, 则会影响滑动窗口性能, 所以该办法不加锁, 失去的值是一个近似准确的值.

实现逻辑:

1. 获取到以后下标 curIndex

2. 设定循环次数: time = seconds(滑动窗口统计工夫) * 1000 /span

3、开始循环, 递加 curIndex 累加以后 array 对应的值,

判断条件

1. 以后 index 对应的 times[index] 合乎 now-times[index]<seconds *1000, 因为如果大于就认为超过该 seconds 统计区间

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;i<size;i++){this.array[i]=new AtomicInteger(0);
        }
        this.times[index]=System.currentTimeMillis();
        this.lock = new ReentrantLock(false);
    }

    public void count(){long now = System.currentTimeMillis();
        lock.lock();
        try{if(now-times[index]>span){
                index++;
                index=index<size?index:0;
            }
            if(now-times[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(){
        int  curIndex = 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<array.length;i++){numBuilder.append(array[i].get()).append(",");
            timeBuilder.append(times[i]).append(",");
        }
        System.out.println("-----------------------------------------");
        int preIndex = index-1<0?size-1: index-1;
        System.out.println("now:"+System.currentTimeMillis()+",curIndex:"+index+",preIndex:"+preIndex);
        System.out.println("indexTime:"+times[index]+",preIndexTime:"+times[preIndex]+",dif:"+(times[index]-times[preIndex]));

        System.out.println("Thread:"+Thread.currentThread().getName());
        System.out.println(numBuilder.toString());
        System.out.println(timeBuilder.toString());
        System.out.println("-----------------------------------------");

    }


    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {ArraySideWindow window = new ArraySideWindow(1);
        AtomicInteger sum =new AtomicInteger(0);
        Random random = new Random(10);
        for(int i=0;i<30;i++){Thread t = new Thread(()->{
                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();
        }
    }
}