算法设计（贪婪算法、漏桶算法、令牌桶算法、计数器）

浅浅的花香味﹌ 2023-03-03 11:15 26阅读 0赞

> # 一、贪心算法 #

也叫贪婪算法，是指在对问题求解时，总是**做出在当前看来是最好的选择**。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的**局部最优解，最终通过各环节局部最优解促成整体的最优解。**

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。

必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）**所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。**

## 1.1 贪心算法的基本思路 ##

*  建立数学模型来描述问题
 *  把求解的问题分成若干个子问题
 *  对每个子问题求解，得到子问题的局部最优解
 *  把子问题的解局部最优解合成原来问题的一个解

**贪心算法的实现框架：**

> 从问题的某一初始解出发：  
> while (朝给定总目标前进一步)  
> \{  
>        利用可行的决策，求出可行解的一个解元素。  
> \}  
> 由所有解元素组合成问题的一个可行解；

## 1.2 经典例子----**纸币找零问题** ##

假设1元、2元、5元、10元、20元、50元、100元的纸币，张数不限制，现在要用来支付K元，至少要多少张纸币？

我们的总目标是完成找零（所有钱加起来等于要找的钱）且用的张数最少，那肯定是按照最大面子往下查找：

public class GreedyTest {
        public static void giveMoney(int money) {
            System.out.println("需要找零: " + money);
            int[] moneyLevel = {1, 5, 10, 20, 50, 100};
            int i = moneyLevel.length - 1;
            while (i >= 0) {
                int num = money/moneyLevel[i];
                int mod = money%moneyLevel[i];
                money = mod;
    
                if(num > 0){
                    System.out.println("需要" + num + "张" + moneyLevel[i] + "块的");
                }
                i--;
            }
        }
    
        public static void main(String[] args) {
            giveMoney(199);
        }
    }

需要找零: 199
    需要1张100块的
    需要1张50块的
    需要2张20块的
    需要1张5块的
    需要4张1块的

这里贪心算法是每次只找最大面值的，最终使得张数最少。

## 1.3 贪心算法适用的问题 ##

**贪心策略适用的前提是：局部最优策略能导致产生全局最优解。**

实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

比如：【背包问题】有一个背包，容量是M=150，有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品：A   B  C   D  E  F   G  
重量：35 30 60 50 40 10 25  
价值：10 40 30 50 35 40 30

分析：

总目标： ∑pi最大

约束条件是装入的物品总质量不超过背包容量：∑wi<=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？  
（2）每次挑选所占重量最小的物品装入是否能得到最优解？  
（3）每次选取单位重量价值最大的物品，成为解本题的策略

对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：

（上面的物品太多，为了易于观察，我们假设只有ABC三个物品）

**（1）选取价值最大者**

假设最大容量：30

物品：A B C

重量：28 12 12

价值：30 20 20

这里只能选择一个A，价值最大为30，且不超过总重量30；但是如果选择BC，价值就是40，且未超过30。

**（2）选取重量最小**

假设最大容量：30

物品：A B C

重量：28 12 12

价值：30 10 10

这里只能选择一个BC，价值最大为20，且不超过总重量30；但是如果选择A，价值就是30，且未超过30。

**（3）选取单位重量价值最大的物品**

假设最大容量：30

物品：A B C

重量：28 20 10

价值：28 20 10

三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。但是果在条件中加一句当遇见单位价值相同的时候,优先装重量小的,这样的问题就可以解决。

贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。比如，**求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法**。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。  
但是它需要证明后才能真正运用到题目的算法中。

> # 二、漏桶算法 #

漏桶算法说的是，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。桶的容量代表最大并发量，如果桶满了，则请求被丢弃。固定速率流出，随意速率流入，流入代表请求，如果流入速率很快，将桶装满，则溢出的请求被放弃，以达到限流的效果。

## **2.1  漏桶算法的描述如下**： ##

一个固定容量的漏桶，按照常量固定速率流出水滴；  
如果桶是空的，则不需流出水滴；  
可以以任意速率流入水滴到漏桶；  
如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

## **2.2  漏桶算法代码实例** ##

**漏桶类：**

@Data
    public class LeakyBucket {
        // 桶的容量
        private int capacity = 100;
        // 木桶剩余的水滴的量(初始化的时候的空的桶)
        private AtomicInteger water = new AtomicInteger(0);
        // 水滴的流出的速率 每1000毫秒流出1滴
        private int leakRate;
        // 第一次请求之后,木桶在这个时间点开始漏水
        private long leakTimeStamp;
    
        public LeakyBucket(int leakRate) {
            this.leakRate = leakRate;
        }
    
        public boolean acquire() {
            // 如果是空桶，就当前时间作为桶开是漏出的时间
            if (water.get() == 0) {
                leakTimeStamp = System.currentTimeMillis();
                water.addAndGet(1);
                return capacity == 0 ? false : true;
            }
            // 先执行漏水，计算剩余水量
            int waterLeft = water.get() - ((int) ((System.currentTimeMillis() - leakTimeStamp) / 1000)) * leakRate;
            water.set(Math.max(0, waterLeft));
            // 重新更新leakTimeStamp
            leakTimeStamp = System.currentTimeMillis();
            // 尝试加水,并且水还未满
            if ((water.get()) < capacity) {
                water.addAndGet(1);
                return true;
            } else {
                // 水满，拒绝加水
                return false;
            }
        }
    }

实现：

@RestController
    public class Index {
    //漏桶：水滴的漏出速率是每秒 1 滴
        private LeakyBucket leakyBucket = new LeakyBucket(1);
    
        @Autowired
        private OrderService orderService;
    //漏桶限流
        @RequestMapping("/searchCustomerInfoByLeakyBucket")
        public Object searchCustomerInfoByLeakyBucket() {
            // 1.限流判断
            boolean acquire = leakyBucket.acquire();
            if (!acquire) {
                System.out.println("稍后再试！");
                return "稍后再试！";
            }
            // 2.如果没有达到限流的要求,直接调用接口查询
            System.out.println(orderService.searchCustomerInfo());
            return orderService.searchCustomerInfo();
        }

> # 三、令牌桶算法 #

上面的漏桶算法是以固定的速率进行流出的，也就是说处理请求的速率是固定的，能够强行限制数据的传输速率，即使你桶的容量再大，短时间内来了大量的请求也只能按照原来固定的速率去处理。

对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

## 3.1 令牌桶算法原理 ##

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。从原理上看，令牌桶算法和漏桶算法是相反的，一个“进水”，一个是“漏水”。

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIzMTkyOA_size_16_color_FFFFFF_t_70][] ###

*  a. 按特定的速率向令牌桶投放令牌
 *  b. 根据预设的匹配规则先对报文进行分类，不符合匹配规则的报文不需要经过令牌桶的处理，直接发送；
 *  c. 符合匹配规则的报文，则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去，同时令牌桶中的令牌 量按报文的长度做相应的减少；
 *  d. 当令牌桶中的令牌不足时，报文将不能被发送，只有等到桶中生成了新的令牌，报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度，达到限制流量的目的。

实际总结就是：系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务。（*QPS* = req/sec = 请求数/秒，每秒查询率）

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量。

## **3.2  令牌桶算法代码实例** ##

令牌桶类：

public class TokenBucket {
        // 默认桶大小个数 即最大瞬间流量是64M
        private static final int DEFAULT_BUCKET_SIZE = 1024 * 1024 * 64;
        // 一个桶的单位是1字节
        private int everyTokenSize = 1;
        // 瞬间最大流量
        private int maxFlowRate;
        // 平均流量
        private int avgFlowRate;
        // 队列来缓存桶数量：最大的流量峰值就是 = everyTokenSize*DEFAULT_BUCKET_SIZE 64M = 1 * 1024 *
        // 1024 * 64
        private ArrayBlockingQueue<Byte> tokenQueue = new ArrayBlockingQueue<Byte>(
                DEFAULT_BUCKET_SIZE);
    
        private ScheduledExecutorService scheduledExecutorService = Executors
                .newSingleThreadScheduledExecutor();
    
        private volatile boolean isStart = false;
    
        private ReentrantLock lock = new ReentrantLock(true);
    
        private static final byte A_CHAR = 'a';
    
        public TokenBucket() {}
    
        public TokenBucket(int maxFlowRate, int avgFlowRate) {
            this.maxFlowRate = maxFlowRate;
            this.avgFlowRate = avgFlowRate;
        }
    
        public TokenBucket(int everyTokenSize, int maxFlowRate, int avgFlowRate) {
            this.everyTokenSize = everyTokenSize;
            this.maxFlowRate = maxFlowRate;
            this.avgFlowRate = avgFlowRate;
        }
    
        public void addTokens(Integer tokenNum) {
            // 若是桶已经满了，就不再加入新的令牌
            for (int i = 0; i < tokenNum; i++) {
                tokenQueue.offer(Byte.valueOf(A_CHAR));
            }
        }
    
        public TokenBucket build() {
            start();
            return this;
        }
    
        /**
         * 获取足够的令牌个数
         * 
         * @return
         */
        public boolean getTokens(byte[] dataSize) {
            int needTokenNum = dataSize.length / everyTokenSize + 1;// 传输内容大小对应的桶个数
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                boolean result = needTokenNum <= tokenQueue.size(); // 是否存在足够的桶数量
                if (!result) {
                    return false;
                }
                int tokenCount = 0;
                for (int i = 0; i < needTokenNum; i++) {
                    Byte poll = tokenQueue.poll();
                    if (poll != null) {
                        tokenCount++;
                    }
                }
                return tokenCount == needTokenNum;
            } finally {
                lock.unlock();
            }
        }
    
        public void start() {
            // 初始化桶队列大小
            if (maxFlowRate != 0) {
                tokenQueue = new ArrayBlockingQueue<Byte>(maxFlowRate);
            }
            // 初始化令牌生产者
            TokenProducer tokenProducer = new TokenProducer(avgFlowRate, this);
            scheduledExecutorService.scheduleAtFixedRate(tokenProducer, 0, 1,
                    TimeUnit.SECONDS);
            isStart = true;
        }
    
        public void stop() {
            isStart = false;
            scheduledExecutorService.shutdown();
        }
    
        public boolean isStarted() {
            return isStart;
        }

令牌生产者：

class TokenProducer implements Runnable {
            private int avgFlowRate;
            private TokenBucket tokenBucket;
    
            public TokenProducer(int avgFlowRate, TokenBucket tokenBucket) {
                this.avgFlowRate = avgFlowRate;
                this.tokenBucket = tokenBucket;
            }
    
            @Override
            public void run() {
                tokenBucket.addTokens(avgFlowRate);
            }
        }

测试：

private static void tokenTest() throws InterruptedException, IOException {
            TokenBucket tokenBucket = TokenBucket.newBuilder().avgFlowRate(512)
                    .maxFlowRate(1024).build();
    
            BufferedWriter bufferedWriter = new BufferedWriter(
                    new OutputStreamWriter(new FileOutputStream("D:/ds_test")));
            String data = "xxxx";// 四个字节
            for (int i = 1; i <= 1000; i++) {
                Random random = new Random();
                int i1 = random.nextInt(100);
                boolean tokens = tokenBucket.getTokens(tokenBucket.stringCopy(data,
                        i1).getBytes());
                TimeUnit.MILLISECONDS.sleep(100);
                if (tokens) {
                    bufferedWriter.write("token pass --- index:" + i1);
                    System.out.println("token pass --- index:" + i1);
                } else {
                    bufferedWriter.write("token rejuect --- index" + i1);
                    System.out.println("token rejuect --- index" + i1);
                }
                bufferedWriter.newLine();
                bufferedWriter.flush();
            }
            bufferedWriter.close();
        }

public static void main(String[] args) throws IOException,
                InterruptedException {
            tokenTest();
        }

令牌桶算法（Token Bucket）：是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

## 漏桶算法和令牌桶算法的选择 ##

漏桶的出水速度是恒定的，那么意味着如果瞬时大流量的话，将有大部分请求被丢弃掉（也就是所谓的溢出）。

生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。

最后，不论是对于令牌桶拿不到令牌被拒绝，还是漏桶的水满了溢出，都是为了保证大部分流量的正常使用，而牺牲掉了少部分流量，这是合理的，如果因为极少部分流量需要保证的话，那么就可能导致系统达到极限而挂掉，得不偿失。

需要注意的是，在某些情况下，漏桶算法不能够有效地使用网络资源，因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。

> # 四、计数器 #

计数器比较简单粗暴，比如我们要限制1s能够通过的请求数，实现的思路就是从第一个请求进来开始计时，在接下来的1s内，每个请求进来请求数就+1，超过最大请求数的请求会被拒绝，等到1s结束后计数清零，重新开始计数。

这种方式有个很大的弊端：比如前10ms已经通过了最大的请求数，那么后面的990ms的请求只能拒绝，这种现象叫做“突刺现象”。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIzMTkyOA_size_16_color_FFFFFF_t_70]: /images/20230208/ffb38c907d934ca5b493aba4a01397ac.png