精华内容
下载资源
问答
  • 发现自己对背包问题还是情有独钟嘛, 毕竟它也算上是我真正学到第一个算法。哎,现在我还是一个苦命挣扎菜鸟。废话也不多说了,下面进入正题吧,这些都是菜鸟在刷背包题遇到基础问题,作为菜鸟我就是刷...
    发现自己对背包问题还是情有独钟的嘛, 毕竟它也算的上是我真正学到的第一个算法。哎,现在我还是一个苦命挣扎的菜鸟。废话也不多说了,下面进入正题吧,这些都是菜鸟在刷背包题遇到的基础问题,作为菜鸟的我就是刷这些题一步一步理解背包的。
    

    01背包问题——Bone Collector HDU - 2602
    (我喜欢叫它基础背包,下面我都用基础背包叫它了)。
    就不复制英文题目了,简单说一下意思,就是有个怪人,很喜欢收集骨头,然后有一堆不同的骨头,每个骨头有不同的价值和体积,你得用一个容量为V的背包尽可能地去装满一袋最大价值的骨头。
    输入:
    有T个案列,输入骨头数N,和袋子的容量V(N<=1000,V<=1000),然后输入一行骨头价值,一行体积。
    至于思路问题好像真没什么说的,感觉就是套模板。
    这个可以简化成基础背包问题,问题描述是这样的:

    有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
    

    然后对比一下,发现其实就是名词变了而已,那么直接写出模板来。它的状态转移公式为f[i][j] = max( f[i-1][j], f[i-1][j-w[i]] + v[i] )。

    对于初学的来说,这个还真难理解,作为菜鸟的我也花了两三天才真正弄懂这公式。不解的可以看看我的另一篇博客对基础背包的公式理解,不过这篇是当时理解灵感来的时候写好的,感觉没有写好,不懂再去翻翻大佬的博客去吧,毕竟我也是个菜鸟╮( •́ ₃•̀ )╭

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1010;
    //用结构体为了绑定每一件物品的价值与体积,直接用两个数组也可以。
    struct Pack
    {
        int cost;
        int val;
    };
    //f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。 用于状态转移的重要函数。
    int f[maxn][maxn];
    int main()
    {
        int t, n, m;
        pack a[maxn];
        cin>>t;
        while(t--)
        {
            memset(f, 0, sizeof(f));
            cin>>n>>m;
            for(int i=1;i<=n;i++)
                cin>>a[i].val;
            for(int i=1; i<=n;i++)
                cin>>a[i].cost;
    
        //两个循环可能看得有点蒙蔽,不过一般用到二维数组都是要两个循环的嘛,第一个是遍历每件物品用的,第二个j循环是表示当前物品放入一个j容量的背包。符合f[][]子问题定义嘛。
            for(int i=1; i<=n; i++)
            for(int j=0; j<=m;j++)
            {
                //有j-a[i].cost在,故而要判断一下,这个也可以不用判断,把j的范围改一下就可以,自己想一下吧。
                if(j >= a[i].cost) f[i][j] = max(f[i-1][j], f[i-1][j-a[i].cost]+a[i].val);
                else f[i][j] = f[i-1][j];
            }
    //跟据子问题定义的f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
    就能推出最大价值的状态为f[n][m],理解很容易,替换一下子母i,v就行了。
            cout<<f[n][m]<<endl;
        }
        return 0;
    }

    这只是一个最简单的,为了优化空间,我们得用到一维数组来写代码。
    这个是基础背包模板代码:

    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 1010
    struct Pack
    {
        int cost;
        int weight;
    }a[maxn];
    int f[maxn], V;
    //核心的循环,而且通用,于是做成函数,以便直接调用了,说的这句话是后话, 不懂看我刚才说的那篇博客吧。
    void Basepack(int cost, int weight)
    {
        for(int v=V; v>=cost; v--)
            f[v] = max(f[v], f[v-cost]+weight);
    }
    int main()
    {
        int t, n;
        cin>>t;
        while(t--)
        {
            cin>>n>>V;
            for(int i=1; i<=n; i++) cin>>a[i].weight;
            for(int i=1; i<=n; i++) cin>>a[i].cost;
    
            memset(f, 0, sizeof(f));
            for(int i=1; i<=n; i++)
                Basepack(a[i].cost, a[i].weight);
            //f[i]代表着把东西装入容量为i的背包里的最大价值,然后自然就知道输出f[V]咯。
            cout<<f[V]<<endl;
        }
        return 0;
    }

    好了这是最基础的基础背包,下面就开始讲解完全背包吧。
    完全背包问题——Piggy-Bank HDU - 1114
    不想浪费我的时间与博客空间了,就直接写输入格式了,其他自己点开链接翻译吧。
    输入:
    有T个案列,钱罐的开始与最后的重量为E和F,下面有n中硬币,可以无限取,n行是硬币的价值与重量。

    求钱罐里最少数目的钱。
    我的代码直接用一维数组了,就是个完全背包的模板,没怎么去看二维的代码,因为用到三个循环真是太麻烦了!
    基础背包公式:f[i][j] = max( f[i-1][j], f[i-1][j-w[i]] + v[i] )。
    完全背包公式:f[i][j] = max(f[i-1][j], f[i - 1][j - k*w[i] ] + k*v[i] );
    很类似吧!因为物品无限嘛,得有个k值一个一个取同种物品。
    二维转一维同基础背包的一维公式一样
    f[v] = max(f[v], f[v-cost]+weight)
    数学思维看问题,不多说了,哎,真是恐怖的数学思维!
    来吧看模板代码吧!

    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 10010
    //求最小值,则f的初始化不能为0了,而是为无穷的,当然程序里是没有无穷大的,就定一个很大的数了。
    #define INF 0x3f3f3f3f
    struct Pack
    {
        int cost;
        int weight;
    }p[maxn];
    int f[maxn], V;
    //与上一个基础背包的模板很类似,因为完全背包每种物品无限个,于是乎是从一个开始取该物品到k个为止,然后呢也就是用它自身的前状态推出后一个状态,所以v是顺循环的。唔我的博客还没有这段讲解,以后补上吧。
    void Competepack(int cost, int weight)
    {
        for(int v=cost; v<=V; v++)
            f[v] = min(f[v], f[v-cost]+weight);
    }
    int main()
    {
        int t, E, F, n;
        cin>>t;
        while(t--)
        {
            cin>>E>>F;
        //V相当于是背包的总容量
            V = F-E;
            memset(f, INF, sizeof(f));
         //动态规划的初始化很微妙,稍微不注意就可能出错!f还得有一个为0,不然可以看
            f[0] = 0;
            cin>>n;
            for(int i=1; i<=n; i++)
            {
                //很巧妙的输入操作,每次遍历都是访问i=1的状态值,不会影响i=2或则i=-1所以就直接在此处输入也行,因为他只会访问a[i]的值,但不访问a[i+1]或者其他的值。
                cin>>p[i].weight>>p[i].cost;
                Competepack(p[i].cost, p[i].weight);
            }
            //发现当容量为V的最小价值为INF呵呵呵,就不行了,INF定义为无穷大嘛,都无穷大的价值了,这不可能是最小价值的,所以是没有成立的条件了。
            if(f[V] == INF)cout<<"This is impossible."<<endl;
            else cout<<"The minimum amount of money in the piggy-bank is "<<f[V]<<"."<<endl;
    
        }
        return 0;
    }

    完全背包这里还是没讲出感觉,哎不管了就这样吧,不懂的就敲几遍代码尝试理解吧!《背包九讲》真心不错,有空就看看,感觉为它打了很多次广告。。。。。。
    博客写到这里太长了,就分两篇写吧,谔谔,也是算是偷懒了,下次把后面的补上,下一篇我来讲解多重背包 和 多重背包与完全背包的混合使用的两个简单而经典的题目。

    哎,越到后面的背包,我讲得越简单模糊,毕竟是入门菜鸟初学没多久,望各位别介意哈......
    
    展开全文
  • 接收自己的一开始的做...作为一个有四五年工作经验的java程序员,并且查了资料以后发现网上有很多例子程序,我开始想当然的认为,这样一个简单的函数调用任何问题,能够很快就实现了。 但是真正开始做的时候,才发...

    接收自己的一开始的做不好,认识到自己现在所处的周期的低谷,才能有更好的心态,才有持续做下去的动力。

    昨天工作上遇到一个技术问题,就是在编写java程序时,需要调用别人提供的动态链接库dll里的函数来进行一些运算。

    作为一个有四五年工作经验的java程序员,并且查了资料以后发现网上有很多例子程序,我开始想当然的认为,这样一个简单的函数调用任何问题,能够很快就实现了。

    但是真正开始做的时候,才发现按照网上的教程根本就做不出来。然后自己又查了一些资料,包括看官方网站的一些文档,折腾了大概有半天的时间,还是没有搞定。

    是自己就有一些气馁了,我想,这样一个简单的问题,怎么会让我一个有这么多工作经验的人处理起来,还觉得有难度呢。这个时候,自己的元认知能力又被调动起来。我突然意识到,我的那么多的工作经验是关于java程序的,但对于java如何调用dll里面的函数,这方面的经验,自己是零。所以不能假想着自己在这方面很有经验,处理起这方面的问题,也像处理别的问题一样那么顺利。在java调用dll函数这方面,自己才刚刚开始,所以一定要接受自己一开始做不好,接受自己所处的周期的低谷的状态。

    于是,我要调整好自己的心态,塌下心来,一点一点理解程序和文档,最终又花了几个小时的时间,就把原来认为很难的问题给解决了。

    展开全文
  • 前些天的电话面试,在交谈中她有讲到关于IE6双倍间距的真正原因,当时自己隐约知道是由于Float影响的,记得以前做过的时候就遇 到这个问题,通过display:inline解决,这个是我在网上找到的答案,平时也没关注这个...
         前些天的电话面试,在交谈中她有讲到关于IE6双倍间距的真正原因,当时自己隐约知道是由于Float影响的,记得以前做过的时候就遇 到这个问题,通过display:inline解决,这个是我在网上找到的答案,平时也没关注这个问题,所以也不能很好的回答这个问题。
     
       电话面试完了以后,我才认真思考了,想在网上看看有什么文章不,发现很难找到,索性我就自己动手用记事本先做个例子试试看问题所在。具体如下:
        Demo1:
    ExpandedBlockStart.gif代码
    <!doctype html>
    <html>
    <head>
    <meta http-equiv="Content-Type" content="text/html;charset=gb2312">
    <title>http://blog.sina.com.cn/xiongyongpengpai</title>
    <style>*{marign:0;padding:0;border:0;}
    #a{width:300px;height:100px;border:1px;background
    -color:#006699;}
    .b{width:60px;height:60px;background
    -color:red;border:1px solid #000;margin-left:50px; }
    </style></head>
    <body>
    <div id="a">
        
    <div class="b"></div>
    </div>
    </body>
    </html>

        IE6显示结果:

        继续添加属性:给class="b"的div上加上float:left;结果就变成了这样:

        从这个例子上面可以看出是float影响的,当添加display:inline;结果是:


    当代码进行改变为:
    Demo2:
    ExpandedBlockStart.gif代码
    <!doctype html>
    <html>
    <head>
    <meta http-equiv="Content-Type" content="text/html;charset=gb2312">
    <title>http://blog.sina.com.cn/xiongyongpengpai</title>
    <style>
    *{marign:0;padding:0;border:0;}
    #a{width:300px;height:100px;border:1px;background
    -color:#006699;}
    .b{width:60px;height:60px;background
    -color:red;border:1px solid #000;margin-left:50px; display:inline;}
    </style></head>
    <body>
    <div id="a">
        
    <div class="b"></div><div class="b"></div>
    </div>
    </body>
    </html>



    效果显示为:


    从图片上可以看出,class="b"并未显示。当在b上面添加float:left;的时候才显示为:


        所以可以看出flaot和display之间有不同寻常的关系;于是我查下css 2.0API关于float和display的属性描述:
       
        float版本:CSS1  兼容性:IE4+ NS4+ 继承性:无
        语法:
        float : none | left | right
        取值:
        none : 默认值。对象不飘浮
        left : 文本流向对象的右边
        right : 文本流向对象的左边
        说明:
        该属性的值指出了对象是否及如何浮动。请参阅 clear 属性。
        当该属性不等于 none 引起对象浮动时,对象将被视作块对象( block-level ),即 display 属性等于  block 。也就是说,浮动对象的 display 属性将被忽略。
        跟随浮动对象的对象将移动到浮动对象的位置。浮动对象会向左或向右移动直到遇到边框( border 、内补丁( padding 、外补丁( margin 或者另一个块对象( block-level )为止。
        在IE5+中, divspan 对象假如没有指定宽度会被分配默认的宽度,而在此前的浏览器版本中则必须指定宽度值才可以呈递此属性。
        此属性对于 currentStyle 对象而言是只读的。对于其他对象而言是可读写的。
        对应的脚本特性为 styleFloat

        display版本:CSS1/CSS2  兼容性:IE4+ NS4+ 继承性:有
        语法:
        display : block | none | inline | compact | marker | inline-table | list-item | run-in | table | table-caption | table-cell | table-column | table-column-group | table-footer-group | table-header-group | table-row | table-row-group
        取值:
        block : CSS1 块对象的默认值。将对象强制作为块对象呈递,为对象之后添加新行
        none : CSS1 隐藏对象。与 visibility 属性的hidden值不同,其不为被隐藏的对象保留其物理空间
        inline : CSS1 内联对象的默认值。将对象强制作为内联对象呈递,从对象中删除行
        inline-block : IE5.5 将对象呈递为内联对象,但是对象的内容作为块对象呈递。旁边的内联对象会被呈递在同一行内
        compact : CSS2 未支持。分配对象为块对象或基于内容之上的内联对象
        marker : CSS2 未支持。指定内容在容器对象之前或之后。要使用此参数,对象必须和 :after:before 伪元素一起使用
        inline-table : CSS2 未支持。将表格显示为无前后换行的内联对象或内联容器
        list-item : CSS2 将块对象指定为列表项目。并可以添加可选项目标志
        run-in : CSS2 未支持。分配对象为块对象或基于内容之上的内联对象
        table : CSS2 未支持。将对象作为块元素级的表格显示
        table-caption : CSS2 未支持。将对象作为表格标题显示
        table-cell : CSS2 未支持。将对象作为表格单元格显示
        table-column : CSS2 未支持。将对象作为表格列显示
        table-column-group : CSS2 未支持。将对象作为表格列组显示
        table-header-group : CSS2 将对象作为表格标题组显示
        table-footer-group : CSS2 将对象作为表格脚注组显示
        table-row : CSS2 未支持。将对象作为表格行显示
        table-row-group : CSS2 未支持。将对象作为表格行组显示
        说明:
        设置或检索对象是否及如何显示。
        对于下列元素来说,此属性的默认值为 block
        ADDRESS QUOTE BODY XMP CENTER COL COLGROUP DD DIR DIV DL DT FIELDSET FORM Hn HR IFRAME LEGEND LISTING MARQUEE MENU OL P PLAINTEXT PRE TABLE TD TH TR UL

        对于下列元素来说,此属性的默认值为 none
        BR FRAME nextID TBODY TFOOT THEAD

        对于下列元素来说,此属性的默认值为 list-item
        LI

        其他元素默认值都是 inline
        在IE6.0以前的版本中, LI 对象的默认值为 block
        在IE4.0中, blockinlinelist-item 值不被支持。但是对象仍然会被呈递。
        在IE5.0中开始支持 blockinline
        在IE5.5中开始支持 inline-block 。你可以使用 inline-block 使对象获得布局而无需指定确切的高( height )和宽( width )。
        在IE6.0中开始支持 list-item
        所有可视的文档对象都是块对象(block element)或者内联对象(inline element)。例如, div 是一个块对象。 span 是一个内联对象。块对象的特征是从新的一行开始且能包含其他块对象和内联对象。内联对象被呈递时不会从新行开始,能够包含其他内联对象和数据。
    改变此属性值对其周围内容布局的影响可能是:
    • 在属性值设为 block 的对象后面添加新行。
    • 从属性值设为 inline 的对象中删除一行。
    • 隐藏属性值设为 none 的对象并释放其在文档中的物理空间。
        table-header-grouptable-footer-group 属性值可用来指定当表格( table )跨越了多页时, tHeadtFoot 对象的内容在每一页都显示。
        此属性对于 currentStyle 对象而言是只读的。对于其他对象而言是可读写的。
        对应的脚本特性为display

        了解了这两个cssstyle,我对内联和块元素有所了解了,float:left;(左浮动)它使得指定元素脱离普通的文档流而产生的特别的布局特性。 并且float必需应用在块级元素之上,也就是说浮动并不应用于内联标签。或换句话来说当应用了float那么这个元素将被指定为块级元素;内联 (display:inline;)元素不能配置宽高,因为内联属于行布局,其特性是在一行里进行布局,所以不能被设定宽高。
       

    网站查找资源:

        Relationships between 'display', 'position', and 'float'

    The three properties that affect box generation and layout — 'display' , 'position' , and 'float' — interact as follows:

    1. If 'display' has the value 'none', then 'position' and 'float' do not apply. In this case, the element generates no box.
    2. Otherwise, if 'position' has the value 'absolute' or 'fixed', the box is absolutely positioned, the computed value of 'float' is 'none', and display is set according to the table below. The position of the box will be determined by the 'top' , 'right' , 'bottom' and 'left' properties and the box's containing block.
    3. Otherwise, if 'float' has a value other than 'none', the box is floated and 'display' is set according to the table below.
    4. Otherwise, if the element is the root element, 'display' is set according to the table below.
    5. Otherwise, the remaining 'display' property values apply as specified.
    Specified value Computed value
    inline-table table表
    inline, run-in, table-row-group, table-column, table-column-group, table-header-group, table-footer-group, table-row, table-cell, table-caption, inline-block block块
    others same as specified

        地址:http://translate.googleusercontent.com/translate_c?hl=zh-CN&ie=UTF-8&sl=en&tl=zh-CN&u=http://www.w3.org/TR/CSS2/visuren.html&prev=_t&rurl=translate.google.com.hk&usg=ALkJrhiU6qNxZYxywoVYVZnRjVQ4WEqq8w#dis-pos-flo
        用google翻译了一下:
       flaot,position,display之间的关系
    这三个属性和布局产生影响框生成和显示'
    'display' , 'position' , and 'float'- 互动如下:

    如果'display' 的值'none',然后'position''float'并不适用。在这种情况下,生成的元素没有
    否则,如果
    'position'的值'absolute''fixed',箱子是绝对定位,计算值'float'是'none',显示设置根据下表。框的立场将取决于 'top' , 'right' , 'bottom''left' 的属性和框的包含块。
    否则,如果
    'float'的值不是'none',这个盒子是浮动和'display'都是根据下表。
    否则,如果该元素是根元素,
    'display'都是根据下表。
    否则,剩下的
    'display'申请成为指定的属性值。

    现在看完这些内容,大家对flaot,display和position对box快元素的影响了吧。

    转载于:https://www.cnblogs.com/fighting_cp/archive/2010/08/11/web_IE6_fighting_cp.html

    展开全文
  • 你必须知道495个C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    难道在C语言中结构不能包含指向自己的指针吗? 1.15 如何定义一对相互引用的结构? 1.16 Struct{ }x1;和typedefstruct{ }x2;这两个声明有什么区别? 1.17 “typedefint(*funcptr)();”是什么意思? const...
  • 《你必须知道495个C语言问题

    热门讨论 2010-03-20 16:41:18
    你难免会遇到各种各样的问题,有些可能让你百思不得其解,甚至翻遍图书馆,也找不到问题的答案。 《你必须知道的495个C语言问题》的出版填补了这一空白。许多知识点的阐述都是其他资料中所没有的,弥足珍贵。 涵盖...
  • 难道在C语言中结构不能包含指向自己的指针吗? 7  1.15 如何定义一对相互引用的结构? 9 1.16 Struct{ } x1;和typedef struct{ } x2; 这两个声明有什么区别? 10 1.17 “typedef int(*funcptr)();”是什么...
  • 你必须知道495个C语言问题(PDF)

    热门讨论 2009-09-15 10:25:47
    难道在C语言中一个结构不能包含指向自己的指针吗? . . . . 3 1.7 怎样建立和理解非常复杂的声明?例如定义一个包含N 个指向返 回指向字符的指针的函数的指针的数组? . . . . . . . . . . . . . . 3 1.8 函数只定义...
  • 我通过实际工作中一个例子,讲解 zookeeper 是如何帮我解决分布式问题,以此引导大家发现自己系统中可以应用 zookeeper 场景。真正把 zookeeper 使用起来!项目...

    我通过实际工作中的一个例子,讲解 zookeeper 是如何帮我解决分布式问题,以此引导大家发现自己系统中可以应用 zookeeper 的场景。真正把 zookeeper 使用起来!


    项目背景介绍

    首先给大家介绍一下本文描述项目的情况。这是一个检索网站,它让你能在几千万份复杂文档数据中检索出你所需要的文档数据。为了加快检索速度,项目的数据分布在 100 台机器的内存里,我们称之为数据服务器。除了数据,这 100 台机器上均部署着检索程序。这些 server 之外,还有数台给前端提供接口的搜索 server,这些机器属一个集群,我们称之为检索服务器。当搜索请求过来时,他们负责把搜索请求转发到那 100 台机器,待所有机器返回结果后进行合并,最终返回给前端页面。结构如下图:

    面临问题

    网站上线之初,由于数据只有几百万,所以数据服务器只有 10 多台。是一个规模比较小的分布式系统,当时没有做分布式系统的协调,也能正常工作,偶尔出问题,马上解决。但是到了近期,机器增长到 100 台,网站几乎每天都会出现问题,导致整个分布式系统挂掉。问题原因如下:

    数据服务器之前没有做分布式协调。对于检索服务器来说,并不知道哪些数据服务器还存活,所以检索服务器每次检索,都会等待 100 台机器返回结果。但假如 100 台数据服务中某一台死掉了,检索服务器也会长时间等待他的返回。这导致了检索服务器积累了大量的请求,最终被压垮。当所有的检索服务器都被压垮时,那么网站也就彻底不可用了。

    问题的本质为检索服务器维护的数据服务器列表是静态不变的,不能感知数据服务器的上下线。

    在 10 台数据服务器的时候,某一台机器出问题的概率很小。但当增长到 100 台服务器时,出问题的概率变成了 10 倍。所以才会导致网站几乎每天都要死掉一次。

    由于一台机器的问题,导致 100 台机器的分布式系统不可用,这是极其不合理,也是无法忍受的。

    之前此项目的数据和检索不由我负责。了解到此问题的时候,我觉得这个问题得立刻解决,否则不但用户体验差,而且开发和运维也要每天疲于系统维护,浪费了大量资源,但由于还有很多新的需求在开发,原来的团队也没时间去处理。今年我有机会来解决这个问题,当时正好刚刚研究完 zookeeper,立刻想到这正是采用 zookeeper 的典型场景。

    如何解决

    我直接说方案,程序分为数据服务器和检索服务器两部分。

    数据服务器:

    1、每台数据服务器启动时候以临时节点的形式把自己注册到 zookeeper 的某节点下,如 / data_servers。这样当某数据服务器死掉时,session 断开链接,该节点被删除。

    检索服务器:

    1、启动时,加载 / data_servers 下所有子节点数据,获取了目前所有能提供服务的数据服务器列表,并且加载到内存中。

    2、启动时,同时监听 / data_servers 节点,当新的数据 server 上线或者某个 server 下线时,获得通知,然后重新加载 / data_servers 下所有子节点数据,刷新内存中数据服务器列表。

    通过以上方案,做到数据服务器上下线时,检索服务器能够动态感知。检索服务器在检索前,从内存中取得的数据服务器列表将是最新的、可用的。即使在刷新时间差内取到了掉线的数据服务器也没关系,最多影响本次查询,而不会拖垮整个集群。见下图:

    代码讲解

    捋清思路后,其实代码就比较简单了。数据服务器只需要启动的时候写 zookeeper 临时节点就好了,同时写入自己服务器的相关信息,比如 ip、port 之类。检索无服务器端会稍微复杂点,不过此处场景和 zookeeper 官方给的例子十分符合,所以我直接参考官方例子进行修改,实现起来也很简单。关于官方例子我写过两篇博文,可以参考学习:

    • zookeeper 官方例子翻译:https://blog.csdn.net/liyiming2017/article/details/83275882

    • zookeeper 官方例子解读:https://blog.csdn.net/liyiming2017/article/details/83276706

    数据服务器

    数据服务器程序十分简单,只会做一件事情:启动的时候,把自己以临时节点的形式注册到 zookeeper。一旦服务器挂掉,zookeeper 自动删除临时 znode。

    我们创建 ServiceRegister.java 实现 Runnable,数据服务启动的时候,单独线程运行此代码,实现注册到 zookeeper 逻辑。维系和 zookeeper 的链接。

    检索服务器

    检索服务器,代码设计完全采用官方案例,所以详细的代码解读请参考上面提到的两篇文章,这里只做下简述。

    代码有两个类 DataMonitor 和 LoadSaidsExecutor。LoadSaidsExecutor 是启动入口,他来启动 DataMonitor 监控 zookeeper 节点变化。DataMonitor 负责监控,初次启动和发现变化时,调用 LoadSaidsExecutor 的方法来加载最新的数据服务器列表信息。

    DataMonitor 和 LoadSaidsExecutor 的工作流程如下:

    1. Excutor 把自己注册为 DataMonitor 的监听

    2. DataMonitor 实现 watcher 接口,并监听 znode

    3. znode 变化时,触发 DataMonitor 的监听回调

    4. 回调中通过 ZooKeeper.exist() 再次监听 znode

    5. 上一步 exist 的回调方法中,调用监听自己的 Executor,执行业务逻辑 6

    6. Executor 启动新的线程加载数据服务器信息到内存中

    注意:图为以前文章配图。图里应该把 6,7 步改为文字描述的第 6 步。

    检索服务启动的时候,单独线程运行 LoadSaIdsExecutor。LoadSaIdsExecutor 会阻塞线程,转为事件驱动。

    总结

    我们通过一个例子,展示了 zookeeper 在实际系统中的应用,通过 zookeeper 解决了分布式系统的问题。其实以上代码还有很大的优化空间。我能想到如下两点:

    1、数据服务器会假死或者变慢,但和 zk 链接还在,并不会从 zk 中删除,但已经拖慢了集群的速度。解决此问题,我们可以在数据服务器中加入定时任务,通过定时跑真实业务查询,监控服务器状态,一旦达到设定的红线阈值,强制下线,而不是等到 server 彻底死掉。

    2、检索服务器每个 server 都监控 zookeeper 同一个节点,在节点变化时会出现羊群效应。当然,检索服务器如果数量不多还好。其实检索服务器应该通过 zookeeper 做一个 leader 选举,只由 leader 去监控 zookeeper 节点变化,更新 redis 中的数据服务器列表缓存即可。

    附:完整代码

    数据服务端代码ServiceRegister.java

    public class ServiceRegister implements Runnable{
     
        private ZooKeeper zk;
     
        private static final String ZNODE = "/sas";
     
        private static final String SA_NODE_PREFIX = "sa_";
     
        private String hostName="localhost:2181";
     
        public void setHostName(String hostName) {
            this.hostName = hostName;
        }
     
        public ServiceRegister() throws IOException {
            zk = new ZooKeeper(hostName, 10000,null);
        }
     
     
        @Override
        public void run() {
            try {
     
                createSaNode();
     
                synchronized (this) {
                    wait();
                }
     
            } catch (KeeperException e) {
                e.printStackTrace();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
     
        //测试用
        public static void main(String[] args){
            try {
                new ServiceRegister().run();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
     
        //创建子节点
        private String createSaNode() throws KeeperException, InterruptedException {
            // 如果根节点不存在,则创建根节点
            Stat stat = zk.exists(ZNODE, false);
            if (stat == null) {
                zk.create(ZNODE, new byte[0], ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.PERSISTENT);
            }
     
            String hostName = System.getenv("HOSTNAME");
            // 创建EPHEMERAL_SEQUENTIAL类型节点
            String saPath = zk.create(ZNODE + "/" + SA_NODE_PREFIX,
                    hostName.getBytes(), ZooDefs.Ids.OPEN_ACL_UNSAFE,
                    CreateMode.EPHEMERAL_SEQUENTIAL);
            return saPath;
        }
    }
    
    

    检索服务端代码DataMonitor.java

    public class DataMonitor implements Watcher, AsyncCallback.ChildrenCallback {
     
        ZooKeeper zk;
     
        String znode;
     
        Watcher chainedWatcher;
     
        boolean dead;
     
        DataMonitorListener listener;
     
        List<String> prevSaIds;
     
        public DataMonitor(ZooKeeper zk, String znode, Watcher chainedWatcher,
                           DataMonitorListener listener) {
            this.zk = zk;
            this.znode = znode;
            this.chainedWatcher = chainedWatcher;
            this.listener = listener;
            // 这是整个监控的真正开始,通过获取children节点开始。设置了本对象为监控对象,回调对象也是本对象。以后均是事件驱动。
            zk.getChildren(znode, true, this, null);
        }
     
        /**
         * 其他和monitor产生交互的类,需要实现此listener
         */
        public interface DataMonitorListener {
            /**
             * The existence status of the node has changed.
             */
            void changed(List<String> saIds);
     
            /**
             * The ZooKeeper session is no longer valid.
             *
             * @param rc
             *                the ZooKeeper reason code
             */
            void closing(int rc);
        }
     
        /*
        *监控/saids的回调函数。除了处理异常外。
        *如果发生变化,和构造函数中一样,通过getChildren,再次监控,并处理children节点变化后的业务
        */
        public void process(WatchedEvent event) {
            String path = event.getPath();
            if (event.getType() == Event.EventType.None) {
                // We are are being told that the state of the
                // connection has changed
                switch (event.getState()) {
                    case SyncConnected:
                        // In this particular example we don't need to do anything
                        // here - watches are automatically re-registered with
                        // server and any watches triggered while the client was
                        // disconnected will be delivered (in order of course)
                        break;
                    case Expired:
                        // It's all over
                        dead = true;
                        listener.closing(Code.SESSIONEXPIRED.intValue());
                        break;
                }
            } else {
                if (path != null && path.equals(znode)) {
                    // Something has changed on the node, let's find out
                    zk.getChildren(znode, true, this, null);
                }
            }
            if (chainedWatcher != null) {
                chainedWatcher.process(event);
            }
        }
     
        //拿到Children节点后的回调函数。
        @Override
        public void processResult(int rc, String path, Object ctx, List<String> children) {
            boolean exists;
            switch (rc) {
                case Code.Ok:
                    exists = true;
                    break;
                case Code.NoNode:
                    exists = false;
                    break;
                case Code.SessionExpired:
                case Code.NoAuth:
                    dead = true;
                    listener.closing(rc);
                    return;
                default:
                    // Retry errors
                    zk.getChildren(znode, true, this, null);
                    return;
            }
     
            List<String> saIds = null;
     
            //如果存在,再次查询到最新children,此时仅查询,不要设置监控了
            if (exists) {
                try {
                    saIds = zk.getChildren(znode,null);
                } catch (KeeperException e) {
                    // We don't need to worry about recovering now. The watch
                    // callbacks will kick off any exception handling
                    e.printStackTrace();
                } catch (InterruptedException e) {
                    return;
                }
            }
     
            //拿到最新saids后,通过listener(executor),加载Saids。
            if ((saIds == null && saIds != prevSaIds)
                    || (saIds != null && !saIds.equals(prevSaIds))) {
                listener.changed(saIds);
                prevSaIds = saIds;
            }
        }
    }
    

    LoadSaIdsExecutor.java

    public class LoadSaIdsExecutor
            implements Watcher, Runnable, DataMonitor.DataMonitorListener
    {
     
        private DataMonitor dm;
     
        private ZooKeeper zk;
     
        private static final String znode = "/sas";
     
        private String hostName="localhost:2181";
     
        public void setHostName(String hostName) {
            this.hostName = hostName;
        }
     
        /*
             *初始化zookeeper及DataMonitor
             * 自己作为zookeeper的监控者,监控和zookeeper连接的变化
             * 自己作为DataMonitor的listener。当dm监控到变化时会调用executor执行业务操作
             */
        public LoadSaIdsExecutor() throws KeeperException, IOException {
            zk = new ZooKeeper(hostName, 300000, this);
            dm = new DataMonitor(zk, znode, null, this);
        }
     
        /**
         * 入口方法,测试用。
         */
        public static void main(String[] args) {
            try {
                new LoadSaIdsExecutor().run();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
     
        /**
         * 作为单独线程运行
         */
        public void run() {
            try {
                synchronized (this) {
                    while (!dm.dead) {
                        wait();
                    }
                }
            } catch (InterruptedException e) {
            }
        }
     
        /*
         *作为zookeeper监控者的回调,直接传递事件给monitor的回调函数统一处理
         */
        @Override
        public void process(WatchedEvent event) {
            dm.process(event);
        }
     
        /*
         *当关闭时,让线程线继续走完
         */
        public void closing(int rc) {
            synchronized (this) {
                notifyAll();
            }
        }
     
        /*
         *监控到/saids变化后的处理类
        */
        static class SaIdsLoader extends Thread {
     
            List<String> saIds = null;
     
            //构造对象后直接启动线程
            public SaIdsLoader(List<String> saIds){
                this.saIds = saIds;
                start();
            }
     
            public void run() {
                System.out.println("------------加载开始------------");
                //业务处理的地方
                if(saIds!=null){
                    saIds.forEach(id->{
                        System.out.println(id);
                    });
                }
                System.out.println("------------加载结束------------");
     
            }
        }
     
        /*
         *作为listener对外暴露的方法,在节点/saids变化时被调用。
        */
        @Override
        public void changed(List<String> data) {
                    new SaIdsLoader(data);
        }
    }
     
    


    者:稀有气体

    链接:

    https://blog.csdn.net/liyiming2017/article/details/85063868

    展开全文
  • 真正加速宽带方法

    2008-05-07 13:40:08
    <br>所以在我实际的例子中 Windows 98, Me 加速的空间最大 , 但是你的ISP提供给你的速度下载不到1MB 你即使最佳化也没用 <br>就像你最佳化后计算机的设定值变成你的计算机可以达到联机速度5000KBPS 你的...
  • PHP中session安全吗?

    2020-12-18 15:31:32
    做PHP开发这么长时间,还真没有真正关注过安全的问题,每次都是以完成项目为主,最近在网上看到了一篇关于安全文章,看完以后才注意到自己以前项目都存在着很大安全漏洞,于是挑了一个项目进行了测试,发现很...
  • 创业思维

    2020-02-24 16:33:19
    举一个很好的例子,就是一个小伙通过空手套白狼的方式“销售压根”没有的口罩,瞬间又100万到账,这就很能说明问题,你苦哈哈的打工的日子应该到头了,从现在开始就开始自己的创业的道路。 1、大家真正需要的...
  • PS:最近读Java编程思想时候发现了一些小问题.就是equals方法和==,感觉自己真正掌握了,其实并没有.简单记录一下. 学习内容: 1.equals 和 == 区别 equals和==想必大家都很熟悉,但是是否真正的掌握了...
  • 我通过实际工作中一个例子,讲解 zookeeper 是如何帮我解决分布式问题,以此引导大家发现自己系统中可以应用 zookeeper 场景。真正把 zookeeper 使用起来!项目背景介绍首先给大家介绍一下本文描述项目情况。...
  • 做PHP开发这么长时间,还真没有真正关注过安全的问题,每次都是以完成项目为主,最近在网上看到了一篇关于安全文章,看完以后才注意到自己以前项目都存在着很大安全漏洞,于是挑了一个项目进行了测试,发现很...
  • 最近被RTP负载类型和时间戳搞郁闷了,一个问题调试了近一周,终于圆满解决,回头看看,发现其实主要原因还是自己没有真正地搞清楚RTP协议中负载类型和时间戳含义。虽然做RTP传输,有着Jrtplib和Ortp这两个强大...
  • 最近被RTP负载类型和时间戳搞郁闷了,一个问题调试了近一周,终于圆满解决,回头看看,发现其实主要原因还是自己没有真正地搞清楚RTP协议中负载类型和时间戳含义。虽然做RTP传输,有着Jrtplib和Ortp这两个强大...
  • 最近被RTP负载类型和时间戳搞郁闷了,一个问题调试了近一周,终于圆满解决,回头看看,发现其实主要原因还是自己没有真正地搞清楚RTP协议中负载类型和时间戳含义。虽然做RTP传输,有着Jrtplib和Ortp这两个强大...
  • 很可能读者比我更聪明,有更好的解决问题的方法,但无论如何,我认为我自己的经验可以为读者所借鉴。如果真是如 此,我将会非常欣慰。 在第二版的编写过程中,我同样要感谢许多人。感谢我的父母和爷爷对我的爱,并...
  • 很可能读者比我更聪明,有更好的解决问题的方法,但无论如何,我认为我自己的经验可以为读者所借鉴。如果真是如 此,我将会非常欣慰。 在第二版的编写过程中,我同样要感谢许多人。感谢我的父母和爷爷对我的爱,并...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 255
精华内容 102
关键字:

发现自己的真正问题的例子