찾다
백엔드 개발PHP 튜토리얼算法无国界 国内算法同样牛_PHP教程

算法无国界 国内算法同样牛_PHP教程

Jul 13, 2016 am 10:37 AM
회사국내의외국의데이터 분석~의연산엮다

【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年,我们也会进入互联网发展的新时代,各种数据充斥在网络中,大数据成为各个互联网公司都要面对的问题之一。如何消耗最小的资源来获得尽可能多的有用信息,这应该是每个互联网公司都要考虑的问题。通过最近关于算法的两篇文章,想必各位读者都能心中有数。当然,每种算法都有各自的优缺点,我们还是要根据在平时工作中的实际使用情况来对算法进行选择,不能一概而论。(王旭东/作者 包研/审校)

 

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/735165.htmlTechArticle【CSDN报道】几天前,CSDN编译了国外AddThis公司的数据分析副总监Matt Abrams在High Scalability上发表的一篇文章,Matt Abrams在这篇文章中向读者介...
성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
PHP vs. Python : 차이점 이해PHP vs. Python : 차이점 이해Apr 11, 2025 am 12:15 AM

PHP와 Python은 각각 고유 한 장점이 있으며 선택은 프로젝트 요구 사항을 기반으로해야합니다. 1.PHP는 간단한 구문과 높은 실행 효율로 웹 개발에 적합합니다. 2. Python은 간결한 구문 및 풍부한 라이브러리를 갖춘 데이터 과학 및 기계 학습에 적합합니다.

PHP : 죽어 가거나 단순히 적응하고 있습니까?PHP : 죽어 가거나 단순히 적응하고 있습니까?Apr 11, 2025 am 12:13 AM

PHP는 죽지 않고 끊임없이 적응하고 진화합니다. 1) PHP는 1994 년부터 새로운 기술 트렌드에 적응하기 위해 여러 버전 반복을 겪었습니다. 2) 현재 전자 상거래, 컨텐츠 관리 시스템 및 기타 분야에서 널리 사용됩니다. 3) PHP8은 성능과 현대화를 개선하기 위해 JIT 컴파일러 및 기타 기능을 소개합니다. 4) Opcache를 사용하고 PSR-12 표준을 따라 성능 및 코드 품질을 최적화하십시오.

PHP의 미래 : 적응 및 혁신PHP의 미래 : 적응 및 혁신Apr 11, 2025 am 12:01 AM

PHP의 미래는 새로운 기술 트렌드에 적응하고 혁신적인 기능을 도입함으로써 달성 될 것입니다. 1) 클라우드 컴퓨팅, 컨테이너화 및 마이크로 서비스 아키텍처에 적응, Docker 및 Kubernetes 지원; 2) 성능 및 데이터 처리 효율을 향상시키기 위해 JIT 컴파일러 및 열거 유형을 도입합니다. 3) 지속적으로 성능을 최적화하고 모범 사례를 홍보합니다.

PHP의 초록 클래스 또는 인터페이스에 대한 특성과 언제 특성을 사용 하시겠습니까?PHP의 초록 클래스 또는 인터페이스에 대한 특성과 언제 특성을 사용 하시겠습니까?Apr 10, 2025 am 09:39 AM

PHP에서, 특성은 방법 재사용이 필요하지만 상속에 적합하지 않은 상황에 적합합니다. 1) 특성은 클래스에서 다중 상속의 복잡성을 피할 수 있도록 수많은 방법을 허용합니다. 2) 특성을 사용할 때는 대안과 키워드를 통해 해결할 수있는 방법 충돌에주의를 기울여야합니다. 3) 성능을 최적화하고 코드 유지 보수성을 향상시키기 위해 특성을 과도하게 사용해야하며 단일 책임을 유지해야합니다.

DIC (Dependency Injection Container) 란 무엇이며 PHP에서 사용하는 이유는 무엇입니까?DIC (Dependency Injection Container) 란 무엇이며 PHP에서 사용하는 이유는 무엇입니까?Apr 10, 2025 am 09:38 AM

의존성 주입 컨테이너 (DIC)는 PHP 프로젝트에 사용하기위한 객체 종속성을 관리하고 제공하는 도구입니다. DIC의 주요 이점에는 다음이 포함됩니다. 1. 디커플링, 구성 요소 독립적 인 코드는 유지 관리 및 테스트가 쉽습니다. 2. 유연성, 의존성을 교체 또는 수정하기 쉽습니다. 3. 테스트 가능성, 단위 테스트를 위해 모의 객체를 주입하기에 편리합니다.

SPL SplfixedArray 및 일반 PHP 어레이에 비해 성능 특성을 설명하십시오.SPL SplfixedArray 및 일반 PHP 어레이에 비해 성능 특성을 설명하십시오.Apr 10, 2025 am 09:37 AM

SplfixedArray는 PHP의 고정 크기 배열로, 고성능 및 메모리 사용이 필요한 시나리오에 적합합니다. 1) 동적 조정으로 인한 오버 헤드를 피하기 위해 생성 할 때 크기를 지정해야합니다. 2) C 언어 배열을 기반으로 메모리 및 빠른 액세스 속도를 직접 작동합니다. 3) 대규모 데이터 처리 및 메모리에 민감한 환경에 적합하지만 크기가 고정되어 있으므로주의해서 사용해야합니다.

PHP는 파일 업로드를 어떻게 단단히 처리합니까?PHP는 파일 업로드를 어떻게 단단히 처리합니까?Apr 10, 2025 am 09:37 AM

PHP는 $ \ _ 파일 변수를 통해 파일 업로드를 처리합니다. 보안을 보장하는 방법에는 다음이 포함됩니다. 1. 오류 확인 확인, 2. 파일 유형 및 크기 확인, 3 파일 덮어 쓰기 방지, 4. 파일을 영구 저장소 위치로 이동하십시오.

Null Coalescing 연산자 (??) 및 Null Coalescing 할당 연산자 (?? =)은 무엇입니까?Null Coalescing 연산자 (??) 및 Null Coalescing 할당 연산자 (?? =)은 무엇입니까?Apr 10, 2025 am 09:33 AM

JavaScript에서는 NullCoalescingOperator (??) 및 NullCoalescingAssignmentOperator (?? =)를 사용할 수 있습니다. 1. 2. ??= 변수를 오른쪽 피연산자의 값에 할당하지만 변수가 무효 또는 정의되지 않은 경우에만. 이 연산자는 코드 로직을 단순화하고 가독성과 성능을 향상시킵니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

에디트플러스 중국어 크랙 버전

에디트플러스 중국어 크랙 버전

작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

WebStorm Mac 버전

WebStorm Mac 버전

유용한 JavaScript 개발 도구

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

Atom Editor Mac 버전 다운로드

Atom Editor Mac 버전 다운로드

가장 인기 있는 오픈 소스 편집기