精华内容
下载资源
问答
  • 幂等性和雪花算法

    2020-09-06 10:57:53
    文章目录幂等性什么是幂等幂等常用思路1.MVCC2.去重表3.TOKEN机制雪花算法算法原理算法实现 幂等性 数据库设计的时候除了自增id之外,通常我们会加一个code字段,来保证幂等性。 什么是幂等幂等性原本是数学...

    幂等性

    数据库设计的时候除了自增id之外,通常我们会加一个code字段,来保证幂等性。

    什么是幂等性

    幂等性原本是数学上的概念,即使公式:f(x)=f(f(x)) 能够成立的数学性质。用在编程领域,则意为对同一个系统,使用同样的条件,一次请求和重复的多次请求对系统资源的影响是一致的

    例如:

    在某平台支付订单的时候,因为网络或者其它原因会发生重复支付的情况,这时候,要阻止扣款两次情况的出现。

    幂等常用思路

    1.MVCC

    多版本并发控制,乐观锁的一种实现,在数据更新时需要去比较持有数据的版本号,版本号不一致的操作无法成功。

    例如博客点赞次数自动+1的接口:

    public boolean addCount(Long id, Long version);
    
    update blogTable set count= count+1,version=version+1 where id=321 and version=123 
    

    每一个version只有一次执行成功的机会,一旦失败必须重新获取。

    2.去重表

    利用数据库表单的特性来实现幂等,常用的一个思路是在表上构建唯一索引,保证某一类数据一旦执行完毕,后续同样的请求再也无法成功写入。

    例子还是上述的博客点赞问题,要想防止一个人重复点赞,可以设计一张表,将博客id与用户id绑定建立唯一索引,每当用户点赞时就往表中写入一条数据,这样重复点赞的数据就无法写入。

    3.TOKEN机制

    这种机制就比较重要了,适用范围较广,有多种不同的实现方式。其核心思想是为每一次操作生成一个唯一性的凭证,也就是token。一个token在操作的每一个阶段只有一次执行权,一旦执行成功则保存执行结果。对重复的请求,返回同一个结果。

    订单id就是最适合的token。当用户下单时,会经历多个环节,比如生成订单,减库存,减优惠券等等。

    每一个环节执行时都先检测一下该订单id是否已经执行过这一步骤,对未执行的请求,执行操作并缓存结果,而对已经执行过的id,则直接返回之前的执行结果,不做任何操作。这样可以在最大程度上避免操作的重复执行问题,缓存起来的执行结果也能用于事务的控制等。

    雪花算法

    前面说到订单id,这种分布式id的生成算法有很多种,Twitter的SnowFlake就是其中经典的一种。

    算法原理

    SnowFlake算法生成id的结果是一个64bit大小的整数(Long类型),它的结构如下图:
    在这里插入图片描述

    • 1bit:二进制中最高位是符号位,1表示负数,0表示正数。生成的id一般都是用正数,所以最高位固定为0。
    • 41bit-时间戳:用来记录时间戳,毫秒级。
    • 10bit-工作机器id,用来记录工作机器id,可以部署在2^10 = 1024个节点,包括5位datacenterId和5位workerId。
    • 12bit-序列号,序列号,用来记录同毫秒内产生的不同id。

    SnowFlake可以保证:

    1. 所有生成的id按时间趋势递增
    2. 整个分布式系统内不会产生重复id(因为有datacenterId和workerId来做区分)

    算法实现

    public class IdWorker{
    
        //下面两个每个5位,加起来就是10位的工作机器id
        private long workerId;    //工作id
        private long datacenterId;   //数据id
        //12位的序列号
        private long sequence;
    
        public IdWorker(long workerId, long datacenterId, long sequence){
            // sanity check for workerId
            if (workerId > maxWorkerId || workerId < 0) {
                throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
            }
            if (datacenterId > maxDatacenterId || datacenterId < 0) {
                throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
            }
            System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
                    timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);
    
            this.workerId = workerId;
            this.datacenterId = datacenterId;
            this.sequence = sequence;
        }
    
        //初始时间戳
        private long twepoch = 1288834974657L;
    
        //长度为5位
        private long workerIdBits = 5L;
        private long datacenterIdBits = 5L;
        //最大值
        private long maxWorkerId = -1L ^ (-1L << workerIdBits);
        private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
        //序列号id长度
        private long sequenceBits = 12L;
        //序列号最大值
        private long sequenceMask = -1L ^ (-1L << sequenceBits);
        
        //工作id需要左移的位数,12位
        private long workerIdShift = sequenceBits;
       //数据id需要左移位数 12+5=17位
        private long datacenterIdShift = sequenceBits + workerIdBits;
        //时间戳需要左移位数 12+5+5=22位
        private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
        
        //上次时间戳,初始值为负数
        private long lastTimestamp = -1L;
    
        public long getWorkerId(){
            return workerId;
        }
    
        public long getDatacenterId(){
            return datacenterId;
        }
    
        public long getTimestamp(){
            return System.currentTimeMillis();
        }
    
         //下一个ID生成算法
        public synchronized long nextId() {
            long timestamp = timeGen();
    
            //获取当前时间戳如果小于上次时间戳,则表示时间戳获取出现异常
            if (timestamp < lastTimestamp) {
                System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
                throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds",
                        lastTimestamp - timestamp));
            }
    
            //获取当前时间戳如果等于上次时间戳(同一毫秒内),则在序列号加一;否则序列号赋值为0,从0开始。
            if (lastTimestamp == timestamp) {
                sequence = (sequence + 1) & sequenceMask;
                if (sequence == 0) {
                    timestamp = tilNextMillis(lastTimestamp);
                }
            } else {
                sequence = 0;
            }
            
            //将上次时间戳值刷新
            lastTimestamp = timestamp;
    
            /**
              * 返回结果:
              * (timestamp - twepoch) << timestampLeftShift) 表示将时间戳减去初始时间戳,再左移相应位数
              * (datacenterId << datacenterIdShift) 表示将数据id左移相应位数
              * (workerId << workerIdShift) 表示将工作id左移相应位数
              * | 是按位或运算符,例如:x | y,只有当x,y都为0的时候结果才为0,其它情况结果都为1。
              * 因为个部分只有相应位上的值有意义,其它位上都是0,所以将各部分的值进行 | 运算就能得到最终拼接好的id
            */
            return ((timestamp - twepoch) << timestampLeftShift) |
                    (datacenterId << datacenterIdShift) |
                    (workerId << workerIdShift) |
                    sequence;
        }
    
        //获取时间戳,并与上次时间戳比较
        private long tilNextMillis(long lastTimestamp) {
            long timestamp = timeGen();
            while (timestamp <= lastTimestamp) {
                timestamp = timeGen();
            }
            return timestamp;
        }
    
        //获取系统时间戳
        private long timeGen(){
            return System.currentTimeMillis();
        }
    
        //---------------测试---------------
        public static void main(String[] args) {
            IdWorker worker = new IdWorker(1,1,1);
            for (int i = 0; i < 30; i++) {
                System.out.println(worker.nextId());
            }
        }
    
    }
    

    参考链接:幂等性浅谈
    参考链接:理解分布式id生成算法SnowFlake

    展开全文
  • PageRank算法详解 + 示例详解数学求解过程

    1.PageRank算法简介

    PageRank算法的详解,请见前面博客:【机器学习】【PageRank算法-1】PageRank算法原理介绍

    为了方便代码,理解,下面给出幂迭代算法+特征值算法+代数方法的介绍:

    1.1几个基本公式

    以存在支队自己出链的网页的出入链关系图,对应的PR值贡献矩阵为,此矩阵是一个左贡献矩阵,又是一个左概率矩阵(即每一列的总和都是1)。

    矩阵HelpS:

    S[i][j]表示网页j对网页i的出链,可知S[i]表示所有网页对网页i的出链值,S[:,j]是网页j对所有网页的出链值。

    矩阵A:


    其中e是所有分量为1的列向量,即e=(1,…1…,1)T,N是网页总数,一般取值α=0.85

    1.2幂迭代法


    先对P0赋随机初值,然后通过上面公式进行迭代计算,直到满足条件停止迭代计算:一直迭代计算,停止直到下面2情况之一发生:每个网页的PR值前后误差dleta_pr小于自定义误差阈值,或者迭代次数超过了自定义的迭代次数阈值

    1.3特征值法

    Markov Chain收敛时,存在:


    1.4代数法

    Markov Chain收敛时,存在:


    可以通过上面公式计算出来PR值矩阵。

    2.PR值生成的幂迭代法的Python实现

    2.1幂迭代法的代码

    这个算法比较简单,人肉出品,详见如下:

    # -*- coding: utf-8 -*-
    """
    Author:蔚蓝的天空Tom
    Talk is cheap, show me the code
    Aim:使用幂迭代法实现PageRank Alogrithm
    """
    
    import numpy as np
    
    class CPageRank(object):
        '''实现PageRank Alogrithm
        '''
        def __init__(self):
            self.PR = [] #PageRank值
    
        def GetPR(self, IOS, alpha, max_itrs, min_delta):
            '''幂迭代方法求PR值
            :param IOS       表示网页出链入链关系的矩阵,是一个左出链矩阵
            :param alpha     阻尼系数α,一般alpha取值0.85
            :param max_itrs  最大迭代次数
            :param min_delta 停止迭代的阈值
            '''
            #IOS左出链矩阵, a阻尼系数alpha, N网页总数
            N = np.shape(IOS)[0]
            #所有分量都为1的列向量
            e = np.ones(shape=(N, 1))
            #计算网页出链个数统计
            L = [np.count_nonzero(e) for e in IOS.T]
            #计算网页PR贡献矩阵helpS,是一个左贡献矩阵
            helps_efunc = lambda ios,l:ios/l
            helps_func  = np.frompyfunc(helps_efunc, 2, 1)
            helpS = helps_func(IOS, L)
            #P[n+1] = AP[n]中的矩阵A
            A = alpha*helpS + ((1-alpha)/N)*np.dot(e, e.T)
            print('左出链矩阵:\n', IOS)
            print('左PR值贡献概率矩阵:\n', helpS)
            #幂迭代法求PR值
            for i in range(max_itrs):
                if 0 == np.shape(self.PR)[0]: #使用1.0/N初始化PR值表
                    self.PR = np.full(shape=(N,1), fill_value=1.0/N)
                    print('初始化的PR值表:', self.PR)
                #使用PR[n+1] = APR[n]递推公式,求PR[n+1]
                old_PR = self.PR
                self.PR = np.dot(A, self.PR)
                #如果所有网页PR值的前后误差 都小于 自定义的误差阈值,则停止迭代
                D = np.array([old-new for old,new in zip(old_PR, self.PR)])
                ret = [e < min_delta for  e in D]
                if ret.count(True) == N:
                    print('迭代次数:%d, succeed PR:\n'%(i+1), self.PR)
                    break
            return self.PR
    
    def CPageRank_manual():
        #表示网页之间的出入链的关系矩阵,是一个左关系矩阵,可以理解成右入链矩阵
        #IOS[i, j]表示网页j对网页i有出链
        IOS = np.array([[0, 0, 0, 0, 1],
                        [1, 0, 0, 0, 0],
                        [1, 0, 0, 0, 0],
                        [1, 1, 0, 0, 0],
                        [0, 1, 1, 1, 0]], dtype=float)
        pg = CPageRank()
        ret = pg.GetPR(IOS, alpha=0.85, max_itrs=100, min_delta=0.0001)
        print('最终的PR值:\n', ret)
    if __name__=='__main__':
        CPageRank_manual()
    

    2.2运行结果

    左出链矩阵:
     [[ 0.  0.  0.  0.  1.]
     [ 1.  0.  0.  0.  0.]
     [ 1.  0.  0.  0.  0.]
     [ 1.  1.  0.  0.  0.]
     [ 0.  1.  1.  1.  0.]]
    左PR值贡献概率矩阵:
     [[0.0 0.0 0.0 0.0 1.0]
     [0.3333333333333333 0.0 0.0 0.0 0.0]
     [0.3333333333333333 0.0 0.0 0.0 0.0]
     [0.3333333333333333 0.5 0.0 0.0 0.0]
     [0.0 0.5 1.0 1.0 0.0]]
    初始化的PR值表: [[ 0.2]
     [ 0.2]
     [ 0.2]
     [ 0.2]
     [ 0.2]]
    迭代次数:29, succeed PR:
     [[0.2962595101978549]
     [0.11393416086464467]
     [0.11393416086464467]
     [0.16239748970660772]
     [0.31347467836624976]]
    最终的PR值:
     [[0.2962595101978549]
     [0.11393416086464467]
     [0.11393416086464467]
     [0.16239748970660772]
     [0.31347467836624976]]

    (end)

    展开全文
  • 快速幂算法

    2020-03-18 10:46:07
    快速幂算法,名如其意,就是快速求一个数a的b次算法,常见于竞赛题目、上机笔试题要求时间的场景。 思路 任何一个整数都可以表示成二进制的形式,比如你想求10的50次方,50的二进制表示为‭110010‬,即,...

    概述

    快速幂算法,名如其意,就是快速求一个数a的b次幂的算法,常见于竞赛题目、上机笔试题等要求时间的场景。

    思路

    任何一个整数都可以表示成二进制的形式,比如你想求10的50次方,50的二进制表示为‭110010‬,即50=2^{1}+2^{4}+2^{5},所以10^{50}=10^{2^{1}}*10^{2^{4}}*10^{2^{5}}。我们根据10的1次方可以快速的求出10的2次方(进行相乘即可)。由10的2次方可以快速求出10的4次方,由10的4次方可以快速求出10的8次方.....。所以这种算法就可以极快的算出a的b次幂,对于10的50次方来说,50转化为二进制共有6位,我们只需要做6次乘法运算即可。

    假设我们知道10的25次方是多少,再进行一次乘法运算10^{25}*10^{25}就可以了,而10^{25}可以转化为10*10^{24},每次指数级别的下降,从而达到了O(log(N))的时间复杂度了。

    通解公式:b为偶数:a^{b}=a^{\frac{b}{2}}*a^{\frac{b}{2}}

                      b为奇数:a^{b}=a*a^{b-1}

    由此公式我们便可以写代码了。

    代码

    /**
    * 快速幂算法求解a^b,对M取模。
    */
    public long quickPow(long a, long b, long M) {
        if (b == 0) {
            return 1;
        } else if ((b & 1) == 1) {
            return a * quickPow(a, b - 1, M) % M;
        } else {
            // System.out.println("运算了");
            // return quickPow(a, b>>1, M) * quickPow(a, b>>1, M);
            // 防止越界
            long temp = quickPow(a, b >> 1, M) % M;
            return temp * temp % M;
        }
    }

    总结

    遇事多想,大佬的思路确实厉害!

    展开全文
  • 分治算法为递归问题,可以用来解决快排、二分归并、斐波那契数列、锦标赛问题、凸包问题       递归方程主要分为两类:(1)(2)f(n)=af(n/b)+d(n)  &nbs...
    分治算法就是分成若干个和原问题一样性质的子问题,然后逐步递归这些子问题,直到遇到规模很小的子问题,求出子问题的解,归结成原问题的解的算法就是分治算法
    分治算法为递归问题,可以用来解决快排、二分归并、斐波那契数列、锦标赛问题、凸包问题等
    

          递归方程主要分为两类:(1)(2)f(n)=af(n/b)+d(n)
          第一种的方程可以用迭代或者递归树求解,如汉诺塔;第二种的方程可以用迭代、递归树、主定理求解,如二分归并排序
          本篇主要介绍分支算法的推导方程的解,即主定理、递归树,以及幂乘运算及其优化、汉诺塔问题

    1、递归树

    什么是递归树

          递归树是迭代过程的一种图像表述。递归树往往被用于求解递归方程, 它的求解表示比一般的迭代会更加的简洁与清晰。
          递归树有如下概念:
    1、递归树是迭代计算的模型。
    2、递归树的生成过程与迭代过程一致。
    3、递归树上所有项恰好是迭代之后产生和式中的项。
    4、对递归树上的项求和就是迭代后方程的解。

    递归树的生成

    T(n)是原问题的解,我们把T(n)写成T(n)=T(m1)+T(m2)+…+T(mt)+f(m1)+f(m2)+…+f(mt)      在这里前面由T写成的方程是递归子问题,而后面由f写成的是归结子问题解的操作。

    这里我们把T写成的式子称为函数项,把f写成的式子成为非函数项

    对于T(n)是原问题的解。我们可以把非函数项写成根,把函数项写成叶子,如图:

    左边的原问题可以写成右边的递归树,右边的递归树根是非函数部分,也就是归结子问题解的部分,而叶子是函数部分,也就是划分子问题的部分,然后我们发现,这棵递归树所有节点的和就是左边原问题的解,这是第一步迭代的过程。

    举个例子:我们在上一篇提到过二分归并排序的算法是T(n)=2T(n/2)+n,这里我们看到,T(n)是原问题的解,而2T(n/2)是函数部分,n是非函数部分。我们可以把2T(n/2)画成叶节点,把n画成根节点。做出迭代两步迭代的递归树:

    那么我们可以得出递归树的生成规则:
    1、初始:递归树只有根结点,其值为T(n)
    2、不断继续下述过程:
    将函数项叶结点的迭代式T(m)表示成二层子树
    用该子树替换该页结点
    3、继续递归树的生成,直至树中无函数项(只有初值)为止。

    我们参考上边的继续将二分归并的递归树画出来:

    我们发现右边的n是左边节点的和,所以原问题的解=所有节点的和=将右边的n全部加起来就可以了
    这是一棵完全二叉树,我们知道完全二叉树的深度是logn,那么logn个n相乘不就是nlogn嘛。所以我们得出二分归并排序的时间复杂度是O(nlogn)。

    递归树的应用

    接下来,我们通过递归树来分析一个递归方程:
    T(n)=2T(n/2)+nlogn (n/2 log(n/2)=n/2(logn-log2)=n/2(logn-1))
    作图,得:

    根据完全二叉树定理,n=2^k,即k=logn(n是节点数,k是深度)
    将上图右边的式子相加得,
    nlogn+n(logn-1)+n(logn-2)+…+n(logn-k+1)
    = nlogn+nlogn+nlogn+…+nlogn-n(1+2+3+4+…+k-1)
    = nklogn(有多少深度,就有多少的logn。绝对不是n个logn) -n(k(k-1)/2)
    = nklogn-n((k^2-k)/2
    这里我们把k=logn带进去得,
    = n(logn)2-n((logn)2/2-(logn)/2)
    = n(logn)2-n(logn)2/2-n(logn)/2
    = O(n(logn)2) (读作:logn的平方乘以n)

    递归树分的叉数还是要看递归的规模是多少。如果是T(n)=3T(n/2)+n-1或者T(n)=T(n/9)+T(4n/9)+T(4n/9)+n,那就是要分三个叉了

    这是用递归树来解这些递归方程

    2、主定理

    什么是主定理

    主定理就是在涉及f(n)=af(n/b)+d(n)递推方程时,可以更快的运用主定理直接求解,不用繁琐计算

    在f(n)=af(n/b)+d(n)中
    a 是规约后的子问题的个数
    n/b 是规约后子问题的规模
    d(n) 是规约过程及组合子问题的解的工作量

    首先我得说清楚O是上界,比如说f(n)=n2+n,我们就说f(n)=O(n^2),像这样f(n)=O(g(n)),f(n)的阶不高于g(n)的阶
    而Ω是下界,比如说f(n)=n2+n,f(n)=Ω(n^2),像这样f(n)=Ω(g(n)),f(n)的阶不低于g(n)的阶
    Θ是当f(n)=O(g(n))而且f(n)=Ω(g(n))则记作f(n)=Θ(g(n))。


    就能得出这样的解

    这里不再证明了,如果感兴趣的话,可以从网上找找证明。这里我们直接应用

    主定理的应用

    比如,我们要求解二分归并排序的递推方程
    T(n)=2T(n/2)+n
    这里a=2,b=2,fn=n
    根据主定理得,n=n,也就是说f(n)=Θ(n),那么T(n)=Θ(nlogn)

    再比如,T(n)=9T(n/3)+n
    这里a=9,b=3,f(n)=n
    根据主定理得,n^log3 9=n2,而f(n)=n,我们可以找到一个E=1(主定理1),使得f(n)=O(n),那么T(n)=Θ(n2)
    或者说,我们可以根据下面的解来直接得出T(n)=O(n2)

    再再比如:T(n)=T(2n/3)+1
    这里a=1,b=3/2,f(n)=1
    根据主定理得,1=n0,即T(n)=Θ(logn)
    或者说,我们可以根据下面的解来直接得出T(n)=O(logn)

    再看一下,T(n)=3T(n/4)+nlogn
    这里a=3,b=4,f(n)=nlogn
    根据主定理得,n^(log4 3)约等于n0.793,那么有E=0.2,使得nlogn=Ω(n^(log4 3)),而且还要使af(n/b)<=cf(n)成立,
    则3(n/4)log(n/4)<=cnlogn
    3(n/4)(logn-log4)=3(n/4)(logn-2)=3(n/4)logn-3(n/2)
    这里我们发现,只要c>=3/4,上述不等式成立。则主定理3成立,即T(n)=Θ(nlogn)
    或者说,我们可以根据下面的解来直接得出T(n)=O(nlogn)

    当然并不是说所有的递推方程都可以用主定理来解决
    大家来看T(n)=2T(n/2)+nlogn
    这里a=2,b=2,f(n)=nlogn
    首先要知道在都单调递增的情况下,幂函数都是大于对数函数的

    你要明白对数函数增长缓慢,而幂函数增长程度是比对数函数要大的多。而指数函数,要比幂函数大的多的多,相比大家听说过指数爆炸吧。如果你的代码量的时间复杂度是个指数函数(比如:2n),我就这么说,你的数据量如果超过了27。那么你的运行时间就可能会超过1秒。所以说算法就是尽量解决这一类问题,让时间复杂度降一个量
    对于时间复杂度的量,就是指数的量>多项式的量>对数的量。你这样的每降一次,那么你的运行效率就会提高不止一个档次。运行时间慢就要考虑你的代码问题,而代码混乱的问题就是代码设计模式的问题,当然设计模式也是可以用来提高性能和效率的,这一点在游戏开发格外重要。所以设计模式+数据结构+算法都是程序员的内功心法

    好了我们回到正题,f(n)要等于Ω(n(1+E))(E>0)。也就是,n·logn=Ω(n·nE)(E>0)。而且幂函数都是大于对数函数。所以logn<nE,因此找不到一个E满足那个下界(大于等于那个函数)。因此不成立,所以不满足主定理3。也就不能求解。

    而且去用下面的解c是logn,不是常数。所以也解不出来。

    那要怎么处理呢,我们可以用递归树解这个递归方程,求解在上面递归树那里有,我已经写出来了。

    主定理就是解决求递归方程解的问题的,当然要根据情况进行求解。

    3、幂乘算法及其优化

    什么是幂乘算法?

    很简单,就是求nx次方,例如求25。25=32

    我们先来看普通的幂乘算法

    普通幂乘算法

    幂乘算法,我记得学循环的时候,不就接触了这个东西了嘛。你用for写,用while写,不都可以。都是很简单的东西,包括递归

    比如啊,你要求an,那么你要传入a,n到函数(方法)里面,用for就是n- -,n>=1,或者啊,就是i=0,i<n,i++。反正方法体里面都是 res*=a(res就是结果)。

    对于递归就是n为0,返回1,n为1,返回本身,其他的就返回a*pow(a,n-1),一直递归,找到出口,然后将值一步步返回

    不多说了,直接上代码

    public static void main(String[] args) {
    		Random random=new Random();
    		int a=random.nextInt(15);
    		int r=random.nextInt(10);
    		System.out.println("计算"+a+"的"+r+"次方的值");
    	    int res=pow(a, r);
    	    System.out.println("结果是:"+res);
    	}
    
    //简单幂乘(迭代写法)
    	public static int pow(int a,int r) {
    		int res=1;
    		for(int i=0;i<r;i++) {
    			res*=a;
    		}
    		return res;
    	}
    	//简单幂乘(递归写法)
    	public static int pow2(int a,int r) {
    		if(r==0)
    			return 1;
    		else if(r==1)
    			return a;
    		else {
    			return a*pow2(a,r-1);
    		}
    	}
    
    简单幂乘算法分析

    顺序相乘,实则就是n从1到n本身,总共n个数。那么时间复杂度就是O(n)

    如果我们还有优化,那就是要优化到O(logn),下面我们来看一下优化的幂乘算法。

    快速幂算法

    我们考虑用分治法进行划分

    当n为偶数时,可以划成n/2个a和n/2个a相乘。这两个是均匀划分的子问题,而且对于这两个n/2个a,既然你都算出来了n/2个a是多少了,那么对于右面我们就不必再计算了,只做一个子问题的计算就行了,右面的直接拿来用就行了。就因为这样减少了一半的时间。就这样递归下去。

    当n为奇数时,我们可以划分成2个(n-1)/2个的a的子问题相乘,然后再和a相乘。也就是
    (n-1)/2个a与(n-1)/2个a与a相乘(大家要多思考,多想想)。这样也是近似减半的算法,也差不多减少了一半的时间。就这样递归下去。

    我们分析下不管奇数还是偶数,我们都可以用(a,n/2)来进行递归,此时,n为1,就返回本身。否则继续递归。

    我们在n=1的时候找到了res=a之后向上返回之后,(在n-1次递归的时候的n要不是2,要不是3。大家可以想想是不是),好我们继续思考,然后进入n的奇偶判断

    我们根据上面的图不难想到,如果是偶数,那么就是res乘以res,如果是奇数那么就是res乘以res乘以a

    好,我们来看下代码

    public static void main(String[] args) {
    		Random random=new Random();
    		int a=random.nextInt(15);
    		int r=random.nextInt(10);
    	    System.out.println("计算"+a+"的"+r+"次方的值");
    	    int res=pow3(a, r);
    	    System.out.println("结果是:"+res3);
    		}
    
    //快速幂算法
    	public static int pow3(int a,int r) {
    		int res=1;
    		if(r==0)
    			return 1;
    		else if(r==1)
    			return a;
    		else 
    			res=pow3(a, r>>1);
    		if(r%2==0)
    			return res*res;  //如果r为偶数,则乘其本身
    		else
    			return res*res*a;  //如果r为奇数,则乘其本身和a
    	}
    
    快速幂算法的分析

    首先,递归肯定是T(n/2),然后乘以res和乘以a,都是一步计算,我们都可以想成O(1)的量。因此T(n)=T(n/2)+O(1)
    用主定理分析解出时间复杂度就是O(logn)。

    快速幂算法下,有一个重要的应用叫作斐波那契数列。我们再下一篇(分治算法的改进和矩阵(斐波那契数列和Strassen矩阵)下的分治算法)中去说

    4、汉诺塔问题

    什么是汉诺塔问题

    汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

    抽象成数学问题就是
    如下图所示,从左到右有A、B、C三根柱子,其中A柱子上面有从小叠到大的n个圆盘,现要求将A柱子上的圆盘移到C柱子上去,期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面,求移动的步骤

    移动的步骤就是这样的

                                         

    对于汉诺塔问题,就是这样分析

    对于三个盘子的情况是这样的:

    我们先把n-1个盘子放到B处

    然后把底下那个最大的盘子放到目标位置处

    最后将那个n-1个盘子放到目标位置处

    ok,移完了

    对于那个什么n-1个盘子怎么移过去的,我不管。

    而且代码也可以这么写。先放伪码
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EhZzMwvd-1586745625936)(/localImg/ArtImage/2020/02/2020022300453016.jpg)]
    大家可以想想刚才的步骤,再看看伪码。你会豁然开朗的。

    对于内部那些操作交由递归来实现就行了。

    然而我们可以分析得出
    (1)中间的一步是把最大的一个盘子由A移到C上去;
    (2)中间一步之上可以看成把A上n-1个盘子通过借助辅助塔(C塔)移到了B上,
    (3)中间一步之下可以看成把B上n-1个盘子通过借助辅助塔(A塔)移到了C上;

    对于内部递归是怎么操作的,大家可以自己动手分析下,这里就放个图

    好,我们上代码

    public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int n=3;  //共有3层
    		char a='A';  //A是出发点
    		char b='B';  //B是暂存点
    		char c='C';  //C是终点
    		Hanoi(n, a, b, c);
    	}
    	
        public static void Hanoi(int n,char A,char B, char C) {
        	if(n==1) 
        		Move(A,C); //将出发点移动到终点
        	else 
        	{
        		Hanoi(n-1, A, C, B);  //将n-1个塔从出发点移动到暂存点,其中以终点为辅助
        	    Move(A, C);
        	    Hanoi(n-1, B, A, C);  //将n-1个塔从暂存点移动到终点,其中以出发点为辅助
        	}
        }
        
        public static void Move(char from,char to) {
        	System.out.println(from+"——>"+to);
        }
    

    把n调调,既可以实现3个,也可以实现4个。

    汉诺塔算法的分析

    两个递归而且都是从n-1开始的,所以是2T(n-1)。对于从A移动到C是1步,那么就是
    T(n)=2T(n-1)+1
    T(1)=1
    求解这个方程的思路是
    T(n)+1=2(T(n-1)+1)
    T(n)+1/(T(n-1)+1)=2
    也就是T(n)+1是初值为2,公比为2的等比数列
    因此得出T(n)=2^n
    所以汉诺塔的时间复杂度是O(2^n),居然是个指数级,那么我们要思考有没有一个优化来降低这个时间复杂度。

    目前的答案是:没有,不存在一个多项式时间的算法。

            靡不有初,鲜克有终《诗经·大雅·荡》
    展开全文
  • 幂等半环上的环负矩阵的加闭环算法及其应用
  • 关于快速其实快速相关的问题,是参加算法竞赛(NOI、ACM)的小伙伴必须要掌握的一小块基础内容。当然,就算你不打算参加算法竞赛,个人觉得只要你是一名程序员,就必须要掌握快速幂算法。在《计算机程序设计艺术...
  • 此文由快速求幂算法讲起,讲到了其中的半群离散数学的概念。并由此仿造出了其他api. 文章中提到“如果想学习这个算法的一些用法或者想知道更多这个算法背后的理论,请查阅这本叫做《Elements of Porgramming》,这...
  • 幂等性HTTP幂等方法,是指无论调用这个url多少次,都不会有不同的结果的HTTP方法。也就是不管你调用1次还是...RESTFUL幂等性探讨我们下面就探讨一下 restful 风格中的 GET POST PUT PATCH DELETE 的幂等性。 HTTP GE...
  • 幂等性HTTP幂等方法,是指无论调用这个url多少次,都不会有不同的结果的HTTP方法。也就是不管你调用1次还是...RESTFUL幂等性探讨我们下面就探讨一下 restful 风格中的 GET POST PUT PATCH DELETE 的幂等性。 HTTP GE...
  • 点击上方Java后端,选择设为星标优质文章,及时送达前言在实际的开发项目中,一个对外暴露的接口往往会面临很多次请求,我们来解释一下幂等的概念:任意多次执行所产生的影响均与一次执行的影响相同。按照这个含义,...
  • 来自:简书,作者:wangzaiplus链接:https://www.jianshu.com/p/6189275403ed一、概念幂等性, 通俗的说就是一个接口, 多次发起同一个请求, 必须保证操作只能执行一次比如:订单接口, 不能多次创建订单支付接口, 重复...
  • 算法设计与优化中的递归法德5道经典例题(如最大值,母牛繁殖,x的n次幂等),用c编写,很适合初学者借鉴。
  • 随机算法 之模函数

    千次阅读 2008-10-24 13:27:00
    在诸如RSA等算法中都要用到求a^n mod p的运算,例如费马小定理(a^(n-1) mod n = 1,p是a的非素数因子)及rsa算法用到的费马定理的推广(a^(y(n))mod n = 1,y(n)为n的欧拉函数)等等都需要用到模运算,那么怎么能快速...
  • 如题,出现需要是否保证接口幂等性的场景,主要是insert和update,因为这两种会对数据库资源造成变动,而select本身只是读取,本身具有幂等性,delete之后再去删,也不会对数据库造成影响,也为幂等的,所以主要设计...
  • 对于暗弱目标探测,现有的方法仍然存在探测误差较大的问题,为了提高夏克-哈特曼波前探测器的质心探测精度,提出了一种改进的距离-指数质心探测算法。在不同情况下将所提算法与现有的几种质心算法进行对比,仿真...
  • 1、二分查找
  • 为了抑制主成分分析PCA对图像中光照变化的较高敏感性、进一步提高人脸识别率, 提出了一种对图像灰度进行次变换预处理的策略。首先采用随机序列来选取人脸库中的训练样本和测试样本, 然后对随机人脸样本进行次...
  • 综上所述,我们需要做的是列出初始条件的 F 矩阵,如F(1) = 1, F(2) = 1初始情况;然后找到 A 矩阵 ,用于求,最后我们算好 即可。 矩阵快速模板 这里使用了斐波那契数列为例子。 #include<bits/stdc++...
  • 幂等性保障

    2020-03-10 10:19:52
    唯一ID+指纹码机制,利用数据库主键去重 唯一ID+指纹码机制,利用数据库...解决方案:跟进ID进行分库分表进行算法路由 利用Redis的原子性去实现 通过在Redis放一个 比如userID+goodsID的key,判断是否存在来进行...
  • RabbitMQ高级特性-幂等性保障

    千次阅读 2018-12-26 06:46:39
    消费端-幂等性保障 幂等性 : 多次执行, 结果保持一致 主流的幂等性操作 唯一ID + 指纹码机制, 利用数据库主键去重 好处 : 实现简单 坏处 : 高并发下有数据库写入的性能瓶颈 解决方案 : 根据ID进行...
  • 比如它传进来的是int类型的最好的答案-------------若是这个数可以被int的最大的x的n次整除,那么他就是 ,否则不是 算法时间复杂度O(1)比如 ------ 如何判断一个数是不是3的 n次 ...
  • 快速、快速乘

    2018-09-26 20:03:00
    快速幂等算法都是基于二进制优化的算法,本文不做过多叙述,在此只是留下模板,并介绍\(O(1)\)快速乘 快速幂 int qpow(int a, int b, int p) { int res = 1 % p; for (; b; b >>= 1, a = (long long) a * a ...
  • 在ACM竞赛中经常会遇到各种的求问题,这种问题一般情况下对应的数字都会很大,所以快速就会经常用到,快速很好用,就算没有弄清楚快速的原理,只要有模板很快就可以解题。先说几个比较重要的公式: 模运算...
  • java幂等性判断

    2021-04-28 11:13:03
    代码如下: ... // 根据 LRU(Least Recently Used,最近最少使用)算法淘汰数据的 Map 集合,最大容量 100 个 private static LRUMap<String, Integer> reqCache = new LRUMap<>(100); /**

空空如也

空空如也

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

幂等算法