【CSDN报道】几天前,CSDN编译了国外AddThis公司的数据分析副总监Matt Abrams在High Scalability上发表的一篇文章,Matt Abrams在这篇文章中向读者介绍了AddThis仅用了1.5KB内存就计算了十亿个不同的对象,充分展示了算法的魅力。
这篇文章在微博上得到了广泛关注,并得知一淘的算法也同样出彩。为此,CSDN采访了一淘数据部的张洋(他曾先后就读于烟台大学和北京航空航天大学,2011年在北京航空航天大学取得计算机理论硕士学位,同年加入淘宝,目前在一淘数据部工作),请他讲解一下一淘的相关算法。
图:一淘数据部工程师 张洋
CSDN:首先请您介绍一下自己以及平时的工作?
张洋:我叫张洋,在公司的花名是夜沨。目前是一淘数据部一名普通码农,和千千万万码农一样,每天以敲代码写程序为工作,同时也将其视为人生第二大乐趣(第一大乐趣是吃)。我对PHP、Nginx、数据挖掘、机器学习、算法、编译器和分布式存储计算等技术兴趣浓厚,喜爱数学和历史。我很喜欢写程序这个工作,也希望能将编程作为毕生的职业。写程序之余也喜欢研究数学和算法,同时我很乐于将自己学到的东西总结成文章发表在博客上和大家分享,有兴趣的朋友可以来我博客逛逛:codinglabs.org。
我在一淘数据部的职位是前端开发,但是我这个“前端开发”比一般意义上的前端工程师做的事要杂一些,除了负责HTML、CSS和JavaScript外,也开发PHP、Lua的后台程序,偶尔也会根据兴趣和需要来开发一些C和算法的程序(我很喜欢写C和算法,十分乐在其中),同时我还做一些运维工作,例如搭建服务器环境和维护线上服务器。
CSDN:是什么原因促使您对算法感兴趣的?
张洋:可能是源自我对数学的兴趣吧,我一直很喜欢数理性的东西。正式接触算法是大二的时候,当时买了一本算法导论,才真正开始了解渐近复杂度、算法分析、动态规划、贪心算法、NP问题等一系列算法领域最基本的东西。看的时候就觉得很神奇,感觉书中的每个算法都闪耀着人类的智慧,阅读和学习这些东西给我带来一种难以用语言表达的满足感和快感。在后来的学习和工作中我不断从实际应用中了解和领会算法是如何解决各个领域的实际问题,推动人类文明的发展,这更加深了我对算法的崇敬。
CSDN:一淘数据部为什么会开发这个基数估计算法?
张洋:一淘数据部主要在电子商务领域做一些数据的分析挖掘,并将这些技术与业务紧密结合形成一些数据产品和服务,例如数据分析、推荐系统等我们都有做。这些数据产品既对外服务,也会对公司或集团内部的运作提供支持。
在电子商务的数据分析领域有一些很关键的指标(例如unique visitor,简称UV,指在一定的时间空间维度约束下独立访客的数量)的计算是很常见的任务。一般来说我们首先会通过某种手段给每一个独立访客做一个标记(例如通过cookie),然后会在所有访问日志中记录下访客的标记,这样一来,UV的计算就等价为在一个可重复的用户标记集合中计算不重复元素的个数,也就是数学上的基数。
基数的计算有两个难点:
一是不利于实时流计算的实现。例如我们的一些产品中经常会提供实时UV,也就是从某个时间点开始(例如今天零点)到目前的独立访客数。为了做到这点,需在内存中为每一个UV数值维护一个查找性能高的数据结构(例如B树),这样当实时流中新来一个访问时,能快速查找这个访客是否已经来过,由此确定UV值是增加1还是不变。如果我们要为100万家店铺同时提供这种服务,就要在内存中维护100万个B树,而如果还要分不同来源维度计算UV的话,这个数量还会迅速膨胀。这对我们的服务器计算资源和内存资源都是一个很大的挑战。
第二点就是传统的基数计算方法无法有效合并。例如,前一小时和这一小时的UV虽然分别计算出来了,但是要看这两个小时的总UV依然要重新进行一遍复杂的计算。使用bitmap数据结构的方案虽然可以快速合并,但是空间复杂度太高,因为时间段的任意组合数量与时间段数量呈幂级关系,所以不论是B树还是简单的bitmap在大数据面前都不是一个有效的方案。
基于以上背景,一淘数据部的技术专家王晓哲(花名清无)研究了基数估计的相关算法及Clearspring的一个java实现(stream-lib),并率先在我们的全息效果平台(代号月光宝盒)的项目中引入了基数估计算法,目前已成功实现利用少量内存对大量UV进行计算的技术难题,并承担了双十一和双十二大促中天猫和淘宝所有会场坑位的效果实时计算任务。
为了方便更多的非Java项目使用此类算法,王晓哲和我根据相关论文并参考stream-lib给出了一个C版本的实现ccard-lib,接着一淘数据部的工程师张维(花名民瞻)又实现了PHP的扩展。目前这个C的实现已经在一淘数据部多个产品中开始使用,并且也已经通过github进行了开源。
CSDN:能不能向读者详细介绍一下一淘数据部的基数估计算法?
张洋:我们使用的算法主要是Adaptive Counting算法,这个算法出现在 “Fast and accurate traffic matrix measurement using adaptive cardinality counting” 这篇论文里,但是我同时在ccard-lib里也实现了Linear Counting、LogLog Counting和HyperLogLog Counting等常见的基数估计算法。
这些算法是概率算法,就是通过牺牲一定的准确性(但是精度可控,并可以通过数学分析给出控制精度的方法),来大幅节省计算的资源使用。例如我们仅仅使用8k的内存就可以对一个数亿量级的UV进行估计,而误差不超过2%,这比使用B树或原始bitmap要大幅节省内存。同时基数估计算法用到了经过哈希变换的bitmap空间,在大幅节省内存的同时依然可以实现高效合并,这就同时解决了上面提到的两个难点。
使用2^16(64K)位时,估算结果如下:
Linear Counting with Murmurhash:
actual: 50000, estimated: 50062, error: 0.12%
actual: 100000, estimated: 99924, error: 0.08%
actual: 150000, estimated: 149865, error: 0.09%
actual: 200000, estimated: 199916, error: 0.04%
actual: 250000, estimated: 250123, error: 0.05%
actual: 300000, estimated: 299942, error: 0.02%
actual: 350000, estimated: 349801, error: 0.06%
actual: 400000, estimated: 400101, error: 0.03%
actual: 450000, estimated: 449955, error: 0.01%
actual: 500000, estimated: 500065, error: 0.01%
Linear Counting with Lookup3hash:
actual: 50000, estimated: 49835, error: 0.33%
actual: 100000, estimated: 99461, error: 0.54%
actual: 150000, estimated: 149006, error: 0.66%
actual: 200000, estimated: 198501, error: 0.75%
actual: 250000, estimated: 248365, error: 0.65%
actual: 300000, estimated: 298065, error: 0.65%
actual: 350000, estimated: 347504, error: 0.71%
actual: 400000, estimated: 397292, error: 0.68%
actual: 450000, estimated: 446700, error: 0.73%
actual: 500000, estimated: 495944, error: 0.81%
Hyperloglog Counting with Murmurhash:
actual: 50000, estimated: 50015, error: 0.03%
actual: 100000, estimated: 100048, error: 0.05%
actual: 150000, estimated: 149709, error: 0.19%
actual: 200000, estimated: 201595, error: 0.80%
actual: 250000, estimated: 250168, error: 0.07%
actual: 300000, estimated: 299864, error: 0.05%
actual: 350000, estimated: 348571, error: 0.41%
actual: 400000, estimated: 398583, error: 0.35%
actual: 450000, estimated: 448632, error: 0.30%
actual: 500000, estimated: 498330, error: 0.33%
Hyperloglog Counting with Lookup3hash:
actual: 50000, estimated: 49628, error: 0.74%
actual: 100000, estimated: 99357, error: 0.64%
actual: 150000, estimated: 148880, error: 0.75%
actual: 200000, estimated: 200475, error: 0.24%
actual: 250000, estimated: 249362, error: 0.26%
actual: 300000, estimated: 299119, error: 0.29%
actual: 350000, estimated: 349225, error: 0.22%
actual: 400000, estimated: 398805, error: 0.30%
actual: 450000, estimated: 448373, error: 0.36%
actual: 500000, estimated: 498183, error: 0.36%
Adaptive Counting with Murmurhash:
actual: 50000, estimated: 50015, error: 0.03%
actual: 100000, estimated: 100048, error: 0.05%
actual: 150000, estimated: 149709, error: 0.19%
actual: 200000, estimated: 201059, error: 0.53%
actual: 250000, estimated: 249991, error: 0.00%
actual: 300000, estimated: 300067, error: 0.02%
actual: 350000, estimated: 349610, error: 0.11%
actual: 400000, estimated: 399875, error: 0.03%
actual: 450000, estimated: 450348, error: 0.08%
actual: 500000, estimated: 500977, error: 0.20%
Adaptive Counting with Lookup3hash:
actual: 50000, estimated: 49628, error: 0.74%
actual: 100000, estimated: 99357, error: 0.64%
actual: 150000, estimated: 148880, error: 0.75%
actual: 200000, estimated: 199895, error: 0.05%
actual: 250000, estimated: 249563, error: 0.17%
actual: 300000, estimated: 299047, error: 0.32%
actual: 350000, estimated: 348665, error: 0.38%
actual: 400000, estimated: 399266, error: 0.18%
actual: 450000, estimated: 450196, error: 0.04%
actual: 500000, estimated: 499516, error: 0.10%
Loglog Counting with Murmurhash:
actual: 50000, estimated: 59857, error: 19.71%
actual: 100000, estimated: 103108, error: 3.11%
actual: 150000, estimated: 150917, error: 0.61%
actual: 200000, estimated: 201059, error: 0.53%
actual: 250000, estimated: 249991, error: 0.00%
actual: 300000, estimated: 300067, error: 0.02%
actual: 350000, estimated: 349610, error: 0.11%
actual: 400000, estimated: 399875, error: 0.03%
actual: 450000, estimated: 450348, error: 0.08%
actual: 500000, estimated: 500977, error: 0.20%
Loglog Counting with Lookup3hash:
actual: 50000, estimated: 59870, error: 19.74%
actual: 100000, estimated: 103044, error: 3.04%
actual: 150000, estimated: 150435, error: 0.29%
actual: 200000, estimated: 199895, error: 0.05%
actual: 250000, estimated: 249563, error: 0.17%
actual: 300000, estimated: 299047, error: 0.32%
actual: 350000, estimated: 348665, error: 0.38%
actual: 400000, estimated: 399266, error: 0.18%
actual: 450000, estimated: 450196, error: 0.04%
actual: 500000, estimated: 499516, error: 0.10%
限于篇幅,我在这里不能具体描述这些算法的细节,之前我在博客上发表了一篇翻译的文章,不过内容也是概括性描述。但是我已经在准备写博文详细介绍基数估计算法了,那里面会包括算法的数理细节以及对论文的一些解读,欢迎有兴趣的朋友关注我的博客。
CSDN:看到您微博上自称“代码洁癖重度患者”,这是一个很有趣的称呼,那么是否可以理解为您对代码的规范性很在意,您在平时在编码过程中如何保持代码的规范?
张洋:这么说其实是有点自嘲的意思吧。对代码格式我确实是很在意的,如果看到代码不规范、不整齐甚至多一个空行我都会觉得非常不舒服,骨子里对代码格式有一种完美主义倾向。
不过这个事情要分两面看,如果是我自己开发的比较专的东西,如算法库,可以坚持这种完美主义,但需要多人合作的场合实际上是不太合适的。实事求是的说,业务代码总是不可能一直很漂亮,需要在业务进度和代码质量中间做一个权衡。在保持代码规范方面,我始终认为不能完全靠程序员的自觉和代码规范的宣讲,通过工具(例如lint)和流程去保证会更有效一些。
CSDN:还有哪些困难是需要在未来工作中克服的?
张洋:需要克服的困难主要来自两方面吧。
一方面是算法本身改进的困难,这世界不存在完美无暇的算法,例如上面的基数估计算法,虽然大大降低了内存使用,但是如果维度爆炸的话,内存使用仍然会很夸张,而且合并bitmap也不是没有代价,有时需要进行内存和磁盘bitmap的合并,当bitmap量过大时磁盘IO会称为瓶颈,因此如何结合具体场景来优化和改进算法就成为一个难点。一个方法是查阅相关论文,了解和借鉴目前全球各大研究机构和公司对相关算法的最新研究成果。另一个方法就是自己进行改进,这块需要对算法本身极其相关的数学分析有非常深入掌握,因此对相关工程师的理论水平要求较高。
另一方面就是算法和业务产品的结合方案。算法毕竟是较为形式化的东西,要具体应用到产品中还有很长一段路要走。寻求算法与产品的最佳契合点和结合方案也是工作中的重点和难点之一。
2012已经过去,我们度过了世界末日,迎来世界新篇章。在2013年,我们也会进入互联网发展的新时代,各种数据充斥在网络中,大数据成为各个互联网公司都要面对的问题之一。如何消耗最小的资源来获得尽可能多的有用信息,这应该是每个互联网公司都要考虑的问题。通过最近关于算法的两篇文章,想必各位读者都能心中有数。当然,每种算法都有各自的优缺点,我们还是要根据在平时工作中的实际使用情况来对算法进行选择,不能一概而论。(王旭东/作者 包研/审校)

特斯拉是一个典型的AI公司,过去一年训练了75000个神经网络,意味着每8分钟就要出一个新的模型,共有281个模型用到了特斯拉的车上。接下来我们分几个方面来解读特斯拉FSD的算法和模型进展。01 感知 Occupancy Network特斯拉今年在感知方面的一个重点技术是Occupancy Network (占据网络)。研究机器人技术的同学肯定对occupancy grid不会陌生,occupancy表示空间中每个3D体素(voxel)是否被占据,可以是0/1二元表示,也可以是[0, 1]之间的

译者 | 朱先忠审校 | 孙淑娟在我之前的博客中,我们已经了解了如何使用因果树来评估政策的异质处理效应。如果你还没有阅读过,我建议你在阅读本文前先读一遍,因为我们在本文中认为你已经了解了此文中的部分与本文相关的内容。为什么是异质处理效应(HTE:heterogenous treatment effects)呢?首先,对异质处理效应的估计允许我们根据它们的预期结果(疾病、公司收入、客户满意度等)选择提供处理(药物、广告、产品等)的用户(患者、用户、客户等)。换句话说,估计HTE有助于我

译者 | 朱先忠审校 | 孙淑娟引言模型超参数(或模型设置)的优化可能是训练机器学习算法中最重要的一步,因为它可以找到最小化模型损失函数的最佳参数。这一步对于构建不易过拟合的泛化模型也是必不可少的。优化模型超参数的最著名技术是穷举网格搜索和随机网格搜索。在第一种方法中,搜索空间被定义为跨越每个模型超参数的域的网格。通过在网格的每个点上训练模型来获得最优超参数。尽管网格搜索非常容易实现,但它在计算上变得昂贵,尤其是当要优化的变量数量很大时。另一方面,随机网格搜索是一种更快的优化方法,可以提供更好的

导读:因果推断是数据科学的一个重要分支,在互联网和工业界的产品迭代、算法和激励策略的评估中都扮演者重要的角色,结合数据、实验或者统计计量模型来计算新的改变带来的收益,是决策制定的基础。然而,因果推断并不是一件简单的事情。首先,在日常生活中,人们常常把相关和因果混为一谈。相关往往代表着两个变量具有同时增长或者降低的趋势,但是因果意味着我们想要知道对一个变量施加改变的时候会发生什么样的结果,或者说我们期望得到反事实的结果,如果过去做了不一样的动作,未来是否会发生改变?然而难点在于,反事实的数据往往是

SimCLR(Simple Framework for Contrastive Learning of Representations)是一种学习图像表示的自监督技术。 与传统的监督学习方法不同,SimCLR 不依赖标记数据来学习有用的表示。 它利用对比学习框架来学习一组有用的特征,这些特征可以从未标记的图像中捕获高级语义信息。SimCLR 已被证明在各种图像分类基准上优于最先进的无监督学习方法。 并且它学习到的表示可以很容易地转移到下游任务,例如对象检测、语义分割和小样本学习,只需在较小的标记

一、盒马供应链介绍1、盒马商业模式盒马是一个技术创新的公司,更是一个消费驱动的公司,回归消费者价值:买的到、买的好、买的方便、买的放心、买的开心。盒马包含盒马鲜生、X 会员店、盒马超云、盒马邻里等多种业务模式,其中最核心的商业模式是线上线下一体化,最快 30 分钟到家的 O2O(即盒马鲜生)模式。2、盒马经营品类介绍盒马精选全球品质商品,追求极致新鲜;结合品类特点和消费者购物体验预期,为不同品类选择最为高效的经营模式。盒马生鲜的销售占比达 60%~70%,是最核心的品类,该品类的特点是用户预期时

译者 | 李睿 审校 | 孙淑娟随着机器学习成为人们每天都在使用的很多应用程序的一部分,人们越来越关注如何识别和解决机器学习模型的安全和隐私方面的威胁。 然而,不同机器学习范式面临的安全威胁各不相同,机器学习安全的某些领域仍未得到充分研究。尤其是强化学习算法的安全性近年来并未受到太多关注。 加拿大的麦吉尔大学、机器学习实验室(MILA)和滑铁卢大学的研究人员开展了一项新研究,主要侧重于深度强化学习算法的隐私威胁。研究人员提出了一个框架,用于测试强化学习模型对成员推理攻击的脆弱性。 研究

1.线性回归线性回归(Linear Regression)可能是最流行的机器学习算法。线性回归就是要找一条直线,并且让这条直线尽可能地拟合散点图中的数据点。它试图通过将直线方程与该数据拟合来表示自变量(x 值)和数值结果(y 值)。然后就可以用这条线来预测未来的值!这种算法最常用的技术是最小二乘法(Least of squares)。这个方法计算出最佳拟合线,以使得与直线上每个数据点的垂直距离最小。总距离是所有数据点的垂直距离(绿线)的平方和。其思想是通过最小化这个平方误差或距离来拟合模型。例如


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

螳螂BT
Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

mPDF
mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

SublimeText3 Linux新版
SublimeText3 Linux最新版