Golang分布式并发---群体性热点淘汰算法

screscent · · 2246 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Golang分布式并发---群体性热点淘汰算法

 

         在传统的算法中,要计算热点的时候,常规采用,收集所有的任务列表,然后进行排序,得出前n的热点数据。此种算法的不好地方有:

1、  需要收集所有的任务列表。任务数过多时,收集是个问题

2、  将任务列表进行排序。在此过程中,如果列表过多,则会排序时间过长。

另外如果需要进行同步的话,则在此算法中,会有个停顿。

 

         那么我们构建一个场景,一个网吧有n个位置,每个人都可以去网吧,但规定,每次只能预约1小时,如果时间到了,则可以续费继续一个小时,如果不需要则放弃位置。

 

         现在有m个人来网吧上网。

         1、m < n时,则m个人都可以获取到上网位置

         2、当m>n时,则有n个人可以获取到上网位置,剩余的人,则在等待

        

有两种调度算法

1、  每个人,都会定期检查自己的时间,是不是到了1个小时,如果是,则判定自己是否需要继续使用,则优先续约1小时,如果不需要则放弃位置。等待的人中,则随机获取到这个位置。

2、每个人,都会定期检查自己的时间,是不是到了1个小时,如果是,则放弃位置。如果还需要继续使用则到等待队列中,不需要使用,则直接退出。

 

此算法中,需要注意的地方有

1、  每个用户自己是自律的。自己评判自己是否需要继续使用,评判自己是否时间到期等

2、  评判能否继续使用的标准,这个很重要。比如当个人贡献度到一定程度,才能继续使用。

简单的用法就是将n个体的贡献进行排序,淘汰尾部一些

 

在经过一段时间之后,热点自动会形成。

 

此算法好处是,每个个体独立公平的争抢机会,只有贡献度比较大的个人,使用时间则会长。这种算法不需要进行同步,提高了并发效率。

 

 

 

 

龚浩华

qq 29185807

2014年11月27日11:14:01

 


有疑问加站长微信联系

本文来自:CSDN博客

感谢作者:screscent

查看原文:Golang分布式并发---群体性热点淘汰算法

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:812540095

2246 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传