精华内容
下载资源
问答
  • 在线算法的竞争比
    千次阅读
    2019-09-06 11:38:45

    竞争比的定义

    考虑一个常见的页面管理问题,计算机中有两层存储,一层是高速cache,它能够缓存k个项目,一层是主存储器,它较为缓慢,但是可存储比cache多得多的项目。学过操作系统这门课程的同学都知道,页面的置换有很多的经典算法,比如LRU,FIFO,LFU等,这些都是在不知道未来的页面请求的情况下,给出页面置换的策略。现在有一个请求序列R = (r1,r2,···rn)为一个在线页面管理算法A的请求序列,如果请求的项目在高速cache中,就为命中(hit),否则称之为缺失(miss),fA(r1,r2,···rn)为在线页面管理算法A在序列R上缺失的数目。对于同样的一个序列R,离线算法MIN知道所有的请求序列,在页面置换的时候就可以置换出未来最远才会被请求的项目,用fO(r1,r2,···rn)表示离线算法在序列R上缺失的最小数目。

    定义:一个确定性在线页面管理算法A被称为是C-竞争的,如果存在常数b,使得对于每个请求序列r1,r2,···rn,满足:
    fA(r1,r2,···rn) - CfO(r1,r2,···rn)<=b
    其中,常数b必与N无关,但可以依赖与k。A的竞争性洗漱是使得A是C-竞争的下确界,记为CA

    从上面这个定义我们可以看出,C越小,表示在线算法A的缺失数目越和最优算法接近,性能也就越好。如果把减号后面的部分移到等号的右边,然后在将fO(r1,r2,···rn)除到左边,C也可以看作最在线算法和最优算法的比值。

    竞争比的一些性质

    还没写完,接着写······

    举一个栗子

    更多相关内容
  • 在线算法(online algorithm)--竞争性分析

    千次阅读 多人点赞 2020-09-08 19:28:12
    文章目录一、competitve analysis二、page replacement2.1 问题背景2.2 deterministic online algorithm2.2.1 LIFO和LFU不是α\alphaα-竞争算法2.2.2 LRU和FIFO是kkk-竞争算法2.3 deterministic online algorithm的...

    基于参考材料,和自己的理解,本文主要整理了在线学习中的竞争性分析,和它的典型例子:page replacement问题。便于自己后续查阅。

    说到这里,真的是不得不吐槽国内的算法课以及百度,几乎不教或者没有这方面的中文资料。必须要去google上去找国外lecture的资料和书。由于自己之前其实也没有接触过competitve analysis,所以才想记录一下自己的了解过程。一些基础的概念就不再记录了。

    一、Problem Setting

    1.1 competitve analysis

    竞争分析是指,将在线算法所产生的费用与离线算法(假设所有信息都知道)所产生的费用进行比较和分析。

    参考文献【1】是难得的一个用中文描述的资料。胡老师在PPT中介绍:

    在这里插入图片描述
    这里有一个重要的概念在于:对于任意给定的 S S S,算法 A A A产生的cost最多是最优算法OPT的 α \alpha α倍。

    1.2 page replacement

    We give a machine with a slow memory that can hold N pages, and a fast memory with k slots. Page requests arrive one at a time, and must be served out of fast memory. If the page is already in fast memory (cache), then a hit occurs, and the operation is free. Otherwise, there is a cache miss, the page is brought into fast memory, and one of the k existing pages in the cache is evicted. The goal is to minimize the number of cache misses over the sequence of page requests.

    简单来说,就是有一个页面请求序列,如果序列里的元素在cache中了,那么就算命中,没有开销;如果不在cache里,必须要evict cache中的一个element,设计出一个算法使得整个序列的miss最少。

    接下来,我们以这个问题为背景展开介绍。

    二、Deterministic Online Algorithms

    2.1 deterministic online algorithm

    在操作系统课上,已经学过不少的确定性的页面置换算法了。这里做个简单的总结:

    • LIFO(last input first output):”后进新出原则“,将最近一次放入cache中的页面交换出去。
    • LFU (leasy frequency used):“最少调用原则”,交换出去最少被调用的页面。
    • LRU(least recently used): “最近最久未使用原则”,交换出这样一个页面它最近的一次调用是最早产生的。
    • FIFO(first input first out):”先进先出原则“,交换出去在cache中时间最长的页面。

    当然,对于离线算法来说,它已经知道了序列的未来,所以就有一个offline 最优的算法(有时候称为MIN),这就是Bedaly在1966年提出的一种算法,选择以后永远不会被访问的页面或者未来最长时间内不再被访问的页面。
    有时候,也被称为LFD (longest-forwarded-distance)。关于它是最优算法的证明,可以参考这篇文章。我们这里省略。

    2.1.1 LIFO和LFU不是 α \alpha α-竞争算法

    定理2-1:LIFO不是 α \alpha α-竞争算法

    证明:若request序列长度为 N N N, 为<p,q,p,q,p,q…>,且初始状态q在cache中,p不在cache中。
    则按照LIFO策略,
    因为,For any α \alpha α, there exists a sequence of requests such that #misses(FIFO) ≥ α \alpha α #misses (LFD)。在上面的分析中,算法的开销为 N N N,而最优策略是1,因此算法的开销/最优的开销为N,也就是说是无穷大了。

    根据竞争分析的定义,存在了一个序列使得 算法的开销/最优的开销 不小于 α \alpha α,因此不能用于竞争性分析。

    下面来看LFU算法:

    在这里插入图片描述

    定理2-2:LFU不是 α \alpha α-竞争算法

    证明:如果cache k k k=3,元素是a,b,c,则我们可以构造一个序列,即出现 m m m次a,再出现 m m m次b,再出现1次d,接着出现1次c,dc这样的组合共出现 m m m次。
    我们可以看到,按照LFU算法,在出现d时,会发生miss替换掉c,接着出现1次c,会发生miss替换掉d。这样就会产生 2 m 2m 2m个miss,而最优算法只会产生1次miss(即第一次出现d时替换掉a即可),因此如果m无穷大,则LFU算法仍然没有bounded。

    换句话说,对于LFU算法,也存在了一个序列使得 算法的开销/最优的开销 不小于 α \alpha α,因此不能用于竞争性分析。


    注:以上2个算法的形式化的证明可以在参考文献【2】中找到。
    在这里插入图片描述

    2.1.2 LRU和FIFO是 k k k-竞争算法

    定理2-3:LRU是 k k k-竞争算法

    这里其实有两个思路来证明定义2-3。我们以参考文献【2】中的证明来举例:
    我们将序列 σ \sigma σ来划分phrase,phrase1以序列的第一个元素开始;phrase i开始是以从阶段i-1开始后,我们看到的第 k k k个元素开始。从图中就可以看到
    在这里插入图片描述
    我们可以分析,由于LRU算法的性质,在每一个阶段,最多出现 k k k次cache miss(不可能出现 k + 1 k+1 k+1次,否则不符合阶段的定义了)如果我们可以证明:每一个阶段OPT算法至少会出现1次cache miss。那么竞争ratio就是小于等于 k k k的。
    我们具体分析:如果 p 2 i p_2^i p2i p k i p_k^i pki中没有发现miss,那么在OPT下 p 1 i + 1 p_1^{i+1} p1i+1必然要发生miss,因为 p 2 i p_2^i p2i p 1 i + 1 p_1^{i+1} p1i+1已经是 k k k个不同的元素了,且此时 p 1 i p_1^i p1i已经在cache中了,而cache只有 k k k个位置;
    如果在OPT下 p 2 i p_2^i p2i p k i p_k^i pki中发现miss,那更说明了每一轮最少发生1次miss了。
    在这里插入图片描述
    当然还有另外一种证明的思路,参考文献【3】和【1】。它划分阶段的方式不一样。但是在【3】中,它提供了一个引理,如果我们可以证明出引理,实际也就证明了定理。

    它划分阶段如下:
    在这里插入图片描述
    接着提出一个引理并证明:这个引理是如果 P ( i ) P(i) P(i)中含有 k k k个不同的且不用于上个阶段最后一个页面 p p p的页面,那么其实就说明OPT下必然至少发生一次miss(因为这样就有 k + 1 k+1 k+1个不同的页面了),而由于我们阶段划分已经保证了每个阶段在LRU下发生 k k k次miss,所以实际就证明了LRU是 k k k-竞争算法。

    证明引理的过程如下:如果在 P ( i ) P(i) P(i) k k k个miss是由于1个页面 q q q引起了2次,也就是说并非是 k k k个不同的页面引起的 k k k个miss,那么实际上这是不可能的事情。
    在这里插入图片描述
    在参考文献【1】中用中文已经举出了这个例子。这里的 p p p就是我们上面的说的 q q q

    在这里插入图片描述
    FIFO的证明类似。我们这里不再证明。

    2.2 deterministic online algorithm的竞争比是 Ω ( k ) \Omega(k) Ω(k)

    这个定理的含义是,对于任意的确定性在线算法,它的竞争比至少是 k k k。换句话说,不可能再有一个在线的确定性算法的竞争比 比 k k k好了,其中 k k k是cache的size。

    证明,参考文献【2】即可。
    不妨假设ALG是某一确定性算法;假设序列长度 N > k N > k N>k,且目前的cache内容就是1,2,3,直到k。假设序列里的内容是1,2,3,k,k+1共k+1个不同的值。那么,对于一个adversary来讲,自然可以把序列变成使得ALG在每个request来的时候都发生miss,这时候ALG的miss是 N N N次。
    对于OPT算法来说,一旦发生一个miss,则意味着它逐出的页面将在至少k个其他请求之后被请求,这是肯定的,因为MIN算法已经保证了这一点,即它逐出的永远都是最晚到来的,当发生下一次的miss的时候,最快也是第k+1个,这就意味着OPT每次发生miss的时候,ALG最少发生k次,也就是说竞争比至少为k,即 Ω ( k ) \Omega(k) Ω(k)

    在这里插入图片描述在这里插入图片描述
    上述的结果其实也扩充了,即如果online算法和offline算法的内存大小不一样,也产生产生类似的结果。证明过程可以参考文献【4】.


    在这里,我对竞争性分析和符号 Ω \Omega Ω的关系总结一下,迷惑点在于竞争性分析是≤符号,即算法损失/最优损失 小于等于 一个值,代表了一个最坏的情况(worst-analysis),不管你找什么样的序列,我的算法最烂的损失也就是在这种情况下最优算法的 α \alpha α倍。而 Ω \Omega Ω是大于等于,代表了最优情况,是一个下限,再加上竞争比肯定是越小越好,所以对于一个算法来说 Ω ( l o g n ) \Omega(log n) Ω(logn)要好于 Ω ( n ) \Omega(n) Ω(n)

    如果我们说一个算法的竞争比为 Ω ( k ) \Omega(k) Ω(k),这意味着这个算法的竞争比的下限为 k k k,即属于这类算法的竞争比会大于等于 k k k, 但最好也不过是 k k k了。我们可以回想确定性算法LIFO和LFU都没有竞争比(即无穷大,没有Bounded),而确定性算法LRU和FIFO是 k k k竞争,是有bounded的。

    这时候如果我们有另一类算法的竞争比是 Ω ( l o g n ) \Omega(log n) Ω(logn),那么它的下限是优于上面的算法的下限的。

    三、Randomised Online Algorithms

    3.1 Marker Algorithm

    Marker算法是最经典的随机在线算法。它的过程如下:
    Classic Marker algorithm: The algorithm runs in phases. At the beginning of each phase, all elements are unmarked. When an element arrives and is already in the cache, the element is marked. If it is not in the cache, a random unmarked element is evicted, the newly arrived element is placed in the cache and is marked. Once all elements are marked, the phase ends and we unmark all of the elements. In other word, each phase ends as soon as k k k distinct elements appear.

    伪代码如下:

    在这里插入图片描述

    举一个例子:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    也就是加了一个对于cache中的每一个元素,加了一个marker位。然后分阶段进行分析。

    在算法中,还有2个概念非常重要即clean元素和stale元素(有时,又被称为new和old,意义相同),它们的定义如下:

    For the purposes of analysis, an element is called clean in phase r r r if it appears during phase r r r,
    but does not appear during phase r − 1 r-1 r1. In contrast, elements that also appeared in the previous
    phase are called stale.

    也就是说,clean元素是上一个阶段(有时,也称为轮,round) 没有,而这个阶段有的;而stale元素上个阶段有,这个阶段也有。

    所以很显然,clean元素是必然会引起miss的。

    接下来我们证明一些mark算法的性质。

    3.2 The Marker algorithm is 2 H k 2H_k 2Hk-competitive.

    3.2.1 marker算法的miss至多是 L H k LH_k LHk

    定理3-1:令L是总共的new元素的数目,则marker算法的miss至多是 L H k LH_k LHk

    我们先定义调和级数Harmonic number H k = 1 + 1 / 2 + 1 / 3 + … + 1 / k = O ( l o g k ) H_k= 1+1/2+1/3+…+1/k = O(log k) Hk=1+1/2+1/3++1/k=O(logk)
    其实调和级数的确界也是 H k = Θ ( log ⁡ k ) H_k = \Theta (\log k) Hk=Θ(logk),证明过程可以参考这里

    证明如下(以参考文献【5】为基础,加上自己的理解):

    l r l_r lr为第 r r r轮(阶段)中new元素的个数。

    根据new和old元素以及算法的流程。有2种情况会造成cache miss:

    1、new page按照定义肯定会产生miss
    2、old page在被evict后又request了,也会产生miss。这种情况较复杂。

    对于第2种情况,我们分析最差的情况是,每轮先有 l r l_r lr个new都来,然后 k − l r k-l_r klr个old元素才来(因为每轮最多有 k k k个不同的元素来)。这里最差的意思是:反正 l r l_r lr个new迟早要来,不如要它们先全来,这样才会尽量的把old元素evict, 使得第2种情况的miss更多。

    我们分析第一个old发生miss的概率,显然是: l r k \frac{l_r}{k} klr,我们可以这么想:一共有 k k k个未标记的old element,还在cache中的未标记的old有 k − l r k-l_r klr个,发生hit的可能是 k − l r k \frac{k-l_r}{k} kklr,自然发生miss的概率是 1 − k − l r k = l r k 1-\frac{k-l_r}{k}=\frac{l_r}{k} 1kklr=klr

    我们再仔细分析一下,如果第一个old发生了miss,那它肯定是被某个new元素驱逐了,不妨假设这个新元素是 N 2 N2 N2,那现在又来了第二个old元素 O 2 O2 O2,则 N 2 N2 N2不可能驱逐 O 2 O2 O2了(因为 N 2 N2 N2已经驱逐了 O 1 O1 O1了)。所以new元素能驱逐 O 2 O2 O2的,只剩下 l r − 1 l_r-1 lr1个了。但是呢, O 1 O1 O1却有可能驱逐 O 2 O2 O2,所以实际上呢,能驱逐 O 2 O2 O2的元素还是 l r − 1 + 1 l_r-1+1 lr1+1,即 l r l_r lr个。

    如果第一个old发生了hit,则不会影响能驱逐 O 2 O2 O2的元素,即还是 l r l_r lr个。

    所以,如果我们假设第一个old发生miss的概率是 p p p,则第二个old发生miss的概率:
    = l r − 1 + 1 k − 1 p + l r k − 1 ( 1 − p ) = l r k − 1 =\frac{l_r-1+1}{k-1}p+\frac{l_r}{k-1}(1-p)=\frac{l_r}{k-1} =k1lr1+1p+k1lr(1p)=k1lr


    当然,我感觉这里这么分析更直观:在第二个old来的时候,一共有 k − 1 k-1 k1个未标记的old element,在cache中的未标记的old有 k − l r − 1 k-l_r-1 klr1个,发生hit的可能是 k − l r − 1 k − 1 \frac{k-l_r-1}{k-1} k1klr1,自然发生miss的概率是 1 − k − l r − 1 k − 1 = l r k − 1 1-\frac{k-l_r-1}{k-1}=\frac{l_r}{k-1} 1k1klr1=k1lr


    类似地,第三个old发生miss的概率是 l r k − 2 \frac{l_r}{k-2} k2lr

    i i i个old发生miss的概率是 l r k − i + 1 \frac{l_r}{k-i+1} ki+1lr

    对于最后一个old页面 k − l r k-l_r klr,发生miss的概率是 l r k − ( k − l r ) + 1 = l r l r + 1 \frac{l_r}{k-(k-l_r)+1}=\frac{l_r}{l_r+1} k(klr)+1lr=lr+1lr

    所以,对于第 r r r轮来说,发生miss的期望为2种造成cache miss的累加,即有:

    E = l r + l r k + l r k − 1 + l r k − 2 … … + l r l r + 1 = l r ( 1 + 1 k + 1 k − 1 + 1 k − 2 … … + 1 l r + 1 ) E=l_r+\frac{l_r}{k}+\frac{l_r}{k-1}+\frac{l_r}{k-2}……+\frac{l_r}{l_r+1}=l_r(1+\frac{1}{k}+\frac{1}{k-1}+\frac{1}{k-2}……+\frac{1}{l_r+1}) E=lr+klr+k1lr+k2lr+lr+1lr=lr(1+k1+k11+k21+lr+11)

    其中 1 k + 1 k − 1 + 1 k − 2 … … + 1 l r + 1 = H k − H l r \frac{1}{k}+\frac{1}{k-1}+\frac{1}{k-2}……+\frac{1}{l_r+1}=H_k-H_{l_r} k1+k11+k21+lr+11=HkHlr

    所以有 E = l r ( 1 + H k − H l r ) E=l_r(1+H_k-H_{l_r}) E=lr(1+HkHlr) l r H k l_rH_k lrHk,因为 H l r H_{l_r} Hlr≥1

    把所有的轮次加起来,有: E ( a l l r o u n d ) E(all round) E(allround) L H k LH_k LHk

    即marker算法的miss至多是 L H k LH_k LHk次,得证。

    3.2.2 最优离线算法的miss至少是 L / 2 L/2 L/2

    定理3-2:令L是总共的new元素的数目,则最优离线算法的miss至少是 L / 2 L/2 L/2

    证明如下(以参考文献【5】为基础,加上自己的理解):

    l r l_r lr为第 r r r轮(阶段)中new元素的个数。令 S O S_O SO为离线算法在cache中元素的集合;令 S M S_M SM为marker算法在cache中元素的集合,对于第 r r r轮来说,定义:

    d I = ∣ S O − S M ∣ d_I=|S_O-S_M| dI=SOSM在第 r r r开始时,offline算法和marker算法在cache中元素不同的个数;

    d F = ∣ S O − S M ∣ d_F=|S_O-S_M| dF=SOSM在第 r r r结束时,offline算法和marker算法在cache中元素不同的个数

    根据new元素的定义,我们知道,在每一轮开始的时候,cache中是肯定没有new元素的(如果有的话,就违反了new元素的定义)。而offline算法在每一轮开始时,在cache中有 d I d_I dI个与mark算法不同的元素,所以至少就有 l r − d I l_r-d_I lrdI个new元素不在offline的cache中,而new元素肯定是要发生miss的,所以offline算法至少有 l r − d I l_r-d_I lrdI个miss发生。

    offline算法还有一类cache miss,那就是对于每轮结束时。我们知道,marker算法在每轮结束时,标记缓存的内容是这轮期间请求的全部 k k k页,但是offline算法有 d F d_F dF个与marker算法不同,不同的地方肯定是要发生cache miss的,所以这种情况下offline算法至少发生 d F d_F dF个miss。

    将这两种情况加起来,对于第 r r r轮有:
    No. of misses ≥ m a x max max{ l r − d I l_r-d_I lrdI d F d_F dF} ≥ l r − d I + d F 2 \frac{l_r-d_I+d_F}{2} 2lrdI+dF

    我们又知道,第 r − 1 r-1 r1轮的 d F d_F dF和第 r r r轮的 d I d_I dI是相同的(因为此时cache的内容没有变),所以我们累加所有的轮次就有:

    No. of misses= ∑ r l r 2 \frac{\sum_{r}l_r}{2} 2rlr+ d F − d I 2 \frac{d_F-d_I}{2} 2dFdI ∑ r l r 2 \frac{\sum_{r}l_r}{2} 2rlr= L / 2 L/2 L/2

    这里 d F d_F dF是最后一轮的, d I d_I dI是第一轮的,都是常数,因此可以忽略。

    得证。

    3.2.3 The Marker algorithm is 2 H k 2H_k 2Hk-competitive.

    结合定理3-1和3-2,以及竞争性分析的概念,不难得出 Marker algorithm is 2 H k 2H_k 2Hk-competitive,即

    c ≤ L H k L / 2 = 2 H k c \le \frac{LH_k}{L/2}=2H_k cL/2LHk=2Hk

    3.3 对于Oblivious Adversary, Randomised Online Algorithms的竞争比是 Ω ( l o g k ) \Omega(log k) Ω(logk)

    3.3.1 Oblivious Adversary

    我们这里先引进一个概念,叫做adversary(敌手),其实我们上面一直避开了这个较为晦涩的词语。这里解释一下:
    我们之前讨论的确定性的在线算法,有一个缺点,即敌手算法总是知道在线算法在遇到某个实例时所采取的步骤,从而它可以邪恶地预设一个实例,使得在线算法陷入窘境。因而,人们提出了一种随机在线算法,它可以更好地对付敌手算法。所谓 随机算法 ,就是在执行过程中要做出随机选择的算法。显然marker算法就是这样一种随机算法。

    不过请注意,当我们设计一个随机在线算法时,必须说明允许敌手算法知道在线算法什么信息。根据知道信息的不同,根据参考文献【3】,主要分为3种:

    • Oblivious Adversary: The oblivious adversary has to generate a complete request sequence in advance, before any requests are served by the online algorithm. The adversary is charged the cost of the optimum offline algorithm for that sequence.
      忘记的对手必须事先生成一个完整的请求序列,然后由在线算法处理任何请求。忘记的对手将被收取该序列的最佳离线算法的费用。
    • Adaptive Online Adversary: This adversary may observe the online algorithm and generate the next request based on the algorithm’s (randomized) answers to all previous requests. The adversary must serve each request online, i.e., without knowing the random choices made by the online algorithm on the present or any future request.
    • Adaptive Offline Adversary: This adversary also generates a request sequence adaptively. However, it is charged the optimum offline cost for that sequence.

    本文不分析后面二种,只分析第一种Oblivious Adversary忘记的对手。包括前面mark算法的结论也都是针对忘记的对手 忘记的对手只知道这个序列,它不知道我们在线算法的策略,也没有办法去修改它的策略,在我们在线算法开始之后。

    关于对手论证,有下面一段话。其实仔细思考一下就又说明了竞争性分析中的≤符号和 Ω \Omega Ω中的≥符号的关系。
    在这里插入图片描述

    3.3.2 Randomised Online Algorithms的竞争比是 Ω ( l o g k ) \Omega(log k) Ω(logk)

    基于参考文献【3】【6】【7】,证明过程 :

    先介绍一下The Yao’s Minimax theorem,

    在这里插入图片描述
    注:inf是下界,sup是上界。

    其实这里是通过:
    在这里插入图片描述
    如果我们想求得随机在线算法的下界,就是求最优的确定算法在最坏的序列下的表现。也就是说,如果我们可以证明在一个分布 P P P上,即便是最差的序列,确定性的在线算法的竞争比是 Ω ( l o g k ) \Omega(log k) Ω(logk)或者 Ω ( H k ) \Omega(H_k) Ω(Hk),那么随机在线算法的竞争比也就是 Ω ( l o g k ) \Omega(log k) Ω(logk)或者 Ω ( H k ) \Omega(H_k) Ω(Hk)了。

    其实我还是不知道为什么要这么算?可能是我不了解Yao的Minimax理论。有时间再了解,假设自己先懂了

    如果我们把序列划分成不重叠的phrase,每个阶段中至多有 k k k个不同的元素,那么显然,每个阶段的最优离线算法只发生1次miss。那么,确定性算法发生多少次呢?

    确定性的在线算法的竞争比分析如下:
    如果我们的序列集合 S S S k + 1 k+1 k+1个不同的元素,cache size是 k k k,那么对于随机从 S S S中取出的每一个request,不在cache中的概率是 1 k + 1 \frac{1}{k+1} k+11,即发生miss的概率为 1 k + 1 \frac{1}{k+1} k+11。那么每一个阶段有多少request?

    我们已经知道,每个阶段中至多有 k k k个不同的元素,即根据彩票收集问题(Coupon Collector’s Problem),不难分析出每个阶段长度的期望 ( k + 1 ) H k (k+1)H_k (k+1)Hk,因为这相当于从 k + 1 k+1 k+1元素中挑选出 k k k个不同的元素的问题。具体:

    如果阶段的第一个元素从 S S S取一个不同于以前的元素概率为 k + 1 k + 1 \frac{k+1}{k+1} k+1k+1,次数为 k + 1 k + 1 \frac{k+1}{k+1} k+1k+1;第二个元素从 S S S取一个不同于以前的元素概率为 k k + 1 \frac{k}{k+1} k+1k,次数为 k + 1 k \frac{k+1}{k} kk+1;第 k k k个元素从 S S S取一个不同于以前的元素概率为 2 k + 1 \frac{2}{k+1} k+12,次数为 k + 1 2 \frac{k+1}{2} 2k+1,所以期望总共为:

    E = k + 1 k + 1 + k + 1 k + k + 1 k − 2 … … + k + 1 2 = ( k + 1 ) ( 1 k + 1 + 1 k + 1 k − 2 … … + 1 2 ) = ( k + 1 ) ( H k + 1 − 1 ) < ( k + 1 ) ( H k ) E=\frac{k+1}{k+1}+\frac{k+1}{k}+\frac{k+1}{k-2}……+\frac{k+1}{2}=(k+1)(\frac{1}{k+1}+\frac{1}{k}+\frac{1}{k-2}……+\frac{1}{2})=(k+1)(H_{k+1}-1)<(k+1)(H_{k}) E=k+1k+1+kk+1+k2k+1+2k+1=(k+1)(k+11+k1+k21+21)=(k+1)(Hk+11)<(k+1)(Hk),

    所以确定性算法发生了 ( k + 1 ) ( H k ) 1 k + 1 = H k (k+1)(H_{k})\frac{1}{k+1}=H_{k} (k+1)(Hk)k+11=Hk次,又由于每个阶段的最优离线算法只发生1次miss,所以Randomised Online Algorithms的竞争比是 Ω ( H k ) \Omega(H_k) Ω(Hk)

    注:感觉这里似乎推的有些问题,因为并非是≤号?感觉上面写错了很多地方。。。
    这里暂时先停下,确实没有想明白。

    参考文献【6】应该是写的最清楚的。有时间再看看吧,头疼。

    参考文献【8】也不错。

    参考文献

    【1】 运筹学_在线算法(中科院胡晓东)

    【2】CS787: Advanced Algorithms:Topic: Caching Algorithms

    【3】Competitive Online Algorithms: Susanne Albers

    【4】Stanford University — CS261: Optimization

    【5】CSL 758: Advanced Algorithms

    【6】Competitive Analysis of Paging: A Survey

    【7】Randomised Online Algorithms

    【8】Online Algorithms

    【9】CS880: Approximation and Online Algorithms 另外一种证明marker算法竞争分析的方法

    展开全文
  • 在线算法 & 离线算法

    千次阅读 2020-01-06 23:37:03
    在线算法设计 一.概念 离线算法: 算法设计策略都是基于在执行算法前输入数据已知的基本假设,也就是说,算法在求解问题已具有与该问题相关的完全信息,通常将这类具有问题完全信息前提下设计出的算法成为...

    在线算法 & 离线算法

    一.概念

    • 离线算法:
      算法设计策略都是基于在执行算法前输入数据已知的基本假设,也就是说,算法在求解问题已具有与该问题相关的完全信息,通常将这类具有问题完全信息前提下设计出的算法成为离线算法( off line algorithms)

    • 在线算法:

    1. 在计算机科学中,一个在线算法是指它可以以序列化的方式一个个的处理输入,也就是说在开始时并不需要已经知道所有的输入。
      相对的,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果。例如,选择排序在排序前就需要知道所有待排序元素,然而插入排序就不必。
    2. 因为在线算法并不知道整个的输入,对在线算法的研究主要集中在当前环境下怎么做出选择,在线算法找到的解只是局部最优解而无法保证整体最优。
    3. 对相同问题的在线算法和离线算法的对比分析形成了以上观点。如果想从其他角度了解在线算法可以看一下 流算法(关注精确呈现过去的输入所使用的内存的量),动态算法(关注维护一个在线输入的结果所需要的时间复杂度)和在线机器学习。

    二.对称移动算法:

    package util;
    
    /**
     * @projName: algorithm
     * @packgeName: util
     * @className: SymMoveLine
     * @author: pentiumCM
     * @email: 842679178@qq.com
     * @date: 2020/1/7 19:41
     * @describe: 对称移动算法-直线上的K服务问题
     */
    public class SymMoveLine {
        //直线上的k服务问题中:请求序列和服务车的位置使用横坐标点来表示
        /**
         * 初始化k个服务车的横坐标的序列,k服务车的序列是升序排列的
         *
         * @return 返回初始化后k个服务车的横坐标
         */
        public static int[] initServices() {
            int[] kServices = {1, 3};
            return kServices;
        }
    
        /**
         * 初始化服务请求序列的的横坐标
         *
         * @param n 服务请求序列的长度
         * @return 返回初始化后的服务请求序列的横坐标
         */
        public static int[] initRequests(int n) {
            int[] requests = new int[n];
            for (int i = 0; i < n; i++) {
                //给服务请求序列的奇数为赋值0,偶数位赋值1, 即服务请求序列为:0,1,0,1,0,1......
                requests[i] = (i % 2 == 0) ? 0 : 1;
            }
            return requests;
        }
    
        /**
         * 对称移动算法---解决直线上的k服务问题
         *
         * @param kServices k个服务车的横坐标
         * @param requests  服务请求序列的横坐标
         * @return 返回k个服务车移动的总距离
         */
        public static int symMoveAlgoLine(int[] kServices, int[] requests) {
            int dists = 0;
            int reqsNum = requests.length;
            int kServiceNum = kServices.length;
            for (int t = 0; t < reqsNum; t++) {
                int reqT = requests[t];
                int d = 0;
                //1. 所有的服务位于Rt的同一侧: 选距Xt最近的服务si向Rt移动距离 d = |si - Rt|
                //请求在最左边
                if (reqT < kServices[0]) {
                    //服务车1移动的距离为d
                    d = kServices[0] - reqT;
                    System.out.println("服务车位置移动 s1: " + kServices[0] + " -> " + reqT + " ; s2:不移动" + "  --移动了" + d);
                    //服务1移动到该请求的位置
                    kServices[0] = reqT;
                }
                //请求在最右边
                else if (reqT > kServices[kServiceNum - 1]) {
                    //服务车2移动的距离为d
                    d = kServices[kServiceNum - 1] - reqT;
                    System.out.println("服务车位置移动 s1:不移动 ; s2: " + kServices[kServiceNum - 1] + " -> " + reqT + "  --移动了" + d);
                    //最右边服务移动到该请求的位置
                    kServices[kServiceNum - 1] = reqT;
                }
                //2. 请求Rt位于服务si,sj之间: si、sj同时向Rt移动距离 d = min{|si - Rt, sj - Rt|}
                else {
                    for (int i = 0; i < kServiceNum - 1; i++) {
                        if (reqT > kServices[i] && reqT < kServices[i + 1]) {
                            int dl = Math.abs(kServices[i] - reqT);
                            int dr = Math.abs(kServices[i + 1] - reqT);
                            //左边服务靠请求更近
                            if (dl < dr) {
                                d = dl * 2;
                                int rposi = kServices[i + 1] - dl;
                                System.out.println("服务车位置移动 s1: " + kServices[i] + " -> " + reqT +
                                        " ; s2: " + kServices[i + 1] + " -> " + rposi + "  --移动了" + d);
                                //左边的服务移动请求的位置
                                kServices[i] = reqT;
                                //右边的服务向请求移动d
                                kServices[i + 1] -= dl;
                            }
                            //右边服务靠请求近
                            else if (dr > dr) {
                                d = dr * 2;
                                int lposi = kServices[i] + dl;
                                System.out.println("服务车位置移动 s1: " + kServices[i] + " -> " + lposi +
                                        " ; s2: " + kServices[i + 1] + " -> " + reqT + "  --移动了" + d);
    
                                //左边的服务移动请求的位置
                                kServices[i] += dr;
                                //右边的服务向请求移动d
                                kServices[i + 1] = reqT;
                            }
                            //两边服务靠请求一样近
                            else {
                                d = dl + dr;
                                System.out.println("服务车位置移动 s1: " + kServices[i] + " -> " + reqT +
                                        " ; s2: " + kServices[i + 1] + " -> " + reqT + "  --移动了" + d);
                                //左边的服务移动请求的位置
                                kServices[i] = reqT;
                                //右边的服务移动请求的位置
                                kServices[i + 1] = reqT;
                            }
                        }
                    }
                }
                dists += d;
            }
            return dists;
        }
    
        public static void main(String[] args) {
            //初始化k服务车的初始横坐标
            int[] kServices = initServices();
    
            //请求序列的横坐标
            int[] requests = initRequests(10);
    
            //调用对称移动算法,获取服务车移动的总距离
            int dist = symMoveAlgoLine(kServices, requests);
    
            System.out.println("移动的总距离为:" + dist);
        }
    }
    
    
    展开全文
  • 算法在线演示工具

    2018-05-20 16:20:52
    1、基于HTML5 2、在线创建图,以xml轻量方式保存 3、在线演示常见的遍历、最小生成树等算法 4、可用于课堂辅助教学和自主学习
  • 在线算法和离线算法

    千次阅读 2018-08-27 19:41:09
    算法设计策略都是基于在执行算法前输入数据已知的基本假设,也就是说,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果,通常将这类具有问题完全信息前提下设计出的...

    离线算法

    算法设计策略都是基于在执行算法前输入数据已知的基本假设,也就是说,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果,通常将这类具有问题完全信息前提下设计出的算法成为离线算法( off line algorithms)

     

    例题可供参考

    http://blog.csdn.net/xj2419174554/article/details/10238557

    http://blog.csdn.net/xj2419174554/article/details/9567989

    在线算法

    在计算机科学中,一个在线算法是指它可以以序列化的方式一个个的处理输入,也就是说在开始时并不需要已经知道所有的输入。相对的,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果。例如,选择排序在排序前就需要知道所有待排序元素,然而插入排序就不必。

    因为在线算法并不知道整个的输入,所以它被迫做出的选择最后可能会被证明不是最优的,对在线算法的研究主要集中在当前环境下怎么做出选择。对相同问题的在线算法和离线算法的对比分析形成了以上观点。如果想从其他角度了解在线算法可以看一下 流算法(关注精确呈现过去的输入所使用的内存的量),动态算法(关注维护一个在线输入的结果所需要的时间复杂度)和在线机器学习。

     

    转自:http://blog.csdn.net/xiaofengcanyuexj

    展开全文
  • 在线算法和离线算法的概念(转)

    千次阅读 2018-07-25 15:44:33
    一、在线算法  在计算机科学中,一个在线算法是指它可以以序列化的方式一个个的处理输入,也就是说在开始时并不需要已经知道所有的输入。相对的,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在...
  • 辨析离线算法与在线算法

    千次阅读 2017-04-23 15:52:49
    离线算法算法设计策略都是基于在执行算法前输入数据已知的基本假设,也就是说,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果,通常将这类具有问题完全信息
  • 基于Jupyter在线算法webIDE开发工具

    千次阅读 多人点赞 2019-07-23 11:40:52
    Jupyter作为开源的项目,可以基于Jupyter二次开发在线算法webIDE。建议基于插件的方式改造Jupyter代码,这样也方便升级。 1.Jupyter文件格式ipynb Jupyter Notebook新建文件和运行代码都要以.ipynb为后缀的JSON...
  • 浅谈LCA的在线算法ST表

    千次阅读 2016-09-15 15:50:06
    求LCA(最近公共祖先)的算法有好多,按在线和离线分为在线算法和离线算法。 离线算法有基于搜索的Tarjan算法比较好,而在线算法则是基于dp的ST算法比较好。 这次先讲一下ST算法。 这个算法是基于RMQ(区间最大...
  • 提出融合遮挡感知的在线Boosting跟踪算法,该算法对跟踪结果实时进行遮挡检测,根据检测结果自适应调整分类器更新策略。该方式能够有效维护分类器特征池的纯净,提高算法在遮挡环境下的顽健性。实验结果表明,与传统...
  • LCA在线算法ST算法

    万次阅读 多人点赞 2014-11-07 08:47:49
    求LCA(最近公共祖先)的算法有好多,按在线和离线
  • 在线算法学习网站

    万次阅读 2016-12-29 02:38:46
    近日发现一个国外学习算法的网站,支持在线编程还能发帖讨论,有空闲时可以玩一玩。 网址:https://leetcode.com/ 网址每天会收录不少题目,看样子挺活跃。courses里面有一些题目练手,比如: 移除重复数据 给定一...
  • 针对LM算法不能在线训练RBF网络以及RBF网络结构设计算法中存在的问题,提出一种基于LM算法在线自适应RBF网络结构优化算法.该算法引入滑动窗口和在线优化网络结构的思想,滑动窗口的引入既使得LM算法能够在线训练RBF...
  • 通过分析标准DTW及其主要衍生算法,对DTW算法的数据结构进行改进以满足在线算法要求,在寻找最佳路径过程中动态连续地分配和释放内存或预先分配固定大小的内存,并将多个关键词的DTW计算分布到多个运算单元;...
  • 在线编程——排序算法总结

    千次阅读 2018-05-23 16:12:18
    在线编程——排序算法总结  找实习,阿里一面遇到手写快排,写出来感觉没错(VS2013能通过),但在阿里的测试平台上运行未通过。细思极恐,赶紧总结一波。有幸看到SteveWang的两篇博客:排序算法总结(1)与排序...
  • 在线考试系统中,自动组卷系统是关键的部分,而自动组卷系统的性能主要取决于组卷算法。文章在分析各种组卷算法的基础上,提出了一种基于遗传算法的组卷算法,文中对组卷算法进行了详细的设计,对编码结构、交叉算子和...
  • 在线协作编辑算法简介- OT算法

    千次阅读 2020-11-14 19:55:07
    今天主要为大家揭开在线协作的神秘面纱,那就是OT算法。 0x01 背景 在线文档,抽象一下,这些产品的模式都是富文本编辑器+后台,富文本编辑器产生内容,展示内容,然后后台负责保存。富文本编辑器现在业界已经有很...
  • 算法基础 - RMQ-ST算法(在线算法)

    千次阅读 2016-05-18 02:23:43
    RMQ问题 在线算法 离线算法 ST Sparse Table 算法 预处理数据 查询区间 完成代码如下RMQ问题RMQ(Range Minimum/Maximum...在线算法说来惭愧,到现在才刚开始清楚说的在线算法和离线算法是什么意思,所谓在线算法就是说
  • matlab经典算法的程序源码 数学建模算法汇总资料: matlab经典算法的程序源码 十大算法讲义.pdf 排队模型.pdf 数学建模算法全收录.pdf ...附录二 Matlab在线性代数中的应用.pdf 附录四 判别分析.pdf
  • 在线算法和离线算法的概念

    千次阅读 2013-10-08 20:27:00
    一、在线算法  在计算机科学中,一个在线算法是指它可以以序列化的方式一个个的处理输入,也就是说在开始时并不需要已经知道所有的输入。相对的,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在...
  • 七月算法-算法结构教程全集 全集一共16个PDF教程,对算法结构进行了详细的讲解
  • 在线算法 online algorithm在线算法 online algorithm
  • Matlab常用算法大集合: Floyd算法.rar 免疫算法.rar 分治算法.rar 动态规划.rar 图论.rar 学习路线.png 搜索算法.rar 概率算法.rar 模拟退火算法.rar ...附录二 Matlab在线性代数中的应用.pdf 附录四 判别分析.pdf
  • 通过SM3算法杂凑用户原始密钥形成新的密钥,将新密钥作为SM4加密算法的密钥。 系统采用Spring MVC开发,其中使用了artery(封装了spring),兼容spring。
  • 这篇帖子,就以推荐引擎产品上的离线算法和在线算法给大家说明下,并且方便后续如果在产品使用中如果发现通用的计算规则不符合自己的场景的时候,需要做一些优化的时候,也能更好地指导怎么调。 如果是最开始的怎么...
  • 算法在没有中央拍卖人的情况下分配或拍卖资源。
  • 主要介绍了基于C++的拼多多算法在线笔试题,列举了四个拼多多的算法笔试题,包括分治法、大数相乘、贪心算法以及迷宫问题,需要的朋友可以参考下
  • 在线学习算法(Online Learning)理论与实践

    万次阅读 多人点赞 2018-11-08 21:17:38
    本文主要介绍Online Learning的基本原理和两种常用的Online Learning算法:FTRL(Follow The Regularized Leader)[1]和BPR(Bayesian Probit Regression)[2],以及Online Learning在美团移动端推荐重...
  • Tarjan算法适用于离线批量处理多个查询请求。基本思想是以深度优先搜索的顺序访问这颗树,给这棵树的结点染色,一开始所有结点都是白色的,而当第一次经过某个结点的时候,将它染成灰色,而当第二次经过这个结点的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 272,452
精华内容 108,980
关键字:

在线算法