精华内容
下载资源
问答
  • 参考链接: 用Python进行存储Bucket Sort排序 Couting Sort 计数排序虽然快,但其只能对整数进行排序有一点的局限性。而 Bucket Sort 排序则没有这个限制。这里我们就来详细介绍该算法,其一般在排序元素的值...

    参考链接: 用Python进行存储桶Bucket Sort排序

    Couting Sort 计数排序虽然快,但其只能对整数进行排序有一点的局限性。而 Bucket Sort 桶排序则没有这个限制。这里我们就来详细介绍该算法,其一般在排序元素的值基本处于均匀分布的场景下应用

      

      算法思想

      在Bucket Sort 桶排序中,我们首先需要设置k个桶用于存储排序元素。先根据映射函数将各排序元素依次放置到合适的桶中,最后对各个桶内的元素进行桶内排序;由于各桶之间是有序的,故遍历各个桶将桶内的有序序列直接拼接起来即可

      Note:

      对桶内元素进行排序时,排序算法不限,但桶内排序算法的稳定性将会直接决定Bucket Sort桶排序的稳定性

      设计与实现

      桶数、映射函数

      在桶排序中,最理想的情况就是每个桶中只被分配一个元素,这样就可以直接避免桶内排序这一步;最坏的情况就是所有元素全部分配到一个桶中,此时桶排序就会完全退化为一个桶内排序,所以排序元素能否均匀地分配到各个桶中将会直接影响桶排序的性能,故一般当排序元素的值基本为均匀分布时才会应用该算法进行排序。对于桶排序算法而言,最重要的就是桶数与映射函数的设计,其同样会影响桶排序的性能,这里我们来介绍一种均匀分配的设计方案

      对于N个元素而言,令其取值范围为 gap(即 elementMaxValue-elementMinValue),易知其可构成 N-1 个区间长度 length 为 gap/(N-1) 的左闭右开区间。由于是左闭右开区间,会使得最后一个区间的右端点无法取到,即排序元素中的最大值elementMaxValue无法被cover,故我们又在后面增加了一个同样长度的区间。如下图所示

      

      

       

      

      至此,我们就将排序元素划分为了N个区间(如上图所示,区间从0开始编号),而对于某个排序元素所属区间的编号 intervalNumber 可通过下式计算获得:

      intervalNumber = floor(  (elementValue - elementMinValue) / length  )

      聪明的朋友可能已经看出来了,这里的区间实际上就是桶排序所需要的桶,而上式计算区间编号的公式即是我们所需的映射函数。在均匀分配的设计方案下,我们会使用N个桶,然后通过上式来计算各排序元素应该在放到哪个桶中。下图所示的结果,每个桶恰好只分配到了一个元素。实际上,一个桶可能会被分配多个元素,所以对于桶内元素一般采用链表进行存储

      

      实现

      我们通过Java来实现桶排序,使大家更好地理解该算法。这里对于桶内排序,我们使用的插入排序

        1/**  2 * 桶排序  3 */  4public class BucketSort {  5    /**  6     * 升序排列  7     */  8    public static void sort() {  9        // 获取测试用例 10        double[] array = getTestCase(); 11 12        System.out.println("before sort: " + Arrays.toString(array) ); 13 14        if( array.length>1 ) {      // 数组大小大于1,则使用Bucket Sort 15            bucketSort(array); 16        } 17 18        System.out.println("after sort: " + Arrays.toString(array) ); 19    } 20 21    private static void bucketSort(double[] array) { 22        // 创建k个桶及桶中的列表 23        int k = array.length; 24        ArrayList> buckets = new ArrayList<>(k); 25        for(int i=0; i 26            buckets.add(new ArrayList<>()); 27        } 28 29        // 求取最值 30        double[] minMax = getMinMax(array); 31        double min = minMax[0]; 32        double max = minMax[1]; 33        double gap = max - min;     // 待排序元素的数据范围长度,即极差 34        double bucketLength = gap / (k-1);   // 桶的区间长度 35 36        // 根据映射函数 f=(element - min)/bucketLength 将待排序元素分配到各个桶中 37        for(double element : array) { 38            int bucketIndex = (int)Math.floor( (element - min)/bucketLength );  //计算该排序元素所属的桶号 39            ArrayList listInBucket = buckets.get(bucketIndex);  // 获取相应桶的列表 40            listInBucket.add(element);  // 向相应桶的列表中添加元素 41        } 42 43        // 遍历所有桶进行桶内排序 44        for(ArrayList listInBucket : buckets) { 45            if( listInBucket.size()<=1 ) { 46                continue;   // 该桶内不超过1个元素,故无需排序 47            } 48            insertSort( listInBucket ); 49        } 50        // 拼接各个桶内的有序序列 51        int index = 0; 52        for(ArrayList listInBucket : buckets) { 53            if( listInBucket==null ) { 54                continue; 55            } 56            for(Double element : listInBucket) { 57                array[index] = element; 58                index++; 59            } 60        } 61    } 62 63    /** 64     * 求指定数组的最值 65     * @param array 66     * @return [0]: 最小值; [1]: 最大值; 67     */ 68    private static double[] getMinMax(double[] array) { 69        double min = Double.MAX_VALUE; 70        double max = Double.MIN_VALUE; 71        for(double element: array) { 72            min = Double.min(element, min); 73            max = Double.max(element, max); 74        } 75        double[] minMax = new double[]{min,max}; 76        return minMax; 77    } 78 79    /** 80     * 插入排序(升序排列) 81     * @param list 82     */ 83    private static void insertSort(ArrayList list) { 84        int size = list.size(); 85        for(int i=1; i 86            double element = list.get(i);  // 待插入元素 87            int j = i-1; 88            for(; j>=0 && list.get(j)>element; j--) { 89                list.set(j+1, list.get(j)); 90            } 91            list.set(j+1, element);    // 插入元素 92        } 93    } 94 95    /** 96     * 获取测试用例 97     */ 98    private static double[] getTestCase() { 99        double[] caseArray = {-1.2, 1.1, 4.3, 6.32, 8.35, 1.2, 4.4, 6.51};100        return caseArray;101    }102}

      测试结果如下:

      

      特点

      空间复杂度

      由于需要分配k个桶,且k个桶一共存储了N个元素,故其空间复杂度为 O(N + k)

      时间复杂度

      1. 最坏的情况

      当N个排序元素全部被分配到一个桶中,此时桶排序算法即退化为对该桶的N个元素的全排序,这时,其时间复杂度将取决于桶内算法。如果桶内排序使用的为插入排序,则其复杂度为平方时间;如果桶内排序使用的为快速排序,则其复杂度为线性对数时间

      2. 最好的情况

      当每个桶中的被分配到的元素最多不超过1个时,其复杂度为线性时间

      3.平均的情况

      当桶内排序为平方时间复杂度的插入排序,其桶排序在平均情况下的时间复杂度为O(N+k+N*N/k)

      稳定性

      如上文所述,桶排序的稳定性取决于桶内排序所使用排序算法的稳定性。本文使用插入排序进行桶内排序,故其稳定;如若在桶内使用不稳定的快速排序,此时桶排序即为不稳定的

      其它

      桶排序虽然没有计数排序所要求的排序元素必须为整数的限制,但其一般也只用于排序元素基本为均匀分布的场景,否则桶排序会发生退化,致使算法效率严重下降该算法的桶数、映射函数设计的好坏会极大程度地影响算法性能空间复杂度较高,属于典型地用空间换时间的策略

      参考文献

      算法导论 · 第3版

    展开全文
  • 令牌桶算法是网络流量整形(Traffic Shaping)速率限制(Rate Limiting)中最常使用的一种算法。 代码 #!/usr/bin/env python # coding:utf-8 """ @Name: tokenBucket.py @Au...

    Why 令牌桶?

    典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。

    What 令牌桶?

    令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。

    代码

    
    #!/usr/bin/env python
    # coding:utf-8
    
    """
    @Name: tokenBucket.py
    @Author: lvah
    @Date:2018-04-10
    @Connect: xc_guofan@163.com
    @Desc:
    
    
    
    
    """
    
    import time
    
    
    class TokenBucket(object):
        """
        令牌桶:
            在网络中传输数据时, 为了防止网络拥塞, 需要限制流出网络的流量,
            使流量以比较均匀的速度向外发送;
    
        令牌桶算法:
            控制发送到网络上数据的数, 并允许突发数据的发送;
    
    
    
        令牌桶思路:
            我们用1块令牌来代表发送1字节数据的资格,假设我们源源不断的发放令牌给程序,程序就有资格源源不断的发送数据,
            当我们不发放令牌给程序,程序就相当于被限流,无法发送数据了。
    
            接下来我们说说限速器,所谓限速器,就是让程序在单位时间内,最多只能发送一定大小的数据。假设在1秒发放10块令牌,
            那么程序发送数据的速度就会被限制在10bytes/s。如果1秒内有大于10bytes的数据需要发送,就会因为没有令牌而被丢弃。
    
    
            限速器改进:
                1秒产生10块令牌,但是我们把产生出来的令牌先放到一个桶里,当程序需要发送的时候,从桶里取令牌,不需要的时候,
                令牌就会在桶里沉淀下来,
        """
    
        # rate是令牌发放速度, capacity是桶的大小;
        def __init__(self, rate, capacity):
            self._rate = rate
            self._capacity = capacity
            self._current_amount = 0
            self._last_consume_time = int(time.time())
    
        # token_amount是发送数据需要的令牌数;
        def consume(self, token_amount):
            # 计算令牌桶中令牌的数量:(now_time-last_time)*speed, 从而避免程序阻塞;
            increment = (int(time.time() - self._last_consume_time))
            # 令牌容量不能超过桶容量;
            self._current_amount = min(
                increment + self._current_amount, self._capacity)
    
            if token_amount > self._current_amount:
                return  False
    
            self._last_consume_time = int(time.time())
            self._current_amount -= token_amount
    
    
    

    参考资料

    令牌桶算法百度百科

    展开全文
  • 主要介绍了15行Python代码带你轻松理解令牌桶算法,需要的朋友可以参考下
  • python令牌桶算法

    2019-10-02 19:50:17
    import time class TokenBucket(object): ... # rate是令牌发放速度,capacity是的大小 def __init__(self, rate, capacity): self._rate = rate self._capacity = capacity se...
    import time
    
    
    class TokenBucket(object):
    
        # rate是令牌发放速度,capacity是桶的大小
        def __init__(self, rate, capacity):
            self._rate = rate
            self._capacity = capacity
            self._current_amount = 0
            self._last_consume_time = int(time.time())
    
        # token_amount是发送数据需要的令牌数
        def consume(self, token_amount):
            increment = (int(time.time()) - self._last_consume_time) * self._rate  # 计算从上次发送到这次发送,新发放的令牌数量
            self._current_amount = min(
                increment + self._current_amount, self._capacity)  # 令牌数量不能超过桶的容量
            if token_amount > self._current_amount:  # 如果没有足够的令牌,则不能发送数据
                return False
            self._last_consume_time = int(time.time())
            self._current_amount -= token_amount
            return True
    
    作者:simpleapples
    链接:https://juejin.im/post/5ab10045518825557005db65
    来源:掘金
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    

      

    转载于:https://www.cnblogs.com/c-x-a/p/9932573.html

    展开全文
  • 2019独角兽企业重金招聘Python工程师标准>>> ...

    漏桶算法

    漏桶可以看作是一个带有常量服务时间的单服务器队列,如果漏桶(包缓存)溢出,那么数据包会被丢弃。这一点和线程池原理是很相似的。

    把请求比作是水,水来了都先放进桶里,并以限定的速度出水,当水来得过猛而出水不够快时就会导致水直接溢出,即拒绝服务。

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

    令牌桶算法

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

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

    单机限流

    Google的Guava包中的RateLimiter类就是令牌桶算法的解决方案。 首先说下单机限流

    package yzy.guava.test;
    
    import com.google.common.base.Optional;
    import com.google.common.util.concurrent.RateLimiter;
    
    import java.nio.channels.ServerSocketChannel;
    
    public class OptionalTest {
        public void guava()
        {
            //guava
            Optional<Integer> possible = Optional.of(6);
            if(possible.isPresent())
            {
                System.out.println("possible isPresent:" +
                        possible.isPresent());
                System.out.println("possible value:" + possible.get());
                ServerSocketChannel s =null;
            }
        }
    
        public static void main(String[] args) throws InterruptedException {
            OptionalTest hello = new OptionalTest();
            hello.guava();
    
    
            RateLimiter limiter = RateLimiter.create(1);//限制qps最大为1
            System.out.println(limiter.acquire()); //输出阻塞的时间
    
            Thread.sleep(2000);
            System.out.println(limiter.acquire() + " " + System.currentTimeMillis() / 1000 );
    
            System.out.println(limiter.acquire() + " " + System.currentTimeMillis() / 1000);
    
            System.out.println(limiter.acquire() + " " + System.currentTimeMillis() / 1000);
    
    
    
            System.out.println(limiter.acquire() + " " + System.currentTimeMillis() / 1000);
            System.out.println(limiter.acquire() + " " + System.currentTimeMillis() / 1000);
    
            System.out.println(limiter.acquire() + " " + System.currentTimeMillis() / 1000);
    
        }
    }
    

    分布式限流

    基于Redis的分布式限流器可以用来在分布式环境下现在请求方的调用频率。既适用于不同Redisson实例下的多线程限流,也适用于相同Redisson实例下的多线程限流。该算法不保证公平性。

    RRateLimiter rateLimiter = redisson.getRateLimiter("myRateLimiter");
    // 初始化
    // 最大流速 = 每1秒钟产生10个令牌
    rateLimiter.trySetRate(RateType.OVERALL, 10, 1, RateIntervalUnit.SECONDS);
    
    // 获取4个令牌
    rateLimiter.tryAcquire(4);
    
    // 尝试获取4个令牌,尝试等待时间为2秒钟
    rateLimiter.tryAcquire(4, 2, TimeUnit.SECONDS);
    
    rateLimiter.tryAcquireAsync(2, 2, TimeUnit.SECONDS);
    
    // 尝试获取1个令牌,等待时间不限
    rateLimiter.acquire();
    
    // 尝试获取1个令牌,等待时间不限
    RFuture<Void> future = rateLimiter.acquireAsync();
    

    转载于:https://my.oschina.net/u/4129361/blog/3053350

    展开全文
  • 桶算法和令牌桶算法

    千次阅读 2018-06-19 10:53:35
    令牌桶算法(Token Bucket) Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象漏洞漏水相反,有个水龙头在不断的加水)...
  • TokenBucket(令牌桶算法) LeakBucket(桶算法) 两种限流算法
  • 在前文 《限流熔断是什么,怎么做,不做行不行?》中针对 “限流” 动作,有提到流量控制其内部对应着两种常用的限流算法。其分别对应桶算法和令牌桶算法。因此会有的读者会好奇,这都是些啥?为...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 在网络中传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送,令牌桶算法就实现了这个功能,可控制发送到网络上数据的数目,并允许突发数据的发送。 更多Python视频、源码、...
  • 限流算法之桶算法、令牌桶算法

    千次阅读 2013-11-04 01:17:00
    常用的更平滑的限流算法有两种:桶算法和令牌桶算法. 很多传统的服务提供商如华为中兴都有类似的专利,参考:  http://www.google.com/patents/CN1536815A?cl=zh 2.1 桶算法 桶(Leaky Bucket)算法思路很...
  • 在网络中传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送,令牌桶算法就实现了这个功能, 可控制发送到网络上数据的数目,并允许突发数据的发送。 什么是令牌 从名字上看...
  • 基于redis的分布式限流方案 为什么要选用redis: redis效率高,易扩展 ...令牌桶算法 计数器算法容易出现不平滑的情况,瞬间的qps有可能超过系统的承载。因此在实际场景中我们一般很少使用。 令牌..
  • 本文针对第一中情况,利用令牌桶算法实现: 这个方法:https://github.com/kwsy/Flask-TrafficShape,其实实现的是限制单个请求的频率。但是思路可以借鉴,我们需要做的是对请求的内容大小进行...
  • python3 -m pip安装起搏器 用法 from pacemaker import pace_me # Function that will yield data that the process function needs def data_gen(n=3): for i in range(n): yield [x for x in range(n)] # ...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 基于flask和令牌桶算法的api限流接口

    千次阅读 2018-06-08 13:48:15
    可使用次数,访问时间,令牌数 ]} # coding=utf-8 # ****************************************************** from flask_limiter import Limiter from flask_limiter.util import get_remote_address ...
  • 基于桶(Leaky bucket)与令牌桶(Token bucket)算法的流量控制 Congestion Control Algorithm 参考以下文章: http://www.javaranger.com/archives/1769 ...
  • 基于桶(Leaky bucket)与令牌桶(Token bucket)算法的流量控制 常用的流控算法 桶(Leaky bucket)   再看看令牌桶(Token bucket) Guava官方文档-RateLimiter类           桶(Leaky bucket)与...
  • 4.2 令牌桶算法 介绍 令牌桶算法是比较常见的限流算法之一,大概描述如下: 1)所有的请求在处理之前都需要拿到一个可用的令牌才会被处理; 2)根据限流大小,设置按照一定的速率往桶里添加令牌; 3)桶设置最大的...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 限流算法主要有如下几种: 基于信号量Semaphore 只有数量维度,没有时间维度 基于fixed window 带上了时间维度,不过在两个窗口的临界点容易出现超出限流的情况,比如限制每分钟10个请求,在00:59请求了10次,在01:...
  • 下文主要与大家一起分析一下桶算法和令牌桶算法,滑动窗口就不在这里这介绍了。好啦,废话不多话,开整。 桶算法 桶算法比较好理解,假设我们现在有一个水桶,我们向这个水桶里添水,虽然我们我们无法预计一次...
  • 前言Sentinel的QPS流控效果有快速失败、预热模式、排队等待、预热+排队等待模式,本文主要分析预热模式中是如何使用令牌桶算法限流的。一、流控效果源码结构在FlowRule更新缓...
  • 在限流时一般会限制每秒或每分钟的请求数,简单点一般会采用计数器算法,这种算法实现相对简单,也很高效,但是无法应对瞬时的突发流量。比如限流每秒100次请求,绝大多数的时间里都不会超过这个数,...
  • 学习一下令牌桶算法

    2016-12-07 11:20:00
    2019独角兽企业重金招聘Python工程师标准>>> ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 889
精华内容 355
关键字:

令牌桶算法和漏桶算法python

python 订阅