最新 | 最热门 | 最高评价

+0  Algorithm In Interview

Tag: Interview | Recommended | 算法 | 问题
四火 发于 2013年03月29日 00:15 | 点击: 2249 | 展开摘要
文章系本人原创,转载请保持完整性并注明出自《四火的唠叨》

The whole team talked about algorithm recently, since we found some leaked written exam questions on Internet so that online test became meaningless soon. On one hand we're thinking about how to contribute

查看全文: http://www.udpwork.com/item/9550.html

+0  IMO2010趣题:用有限次操作得到2010^(2010^2010)枚硬币

Tag: 递归 | Brain Storm | 算法 | 趣题
Matrix67 发于 2013年03月27日 21:32 | 点击: 1746 | 展开摘要
    下面这个问题来自于 IMO 2010 中的第 5 题。桌子上有 B1 、 B2 、 B3 、 B4 、 B5 、 B6 共六个盒子,初始时每个盒子里面都有一枚硬币。允许以下两种操作:

      (1) 选择一个非空的盒子 Bj (1 ≤ j ≤ 5),从 Bj 里拿走一枚硬币,然后在 Bj+1 里添加两枚硬币。

    &n

查看全文: http://www.udpwork.com/item/9540.html

+0  网络流和棒球赛淘汰问题

Tag: 图论 | Brain Storm | 网络流 | 算法 | 证明
Matrix67 发于 2013年03月08日 16:03 | 点击: 1835 | 展开摘要
    1996 年 9 月 10 日,《旧金山纪事报》的体育版上登载了《巨人队正式告别 NL 西区比赛》一文,宣布了旧金山巨人队输掉比赛的消息。当时,圣地亚哥教士队凭借80场胜利暂列西区比赛第一,旧金山巨人队只赢得了 59 场比赛,要想追上圣地亚哥教士队,至少还得再赢 21 场比赛才行。然而,根据赛程安排,巨人队只剩下 20 场比赛没打了,因而彻底与冠军无缘。

    有趣的是,报社可能没有发

查看全文: http://www.udpwork.com/item/9414.html

+0  趣题:证明边权递增的路径始终存在

Tag: 图论 | Brain Storm | 算法 | 趣题 | 证明
Matrix67 发于 2013年02月28日 00:44 | 点击: 1680 | 展开摘要
    一个树林里有 100 个村庄,它们之间有 1000 条小路,每条小路都连接着两个不同的村庄。每条小路 e 都有一条难度系数 l(e) ,所有小路的难度系数都不相同。现在有一个探险家,他想要选择一条长度为 20 的路径,使得所经过的小路的难度系数不断增加。求证:他总能找到这样的路径。

    探险家可以任意选择路径的起点和终点。

    为了证明这

查看全文: http://www.udpwork.com/item/9337.html

+0  用pLSA实现博文分类

Tag: 数据挖掘 | 算法艺术 | pLSA | 分类
diaorui 发于 2013年01月30日 00:33 | 点击: 2349 | 展开摘要
pLSA应该是做文本聚类的,不是文本分类的。

不过我是杂牌军,非专业人士,自己看的pLSA,所以会yy还能用到哪里去。

出发点是这样一个问题:有若干博文,需要将他们自动分类为ACM竞赛相关博文,非ACM竞赛的技术相关博文,非技术博文三种类型。这个问题的来源是因为 blog.acmicpc.info 这个网站的需要,在完成后会实际上线使用。目前也有一个正在进行中的比赛针对这个问题: http://acmicpc.info/archives/1194

因为需要实际上线用,难

查看全文: http://www.udpwork.com/item/10649.html

+0  一致性hash算法和lvs sh调度算法改进

Tag: 算法
网络技术实验室 发于 2013年01月17日 16:55 | 点击: 4271 | 展开摘要
1 LVS-sh调度算法(souce address hash)

本节是LVS中sh调度算法的实现分析;

ip_vs_sh_init_svc() -
创建256个hash bucket的hash table,并将rs映射到这256个bucket中,增加rs的引用计数器;

ip_vs_sh_done_svc() -
释放rs引用计数器,并销毁hash table;

ip_vs_sh_update_svc -
销毁hash
table,重新创建hash table并

查看全文: http://www.udpwork.com/item/9107.html

+0  解读Cardinality Estimation算法(第四部分:HyperLogLog Counting及Adaptive Counting)

Tag: 数学及算法 | 基数估计 | 大数据 | 概率 | 算法
ericzhang 发于 2013年01月09日 17:35 | 点击: 3699 | 展开摘要
在前一篇文章中,我们了解了LogLog Counting。LLC算法的空间复杂度为的几何平均数,而几何平均数对于特殊值(这里就是指0)非常敏感,因此当存在一些空桶时,LLC的估计效果就变得较差。

这一篇文章中将要介绍的HyperLogLog Counting及Adaptive Counting算法均是对LLC算法的改进,可以有效克服LLC对于较小基数估计效果差的缺点。

评价基数估计算法的精度

首先我们来分析一下LLC的问题。一般来说LLC最大问题在于当基数不太大时,估计

查看全文: http://www.udpwork.com/item/9048.html

+0  解读Cardinality Estimation算法(第三部分:LogLog Counting)

Tag: 数学及算法 | 基数估计 | 大数据 | 概率 | 算法
ericzhang 发于 2013年01月03日 21:17 | 点击: 4828 | 展开摘要
上一篇文章介绍的Linear Counting算法相较于直接映射bitmap的方法能大大节省内存(大约只需后者1/10的内存),但毕竟只是一个常系数级的降低,空间复杂度仍然为。例如,假设基数的上限为1亿,原始bitmap方法需要12.5M内存,而LogLog Counting只需不到1K内存(640字节)就可以在标准误差不超过4%的精度下对基数进行估计,效果可谓十分惊人。

本文将介绍LogLog Counting。

简介

LogLog Counting(以下简称LLC)

查看全文: http://www.udpwork.com/item/8971.html

+0  解读Cardinality Estimation算法(第二部分:Linear Counting)

Tag: 数学及算法 | 基数估计 | 大数据 | 概率 | 算法
ericzhang 发于 2012年12月31日 17:35 | 点击: 2975 | 展开摘要
在上一篇文章中,我们知道传统的精确基数计数算法在数据量大时会存在一定瓶颈,瓶颈主要来自于数据结构合并和内存使用两个方面。因此出现了很多基数估计的概率算法,这些算法虽然计算出的结果不是精确的,但误差可控,重要的是这些算法所使用的数据结构易于合并,同时比传统方法大大节省内存。

在这一篇文章中,我们讨论Linear Counting算法。

简介

Linear Counting(以下简称LC)在1990年的一篇论文“A linear-time probabilistic cou

查看全文: http://www.udpwork.com/item/8950.html

+0  解读Cardinality Estimation算法(第一部分:基本概念)

Tag: 数学及算法 | 基数估计 | 大数据 | 概率 | 算法
ericzhang 发于 2012年12月30日 22:11 | 点击: 3010 | 展开摘要
基数计数(cardinality counting)是实际应用中一种常见的计算场景,在数据分析、网络监控及数据库优化等领域都有相关需求。精确的基数计数算法由于种种原因,在面对大数据场景时往往力不从心,因此如何在误差可控的情况下对基数进行估计就显得十分重要。目前常见的基数估计算法有Linear Counting、LogLog Counting、HyperLogLog Counting及Adaptive Counting等。这几种算法都是基于概率统计理论所设计的概率算法,它们克服

查看全文: http://www.udpwork.com/item/8947.html

+0  一淘数据部-基数估计的概率算法

Tag: 数据结构与算法 | UV | 一淘数据部 | 基数 | 数据部 | 概率算法 | 量子恒道
gang.yug 发于 2012年12月26日 11:35 | 点击: 2227 | 展开摘要
本博客会陆续更新一淘数据部 各位技术同学分享的资料。

本次分享的内容来自夜沨同学:

受众:

对基数 概率算法感兴趣的同学。

简介:

内容:

1、基数的概念、应用、传统计算方式极其局限;

2、三种计算基数的概率算法、相关数理分析、比较及实现重点

文件下载:基数估计的概率算法及uv计算中的应用-PDF文件

查看全文: http://www.udpwork.com/item/8921.html

+0  跨越千年的RSA算法

Tag: 密码学 | 协议 | 质数 | Brain Storm | 算法 | 数论
Matrix67 发于 2012年12月15日 13:46 | 点击: 2109 | 展开摘要
    数论,数学中的皇冠,最纯粹的数学。早在古希腊时代,人们就开始痴迷地研究数字,沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后,几千年来的数论研究成果突然有了实际的应用,这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》,但受篇幅限制,只有一万字左右的内容。其实,从数论到 RSA 算法,里面的数学之美哪里是一万字能扯完的?在写作的过程中,我查了很多资料,找到了很多漂

查看全文: http://www.udpwork.com/item/8861.html
|<<<2345678>>>| 一共12页, 143条记录