作者 | 潇楠来源 | 阿里技术公众号写在最前我个人有写年度总结的习惯，2020年我的工作职责有所变化，从垂直方向的广告算法变化到了水平横向的算法整体，所以这篇总结是关于阿里巴巴国际站（Alibaba.com，简称ICBU）算法团队的。本文内容主要包括以下几个部分：第一部分，分享我对算法、电商算法的理解，以及ICBU算法团队的整体工作。第二部分，ICBU算法团队在2020年的一些重要技术突破。第三部分，关于工作中一些开放性问题的思考。第四部分，明年的展望。一 ICBU算法团队简介当年在做广告算法的时候，我曾经想过一个问题，“什么是广告算法工程师”？当时我从广告、广告算法、广告算法工程师这3个维度，分别阐述了这个问题。而现在，随着职责的变化，我问自己的问题就变成了，“什么是算法工程师？”1 算法什么是算法？当我们提到《算法导论》这本书的时候，当我们给一个面试候选人出了一道“算法题”的时候，当我们提到“区块链算法”的时候，我们所说的算法，可能指的是排序算法、递归算法、随机算法、加密算法等等。这些“算法”，未必是我们现在“算法工程师”们日常工作中的最主要的内容，这其中有一些“算法”，是所有程序员必备的基础知识；而另外一些“算法”，似乎是算法工程师们所专有的。“算法（Algorithms）”这个概念太模糊，以至于不会有一个清晰的内涵和外延。假如“算法”这个概念本身不那么清晰，那么“算法工程师”又是如何定义的呢？在国外，比如硅谷，是没有“算法工程师”这样的概念的，那里有数据科学家（Data Scientist）、应用科学家（Applied Scientist）、AI工程师（AI Engineer）、机器学习工程师（Machine Learning Engineer），唯独没有“Algorithm Engineer”这样的职位。在国内互联网公司，最常见的对于“算法工程师”的定义，有两种：工具视角：以“机器学习（或优化）”等技术为日常工作主要工具的工程师，称为算法工程师。就好比说，以“锛凿斧锯”为日常工作主要工具的工程师，我们称之为“木匠”一样，这种定义类似于Machine Learning Engineer。目的视角：以“优化某可量化业务指标”为日常工作主要目的的工程师，称为算法工程师。就好比说，以“制作一个木质家具”为日常工作主要目的的工程师，我们称之为“木匠”一样，这种定义类似于“指标优化工程师”。两种定义的视角，无所谓对错，但是会塑造出不一样的算法工程师。“工具视角”下的算法工程师，对于“工具”的使用熟练程度可能会比较高，但是可能会缺少业务感和目的感，缺少全栈化的能力和意愿；而“目的视角”下的算法工程师，与前者相反，有不错的业务感和目的感，大多数有不错的全栈化能力和意愿，但是对于“工具”的使用熟练程度未必那么高。（PS：“目的视角”下的算法工程师的定义，引发了另外一个问题：假如说以“优化某可量化业务指标”为日常工作主要目的的工程师，是算法工程师，那么非算法岗位的其他开发工程师，是否就不关心或者说不能优化业务指标了呢？答案当然是否定的，本文就不详细展开讨论了。）2 电商算法阿里的算法工程师有很大一部分是服务于电商业务的，说说我对于“电商算法”的理解：我们认为，电商算法的主要工作，都围绕着“分配（Allocation）”二字展开，要么是“分配”本身，比如对于外投营销预算、销售佣金、广告主的P4P预算和运营红包的分配、对于销售、拍档和运营的时间精力的分配、对于买家的注意力（商机）的分配；要么就是为了更好地“分配”而做的基建或准备工作，比如对电商核心要素的数据标准化、对于视频和直播等内容更深入的理解、对于分配过程中作弊行为的识别和打击。根据资源“分配”过程本身市场化程度的高低、分配过程中人为主观因素的重要程度、被分配资源的规模量级、分配所造成的业务影响的即时性、分配对于实时性的要求，演化出了对算法团队不同的要求：从以市场经济为主体，算法以中立（neutral）身份参与分配过程的方式到以宏观调控为主体，算法主动干预分配过程的方式。从组合和最优化类的算法问题到机器学习类的算法问题。从以模型预测精准度为目标的有监督学习任务到以长期和全局的收益（reward）最大化为目标的强化学习任务。从基于强可解释性要求的树模型算法到基于弱可解释性的深度神经网络模型算法。从离线的算法建模工作到提供在线实时化的算法产品化的服务。从单目标优化的算法问题到多目标带约束优化的算法问题。丰富多彩的应用场景，孕育了各种各样的问题定义，不同的问题定义又催生出了不同的算法方案以及对于算法同学能力的不同要求。效率和公平是衡量“分配”是否是“好分配”的两个重要维度，通常来说，在分配效率还很低的时候，算法的关注点与优化的重点都在效率提升方面，对于“公平”还不会考虑太多，而一旦效率提升到接近天花板的水平之后，“公平”问题开始浮出水面，应该引起算法更多的重视。如何量化“效率和公平（尤其是公平）”不仅仅是算法问题，更涉及到道德伦理、经济学、博弈论、数据科学等交叉学科，可以说是电商算法领域最复杂最核心的问题，甚至受到了人民日报[2]的关注。3 ICBU算法先从一张所谓的“算法大图”开始：ICBU算法团队，隶属于ICBU技术部，服务于ICBU业务。它的整体工作，从上面算法大图的视角来看，可以分为3大部分：理解（Understanding）、增长（Growth）和匹配（Matching），它们也分别对应了Market Place的“货、人、场”三个部分：理解（Understanding）指的是基于计算机视觉（CV）、自然语言处理（NLP）、深度学习（Deep Learning）、数据标准化（Data Standardization）和知识图谱（Knowledge Graph）等基础算法能力，打造整个业务的数字化基建底盘，提升我们对于商品（货）、内容（短视频和直播）、买卖家、行业趋势、市场供需等方面的理解，提升商品、内容和商家的数字化程度，并基于这些理解去赋能增长和匹配的环节，降本增效。增长（Growth）指的是在固定资源成本约束下，通过算法对于资源的最优化分配，来实现电商业务核心要素的买卖家（人）最大化增长，根据所分配资源的不同，可以分成三个方面：第一方面（狭义理解的）买家增长，主要是基于组合优化、趋势发现（forecasting）、最优化（Optimization）、对抗智能等基础算法能力，来最优化分配外投的市场预算，实现固定预算的情况下的业务价值（LTV/AB）最大化。第二方面，卖家增长，主要是基于数据驱动、机器学习、统计建模、因果推断（Casual Inference）等基础算法能力，来最优化分配销售和拍档的时间与精力，实现有限销售和拍档规模的情况下，新签、续签的会员费营收最大化。第三方面，智能运营，基于算法赋能，最优化分配运营的精力、买卖家运营红包和免服务费等运营权益，实现支付买家数、订单数、GMV和供应链营收的最大化。匹配（Matching）指的是在包括搜索、推荐和广告在内的大市场，完成买卖家的高效撮合匹配。主要是基于机器学习、最优化和E&E等基础算法能力，在最大化市场长期和全局的匹配效率，追求有效商机极大产出（AB/Pay/GMV）的同时，实现商机在自然品和广告品之间的合理分配（商业化问题）、商机在首次商机和往复商机之间的合理分配（贪心问题）、商机在头部商家和尾部商家之间的合理分配（马太问题）、商机在新品和爆品之间的合理分配（新品成长问题）、商机在RTS品和询盘品之间的合理分配（双赛道问题）、商机在CGS和GGS商家之间的合理分配（GGS问题）、商机在各个行业之间的合理分配（行业化问题）、算法需要回答如何定义和度量（Define & Measure）上述7个“合理”，它们之间的关系，以及如何优化它们。如上图所示，理解、增长和匹配，形成了一个：理解->增长->匹配->增长……的飞轮，带动整个ICBU业务的数字智能化的进程。二 2020年ICBU算法工作总结接下来分别向大家分享一下“理解”、“增长”和“匹配”三个领域的重要技术成果（以下内容引用自ICBU算法团队相关文章）。1 理解（Understanding）场景底料挖掘Alibaba.com国际站中，场景导购在首页中占据着非常重要的地位，但长期起来并没有体系化的场景生成方案，基本依靠人工经验来完成场景的构建，而且B类采购的专业性、跨境贸易的文化多样性、国际环境的不确定性更为有效的导购场景设置了天然的障碍。因此我们针对B类采购的需求，构建了B类场景生成方案，包含了2大特色：基于cpv的细分市场生成。模拟用户组合采购的事件场景生成。在网站App首页、搜索推荐、云主题等场景应用，在过去一年里，算法对场景内容的丰富和优化，为网站带来了AB和支付买家数提升的业务价值。智能发品ICBU作为承接全球B类买家寻源的重要电商平台之一，一直致力于帮助来自国内的供应商（CGS）和海外供应商（GGS）发布优质的商品信息。商品表达的丰富度和确定性一直是影响买家询盘，交易转化的重要因素。为了解决很多商家缺乏运营能力、表达能力弱、重要属性不填或者滥填、不知道该怎么填写合理的商品标题等问题，算法建立标题属性自动生成工具，其中提出了两大创新点：finetuning预训练文本生成模型BART，构建了文本生成模型。结合ICBU流量特性，将生成语料更符合B类电商检索和阅读。项目上线实验效果为，在商品信息丰富度上整体约提升6%，算法推荐标题内容采纳率CGS约32%，GGS约42%，实验对比发现通过智能发布的商品在曝光效果提高约40%。电商场景下的细粒度图像分类商品图像是商品信息展示最重要的组成部分之一，网站图像质量经过商品信息治理后已有很大提升，但仍缺乏对图像内容的识别和理解能力。同时，B类商品标准化需要结合图像标签能力进行商品信息扩展和校验，输出商品结构化表达。我们针对网站需求构建的图像标签服务具有以下特色：细粒度图像分类模型。为提高对相似商品识别的区分能力，提出一种基于主体分割和图关系网络的图像标签识别方法，扩大图像标签的精准度和召回率。沉淀了B类特色图像标签体系，基于CPV品类体系抽象出外观有显著区分度的品类以及属性作为图像标签输出能力，标签体系已覆盖交易TOP15行业，数千个品类标签。该项目会应用于搜索相关性提升和商品内容理解，沉淀的技术创新《Object Decoupling with Graph Correlation for Fine-Grained Image Classification》已投稿于ICME2021会议。视频检测、分析、创意在视频创意外投承接项目中，我们基于对视频智能创作流程的理解，设计出了一套基于优质视频进行视频合成的方法，提出视频智能裁切等创新点，解决了视频智能多尺寸、视频素材优选、视频创意美化的难题，克服了目前网站视频素材质量参差不齐、海外平台本地化的挑战。该项目上线后，共生成视频创意若干个，为ICBU业务节省了若干的创意成本；该项目在取得业务价值的同时，所沉淀的技术创新能力也得到了业界的认可，该技术目前已经应用开源。2 增长（Growth）外投预算分配在智能预算分配1.0项目中，我们基于站内外付费流量数据的深刻洞察，提出了基于分层强化学习的智能预算分配方案，包含了3大创新点:设计了预估器-求解器架构求解整体预算分配问题。使用站内外渠道/国家等特征对付费渠道进行回归预估，构建模型学习环境。设计了基于分层强化学习的算法求解器，高效求解预算分配问题。通过分层强化学习等创新设计，有效克服了预算分配与强化学习领域中的稀疏奖赏与延迟奖赏问题，增加求解精度与效率。项目上线后，为付费PPC渠道cpab降低10.3%，该项目还形成了核心创新方案《基于自注意力机制的强化学习预算分配解决方案》和《基于分布式神经进化算法的多目标预算分配模型优化方案》。horae精排在horae 1.0项目中，我们基于对付费流量特性的深刻洞察，在付费流量场景从0开始搭建整套召回+排序体系，提出3大创新点：基于站外曝光品的用户行为采集。充分使用站外渠道/国家特征。基于核心属性的交叉特征构建。对付费流量进行单独建模，解决了付费流量与站内流量在分布上存在巨大差异的领域难题。同时克服了付费流量样本较少的问题，context特征大量采用站外特征，而商品特征大量采用全站统计特征，充分利用站内数据进行辅助学习。项目上线后，为ICBU展示广告业务带来了App端AB rate提升13.6%，Wap端AB rate 提升3%。供需匹配构建在先知（红蓝海）项目中，我们基于对买卖家数据的深刻洞察，设计出了用来度量人货匹配和供给选择的量化指标，提出了蓝海度、竞争力、丰富度三维指数， 带来了从销售驱动的供给升级为基于行业路径和买家需求的定招培育新引擎。该项目上线后，平均签单周期缩短8%，发MC15提升44%，品效是大盘2倍之多。该项目在取得业务价值的同时，也取得了技术创新，各指数综合了站内数百特征的同时，结合利用基于时序TRMF预测的未来趋势和周期性走势。买家意愿订单确认在Stellar项目中，我们基于卖家待确认PO单数量较大导致订单无法及时确认，影响O-P转化的业务痛点，提出基于买家质量、卖家接单偏好及订单质量等维度，基于树模型实时预测优质PO单，并解决了数据质量提升、样本不均衡、id特征及长尾类别特征等技术难题，缓解了O-P链路环节中卖家确认率低的业务难题。该项目上线后，PO单确认率提升7pt，O-P转化+1.2%。TAO商家智能运营在TAO拉新项目中，我们发现在供应链运营场景，拍档的人力是有限的，但是客户规模不断在增长，如何在有限的人力情况下提升拍档的人效，我们提出通过大数据的学习及模型可解释能力，预测潜客分层及千人千面诊断&Action，为拍档提供傻瓜式的行动指引，项目中使用SHAP、子模型等可解释技术方案，并将算法解释转换为可执行的Action。该项目上线后，为ICBU业务带来了，TAO拉新转化率+8.46%，累计贡献GMV提升的业务价值。物流费用精准预测在尼斯湖双十二买家物流五折项目中，我们发现传统的营销运营是广撒网式的做法，由于与自然转化客群有较大的交集会造成较多的预算浪费，因此我们首先通过对具备采购需求严肃买家支付卡点的分析洞察，进而提出在营销预算有限的情况下，通过算法精准预测物流费用敏感的支付增量人群的创新点。该项目上线后，为ICBU业务带来了月均支付增量买家数提升，和ROI提升的业务价值。3 匹配（Matching）动态网络表征学习在DyHAN（动态图向量检索）项目中，我们发现买家在寻源过程中在不断尝试寻找更有效的供应商，导致买卖家形成的关系图随着时间推移在不断演进。而之前基于静态图的模型无法捕捉这种变化，因此我们提出了基于动态图的表征学习方法，解决了电商表征建模领域节点信息不断演进带来的问题。该项目在ICBU商品详情页跨店推荐上线后，核心的询盘转化率提升3.54%，创建订单转化率提升14.23%；该项目在取得业务价值的同时，所沉淀的技术创新也得到了业界认可，沉淀的《Dynamic Heterogeneous Graph Embedding using Hierarchical Attentions》和《Modeling Dynamic Heterogeneous Network for Link Prediction using Hierarchical Attention with Temporal RNN》论文，分别被ECIR2020和ECML-PKDD2020会议收录 。深度多兴趣网络在DMIN（深度多兴趣排序建模）项目中，我们基于ICBU买家特点，发现部分零售商和采购商，其采购商品往往横跨多个类目，且在多个类目的偏好程度随时间出现变化。我们基于DIN模型，提出多层次的多兴趣抽取网络模型，提升了模型动态建模买家多兴趣的精准性。该项目在ICBU推送推荐场景上线后，曝光点击率提升10.4%，买家订单转化率提升13%；该项目在取得业务价值的同时，所沉淀的技术创新也得到了业界认可，沉淀的《Deep Multi-Interest Network for Click-through Rate Prediction》论文，被CIKM’20会议收录。向量召回跨境B类搜索场景下用户搜索词更加多样化、表达更加专业化，基于传统的关键字召回技术零少问题很严重，搜索长尾流量占比将近30%。从2018年开始，ICBU搜索就开始着手探索向量召回技术，用空间向量距离来进行相似度估计，从语义层面进行最相关(距离最近)产品的召回。今年ICBU搜索首次尝试利用BERT模型结构，自研FashionBERT做到更细粒度的多模态匹配，目前已经基本解决ICBU搜索的零少问题。在项目中，我们将商品图像用于召回，即将Query和item image的对应关系转化为图文匹配。我们提出FashionBERT图文匹配模型，直接将图像split相同大小的Patch，然后将Patch作为图像的token，和文本进行拟合。同时增加wordpiece来解决oov问题，query graph attention(GAT)来增加长尾Query的泛化能力。我们在电商领域FashionGen数据集，对比了主流图文匹配技术，FashionBERT取得非常明显的提升，目前论文《FashionBERT: Text and Image Matching with Adaptive Loss for Cross-modal Retrieval》已被SIGIR2020 Industry Track接收。语义搜索ICBU用户搜索词更加多样化表达更加专业化，召回和匹配一直是ICBU网站的搜索优化重点。2020年上半年我们完成了语义搜索1.0（向量召回3.0+语义匹配1.0）的升级，基本解决了相关性零少问题和缓解了关键字字面匹配局限问题，但是从通过人工达标分析case，发现当前链路依然存在Query理解不足-类目预测不准；核心词提取不准；关键相关性和语义相关性融合方式欠佳等三个问题；针对这些问题，我们融合三个子项目ICBU NER 1.0，类目预测2.0和相关性2.0（融合优化+NER调档）。进行联合优化，取得了非常不错的业务结果：高相关商品曝光占比提升6%，搜索相关性零少下降8%，点击提升+0.65%，询盘提升1.44%，支付转化提升6.30%。类目预测对于ICBU而言，类目预测算法的应用场景非常广泛。在搜索系统中，类目预测结果是商品相关性的重要判定标准，会直接影响搜索结果的召回和排序。对于搜索广告而言，类目预测也直接影响买家体验和广告主效果。因此我们针对ICBU类目预测算法中存在的核心问题进行了重点优化：文本语义分类模型由fasttext升级到了BERT。借助ICBU在NER技术上的沉淀，通过Query中关键NER属性词组召回相应类目。类目预测算法优化取得了不错的效果：离线评测指标：0档位top1类目准确率+5%, 0档位整体类目准确率+2.4%，0档位类目召回提升了12.0%。打包语义搜索项目整体，搜索业务指标影响：PC端 L-D +0.65%，L-AB +1.44%，L-P +6.30% ；APP端 L-D +0.69%，L-AB +1.93%，L-P +1.96%。对于广告业务指标影响：预算分桶下pv2f +2%，rpm+1%，badcase降低3.4%。跨语言向量召回我们利用全新的跨语言向量召回技术，跨越Query翻译的障碍，极大丰富搜索召回结果，促进转化效率的提升。该创新技术通过基于大规模平行数据的跨语言预训练模型EcomLM，解决不同语言难以映射到同一语义空间的难题。结合商业表征以及用户行为信息的间接交互模型，克服了传统双塔模型信息隔离的问题。实验结果表明，通过跨语言向量召回，搜索零少结果率下降至1%以下，V1.0版本多语言整体L-AB +1.34%，L-P +4.2%。此外，我们在语种识别、Query翻译、多语言语义相关性模型等模块也有一定的技术积累，旨在打造一套完整的跨语言搜索解决方案。结构化理解ICBU作为国际B类跨境贸易的战场，在当前网站的关键词相关性部分仍存在这个一些问题，例如匹配准度不够、中心词提取错误、类目预测准确率低。以中心词提取模块为例，在关键词匹配的错误中，中心词提取错误占了40%，不仅如此，中心词提取也缺乏提取Query或title中关键属性的能力，例如用户搜索商品时指定的颜色、规格等，这些都是中心词提取模块所欠缺的，因此从国际站搜索的角度来看，迫切需要NER工具来提升目前的关键词匹配准确行。首先，我们通过与达摩院多语言NLP基础团队的合作将NER直接用于搜索匹配中，通过NER来对Query与商品之间实现属性匹配，基于NER模型的属性匹配，不仅解决了中心词提取模块准确率低的问题，同时也能够通过对其Query与offfer中的相同属性，从而给予用户更加精准的搜索体验。另一方面，NER也赋能ICBU中的其他业务，如类目预测等、新属性发现、CPV属性扩充等，在新的季度，我们也会将NER搜索算法的各个方面，如深度语义匹配，个性化召回等。三 一些思考1 数据与算法对于业务技术团队而言，数据，可以从两个方面去理解它：数据科学（业务指标和因果推断）——用来回答“算法要去向何方以及如何判断算法做的事情是否成功”的一个可量化的标准。数据资产——买卖家的行为和整个业务连路上沉淀下的所有数据资产。数据资产和算法的关系可以理解为：数据资产是燃料，算法是引擎，引擎的输出取决于燃料的质量和数量。或者说，数据资产是底层的基础，算法是上层的应用，算法离开了数据资产的养分，就是无源之水无本之木。数据科学和算法的关系可以理解为：数据科学是确定方向和目标、定义问题、指路明灯，是立靶子。而算法做的事情是在定了方向和目标之后，如何高效率地去标准靶子，去高效率地追逐目标。结合这两个角度来看，算法和数据，密不可分，数据科学为算法定义了问题和目标方向，而数据资产又为算法提供了燃料，供算法充分挖掘并使得算法有机会去逼近数据科学指定的目标，并高效地解决数据科学所提出的问题。2 目标的重要性前面刚刚说到了“数据科学为算法定义了问题和目标方向”，下面我聊聊“目标”这个话题，我拿一个真实的故事举个例子：《印尼悬赏除鼠患遭质疑：有人为领奖会养老鼠》[1]。上面真实故事里面，初衷是好的，以OKR来举例的话，O（目标）可能是“创建卫生城市，消灭鼠患”。KR的话，有可能是：“通过科学灭鼠的方式，（消灭1000w只老鼠）收集到1000w条的老鼠尾巴。”消灭鼠患，当然要杀死老鼠；杀死老鼠越多，鼠患消除的越彻底；而杀死老鼠越多，老鼠尾巴就应该会越多——所以我们拿“老鼠尾巴”的个数，来作为一个可量化指标来度量“消灭鼠患”这个目标完成的怎么样，似乎是一个合理的选择？问题在于落地和执行，在这个“老鼠尾巴”这个量化指标的激励下，人们在执行时，会走偏，会发生“养老鼠”这样奇葩的事情。一个目标，对于一个业务的成败来说，其重要性，无论多么强调都不为过。3 对于未来AB的优化我们B类跨境外贸在大市场（搜索推荐）算法领域的特点是什么？传统偏C类电商的搜索推荐场景下，买家的转化行为周期比较短，这个转化的目标是一个离散的目标：可以是强转化（成交），也可以是弱转化（加购、收藏、关注），但无论是强弱转化目标，算法建模的目标的都是一个离散的、脉冲式的单点的短期转化行为的概率，算法优化的目标也同样是这个离散的、脉冲式的单点的短期转化行为的数学期望的最大化。而我们B类的跨境贸易电商场景下，一个B类买家的转化行为周期很长，这个转化的目标，不应该是一个离散的目标——比如当天是否会发生AB行为，而应该是一个连续化的目标：一个买家在未来的每一天里会发生AB的行为的概率，我们需要对这个AB在他整个生意周期当中，会留存在ICBU的概率进行连续化地建模和连续化地优化。如果说C类电商搜索推荐场景下，C类买家的整个转化行为周期比较短，因此建模和优化的目标本身应该也比较短的，是一个突兀的脉冲点的话，那么我们B类电商搜索推荐建模和优化的目标应该是一段持续稳健上升的曲线。也许是我们B类跨境贸易算法需要优化和建模的重要特点，值得我们思考。当下的优化简单的说，当下的优化，算法的目标是去最大化每一次曝光机会转化为一个AB行为的概率，因此算法真正需要去建模的，就是下面这个概率：对于当下优化的反思与拆解我们对当下的搜索推荐的算法优化的反思主要来自两个方面：让我们再仔细回顾一下我们真正想要的Tartet 0（原目标），并对它进行一个细致的拆解：如上图所示，我们有几个思考：首先，“日均AB”可以拆解为首次AB（AB Today）+往复AB（AB Past）。我们假设——在搜索推荐当下的算法策略，会影响到未来的往复AB，基于这个假设，可以将这里的往复AB，继续拆解，成一个无穷级数，从昨天（-T1）开始，一直回溯到无穷远（-T∞）的过去，然后累加，当然越久远的过去对当下的影响会越弱。过去与未来的置换过去的曝光我们已经无法优化了，但是未来对于我们有意义的，因此我们把经过拆解的Target 0里面的AB Past（往复AB）里面的“过去”的概念，替换为“未来”，从新生成一个值：AB Future，它度量的是当天由搜索推荐分发的所有商机对于未来贡献的往复AB的总和的一个期望。同时基于AB Future我们提出了一个新的优化目标：Target 4而当i=0的时候，T0对于T0的AB贡献，就是首次AB的定义，因此可以将上面的目标简写成如下的格式，i从0开始。四 展望接下来，我们的几个重点包括：智能化运营&买卖家增长之间的更多联动、内容化、搜推大市场的优化目标新定义、E&E马太问题&在监管之下的调控等。接下来的一年，将是算法团队再起飞的一年，算法团队将更聚焦、做更少的事（但需要更多的人），每做一件事都做深做透，不求每件事都成功，但求每件事都有收获，无论是业务上的、技术上的，还是经验教训上的，并争取交出算法团队自身的代表作。

一 问题排查 1 常见问题 Know Your Enemy：知己知彼，百战不殆。 日常遇到的大部分问题，大致可以归到如下几类： 逻辑缺陷：e.g. NPE、死循环、边界情况未覆盖。 性能瓶颈：e.g. 接口 RT 陡增、吞吐率上不去。 内存异常：e.g. GC 卡顿、频繁 FGC、内存泄露、OOM 并发/分布式：e.g. 存在竞争条件、时钟不同步。 数据问题：e.g. 出现脏数据、序列化失败。 安全问题：e.g. DDoS 攻击、数据泄露。 环境故障：e.g. 宿主机宕机、网络不通、丢包。 操作失误：e.g. 配置推错、删库跑路（危险动作，请勿尝试..）。 上述分类可能不太完备和严谨，想传达的点是：你也可以积累一个这样的 checklist，当遇到问题百思不得其解时，耐心过一遍，也许很快就能对号入座。 2 排查流程 医生：小王你看，这个伤口的形状，像不像一朵漂浮的白云？ 病人：...再不给我包扎止血，就要变成火烧云了。 快速止血 问题排查的第一步，一定是先把血止住，及时止损。如何快速止血？常见方式包括： 发布期间开始报错，且发布前一切正常？啥也别管，先回滚再说，恢复正常后再慢慢排查。 应用已经稳定运行很长一段时间，突然开始出现进程退出现象？很可能是内存泄露，默默上重启大法吧。 只有少数固定机器报错？试试隔离这部分机器（关闭流量入口）。 单用户流量突增导致服务不稳定？如果不是惹不起的金主爸爸，请勇敢推送限流规则。 下游依赖挂了导致服务雪崩？还想什么呢，降级预案走起。 保留现场 血止住了？那么恭喜你，至少故障影响不会再扩大了。卸下锅，先喘口气再说。下一步，就是要根据线索找出问题元凶了。作为一名排查老手，你需要有尽量保留现场的意识，例如： 隔离一两台机器：将这部分机器入口流量关闭，让它们静静等待你的检阅。 Dump 应用快照：常用的快照类型一般就是线程堆栈和堆内存映射。 所有机器都回滚了，咋办？别慌，如果你的应用监控运维体系足够健全，那么你还有多维度的历史数据可以回溯：应用日志、中间件日志、GC 日志、内核日志、Metrics 指标等。 定位原因 OK，排查线索也有了，接下来该怎么定位具体原因？这个环节会综合考验你的技术深度、业务熟悉度和实操经验，因为原因往往都千奇百怪，需要 case by case 的追踪与分析。这里给出几个排查方向上的建议： 关联近期变更：90% 以上的线上问题都是由变更引发，这也是为什么集团安全生产的重点一直是在管控“变更”。所以，先不要急着否认（“肯定不是我刚加的那行代码问题！”），相信统计学概率，好好 review 下近期的变更历史（从近至远）。 全链路追踪分析：微服务和中台化盛行的当下，一次业务请求不经过十个八个应用处理一遍，都不好意思说自己是写 Java 的。所以，不要只盯着自己的应用不放，你需要把排查 scope 放大到全链路。 还原事件时间线：请把自己想象成福尔摩斯（柯南也行），摆在你面前的就是一个案发现场，你需要做的是把不同时间点的所有事件线索都串起来，重建和还原整个案发过程。要相信，时间戳是不会骗人的。 找到 Root Cause：排查问题多了你会发现，很多疑似原因往往只是另一个更深层次原因的表象结果之一。作为福尔摩斯，你最需要找到的是幕后凶手，而不是雇佣的杀人犯 —— 否则 TA 还会雇人再来一次。 尝试复现问题：千辛万苦推导出了根因，也不要就急着开始修 bug 了。如果可以，最好能把问题稳定复现出来，这样才更有说服力。这里提醒一点：可千万别在生产环境干这事（除非你真的 know what you're doing），否则搞不好就是二次伤害（你：哈哈哈，你看，这把刀当时就是从这个角度捅进去的，轨迹完全一样。用户：...）。 解决问题 最后，问题根因已经找到，如何完美解决收尾？几个基本原则： 修复也是一种变更，需要经过完整的回归测试、灰度发布；切忌火急火燎上线了 bugfix，结果引发更多的 bugs to fix。 修复发布后，一定要做线上验证，并且保持观察一段时间，确保是真的真的修复了。 最后，如果问题已经上升到了故障这个程度，那就拉上大伙好好做个故障复盘吧。整个处理过程一定还有提升空间，你的经验教训对其他同学来说也是一次很好的输入和自查机会：幸福总是相似的，故障也是。 3 排查工具 手里只有锤子，那看什么都像钉子。作为工程师，你需要的是一整套工具箱。 问题排查其实就是一次持续观测应用行为的过程。为了确保不遗漏关键细节，你需要让自己的应用变得更“可观测（Observable）。 提升应用可观测性有三大利器：日志（Logging）、监控（Metrics）、追踪（Tracing）。在我之前所做的项目中，这三块能力分别是由 SLS、Alimonitor / AliMetrics / Tsar、EagleEye 提供的，这里就不再展开描述了。 另外也很推荐 Arthas 这个工具，非常实用和顺手，相信很多同学都已经用过。 二 系统优化 只学会了问题排查还远远不够（当然技能必须点满，shit always happen），再熟练也只是治标不治本。如果想从根源上规避问题，必须从系统本身出发：按照性能、稳定性和可维护性三个方向，持续优化你的系统实现，扼杀问题于摇篮之中，让自己每天都能睡个安稳觉。 老板：既要快，又要稳，还要好。哦，工资的事你别担心，下个月一定能发出来。 系统优化的三个基本方向：性能（Performance）、稳定性（Stability）、可维护性（Maintainability）。三者之间并不是完全独立的，而是存在着复杂的相互作用关系，有时甚至会此消彼长。 最优秀的软件系统，并非要把这三个方向都做到极致，而是会根据自己实际的业务需求和场景合理取舍，在这三者之间达到一个综合最优的动态平衡状态，让各方面都能做到足够好即可。 所以，优化不只是一门科学，也是一门艺术。 1 性能优化 问：要跑出最快的圈速，是车手重要，还是赛车重要？ 答：全都重要。 没有哪个男人会不喜欢高性能跑车，也没有哪个女人会希望在看李佳琦直播时突然卡顿。 性能，是各行各业工程师们共同追求的终极浪漫。 性能指标 指标（Indicators）是衡量一件事物好坏的科学量化手段。对于性能而言，一般会使用如下指标评估： 吞吐率（Throughput）：系统单位时间内能处理的工作负载，例如：在线 Web 系统 - QPS/TPS，离线数据分析系统 - 每秒处理的数据量。 响应时间（Response Time）：以 Web 请求处理为例，响应时间（RT）即请求从发出到收到的往返时间，一般会由网络传输延迟、排队延迟和实际处理耗时几个部分共同组成。 可伸缩性（Scalability）：系统通过增加机器资源（垂直/水平）来承载更多工作负载的能力；投入产出比越高（理想情况是线性伸缩），则说明系统的可伸缩性越好。 此外，同一个系统的吞吐率与响应时间，一般还会存在如下关联关系：吞吐率小于某个临界值时，响应时间几乎不变；一旦超出这个临界值，系统将进入超载状态（overloaded），响应时间开始线性增长。对于一个有稳定性要求的系统，需要在做性能压测和容量规划时充分考虑这个临界值的大小。 注：其实按更严谨的说法，性能就是单指一个系统有多“快”；上述部分指标并不纯粹只代表系统快慢，但也都与快慢息息相关。 性能分析 古人有句老话，If you can't measure it, you can't improve It. 要优化一个系统的性能（例如Web请求响应时间），你必须首先准确地测量和分析出，当前系统的性能究竟差在哪：是请求解析不够快，还是查询 DB 太慢？如果是后者，那又是扫描数据条目阶段太慢，还是返回结果集太慢？或者会不会只是应用与 DB 之间的网络延迟太大？ 任何复杂请求的处理过程，最终都可以拆解出一系列并行/串行的原子操作。如果只是逮住哪个就去优化哪个，显然效率不会太高（除非你运气爆棚）。更合理的做法，应该是坚持 2/8 原则：优先分析和优化系统瓶颈，即当前对系统性能影响最大的原子操作；他们很可能就是 ROI 最高的优化点。 具体该如何去量化分析性能？这里列出了一些工具参考： 系统层面：tsar、top、iostat、vmstat 网络层面：iftop、tcpdump、wireshark 数据库层面：SQL explain、CloudDBA 应用代码层面：JProfiler、Arthas、jstack 其中很多工具也是问题排查时常用的诊断工具；毕竟，无论是性能分析还是诊断分析，目的都是去理解一个系统和他所处的环境，所需要做的事情都是相似的。 优化原则 你应该做的：上面已经提了很多，这里再补充一点：性能优化与做功能需求一样，都是为业务服务的，因此优化时千万不要忙着自嗨，一定要结合目标需求和应用场景 —— 也许这块你想做的优化，压根线上就碰不到；也许那块很难做的优化，可以根据流量特征做非通用的定制优化。 你不应该做的：即老生常谈的提前优化（Premature-optimization）与过度优化（Over-optimization） —— 通常而言（并不绝对），性能优化都不是免费的午餐，优化做的越多，往往可维护性也会越差。 优化手段 常用的性能优化手段有哪些？我这里总结了 8 个套路（最后 1 个是小霸王多合一汇总套路）。 1）简化 有些事，你可以选择不做。 业务层面：e.g. 流程精简、需求简化。 编码层面：e.g. 循环内减少高开销操作。 架构层面：e.g. 减少没必要的抽象/分层。 数据层面：e.g. 数据清洗、提取、聚合。 2）并行 有些事，你可以找人一起做。 方式：单机并行（多线程）、多机并行（分布式）。 优点：充分利用机器资源（多核、集群）。 缺点：同步开销、线程开销、数据倾斜。 同步优化：乐观锁、细粒度锁、无锁。 线程替代（如协程：Java WISP、Go routines、Kotlin coroutines）。 数据倾斜：负载均衡（Hash / RR / 动态）。 3）异步 有些事，你可以放手，不用死等。 方式：消息队列 + 任务线程 + 通知机制。 优点：提升吞吐率、组件解耦、削峰填谷。 缺点：排队延迟（队列积压）。 避免过度积压：Back-pressure（Reactive思想）。 4）批量 有些事，你可以合起来一起做。 方式：多次单一操作 → 合并为单次批量操作。 案例：TCP Nagel 算法；DB 的批量读写接口。 优点：避免单次操作的固有开销，均摊后总开销更低。 缺点：等待延迟 + 聚合延迟。 减少等待延迟：Timeout 触发提交，控制延迟上限。 5）时间空间互换 游戏的本质：要么有闲，要么有钱。 空间换时间：避免重复计算、拉近传输距离、分流减少压力。 案例：缓存、CDN、索引、只读副本（replication）。 时间换空间：有时候也能达到“更快”的效果（数据量减少 → 传输时间减少）。 案例：数据压缩（HTTP/2 头部压缩、Bitmap）。 6）数据结构与算法优化 程序 = 数据结构 + 算法 多了解一些“冷门”的数据结构 ：Skip list、Bloom filter、Time Wheel 等。 一些“简单”的算法思想：递归、分治、贪心、动态规划。 7）池化 & 局部化 共享经济 & 小区超市 池化（Pooling）：减少资源创建和销毁开销。 案例：线程池、内存池、DB 连接池、Socket 连接池。 局部化（Localization）：避免共享资源竞争开销。 案例：TLB（ThreadLocalBuffer）、多级缓存（本地局部缓存 -> 共享全局缓存）。 8）更多优化手段 升级红利：内核、JRE、依赖库、协议。 调参大师：配置、JVM、内核、网卡。 SQL 优化：索引、SELECT *、LIMIT 1。 业务特征定制优化：e.g. 凌晨业务低峰期做日志轮转。 Hybrid 思想（优点结合）：JDK sort() 实现、Weex/RN。 2 稳定性优化 稳住，我们能赢。—— by [0 杀 10 死] 正在等待复活的鲁班七号 维持稳定性是我们程序员每天都要思考和讨论的大事。 什么样的系统才算稳定？我自己写了个小工具，本地跑跑从来没出过问题，算稳定吗？淘宝网站几千人维护，但双十一零点还是经常下单失败，所以它不稳定喽？ 稳定是相对的，业务规模越大、场景越复杂，系统越容易出现不稳定，且带来的影响也越严重。 衡量指标 不同业务所提供的服务类型千差万别，如何用一致的指标去衡量系统稳定性？标准做法是定义服务的可用性（Availability）：只要对用户而言服务“可用”，那就认为系统当前是稳定的；否则就是不稳定。用这样的方式，采集和汇总后就能得到服务总的可用/不可用比例（服务时长 or 服务次数），以此来监测和量化一个系统的稳定性。 可是，通过什么来定义某个服务当前是否可用呢？这一点确实跟业务相关，但大部分同类业务都可以用类似的方式去定义。例如，对于一般的 Web 网站，我们可以按如下方式去定义服务是否可用：API 请求都返回成功，且页面总加载时间 < 3 秒。 对于阿里云对外提供的云产品而言，服务可用性是一个更加需要格外重视并持续提升的指标：阿里云上的很多用户会同时使用多款云产品，其中任何一款产品出现可用性问题，都会直接被用户的用户感知和放大。所以，越是底层的基础设施，可用性要求就越高。关于可用性的更多细节指标和概念（SLI / SLO / SLA），可进一步参考云智能 SLA 了解。 可用性测量 有了上述可用性指标定义后，接下来该如何去准确测量系统的可用性表现？一般有如下两种方式。 1）探针模拟 从客户端侧，模拟用户的调用行为。 优点：数据真实（客户端角度） 缺点：数据不全面（单一客户数据） 2）服务端采集 从服务端侧，直接分析日志和数据。 优点：覆盖所有调用数据。 缺点：缺失客户端链路数据。 对可用性数据要求较高的系统，也可以同时运用上述两种方式，建议结合你的业务场景综合评估选择。 优化原则 你应该做的：关注 RT 的数据分布（如：p50/p99/p999 分位点），而不是平均值（mean） —— 平均值并没有太大意义，更应该去关注你那 1%、0.1% 用户的准确感受。 你不应该做的：不要尝试承诺和优化可用性到 100% —— 一方面是无法实现，存在太多客观不可控因素；另一方面也没有意义，客户几乎关注不到 0.001% 的可用性差别。 优化手段 常用的稳定性优化手段有哪些？这里也总结了 8 个套路： 1）避免单点 父母：一个人在外漂了这么多年，也该找个人稳定下来了。 如何避免？ 集群部署 数据副本 多机房容灾 只堆量不够，还需要具备故障转移能力（Failover）。 接入层：DNS、VipServer、SLB。 服务层：服务发现 + 健康检查 + 剔除机制。 应用层：无状态设计（Stateless），便于随时和快速切换。 2）流控/限流 计划生育、上学调剂、车牌限号、景区限行... 人生处处被流控。 类型：QPS 流控、并发度流控。 工具：RateLimiter、信号量、Sentinel。 粒度：全局、用户级、接口级。 热点流控：避免意料之外的突增流量。 3）熔断 上午买的股票熔断，晚上家里保险丝熔断... 淡定，及时止损而已。 目的：防止连锁故障（雪崩效应）。 工具：Hystrix、Failsafe、Resilience4j。 功能：自动绕开异常服务并检测恢复状态。 流程：关闭 → 打开 → 半开。 4）降级 没时间做饭了，今天就吃外卖吧... 对于健康问题，还是得少一点降级。 触发原因：流控、熔断、负载过高。 常见降级方式： 关闭非核心功能：停止应用日志打印 牺牲数据时效性：返回缓存中旧数据 牺牲数据精确性：降低数据采样频率 5）超时/重试 钉钉不回怎么办？每 10 分钟 ping 一次，超过 1 小时打电话。 超时：避免调用端陷入永久阻塞。 超时时间设置：全链路自上而下规划 Timeout vs. Deadline：使用绝对时间会更好 重试：确保可重试操作的幂等性。 消息去重 异步重试 指数退避 6）资源设限 双 11 如何避免女友败家？提前把自己信用卡额度调低。 目的：防止资源被异常流量耗尽 资源类型：线程、队列、DB 连接 设限方式：资源池化、有界队列 超限处理：返回 ServiceUnavailable / QuotaExceeded 7）资源隔离 双 12 女友还是要败家？得嘞刷你自个的卡吧，别动我的。 目的：防止资源被部分异常流量耗尽；为 VIP 客户提供服务质量保证（QoS）。 隔离方式：队列划分、独立集群；注意处理优先级和资源分配比例。 8 ）安全生产 女友哭着说再让我最后剁一次手吧？安全第一，宁愿心疼也不要肉疼。 程序动态性：开关、配置、热升级。 Switch：类型安全；侵入性小。 审核机制：代码 Review、发布审批。 灰度发布；分批部署；回滚预案。 DUCT：自动/手动调整 HSF 节点权重。 可维护性优化 前人栽树，后人乘凉。 前人挖坑，后人凉凉。 维护的英文是 maintain，也能翻译成：维持、供给。所以软件维护能有多重要？它就是软件系统的呼吸机和食物管道，维持软件生命的必要供给。 系统开发完成上线，不过只是把它“生”下来而已。软件真正能发挥多大价值，看的是交付后持续的价值兑现过程 —— 是不断茁壮成长，为用户发光发热？还是慢慢堕落，逐渐被用户所遗忘？这并不是取决于它当下瞬时是否足够优秀（性能）和靠谱（稳定），而是取决于未来 —— 能否在不断变化的市场环境、客户需求和人为因素中，始终保持足够优秀和靠谱，并且能越来越好。 相比性能和稳定性而言，可维护性所体现的价值往往是最长远、但也最难在短期内可兑现的，因此很多软件项目都选择了在前期牺牲可维护性。这样决策带来的后果，就跟架构设计一样，是几乎无法（或者需要非常高的成本）去弥补和挽回的。太多的软件项目，就是因为越来越不可维护（代码改不动、bug 修不完、feature 加不上），最后只能慢慢沦落为一个谁都不想碰的遗留项目。 衡量指标 相比性能和稳定性而言，可维护性确实不太好量化（艺术成分 > 科学成分）。这里我选取了几个偏定性分析的指标： 1）复杂度（Complexity）：是否复杂度可控？ 编码：简洁度、命名一致性、代码行数等。 架构：组件耦合度、层次清晰度、职责单一性等。 2）可扩展性（Extensibility）：是否易于变更？ 需要变更代码或配置时，是否简单优雅、不易出错。 3）可运维性（Operability）：是否方便运维？ 日志、监控是否完善；部署、扩容是否容易。 重要性 这里给了几个观点，进一步强调可维护性的重要性。 软件生命周期：维护周期 >> 开发周期。 破窗效应、熵增定律：可维护性会趋向于越来越差。 遗留系统的危害：理解难度，修改成本，变更风险；陷入不断踩坑、填坑、又挖坑的循环。 优化原则 你应该做的：遵循 KISS 原则、DRY 原则、各种代码可读性和架构设计原则等。 你不应该做的：引入过多临时性、Hack 代码；功能 Work 就 OK，欠一堆技术债（出来混总是要还的）。 优化手段 常用的可维护性优化手段有哪些？这里我总结了 4 个套路： 1）编码规范 无规矩，不成方圆。 编码：推荐《Java 开发手册》，另外也推荐 The Art of Readable Code 这本书。 日志：无盲点、无冗余、TraceID。 测试：代码覆盖度、自动化回归。 2）代码重构 别灰心，代码还有救。 何时重构：任何时候代码中嗅到坏味道（bad smell）。 重构节奏：小步迭代、回归验证。 重构 vs. 重写：需要综合考虑成本、风险、并行版本维护等因素。 推荐阅读：Refactoring: Improving the Design of Existing Code。 3）数据驱动 相信数据的力量。 系统数据：监控覆盖、Metrics 采集等，对于理解系统、排查问题至关重要。 业务数据：一致性校验、旧数据清理等；要相信，数据往往比代码要活得更久。 4）技术演进 技术是第一生产力。 死守阵地 or 紧跟潮流? 需要综合评估风险、生产力、学习成本。 当前方向：微服务化、容器化。 三 结语 Truth lies underneath the skin - 真理永远暗藏在表象底下。 对，就在这句话底下。 欢迎各位技术同路人加入阿里云云原生应用研发平台 EMAS 团队，我们专注于广泛的云原生技术（Backend as a Service、Serverless、DevOps、低代码平台等），致力于为企业、开发者提供一站式的应用研发管理服务，内推直达：pengqun.pq # alibaba-inc.com，有信必回。

主要版本 更新时间 备注 v1.0 2015-08-01 首次发布 v1.1 2018-03-12 增加新技术知识、完善知识体系 v2.0 2019-02-19 结构调整，更适合从入门到精通；进一步完善知识体系； 新技术补充； 一、基础篇 面向对象 什么是面向对象 面向对象、面向过程 面向对象的三大基本特征和五大基本原则 平台无关性 Java如何实现的平台无关 JVM还支持哪些语言（Kotlin、Groovy、JRuby、Jython、Scala） 值传递 值传递、引用传递 为什么说Java中只有值传递 封装、继承、多态 什么是多态、方法重写与重载 Java的继承与实现 构造函数与默认构造函数 类变量、成员变量和局部变量 成员变量和方法作用域 Java基础知识 基本数据类型 8种基本数据类型：整型、浮点型、布尔型、字符型 整型中byte、short、int、long的取值范围 什么是浮点型？什么是单精度和双精度？为什么不能用浮点型表示金额？ 自动拆装箱 什么是包装类型、什么是基本类型、什么是自动拆装箱 Integer的缓存机制 String 字符串的不可变性 JDK 6和JDK 7中substring的原理及区别、 replaceFirst、replaceAll、replace区别、 String对“+”的重载、字符串拼接的几种方式和区别 String.valueOf和Integer.toString的区别、 switch对String的支持 字符串池、常量池（运行时常量池、Class常量池）、intern 熟悉Java中各种关键字 transient、instanceof、volatile、synchronized、final、static、const 原理及用法。 集合类 常用集合类的使用、ArrayList和LinkedList和Vector的区别 、SynchronizedList和Vector的区别、HashMap、HashTable、ConcurrentHashMap区别、 Set和List区别？Set如何保证元素不重复？ Java 8中stream相关用法、apache集合处理工具类的使用、不同版本的JDK中HashMap的实现的区别以及原因 Collection和Collections区别 Arrays.asList获得的List使用时需要注意什么 Enumeration和Iterator区别 fail-fast 和 fail-safe CopyOnWriteArrayList、ConcurrentSkipListMap 枚举 枚举的用法、枚举的实现、枚举与单例、Enum类 Java枚举如何比较 switch对枚举的支持 枚举的序列化如何实现 枚举的线程安全性问题 IO 字符流、字节流、输入流、输出流、 同步、异步、阻塞、非阻塞、Linux 5种IO模型 BIO、NIO和AIO的区别、三种IO的用法与原理、netty Java反射与javassist 反射与工厂模式、 反射有什么作用 Class类 java.lang.reflect.* 动态代理 静态代理、动态代理 动态代理和反射的关系 动态代理的几种实现方式 AOP 序列化 什么是序列化与反序列化、为什么序列化、序列化底层原理、序列化与单例模式、protobuf、为什么说序列化并不安全 注解 元注解、自定义注解、Java中常用注解使用、注解与反射的结合 Spring常用注解 JMS 什么是Java消息服务、JMS消息传送模型 JMX java.lang.management.*、 javax.management.* 泛型 泛型与继承、类型擦除、泛型中K T V E ？ object等的含义、泛型各种用法 限定通配符和非限定通配符、上下界限定符extends 和 super List List<?>和List 单元测试 junit、mock、mockito、内存数据库（h2） 正则表达式 java.lang.util.regex.* 常用的Java工具库 commons.lang, commons.*... guava-libraries netty API&SPI API、API和SPI的关系和区别 如何定义SPI、SPI的实现原理 异常 异常类型、正确处理异常、自定义异常 Error和Exception 异常链、try-with-resources finally和return的执行顺序 时间处理 时区、冬令时和夏令时、时间戳、Java中时间API 格林威治时间、CET,UTC,GMT,CST几种常见时间的含义和关系 SimpleDateFormat的线程安全性问题 Java 8中的时间处理 如何在东八区的计算机上获取美国时间 编码方式 Unicode、有了Unicode为啥还需要UTF-8 GBK、GB2312、GB18030之间的区别 UTF8、UTF16、UTF32区别 URL编解码、Big Endian和Little Endian 如何解决乱码问题 语法糖 Java中语法糖原理、解语法糖 语法糖：switch 支持 String 与枚举、泛型、自动装箱与拆箱、方法变长参数、枚举、内部类、条件编译、 断言、数值字面量、for-each、try-with-resource、Lambda表达式、 阅读源代码 String、Integer、Long、Enum、BigDecimal、ThreadLocal、ClassLoader & URLClassLoader、ArrayList & LinkedList、 HashMap & LinkedHashMap & TreeMap & CouncurrentHashMap、HashSet & LinkedHashSet & TreeSet Java并发编程 并发与并行 什么是并发 什么是并行 并发与并行的区别 线程 线程的实现、线程的状态、优先级、线程调度、创建线程的多种方式、守护线程 线程与进程的区别 线程池 自己设计线程池、submit() 和 execute()、线程池原理 为什么不允许使用Executors创建线程池 线程安全 死锁、死锁如何排查、线程安全和内存模型的关系 锁 CAS、乐观锁与悲观锁、数据库相关锁机制、分布式锁、偏向锁、轻量级锁、重量级锁、monitor、 锁优化、锁消除、锁粗化、自旋锁、可重入锁、阻塞锁、死锁 死锁 死锁的原因 死锁的解决办法 synchronized synchronized是如何实现的？ synchronized和lock之间关系、不使用synchronized如何实现一个线程安全的单例 synchronized和原子性、可见性和有序性之间的关系 volatile happens-before、内存屏障、编译器指令重排和CPU指令重 volatile的实现原理 volatile和原子性、可见性和有序性之间的关系 有了symchronized为什么还需要volatile sleep 和 wait wait 和 notify notify 和 notifyAll ThreadLocal 写一个死锁的程序 写代码来解决生产者消费者问题 并发包 阅读源代码，并学会使用 Thread、Runnable、Callable、ReentrantLock、ReentrantReadWriteLock、Atomic*、Semaphore、CountDownLatch、、ConcurrentHashMap、Executors 二、底层篇 JVM JVM内存结构 class文件格式、运行时数据区：堆、栈、方法区、直接内存、运行时常量池、 堆和栈区别 Java中的对象一定在堆上分配吗？ Java内存模型 计算机内存模型、缓存一致性、MESI协议 可见性、原子性、顺序性、happens-before、 内存屏障、synchronized、volatile、final、锁 垃圾回收 GC算法：标记清除、引用计数、复制、标记压缩、分代回收、增量式回收 GC参数、对象存活的判定、垃圾收集器（CMS、G1、ZGC、Epsilon） JVM参数及调优 -Xmx、-Xmn、-Xms、Xss、-XX:SurvivorRatio、 -XX:PermSize、-XX:MaxPermSize、-XX:MaxTenuringThreshold Java对象模型 oop-klass、对象头 HotSpot 即时编译器、编译优化 虚拟机性能监控与故障处理工具 jps, jstack, jmap、jstat, jconsole, jinfo, jhat, javap, btrace、TProfiler Arthas 类加载机制 classLoader、类加载过程、双亲委派（破坏双亲委派）、模块化（jboss modules、osgi、jigsaw） 编译与反编译 什么是编译（前端编译、后端编译）、什么是反编译 JIT、JIT优化（逃逸分析、栈上分配、标量替换、锁优化） 编译工具：javac 反编译工具：javap 、jad 、CRF 三、 进阶篇 Java底层知识 字节码、class文件格式 CPU缓存，L1，L2，L3和伪共享 尾递归 位运算 用位运算实现加、减、乘、除、取余 设计模式 设计模式的六大原则： 开闭原则（Open Close Principle）、里氏代换原则（Liskov Substitution Principle）、依赖倒转原则（Dependence Inversion Principle） 接口隔离原则（Interface Segregation Principle）、迪米特法则（最少知道原则）（Demeter Principle）、合成复用原则（Composite Reuse Principle） 了解23种设计模式 创建型模式：单例模式、抽象工厂模式、建造者模式、工厂模式、原型模式。 结构型模式：适配器模式、桥接模式、装饰模式、组合模式、外观模式、享元模式、代理模式。 行为型模式：模版方法模式、命令模式、迭代器模式、观察者模式、中介者模式、备忘录模式、解释器模式（Interpreter模式）、状态模式、策略模式、职责链模式(责任链模式)、访问者模式。 会使用常用设计模式 单例的七种写法：懒汉——线程不安全、懒汉——线程安全、饿汉、饿汉——变种、静态内部类、枚举、双重校验锁 工厂模式、适配器模式、策略模式、模板方法模式、观察者模式、外观模式、代理模式等必会 不用synchronized和lock，实现线程安全的单例模式 实现AOP 实现IOC nio和reactor设计模式 网络编程知识 tcp、udp、http、https等常用协议 三次握手与四次关闭、流量控制和拥塞控制、OSI七层模型、tcp粘包与拆包 http/1.0 http/1.1 http/2之间的区别 http中 get和post区别 常见的web请求返回的状态码 404、302、301、500分别代表什么 http/3 Java RMI，Socket，HttpClient cookie 与 session cookie被禁用，如何实现session 用Java写一个简单的静态文件的HTTP服务器 了解nginx和apache服务器的特性并搭建一个对应的服务器 用Java实现FTP、SMTP协议 进程间通讯的方式 什么是CDN？如果实现？ DNS？ 什么是DNS 、记录类型:A记录、CNAME记录、AAAA记录等 域名解析、根域名服务器 DNS污染、DNS劫持、公共DNS：114 DNS、Google DNS、OpenDNS 反向代理 正向代理、反向代理 反向代理服务器 框架知识 Servlet 生命周期 线程安全问题 filter和listener web.xml中常用配置及作用 Hibernate 什么是OR Mapping Hibernate的缓存机制 Hibernate的懒加载 Hibernate/Ibatis/MyBatis之间的区别 Spring Bean的初始化 AOP原理 实现Spring的IOC spring四种依赖注入方式 Spring MVC 什么是MVC Spring mvc与Struts mvc的区别 Spring Boot Spring Boot 2.0、起步依赖、自动配置、 Spring Boot的starter原理，自己实现一个starter Spring Security Spring Cloud 服务发现与注册：Eureka、Zookeeper、Consul 负载均衡：Feign、Spring Cloud Loadbalance 服务配置：Spring Cloud Config 服务限流与熔断：Hystrix 服务链路追踪：Dapper 服务网关、安全、消息 应用服务器知识 JBoss tomcat jetty Weblogic 工具 git & svn maven & gradle Intellij IDEA 常用插件：Maven Helper 、FindBugs-IDEA、阿里巴巴代码规约检测、GsonFormat Lombok plugin、.ignore、Mybatis plugin 四、 高级篇 新技术 Java 8 lambda表达式、Stream API、时间API Java 9 Jigsaw、Jshell、Reactive Streams Java 10 局部变量类型推断、G1的并行Full GC、ThreadLocal握手机制 Java 11 ZGC、Epsilon、增强var、 Spring 5 响应式编程 Spring Boot 2.0 http/2 http/3 性能优化 使用单例、使用Future模式、使用线程池、选择就绪、减少上下文切换、减少锁粒度、数据压缩、结果缓存 线上问题分析 dump获取 线程Dump、内存Dump、gc情况 dump分析 分析死锁、分析内存泄露 dump分析及获取工具 jstack、jstat、jmap、jhat、Arthas 自己编写各种outofmemory，stackoverflow程序 HeapOutOfMemory、 Young OutOfMemory、MethodArea OutOfMemory、ConstantPool OutOfMemory、DirectMemory OutOfMemory、Stack OutOfMemory Stack OverFlow Arthas jvm相关、class/classloader相关、monitor/watch/trace相关、 options、管道、后台异步任务 文档：https://alibaba.github.io/arthas/advanced-use.html 常见问题解决思路 内存溢出、线程死锁、类加载冲突 使用工具尝试解决以下问题，并写下总结 当一个Java程序响应很慢时如何查找问题、 当一个Java程序频繁FullGC时如何解决问题、 如何查看垃圾回收日志、 当一个Java应用发生OutOfMemory时该如何解决、 如何判断是否出现死锁、 如何判断是否存在内存泄露 使用Arthas快速排查Spring Boot应用404/401问题 使用Arthas排查线上应用日志打满问题 利用Arthas排查Spring Boot应用NoSuchMethodError 编译原理知识 编译与反编译 Java代码的编译与反编译 Java的反编译工具 javap 、jad 、CRF 即时编译器 词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间代码，代码生成，代码优化 操作系统知识 Linux的常用命令 进程间通信 进程同步 生产者消费者问题、哲学家就餐问题、读者写者问题 缓冲区溢出 分段和分页 虚拟内存与主存 虚拟内存管理 换页算法 数据库知识 MySql 执行引擎 MySQL 执行计划 如何查看执行计划，如何根据执行计划进行SQL优化 索引 Hash索引、B树索引（B+树、和B树、R树） 普通索引、唯一索引 覆盖索引、最左前缀原则、索引下推 SQL优化 数据库事务和隔离级别 事务的隔离级别、事务能不能实现锁的功能 数据库锁 行锁、表锁、使用数据库锁实现乐观锁、 连接 内连接，左连接，右连接 数据库主备搭建 binlog redolog 内存数据库 h2 分库分表 读写分离 常用的nosql数据库 redis、memcached 分别使用数据库锁、NoSql实现分布式锁 性能调优 数据库连接池 数据结构与算法知识 简单的数据结构 栈、队列、链表、数组、哈希表、 栈和队列的相同和不同之处 栈通常采用的两种存储结构 树 二叉树、字典树、平衡树、排序树、B树、B+树、R树、多路树、红黑树 堆 大根堆、小根堆 图 有向图、无向图、拓扑 排序算法 稳定的排序：冒泡排序、插入排序、鸡尾酒排序、桶排序、计数排序、归并排序、原地归并排序、二叉排序树排序、鸽巢排序、基数排序、侏儒排序、图书馆排序、块排序 不稳定的排序：选择排序、希尔排序、Clover排序算法、梳排序、堆排序、平滑排序、快速排序、内省排序、耐心排序 各种排序算法和时间复杂度 深度优先和广度优先搜索 全排列、贪心算法、KMP算法、hash算法 海量数据处理 分治，hash映射，堆排序，双层桶划分，Bloom Filter，bitmap，数据库索引，mapreduce等。 两个栈实现队列，和两个队列实现栈 大数据知识 Zookeeper 基本概念、常见用法 Solr，Lucene，ElasticSearch 在linux上部署solr，solrcloud，，新增、删除、查询索引 Storm，流式计算，了解Spark，S4 在linux上部署storm，用zookeeper做协调，运行storm hello world，local和remote模式运行调试storm topology。 Hadoop，离线计算 HDFS、MapReduce 分布式日志收集flume，kafka，logstash 数据挖掘，mahout 网络安全知识 XSS XSS的防御 CSRF 注入攻击 SQL注入、XML注入、CRLF注入 文件上传漏洞 加密与解密 对称加密、非对称加密、哈希算法、加盐哈希算法 MD5，SHA1、DES、AES、RSA、DSA 彩虹表 DDOS攻击 DOS攻击、DDOS攻击 memcached为什么可以导致DDos攻击、什么是反射型DDoS 如何通过Hash碰撞进行DOS攻击 SSL、TLS，HTTPS 用openssl签一个证书部署到apache或nginx 五、架构篇 分布式 数据一致性、服务治理、服务降级 分布式事务 2PC、3PC、CAP、BASE、 可靠消息最终一致性、最大努力通知、TCC Dubbo 服务注册、服务发现，服务治理 http://dubbo.apache.org/zh-cn/ 分布式数据库 怎样打造一个分布式数据库、什么时候需要分布式数据库、mycat、otter、HBase 分布式文件系统 mfs、fastdfs 分布式缓存 缓存一致性、缓存命中率、缓存冗余 限流降级 Hystrix、Sentinal 算法 共识算法、Raft协议、Paxos 算法与 Raft 算法、拜占庭问题与算法 2PC、3PC 微服务 SOA、康威定律 ServiceMesh sidecar Docker & Kubernets Spring Boot Spring Cloud 高并发 分库分表 CDN技术 消息队列 ActiveMQ 监控 监控什么 CPU、内存、磁盘I/O、网络I/O等 监控手段 进程监控、语义监控、机器资源监控、数据波动 监控数据采集 日志、埋点 Dapper 负载均衡 tomcat负载均衡、Nginx负载均衡 四层负载均衡、七层负载均衡 DNS DNS原理、DNS的设计 CDN 数据一致性 六、 扩展篇 云计算 IaaS、SaaS、PaaS、虚拟化技术、openstack、Serverlsess 搜索引擎 Solr、Lucene、Nutch、Elasticsearch 权限管理 Shiro 区块链 哈希算法、Merkle树、公钥密码算法、共识算法、Raft协议、Paxos 算法与 Raft 算法、拜占庭问题与算法、消息认证码与数字签名 比特币 挖矿、共识机制、闪电网络、侧链、热点问题、分叉 以太坊 超级账本 人工智能 数学基础、机器学习、人工神经网络、深度学习、应用场景。 常用框架 TensorFlow、DeepLearning4J IoT 量子计算 AR & VR 其他语言 Groovy、Python、Go、NodeJs、Swift、Rust 六、 推荐书籍 《深入理解Java虚拟机》 《Effective Java》 《深入分析Java Web技术内幕》 《大型网站技术架构》 《代码整洁之道》 《架构整洁之道》 《Head First设计模式》 《maven实战》 《区块链原理、设计与应用》 《Java并发编程实战》 《鸟哥的Linux私房菜》 《从Paxos到Zookeeper》 《架构即未来》 本文首发自微信公众号：Hollis（hollischuang），关注公众号，后台回复『成神导图』，可以获得成神之路思维导图。

一、背景 - 边缘智能 人工智能（Artificial intelligence）的迅速发展正在改变世界。以深度学习（Deep learning）为驱动力和代表的第三波AI浪潮，正在变革和赋能金融、制造、农业、交通、医疗、零售、教育等众多行业，同时也极大地影响着我们每个人的生活。当前，在移动设备上各种新的AI应用场景正在不断涌现。大量新的需求对端上的智能能力提出了新的挑战，也带来了新的机遇。今天，得益于AI技术的巨大突破与进步，我们可以与设备像人一样通过语音、手势等方式沟通，扫一下人脸即可确定身份进行支付，穿戴式设备可分析健康状况并给出建议，系统可以根据用户的使用习惯自动优化，汽车会检测识别周围环境给出指引或者自动驾驶。这样的应用还有许许多多。所有这些，背后都离不开AI的助力。 过去几年将智能计算放于云上的方式被广泛采用，即智能强依赖云端。这几年随着移动设备硬件能力飞速提升及智能需求井喷，边缘计算开始兴起。机器学习模型在服务器上训练好后可以被部署到端设备上，执行过程不依赖云端，从而很大程度地改善了用户体验。在不侵犯隐私的前提下，使用过程中产生的数据又可以帮助改善模型的效果，最终构成一个良性的智能闭环。总得来说，端上智能具有以下优点： 降低延迟：避免了与服务器沟通所带来的延迟，可以保证实时性。这在像ADAS等对实时性要求极高的场景下尤为重要，因为如果慢一些可能人就已经凉了。 不依赖网络：计算在本地完成，因此不受网络质量影响。像手机、车等移动设备因环境变化往往不能保证网络一直高质量可用。 保护隐私：数据不需要离开设备。对于像聊天记录、照片等隐私信息能得到充分地保护。 个性化：可以根据个体用户的特性和习惯进行适配，做到千人千面，提高用户粘度。 成本可伸缩性：计算如果放在服务器端，服务器的成本可能会随着用户的增长而同比增长。如果放在移动端上计算则不会有这个问题。 也正是由于边缘智能计算具备这些优点，使它成为业界的热点。但是，在带来机遇的同时，它也带来了巨大的挑战。这些挑战主要来源于边缘设备的资源限制，如计算速度、存储与功耗等。 二、基本问题 - 算力之殇 在过去几年里，深度学习在视觉、自然语言处理、语音识别、推荐、智能控制等领域获得了许多重大的突破，并在很多的专项上超越了人类水平。我们知道，深度学习有三大基石：数据、算法和算力。大数据的兴起为AI提供了契机，深度学习的主要优势之一就是能基于大量数据进行学习。算法则提供了处理数据和从数据中进行学习的有效方法。而要对大量数据和复杂的网络进行计算，需要强大算力的支撑。而某种意义上来说它们之间有一些互补关系。如随着近几年AutoML的火热，人们发现让机器搜索网络架构可以找到比人工设计更优的方案。Google的大神Jeff Dean（对，就是编译器从不给他警告，只有他给编译器警告的那位）就曾经表示：未来谷歌可能会用100倍的计算能力，取代机器学习专业知识。换句话说，如果拥有足够的算力，可以替代很大部分算法设计。 这就引出一个问题，多少的算力是足够的？这个问题估计谁也没法给出一个准确的答案，但我们可以通过一些数据侧面感受下。OpenAI发布的分析表明：自2012年，也就是深度学习爆发以来，人工智能训练任务中使用的算力呈指数级增长，其目前速度为每3.5个月翻一倍。相比之下，摩尔定律中芯片性能翻倍的速度是18个月。2012年来人们对于算力的需求增长了超过30万倍。另外，随之而来的能耗和成本问题也不容小视。据美国马萨诸塞大学研究人员表示，训练一个经典的Transformer网络，碳排放180吨，相当于把三辆汽车从全新用到报废。当然，这里是训练时所需的算力，移动端上因为大多只需要推理，其算力需求会小得多。我们以比较热门的自动驾驶来举例。自动驾驶汽车为了完成周围环境的感知，需要处理从camera、radar、LIDAR等一系列传感器来的数据。Intel CEO Brian Krzanich曾在一次大会keynote中称：估计到2020年，一辆自动驾驶车每天大约会产生4TB的数据。而这些数据很多是需要实时处理的。要处理如此大量的数据，其算力需求可想可知。Imagination汽车市场总监Bryce Johnstone表示：自动驾驶级别每升高一级，对计算力的需求至少增长十倍。第五级全自动驾驶，可能需要500TOPS以上计算力。而作为“低配版”自动驾驶的ADAS，根据功能的不同，也需要10到100+GFLOPS的计算力。 这几年，机器学习学术研究空前繁荣。Jeff Dean就曾发推给出数据：根据对arXiv上论文的统计，到2018年底，平均每天产生100篇。难怪有种论文读不过来的感觉。。。然而，与学术界遍地开花的一派繁荣景象相比，工业界落地难的尴尬境地困扰着不少业内人士。不少AI产品停留在PPT和概念演示阶段，然后，就没有然后了。。。其中最大的阻碍之一就是端上的计算资源有限，难以支持多样的、实时的AI相关计算任务。 以深度神经网络（DNN）为代表的AI计算任务，本质上是推动了边缘设备计算模式的转变。传统的移动端基本以I/O密集任务为主，偶尔来个计算密集任务可能用户就会觉得发烫，是不是哪里出问题了。而DNN的推理一次就动不动几十亿次运算，而且还是周期性高频率运行，外加系统中可能还有多个DNN同时运行，这传统的玩法根本扛不住。因此，我们的核心问题是算法需求与边缘硬件算力之间的矛盾。而且这个矛盾很可能会长期存在。就像之前的Andy and Bill’s Law，即便算力大幅度提升，市场会出现更多的场景需求，更高的准确率要求把这些增长的算力吃掉。注意算力还与存储、能耗等资源密切相关，因此在移动端性能优化的目标除了耗时外，还包括内存占用及功耗等等。 三、解决方向 - 希望之光 要解决上一节提到的问题，缓解算法需求与移动端算力的矛盾，业界有几个基本思路： 给定算法模型如何让它跑得快 设计牛X的专用硬件 结合硬件做深度计算优化 通过调度提高硬件利用率 给定准确率目标如何让模型尽可能简化 如何设计更轻量化的网络结构 给定模型的情况下其计算量是否必要（不是的话如何压缩） 下面分别就这几个思路稍作展开。 1. 神经网络芯片 - 软件定义芯片 以DNN为代表的现代流行机器学习模型在端上的大量应用带来了计算模式的变化。DNN中的典型计算（如矩阵乘加）普遍有逻辑简单，计算量大，且反复计算的特点。这种计算模式的变化推动了芯片的发展与变化。目前主要的挑战来自两个方面： 摩尔定律的失效：1965年英特尔联合创始人戈登·摩尔提出了著名的摩尔定律：当价格不变时，集成电路上可容纳的元器件的数目，约每隔18-24个月便会增加一倍，性能也将提升一倍。半导体行业在这个定律的推动或者说引导下发展了50多年。然而，物理元件不可能无限缩小。当晶体管体积到达物理极限，该趋势将难以为继。摩尔定律虽称为定律，但并不是推导出来的科学定律，而是经验法则。今天，就算不能说它完全失效，也可以说是明显地放缓了。 冯·诺依曼瓶颈：现代的主流处理器基于冯·诺依曼架构。在该架构中，计算模块和存储单元互相分离，数据需要从存储器提取，经过处理单元处理后再写回存储器。这些频繁的访存操作造成了延时，也提高了功耗。这种架构优点是通用性，适用于逻辑复杂的计算，但对于像矩阵乘加这种比较特殊的计算，效率并不高。使情况变得更糟的是，摩尔定律加持下的芯片计算性能在过去几十年里迅猛增长，而存储器的性能增长却远不及它，从而形成了处理器与存储器速度的gap。另外，DNN中的计算中涉及大量参数与中间结果，因此需要很大的memory bandwidth。这多种因素使得DNN的计算很多时候的瓶颈在于访存而不是计算。 针对以上挑战，业界进行了各种尝试来克服。我们知道，神经网络的执行很多时候就是在做矩阵计算。既然是非常耗时的特殊计算，那最好的方式就是用专门的硬件（就像编解码芯片），从而达到高性能、低功耗。这种为专门目的而设计的集成电路被称为ASIC。FPGA与ASIC类似，也是用硬件实现软件算法。只是它是一种“半成品”，可以自定义。这几年，各种神经网络芯片可以说是一个接一个，层出不穷。一时间，各种"xPU"横空出世。貌似26个字第都快用完了。。。 本质上，它们大多是为了解决上面提到的根本问题。对于摩尔定律的放缓或者失效，一个自然的路子就是通过并行来提速。CPU经历了从单核到双核再到多核的发展历程，然而毕竟作为通用处理器由于硬件设计上的一些限制无法堆太多核。将并行计算推向大规模的先行者是Nvidia，早在2006年，Nvidia推出了CUDA，非常明智地将之前专用于图形领域的GPU推向通用计算领域，摇身变为GPGPU。2012年，以绝对优势获得ImageNet冠军的AlexNet正是用了CUDA来加速训练。Nvidia随着之后兴起的深度学习浪潮进入了一条快车道，其硬件与软件生态已成为服务器端的绝对主流和标配。与CPU不同，GPU拥有数以千计的核心，能同时做并行任务中的操作。这样其整体性能就可以不受单个核心频率的限制。其局限是只适用于规则的可并行计算任务，对于DNN中的矩阵乘加就非常适合，因此，在深度学习的任务中，GPU的吞吐量可以比CPU高出一个数量级。 然而，GPU毕竟设计之初不是为神经网络专用的，它仍是一个通用处理器。虽比CPU更专用了，但硬件设计仍需考虑一定的通用性，因此也不能做得太激进。 这就给了ASIC进一步的发展空间。ASIC因为是专用的，因此可以针对性地进行硬件设计，从而达到极致的能效。与GPU相比，用于神经网络的ASIC芯片的显著特点是一般会有更多的计算单元（如TPU包含65536个8位MAC矩阵乘法单元）。但是，像之前提到的，只考虑计算速度是不够的，很多时候瓶颈在于访存。很多时候我们谈算力指标言必FLOPS，其实这个指标很容易让人误解，似乎只需FLOPS到了一切都妥妥的了。其实由于访存速率的限制很多时候硬件算力只能发挥出一部分甚至是10%不到。在Roofline模型中，由计算平台的算力和带宽上限决定的"roofline"将整个区域分为两个部分-memory bound和compute bound。根据模型在图中的位置可以判断它的瓶颈在哪里。我们发现不少模型，尤其是像MobileNet等轻量级的模型由于计算密度较低大多会落入memory bound区域。也就是说，这种情况下硬件计算速度再快也白瞎。针对访存这块，神经网络芯片一般会在设计上做针对性的优化，比如更大的片上内存（如TPU的有28M）。另外，像有David Patterson（图灵奖获得者）背书的Google出品的TPU为了更大幅度缓解冯·诺依曼瓶颈，让脉动阵列架构重回到舞台。在这种架构下，每次执行乘法运算时，结果会被直接传递给后面的乘法器，并进行求和。在整个过程中，无需访问内存。去除这些访存开销，还会有额外好处，即功耗的降低。我们知道与计算相比，访存才是功耗大户。通过这种方式可以有效提高能效比。 以上只是举些小例子，其它各种神经网络的ASIC也是各显神通，用足了各种优化来克服传统计算方式的缺点。虽然目前这条路子仍然是绝对的主流，但人们同时也开始探索新型的计算形式和计算硬件用于神经网络计算，如： 神经拟态计算：又称脉冲神经网络（SNN）。它来自于大脑的启发。在神经系统中，神经元间通过突触发送脉冲信号，其间的连接可能被抑制或是被强化。神经信息被认为是通过神经元的触发频率来编码的。相比之下，传统方式则需要较大的memory来存储模型权重。相关的研究包括IBM的True North、Intel的Loihi、BrainChip的Akida NSoC和清华大学等机构提出的天机芯片架构。 光学计算：虽然光纤可以以光的形式传输数据，但最终要分析这些数据时，需要进行光-电转换后再进行处理。MIT的研究者提出了一种使用光子技术实现神经网络的方法。这种可编程纳米光子处理器用光来执行人工智能算法的计算。德国明斯特大学物理研究所的研究者提出了一种在光子芯片上实现的全光学神经网络。使用基于光学计算的方法在加速和能耗方面都会有很大的优势。 量子计算：量子计算基于量子力学的模型来实现计算。量子计算机的理论基础也是图灵机，它可以实现经典计算机能实现的计算。量子计算的核心优势是拥有指数级的存储和计算能力。因此，它可以使现在很多“不可解”的问题变得可解。这将是颠覆性的，因此也引得大家的极大关注。神经网络作为当前热点之一，自然也是量子计算的应用方向之一。如Google构建了量子神经网络QNN，用于在量子处理器上执行神经网络。 尽管经过科学家们的不懈努力，这些新型的计算方式和硬件的价值已初现端倪，但目前仍主要处在研究阶段。要将它们落地并大规模应用，还需要克服很多困难。而一旦它们技术成熟，那将会是革命性的。 2. 计算实现优化 - 结合硬件特性与能力 很多时候，程序执行符合80/20法则。即80%的时间在跑20%的代码（当然，这里的数是虚指）。对于神经网络来说也不例外。如对于视觉任务中典型的CNN，通常卷积与全连接层会占到总计算量的80%~90%甚至更高。另外像在语音、自然语言理解领域常用的RNN中大量存在LSTM和GRU层，它们本质上也是做矩阵计算。因此很多时候大家做性能优化会focus在矩阵计算上。 抛开实现谈优化意义不大，或者说油水不多。只有考虑与平台硬件结合的深度优化，才能充分挖掘潜在的性能。因此，在计算实现中，需要考虑硬件特性和能力。例如处理器对于不同类型指令性能差异（如大多计算硬件上乘法比加法更耗时和耗能）和存储器层次结构（每一级的延时和能耗都可能相差数量级）。考虑到平台相关的硬件加速能力还有CPU的并行指令、GPU的并行编程等等。 最简单的方法当然是按公式来计算，称为直接法。全连接层其实就是矩阵和向量乘，不用多说。卷积层的定义稍稍复杂一些。为简单先不考虑stride，dilation等特殊卷积，且卷积核size宽高相等。记输入为$X$，其维度为$N \times C_i \times H_i \times W_i$，卷积核为$W$，其维度$C_o \times C_i \times K \times K$，输出为$Y$，维度为$N \times C_o \times H_o \times W_o$，则对输出张量中的每个元素，计算公式为： $$ Y_{n,c,x,y} = \sum_{m=0}^{C_i - 1} \sum_{u=0}^{K - 1} \sum_{v=0}^{K - 1} X_{n, m, x+u, y+v} W_{c, m, u, v} $$ 算法复杂度为$O(N C_i C_o H_o W_o K^2)$。其优点简单粗暴，且几乎无需额外的内存开销。其缺点也是显而易见的，就是效率会比较低。现代计算库一般都会使用一系列的计算实现优化，几个比较典型的如： Im2col-based：一边是大量卷积计算需求，另一边是几十年来深度优化的成熟的BLAS库。如何将两者连接起来呢？经典的im2col方法将输入矩阵转化成Teoplitz矩阵，这样卷积操作就转化成了矩阵间乘法操作，从而可以作为GEMM利用成熟计算库来加速。但它有个缺点是需要比较大的内存开销来存储临时矩阵。 kn2系：im2col方法虽然可以利用BLAS的GEMM函数加速，但它需要$O(C_iK^2H_iW_i)$的额外存储空间。在移动端设备内存也是很稀缺的资源，有没有可能在享受到BLAS加速的同时又可以占用少一些内存呢。kn2系方法避免了Toepliz矩阵的构建，其基本思想是将卷积分解成为多个矩阵乘用GEMM计算，然后移位后累加。额外内存减少到$O(C_o H_i W_i)$。其代价是更多次的GEMM调用。如果说im2col是拿空间换时间，那这个就是拿时间再换回一些空间。 Strassen algorithm：这个矩阵乘法的优化大家一定不陌生，它也可以被扩展到卷积计算。我们知道，不少看上去还比较intuitive的算法会让人有种“我要是他我也能想出来”的错觉，然而有一些看完则会让人觉得“这怎么想出来的！”。该算法应该就属于后一种。通过一系列tricky的构造，它将分块递归过程中的8个子矩阵乘法干到7个，硬生生将复杂度从$\Theta(n^3)$减到$O(n^{2.81})$。但其代价是会引入一些额外的矩阵加操作，因此在实际使用中需要有条件地使用，如矩阵比较大时。 FFT-based：根据经典的Convolution theorem，空间域上的卷积操作等同于频率域上的乘积。因此，可以将原卷积经过傅立叶变换转到频率域，在频率域经过乘积后再通过逆傅立叶变换转到原空间域。这个过程的计算复杂度为$O(H_iW_i \log (H_iW_i) (C_o C_i + NC_i + NC_o) + H_iW_iNC_iC_o)$。先不要管这式子为毛这么长，总之与前面直接法时间复杂度相比，这里没有卷积核的size了。这非常好，同时这也意味着只有当卷积核越大，它的优势越明显。另外，虽然这里有一来一回域间变换的额外运算，但一方面有快速傅立叶变换助力，另一方面由于每一个输入feature map要被重复使用多次，因此对应的转换可以重用。当然，这也意味着，feature map的通道数越多越适用。 Winograd-based：该方法基于Winograd algorithm。它以更多的加法数量和中间结果乘法数量为代价达到理论上最少的乘法次数。该方法的计算复杂度随着卷积核size平方的速度增长，因此和上面FFT-based方法相反，它主要适用于小的kernel（如3x3）。不过，好在现代主流的神经网络也是以这种小kernel为主，因此被广泛使用。 我们可以看到，就像其它很多计算任务一样，没有一种实现方法是万能的。因此，用时需要根据实际情况来。实际使用中还会有不少坑，如有些方法可能对精度有较大影响，而有些是基于一些硬件特性假设的。因此，如果你尝试了一种看起来非常牛X的计算优化，结果却不尽如人意，不要伤心，不要难过，很可能只是不满足该算法的某些隐式假设。为了避免人肉挑选之苦，业界也有尝试通过自动化的方法来为神经网络中每个卷积选取最合适的实现算法。 还有一类优化是并行优化。对于矩阵乘加这样天然可并行的计算，不并行白不并行。常用的手段有几类： CPU并行指令：SIMD指令，即一条指令可以操作多个数据。比如对于4个乘法操作，原本要分4个指令，现在一条指令搞定。x86平台上有SSE和AVX指令集，ARM平台上有NEON指令集。当只能用CPU时，这几乎总能给性能带来明显的提升。 多线程：虽没有GPU的大规模并行能力，但CPU也有多核。其并行能力可以通过多线程来利用。我们大多时候不必从头写线程调度，可以依赖OpenMP这样的库，或者更高层的库。 GPU并行编程：这个topic就非常非常大了。比较主流的有CUDA和OpenCL。严格意义上讲两个不是完全平级的东西，虽然都可以指一种并行编程接口。前者是Nvidia家的，是一整个生态，只要用的N卡基本没谁就它了。后者是一个标准，具体由各厂家去实现，最大优点就是跨平台通用（不过也得看各家支持的情况。。。）。 再次回到访存优化的话题。无论是CPU还是GPU，都存在存储器层次结构（memory hierarchy）的概念。对于这个hierarchy中的每两个层级之间，其速率都可能有数量级的差异。为了让计算尽可能少地访问内存，就需要让程序尽可能cache friendly。做得好和不好有时性能会是成倍的差异。在NN计算优化中，针对访存的优化很多。举两个常见且效果明显的典型例子： Tiling/Blocking：对于两个矩阵相乘，我们知道用原始定义计算的话对cache不友好。如果矩阵比较大的话，尽管一个元素会多次参与计算，但当它下次参与计算时，早被踢出cache了。一个好的办法就是分块。那么问题来了，分块分多大，按哪个轴分，都对性能有很大影响。另问题更加复杂的是这个最优值还是和具体计算任务和硬件平台相关的。一种方法是针对平台做尽可能通用的优化。这就像做爆款，对大部分人来说都不错；另一种方式就是干脆量体裁衣，对给定模型在特定平台通过tuning得到最合适的参数，如AutoTVM通过Halide分离算法实现与硬件上的计算调度，然后通过自动搜索找出最合适的执行参数。经过tuning后其性能很多时候可以超过芯片厂商的推理引擎（毕竟厂商的推理引擎没法给每个模型量身定制）。 Operator fusion：这是一种最为常用的graph-level的优化。它将多个算子融合成一个，从而减少运行时间。无论是像Conv-BN-ReLU这样的纵向融合，还是Inception module这种多分支结构的横向融合，其实本质上都没有减少计算量，但现实中往往能给性能带来比较明显的提升。主要原因之一是它避免了中间数据的传输开销。 3. 异构调度 - 充分榨取多硬件能力 在过去的几年里，服务器市场基本是Nvidia GPU的天下。尽管近几年它也受到了来自TPU等各方面的压力，但总体来说，对于服务器端异构多元化程度没那么大。而与之不同的是，在移动端，不仅硬件种类多，而且同一类硬件差异也大。CPU有ARM和x86的，GPU有Adreno、Mali、Vivante等（虽说有像OpenCL这样的接口标准，但和CUDA不同，毕竟是多厂商各有各的实现，良莠不齐。而且很多厂商还会有私有扩展）。各类芯片如CPU、GPU、FPGA、DSP、ASIC不仅能力各异，算力也有数量级的差异，能效甚至有几个数量级之差。当然，理想情况下，如果ASIC一统江湖，在性能、成本、算子支持等方面都完爆、吊打和摩擦其它芯片，那事情倒简单一些。但这毕竟还需要些时间。因此，当前如何在AI时代充分挖掘和利用这些异构硬件的计算能力就成了一个很有趣的问题。 要解决问题，首先是问题的定义与描述。绝大多数计算任务可以被抽象成计算图，或者更具体地，有向无环图（DAG）。如一个DNN就是一个典型的DAG，一个场景中pipeline的各个节点也可以抽象成一个DAG。如在监控场景，一般摄像头数据进来先做预处理，再进行物体检测，同时可能还会做光流。物体检测结果会送去做细分类（如车牌识别，车型识别，行人ID识别等），另外还会拿来做跟踪。形式化地，计算图记为$G=(V, E, w, c)$。节点$V=v_1, ..., v_n$为操作，边$E=e_1, ..., e_m$表示操作间的依赖关系。$w_i \in \mathbb{R}$对应边上对应的通信代价。$c_i \in \mathbb{R}$对应节点上的计算代价。目标是使某个指定的性能指标最小（如整个计算图执行完的时间）。对于异构调度来说，同时还需要满足一些约束。这些约束包括但不限于：有些硬件只能执行整型计算，某些硬件只能支持或者加速某些特定算子，某几个算子需要放在同一设备上跑等等。 显然，这本质上是一个调度问题，而调度问题古而有之。因此，类似的问题也一定被前人研究过。对于一般的调度问题，可以描述为RCPS（Resource-constrained project scheduling）问题。RCPS问题的一种特例为MS（Machine scheduling）问题。MS问题的一种重要特例为JSS（Job shop scheduling）问题。在该问题中，一坨job需要调度到一堆机器上。每个job包含一个或多个必须按序执行的操作。而每个操作必须在指定机器上完成。目标是找到每台机器上的操作序列使得某个性能指标（如makespan）最小。基于JSS问题衍生出非常多的变体和扩展。其中与本节关注问题比较相切的是FJSS（Flexible job shop scheduling）问题。它将操作与机器的绑定关系解除了，即一个操作可以在多台机器上执行。这意味我们还需要确定操作与机器的对应关系，于是调度就分为两个子问题：machine assignment和local scheduling。遗憾的是，无论是对于JSS问题还是它的扩展，亦或是子问题，都是NP-hard的。也就是说，至少在目前的人类文明水平下，无法在多项式时间复杂度下找到最优解。 那么问题来了，怎么解呢？业界大体有这么几类方式： 精确算法：最简单最爽快的办法，直接奔着最优解去。前面的调度问题可以被形式化成MILP（Mixed integer linear programming）问题，然后用像常见的branch and bound algorithm咔咔走起。但是，就像前面提到的该问题是NP-hard的，意味着除非是在非常小的规模下，基本不能在合理时间保证找到最优解。而现代流行的大多数神经网络过于复杂，不太符合这种前提假设。 启发式策略：基于某种与问题领域相关的启发构造近似解。比如最简单的策略就是将每个算子都分配到最快的设备上执行。复杂些的启发比如基于后续节点的计算开销，计算图中的关键路径，或者聚类信息等。这类方法大多基于贪心法思想，因此无法保证找到最优解（准确来说，其它方法也不能保证，只能说它找不到更全局意义上的更优解）。其优点是速度快，运行时间可控。因不需要搜索或者学习的过程，在移动端可以在线完成。 元启发式搜索：为了避免启发式策略的局限，元启发式搜索通过本地提升方法与高层搜索策略的交互迭代过程来在解空间中进行搜索，更大程度上避免局部最优解。因为元启发式搜索对问题的特有条件相关性较小，因此，常见的比如遗传算法，禁忌搜索，模拟退火，粒子群算法，蚁群算法等都可以应用到调度问题上。这类方法一般可以比单纯的启发式策略或规则找到更优的解，但也需要耗费更长的时间，因此比较难做到在线即用。 基于学习的方法：其实把这块放在上面也能说得通，把它单列纯粹是想把它单列来说。毕竟我们理想的目标不仅仅是找到优的解，最好还能“举一反三”，而这需要知识的迁移。我们可以用基于机器学习的方法来实现调度，另外近年发展迅猛的GNN给调度的知识迁移提供了充足弹药。Reinforcement learning（增强学习，或译强化学习）是一类常用于智能决策的方法。而调度本质上也是一种决策，因此强化学习也是调度问题中的常客。如Microsoft和Google分别基于它来做服务器端的任务调度与网络模型执行时算子的device placement，获得了可观的性能收益。强化学习是有着几十年历史的机器学习重要分支之一，自从与深度学习结合后演变成DRL后重新焕发出强大的活力（早些年写的几篇reinforcement learning相关介绍：深度增强学习漫谈 - 从DQN到AlphaGo，深度增强学习漫谈 - 从AC到A3C，深度增强学习漫谈 - 信赖域（Trust Region）系方法）。 要进行异构调度，还需要有软件框架。这个框架需要有runtime来进行模型解析、优化、调度、执行等任务，还需要能接入各种硬件加速方案以供调度。硬件加速组件需要用HAL进行抽象封装，这样就可以将runtime与HAL加速实现解耦，让第三方加速方案方便地接入。业界的典型例子如Google的Android NN runtime。自Android 8.1以来，厂商可以通过NN HAL接口接入runtime被其调度。另一个例子如Microsoft的ONNXRuntime。它通过ExecutionProvider接口接入多种加速后端。但是，它们目前的分图和调度方案都是基于比较简单的规则，基本原则是哪个快让让哪个跑。这样的贪心策略注定无法得到全局更优的解。虽然通过异构调度我们可以得到一些性能上的好处，但仍有不少的挑战亟待我们解决。如： 动态负载：以上的很多方法中，要得到优的调度依赖于精确的cost model。静态条件下的cost model其实还好，可以通过对不同类型的算子进行采样得到样本，然后通过机器学习方法进行建模，可以达到比较低的预测误差。但是，要在考虑动态负载的情况下对广泛的情况建立准确的cost model这就是个比较大的挑战了。而在实际使用中，动态负载是个不得不考虑的问题。比如ASIC是很快，但如果它已经满负载了，再来一个任务的话，与其将它放于ASIC，还不如放在GPU或者CPU上，从而避免一块芯片忙到吐血，其它芯片吃瓜的状态。 多任务多优先级：在一个系统中，通常会有多个AI应用同时运行。它们可能有不同的优先级，ADAS可能需要更高优先级，交互相关的优先级可能略低一些。当计算资源冲突时，我们需要进行调度保证前者的延时在可接受范围。这将涉及到资源的优先调度和任务抢占，考虑抢占的话还要考虑抢占的粒度，不同硬件上抢占的实现等。另外，不同任务的主要指标和工作频率可能也不同，如监控中的目标检测一般高频执行，且优先考虑延迟；而车牌识别一般低频执行，优先考虑准确率，对延迟不敏感。所有这些，都是未来值得深挖的方向。 4. 轻量化网络结构 - 网络容量与计算开销间的权衡 模型的容量（Capacity）即其能拟合复杂函数的能力，简单来说即其表达能力。这是个非常抽象的概念，我们很难用具体的测度衡量它。但很多时候，从统计意义上来说，模型参数越多，capacity相对更大（虽然也不绝对）。它像是一把双刃剑。更强的表达能力当然是我们想要的。然后同时它可能也会让网络更难训练，且计算量更大。从2012年深度学习火热起来的几年里，学界的主流方向就是奔着更高的准确率刷榜，ImageNet就像奥运会百米赛跑一样，记录一次次被刷新。但与此同时，网络也变得越来越重，越来越复杂。而实际使用中，尤其是移动端往往难以运行这样重量级的网络。人们看到这样的问题，于是一系列轻量级的网络应运而生。当然，各个子领域基本都会有针对性的轻量化工作。由于这个topic涉及内容很多，而且网上这方面的介绍多如牛毛。这里篇幅有限，只拿几个经典的通用主干网络简单走一下。另外因一些网络有多个版本，所以这里我想按年份来排： 2015及以前：主要处在萌芽期。业界已经开始意识到工业及商业应用中的轻量化需求，但这时大多网络设计还不是专门奔着轻量化去的，基本是在主要追求更高准确率的同时也会考虑降低计算量。像经典的Inception系列引入了一系列设计原则和技巧提升参数的利用效率，让网络在达到高准确率的同时比早年VGG这种“大家伙”轻了不少。其中一些经典的思想也启蒙了后面的不少相关工作。这时的一些网络你放到移动平台上去跑吧，也能跑，但可能会跑得比较。。。勉强。这一时期还出现了像深度可分离卷积（Depthwise separable convolution）这样对往后轻量化网络设计产生重大影响的结构，它是后面Xception、MobileNet等经典网络中的基础。 2016年：SqueezeNet是早期比较经典的针对嵌入式平台网络结构设计的尝试。它的核心fire module，由squeeze和expand两层组成：Squeeze层通过1x1卷积核进行通道降维，再由expand层的一系列1x1和3x3卷积核对其计算，最后进行concat融合。由于squeeze层相当于做了“压缩”的操作因此可以降低后面操作的计算量。论文中实验表明它可将模型压缩50倍且准确率几乎无影响，比同期的模型压缩方法还要有效。而结合模型压缩方法能进一步将模型压缩数百倍。 2017年：这一年，Google推出了专用于移动平台的MobileNet，旷视也推出了类似定位的ShuffleNet，开始了他们竞赛的旅程。MobileNet主要基于深度可分离卷积。直觉上，在一个卷积层，我们想要空间维度和通道维度的信息都充分融合，普通卷积就是将这两个维度信息同时融合。基于这两个维度信息相互正交的假设，深度可分离卷积采取让它们一个一个来的做法。即先用depthwise convolution融合空间维再用pointwise convolution融合通道维。这样一来3x3卷积核下计算量可以减少8、9倍，同时对准确率影响还不太大。另一方面它引入两个调节因子width和resolution multiplier分别用于调节通道数和输入的分辨率，使网络可以在准确率和计算量间根据需要调节。ShuffleNet针对当时网络中大量使用的1x1卷积，建议使用group convolution降低计算量。又由于group convolution不利于通道间信息融合的问题提出了特色的channel shuffle操作，并且表示效果上胜于MobileNet。 2018年：Google推出了升级版MobileNet v2，旷视也推出了升级版ShuffleNet v2。MobileNet v2通过对非线性激活函数ReLU对高维空间中内嵌的低维流形影响的研究，和bottleneck已经包含所有必要信息的intuition，提出了结合了linear bottleneck和inverted residual的新结构，在前面工作基础上进一步提升了效果。ShuffleNet v2重点关注了影响运行速度中除了FLOPs外的另外因素-访存开销与并行度，提出了设计轻量化网络四大原则，并且基于这些原则设计了ShuffleNet v2，达到了当时的SOTA。我们知道，理论计算量小未必跑得快，因为可能对硬件不友好。要设计对硬件友好的网络架构，一条路是老师傅人工设计；还有条路就是让机器自己找硬件友好的网络结构。这就要提到自动神经网络架构搜索（NAS）了。自2016年左右，NAS的春风吹遍大地，经过一段时间的高速发展其耗时以数量级的速度减少，实用性大大增强（之前整理的一些NAS相关东西：神经网络架构搜索（Neural Architecture Search）杂谈）。Google在NAS领域非常活跃，在轻量化网络上自然也不会落下。这一年Google提出了MnasNet，同准确率下性能优于MobileNet v2。与早期传统NAS只关注准确率不同，它在优化目标中加入了性能因素，从而扩展到了多目标优化问题。 后面关于NAS的研究也越来越多考虑执行性能，出现了像FBNet等一批hardware/platform-aware NAS方法。 2019年：Google再度升级MobileNet，推出了MobileNet v3，并表示比前面几代MobileNet、ShuffleNet啥的都牛掰。这次比较特色的是通过人机共创的方式设计网络架构。它先结合platform-aware NAS和NetAdapt对网络结构进行搜索，然后再对搜索得到的网络中最前和最后计算量比较大的部分进行了人工调整。同年，Google还提出了EfficientNet。前面提到MobileNet引入width/resolution multiplier作为参数对模型进行调节，这里还加了控制网络层数的depth参数，并且指出它们的调节不能瞎调，得按套路，即按固定的比例。通过调节这个比例系数，可以得到一系列各个重量级下的EfficientNet变种，并且在每个重量级上表现都不错。 5. 模型压缩 - 探索模型计算量下界 众所周知，机器学习分为训练和推理两个阶段。在这两个阶段中，计算任务是有差别的。一方面，一些算子在训练时需要，而在推理时是不需要的（或者形式不一样）。另外模型中的计算图可以作很多简化和优化（如冗余计算消除，内存布局优化，Operator fusion等）。因此我们在将训练好的模型部署前会对模型进行一些图优化和转化；另一方面，业界普遍认为模型过参数化（Over-parameterization）和高精度对训练有好处，而在推理时并不必要。这样的假设支持我们可以在不严重影响准确率的前提下对模型进行简化。这样的好处是多方面的。不仅减少了延时，也降低了功耗。同时还减少了内存占用，内存占用的减少还会提高cache利用率，甚至可能原来需要放在DRAM中的模型现在可以塞进SRAM中，从而又进一步提高性能、降低功耗。另外，更小的模型还利于应用更新或者OTA升级。可谓好处多多，一举多得。 深度学习自爆发后朝着更高、更强目标狂奔几年后，比较明显的轻量化之风大约兴起于2015年左右。除了轻量化网络结构设计之外，另一个重要的分支就是模型压缩。当时，韩松等人的deep compression相关工作有着标志性的影响。它通过结合多种压缩方法，将网络模型size压缩了几十倍，性能获得成倍的提升。这让大家意识到当时的DNN模型中可榨油水如此之多。另外，因深度学习领域工作获得图灵奖的三位大神Geoffrey Hinton, Yann LeCun和Yoshua Bengio在该领域也早有布局，做了先驱和奠基性的工作，如Hinton的知识蒸馏，Bengio在量化模型训练方法上的研究及二值化网络BinaryConnect，和LeCun用于网络参数裁剪的OBD方法以及低轶分解方面的工作。 剪枝（Pruning）：基于上面提到的过参数化假设，对网络的连接进行裁剪可能是最直觉的做法了。早在上世纪90年代，就有学者开始研究神经网络的参数裁剪（当然，当时还不是DNN）。这里最大的困难在于pruning的同时我们需要让准确率损失尽可能小。不能说pruning完快是快了，但啥都识别不出来了。。。就像前面的调度问题一样，给个解容易，找最优解那是难上加难。业界提出了很多方法，比如逐层按重要程度来进行裁剪，重要程度排序可以按其绝对值、对最终loss或者对特征的可重建性的影响。而对于参数的裁剪比例，一些论文指出网络中每层其敏感程度都不一样，因此也不能一刀切。对一些模型，其中的某些层可能裁剪个三、四成就会明显降低准确率，而一些层即使裁剪九成也不会对准确率造成很大影响，另外有些层可能是由于overfit，反而在pruning后准确率提高了。为了考虑参数间的相互影响关系，研究者们也提出了各种（如基于离散空间搜索、基于梯度、基于聚类、基于Bayesian等）方法来试图找全局意义上的更优解。为了弥补准确率的损失，一般会在pruning后做fine-tuning用来恢复准确率。另外，pruning的姿势也很重要，早期的pruning是非结构化剪枝，这样就有个问题：参数张量上都是“洞”，除非拿专门的硬件加速，否则该做的计算还是省不了，所以目前主流研究的是结构化剪枝，即以channel/filter这个维度来剪，剪完后参数张量只是变“瘦”，这样便可以实打实地减少计算量。值得注意的是，近年比较有意思的一些工作开始重新审视了以前固有的假设，比如过参数化是否真是那么有益，重用pretrained模型参数是否是最好的选择。另外业界还有非常多有意思的工作，这里不一一展开（之前读一些pruning相关论文的整理：闲话模型压缩之网络剪枝（Network Pruning）篇）。 量化（Quantization）：业界共识是对于推理而言，不需要和训练一样的精度。基于这样的假设，量化通过降低weight和activation的精度，成倍减少模型的大小（如32位到8位就是4倍），同时也提高了性能和降低了功耗。一方面一般整数运算要快于浮点运算，另一方面就8位整数和32位浮点操作为例，其能耗可以相差几十倍。正是因为这么明显的好处，量化成为了业界的趋势。无论是框架，计算库和芯片硬件，都在逐步完善对量化模型的支持。和pruning类似，量化本身不是事儿，难的是如何量化的同时保留尽可能高的准确率。量化按精度可分很多种。最为安全的是FP16，大多数情况下它能对性能有较大比例的提升，且对准确率不会有很大影响。但它仍是浮点运算。整数量化中目前最流行的是8位，基本主流训练框架和多数推理框架都官方支持了。在实践中它是一种很有效的提升性能的做法，尤其是对于除CPU外都比较弱的低端平台。但8位量化下就得比较小心准确率的损失了。本质上我们需要为每一层找到最优的量化所需参数，使其量化后信息量损失最小。大体可以分为两种方式：post-training quantization和quantization-aware training。前者是拿到模型后做的压缩，不需要训练环境；后者需在训练时加入特殊算子，一方面在forward时模拟量化效果，另一方面帮助得到量化所需参数，因此准确率损失会更小。但对于post-training quantization，我们可以通过少量数据集来得到量化所需参数（如Nvidia的TensorRT中的calibration过程）。更加激进的就是更低精度的量化了，如4位，3位，2位甚至1位。到了1位时，像卷积和全连接层就可以通过位运算完成，这样的计算对硬件来说是很友好的。然而在这样低的精度下，在量化同时保持准确率就是个大问题了。很多时候纯靠训练后量化就不行了，需要在训练时就考虑低精度。这几年该分支涌现出了像BinaryConnect，BWN，TWN，XNOR，FFN，INQ，BNN等一系列优秀的方法，到今天仍然是个炙手可热的研究方向。 低轶分解（Low-rank factorization）：对于搞工程的同学降维是个老朋友了，很多时候我们对于高维输入先做个降维是常规操作之一。如大家熟悉的SVD分解，通过对分解后对角线矩阵中奇异值的筛选，我们可以用多个低轶矩阵的累加代替或者说近似原矩阵。模型压缩中的低轶分解方法就是基于类似的思想，基于参数张量中普遍存在大量冗余的假设，对参数张量进行低轶分解来近似原参数，从而减少计算量。对于全连接层或卷积的Toeplitz矩阵，可以直接应用SVD。而对于卷积核这样的高阶张量，可以使用SVD的推广 - Tucker分解。另外常见的分解方法还包括CP分解，Block Term分解等。 知识蒸馏（Knowledge distillation）：基本思想是将比较重的（一个或一坨）teacher模型的知识迁移到比较轻（适于部署）的student模型中去，这个过程称为“蒸馏”。就像AI中很多其它算法一样，其实你也没法从数学上严格证明它的正确及有效性，只是从生物界得到的启发，而且事实上也很好用。2015年Hinton老爷子提出和阐述了神经网络中的KD方法。我们知道，在图片分类的网络模型中，最后给的是logit（如果经过softmax则可以看作一个分布），我们一般会选最大的作为预测输出。文中指出teacher模型中该分布中所有其它的值其实也能提供如何泛化的信息，这些信息有助于student模型的学习。换言之，它可以提供除ground truth以外更丰富的监督信息。最朴素的版本是让student模型去学习teacher模型的logit层。后面，研究者们就将它玩出各种花来了，比如演变出student模型去学习teacher模型的feature map，两个student网络相互学习，自我学习等等。另外，知识蒸馏还可以与其它模型压缩方法自然地结合，因为其它方法中经过“压缩”的模型可以作为student模型。 四、小结 在文章的末尾，我想简单聊下个人以为的，对于未来发展趋势和方向的，一些不成熟的看法。 Hardware/Software Co-design：极致的优化一定需要软件和硬件的协同与配合。一方面软件充分利用硬件特性与能力深度优化；而另一方面硬件也正被软件重新定义与推动。当今我们看到这两个方向都在快速的演进。目前，AI芯片除了针对矩阵计算作了大量优化外，还针对当前深度神经网络的一些发展趋势加入相应的特性，如低精度量化，稀疏计算的支持等等。 神经科学交叉：到今天为止，人类对自己的大脑的认知仍然非常有限。尽管由于各种小编为博眼球的断章取义，让刷着科技新闻的我们可能会有种“一切已尽在掌握”的错觉。然而，大脑的创造力、情感、记忆、推理如何运作，还有那超高的能效，其实我们都还知之甚少。但即便是这样，人类也已经从神经科学中获得了不少启发，推动了机器学习领域中不少技术的发展。人脑就像是个巨大的宝藏等待发掘。人工智能的目标不是为了复制人脑，但是，每次对人脑的解密和神经科学的突破，总能给机器学习带来很大的启迪。DeepMind创始人Hassabis本身是神经科学博士，或许也正是这样的交叉学科背景帮助它缔造了这样一家传奇的公司。相信通往AGI的路上神经科学必是最有力的助推器之一。 AutoML：我们知道一个完整的机器学习流程有很多步骤，包括数据生产、采集、处理、训练、部署、优化等等。展望过去的若干年，你会看到机器在各个步骤上正逐步替代人类，而且一些任务中机器会比人类做的更好。从特征选取、网络架构搜索、优化器设计到关乎性能优化的算子调参、模型压缩等各个方面，都被自动化方法替代或部分替代。因为其中的很多问题本质上都是大规模空间中的参数搜索问题。而这类问题不是人类的强项，却是机器的强项。长远来看，这方面人很难干过机器。人类围棋数千年的经验，却被AlphaGo碾压就是一个例子。蓬勃发展的AutoML在短中期将加速促进AI民主化；长期还有可能让机器具备自我进化的能力，这给我们巨大的想象空间。 基于编译器优化：神经网络模型本质上描述了一段计算逻辑，和代码一样。就如代码可以用编译器优化获得性能提升一样，神经网络模型也可以。我们可以看到，其实神经网络计算引擎中的不少优化和传统编译器中的优化是类似的。目前，业界已有不少相关的项目，如XLA，TVM，Glow，Tensor Comprehensions。各个主流深度学习框架似乎也将基于编译器的优化作为必备和大力发展方向。这给结合多个level的end-to-end优化带来巨大的机会。这些技术发展到最后是会相互正交互补，还是合并趋同，是件很有意思的事。 端-云协同：边缘智能计算不代表与云端割裂，相反，它需要云和端更加紧密的结合。尤其是结合5G的发展，给我们广阔的想象空间。一方面，对于计算而言，未来的很多计算可以是中心控制分布计算的方式。一个计算任务可以分布到其它边缘设备，或者云端来共同完成。另一方面，这种协同还可以进一步提高智能化水平。尽管现在智能化产品应用广泛，但很多时候我们会戏称它们不是人工智能而是“人工智障”。个人认为，主要因素之一是因为目前主流方式都是云端统一训练，然后部署到端，过段时间再统一更新模型，进化不够及时。Google的federated learning起了一个好头，更多的变革让我们拭目以待。

本文讲的是Google Interview University - 坚持完成这套学习手册，你就可以去 Google 面试了， 这是我为了从 web 开发者（自学、非计算机科学学位）蜕变至 Google 软件工程师所制定的计划，其内容历时数月。 这一长列表是从 Google 的指导笔记 中萃取出来并进行扩展。因此，有些事情你必须去了解一下。我在列表的底部添加了一些额外项，用于解决面试中可能会出现的问题。这些额外项大部分是来自于 Steve Yegge 的“得到在 Google 工作的机会”。而在 Google 指导笔记的逐字间，它们有时也会被反映出来。 目录 这是？ 为何要用到它？ 如何使用它 拥有一名 Googler 的心态 我得到了工作吗？ 跟随着我 不要自以为自己足够聪明 关于 Google 相关视频资源 面试过程 & 通用的面试准备 为你的面试选择一种语言 在你开始之前 你所看不到的 日常计划 必备知识 算法复杂度 / Big-O / 渐进分析法 数据结构 数组（Arrays） 链表（Linked Lists） 堆栈（Stack） 队列（Queue） 哈希表（Hash table） 更多的知识 二分查找（Binary search） 按位运算（Bitwise operations） 树（Trees） 树 —— 笔记 & 背景 二叉查找树（Binary search trees）：BSTs 堆（Heap） / 优先级队列（Priority Queue） / 二叉堆（Binary Heap） 字典树（Tries） 平衡查找树（Balanced search trees） N 叉树（K 叉树、M 叉树） 排序 图（Graphs） 更多知识 递归 动态规划 组合 & 概率 NP, NP-完全和近似算法 缓存 进程和线程 系统设计、可伸缩性、数据处理 论文 测试 调度 实现系统例程 字符串搜索和操作 终面 书籍 编码练习和挑战 当你临近面试时 你的简历 当面试来临的时候 问面试官的问题 当你获得了梦想的职位 ---------------- 下面的内容是可选的 ---------------- 附加的学习 Unicode 字节顺序 Emacs and vi(m) Unix 命令行工具 信息资源 (视频) 奇偶校验位 & 汉明码 (视频) 系统熵值（系统复杂度） 密码学 压缩 网络 (视频) 计算机安全 释放缓存 并行/并发编程 设计模式 信息传输, 序列化, 和队列化的系统 快速傅里叶变换 布隆过滤器 van Emde Boas 树 更深入的数据结构 跳表 网络流 不相交集 & 联合查找 快速处理数学 树堆 (Treap) 线性规划 几何：凸包（Geometry, Convex hull） 离散数学 机器学习 Go 语言 一些主题的额外内容 视频系列 计算机科学课程 为何要用到它？ 我一直都是遵循该计划去准备 Google 的面试。自 1997 年以来，我一直从事于 web 程序的构建、服务器的构建及创业型公司的创办。对于只有着一个经济学学位，而不是计算机科学学位（CS degree）的我来说，在职业生涯中所取得的都非常成功。然而，我想在 Google 工作，并进入大型系统中，真正地去理解计算机系统、算法效率、数据结构性能、低级别编程语言及其工作原理。可一项都不了解的我，怎么会被 Google 所应聘呢？ 当我创建该项目时，我从一个堆栈到一个堆都不了解。那时的我，完全不了解 Big-O 、树，或如何去遍历一个图。如果非要我去编写一个排序算法的话，我只能说我所写的肯定是很糟糕。一直以来，我所用的任何数据结构都是内建于编程语言当中。至于它们在背后是如何运作，对此我一概不清楚。此外，以前的我并不需要对内存进行管理，最多就只是在一个正在执行的进程抛出了“内存不足”的错误后，采取一些权变措施。而在我的编程生活中，也甚少使用到多维数组，可关联数组却成千上万。而且，从一开始到现在，我都还未曾自己实现过数据结构。 就是这样的我，在经过该学习计划后，已然对被 Google 所雇佣充满信心。这是一个漫长的计划，以至于花费了我数月的时间。若您早已熟悉大部分的知识，那么也许能节省大量的时间。 如何使用它 下面所有的东西都只是一个概述。因此，你需要由上而下逐一地去处理它。 在学习过程中，我是使用 GitHub 特殊的语法特性 markdown flavor 去检查计划的进展，包括使用任务列表。  创建一个新的分支，以使得你可以像这样去检查计划的进展。直接往方括号中填写一个字符 x 即可：[x] 更多关于 Github-flavored markdown 的详情 拥有一名 Googler 的心态 把一个（或两个）印有“future Googler”的图案打印出来，并用你誓要成功的眼神盯着它。 我得到了工作吗？ 我还没去应聘。 因为我离完成学习（完成该疯狂的计划列表）还需要数天的时间，并打算在下周开始用一整天的时间，以编程的方式去解决问题。当然，这将会持续数周的时间。然后，我才通过使用在二月份所得到的一个介绍资格，去正式应聘 Google（没错，是二月份时就得到的）。 感谢 JP 的这次介绍。 跟随着我 目前我仍在该计划的执行过程中，如果你想跟随我脚步去学习的话，可以登进我在 GoogleyAsHeck.com 上所写的博客。 下面是我的联系方式： Twitter: @googleyasheck Twitter: @StartupNextDoor Google+: +Googleyasheck LinkedIn: johnawasham 不要自以为自己足够聪明 Google 的工程师都是才智过人的。但是，就算是工作在 Google 的他们，仍然会因为自己不够聪明而感到一种不安。 天才程序员的神话 关于 Google  面向学生 —— Google 的职业生涯：技术开发指导  Google 检索的原理：  Google 检索的发展史（视频）  Google 检索的原理 —— 故事篇  Google 检索的原理  Google 检索的原理 —— Matt Cutts（视频）  Google 是如何改善其检索算法（视频）  系列文章：  Google 检索是如何处理移动设备  Google 为了寻找大众需求的秘密研究  Google 检索将成为你的下一个大脑  Demis Hassabis 的心灵直白  书籍：Google 公司是如何运作的  由 Google 通告所制作 —— 2016年10月（视频） 相关视频资源 部分视频只能通过在 Coursera、Edx 或 Lynda.com class 上注册登录才能观看。这些视频被称为网络公开课程（MOOC）。即便是免费观看，部分课程可能会由于不在时间段内而无法获取。因此，你需要多等待几个月。 很感谢您能帮我把网络公开课程的视频链接转换成公开的视频源，以代替那些在线课程的视频。此外，一些大学的讲座视频也是我所青睐的。 面试过程 & 通用的面试准备  视频：  如何在 Google 工作 —— 考生指导课程（视频）  Google 招聘者所分享的技术面试小窍门（视频）  如何在 Google 工作：技术型简历的准备（视频）  文章：  三步成为 Googler  得到在 Google 的工作机会 所有他所提及的事情都列在了下面  （早已过期） 如何得到 Google 的一份工作，面试题，应聘过程  手机设备屏幕的问题  附加的（虽然 Google 不建议，但我还是添加在此）：  ABC：永远都要去编程（Always Be Coding）  四步成为 Google 里一名没有学位的员工  共享白板（Whiteboarding）  Google 是如何看待应聘、管理和公司文化  程序开发面试中有效的白板（Whiteboarding）  震撼开发类面试 第一集：  Gayle L McDowell —— 震撼开发类面试（视频）  震撼开发类面试 —— 作者 Gayle Laakmann McDowell（视频）  如何在世界四强企业中获得一份工作：  “如何在世界四强企业中获得一份工作 —— Amazon、Facebook、Google 和 Microsoft”（视频）  面试 Google 失败 为你的面试选择一种语言 在这，我就以下话题写一篇短文 —— 重点：为在 Google 的面试选择一种语言 在大多数公司的面试当中，你可以在编程这一环节，使用一种自己用起来较为舒适的语言去完成编程。但在 Google，你只有三种固定的选择： C++ Java Python 有时你也可以使用下面两种，但需要事先查阅说明。因为，说明中会有警告： JavaScript Ruby 你需要对你所选择的语言感到非常舒适且足够了解。 更多关于语言选择的阅读： http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/ http://blog.codingforinterviews.com/best-programming-language-jobs/ https://www.quora.com/What-is-the-best-language-to-program-in-for-an-in-person-Google-interview 在此查看相关语言的资源 由于，我正在学习C、C++ 和 Python。因此，在下面你会看到部分关于它们的学习资料。相关书籍请看文章的底部。 在你开始之前 该列表已经持续更新了很长的一段时间，所以，我们的确很容易会对其失去控制。 这里列出了一些我所犯过的错误，希望您不要重滔覆辙。 1. 你不可能把所有的东西都记住 就算我查看了数小时的视频，并记录了大量的笔记。几个月后的我，仍然会忘却其中大部分的东西。所以，我翻阅了我的笔记，并将可回顾的东西制作成抽认卡（flashcard）（请往下看） 2. 使用抽认卡 为了解决善忘的问题，我制作了一些关于抽认卡的页面，用于添加两种抽认卡：正常的及带有代码的。每种卡都会有不同的格式设计。 而且，我还以移动设备为先去设计这些网页，以使得在任何地方的我，都能通过我的手机及平板去回顾知识。 你也可以免费制作属于你自己的抽认卡网站： 抽认卡页面的代码仓库 我的抽认卡数据库：有一点需要记住的是，我做事有点过头，以至于把卡片都覆盖到所有的东西上。从汇编语言和 Python 的细枝末节，乃至到机器学习和统计都被覆盖到卡片上。而这种做法，对于 Google 的要求来说，却是多余。 在抽认卡上做笔记： 若你第一次发现你知道问题的答案时，先不要急着把其标注成“已懂”。你需要做的，是去查看一下是否有同样的抽认卡，并在你真正懂得如何解决问题之前，多问自己几次。重复地问答可帮助您深刻记住该知识点。 3. 回顾，回顾，回顾 我留有一组 ASCII 码表、OSI 堆栈、Big-O 记号及更多的小抄纸，以便在空余的时候可以学习。 每编程半个小时就要休息一下，并去回顾你的抽认卡。 4. 专注 在学习的过程中，往往会有许多令人分心的事占据着我们宝贵的时间。因此，专注和集中注意力是非常困难的。 你所看不到的 由于，这个巨大的列表一开始是作为我个人从 Google 面试指导笔记所形成的一个事件处理列表。因此，有一些我熟悉且普遍的技术在此都未被谈及到： SQL Javascript HTML、CSS 和其他前端技术 日常计划 部分问题可能会花费一天的时间去学习，而部分则会花费多天。当然，有些学习并不需要我们懂得如何实现。 因此，每一天我都会在下面所列出的列表中选择一项，并查看相关的视频。然后，使用以下的一种语言去实现： C —— 使用结构体和函数，该函数会接受一个结构体指针 * 及其他数据作为参数。 C++ —— 不使用内建的数据类型。 C++ —— 使用内建的数据类型，如使用 STL 的 std::list 来作为链表。 Python —— 使用内建的数据类型（为了持续练习 Python），并编写一些测试去保证自己代码的正确性。有时，只需要使用断言函数 assert() 即可。 此外，你也可以使用 Java 或其他语言。以上只是我的个人偏好而已。 为何要在这些语言上分别实现一次？ 因为可以练习，练习，练习，直至我厌倦它，并完美地实现出来。（若有部分边缘条件没想到时，我会用书写的形式记录下来并去记忆） 因为可以在纯原生的条件下工作（不需垃圾回收机制的帮助下，分配/释放内存（除了 Python）） 因为可以利用上内建的数据类型，以使得我拥有在现实中使用内建工具的经验（在生产环境中，我不会去实现自己的链表） 就算我没有时间去每一项都这么做，但我也会尽我所能的。 在这里，你可以查看到我的代码： C C++ Python 你不需要记住每一个算法的内部原理。 在一个白板上写代码，而不要直接在计算机上编写。在测试完部分简单的输入后，到计算机上再测试一遍。 必备知识  计算机是如何处理一段程序：  CPU 是如何执行代码（视频）  机器码指令（视频）  编译器  编译器是如何在 ~1 分钟内工作（视频）  Hardvard CS50 —— 编译器（视频）  C++（视频）  掌握编译器的优化（C++）（视频）  浮点数是如何存储的：  简单的 8-bit：浮点数的表达形式　—— 1（视频 —— 在计算上有一个错误 —— 详情请查看视频的介绍）  32 bit：IEEE754 32-bit 浮点二进制（视频） 算法复杂度 / Big-O / 渐进分析法 并不需要实现  Harvard CS50 —— 渐进表示（视频）  Big O 记号（通用快速教程）（视频）  Big O 记号（以及 Omega 和 Theta）—— 最佳数学解释（视频）  Skiena 算法： 视频 幻灯片  对于算法复杂度分析的一次详细介绍  增长阶数（Orders of Growth）（视频）  渐进性（Asymptotics）（视频）  UC Berkeley Big O（视频）  UC Berkeley Big Omega（视频）  平摊分析法（Amortized Analysis）（视频）  举证“Big O”（视频）  高级编程（包括递归关系和主定理）： 计算性复杂度：第一部 计算性复杂度：第二部  速查表（Cheat sheet） 如果部分课程过于学术性，你可直接跳到文章底部，去查看离散数学的视频以获取相关背景知识。 数据结构 数组（Arrays） 实现一个可自动调整大小的动态数组。  介绍： 数组（视频） 数组的基础知识（视频） 多维数组（视频） 动态数组（视频） 不规则数组（视频） 调整数组的大小（视频）  实现一个动态数组（可自动调整大小的可变数组）：  练习使用数组和指针去编码，并且指针是通过计算去跳转而不是使用索引  通过分配内存来新建一个原生数据型数组 可以使用 int 类型的数组，但不能使用其语法特性 从大小为16或更大的数（使用2的倍数 —— 16、32、64、128）开始编写  size() —— 数组元素的个数  capacity() —— 可容纳元素的个数  is_empty()  at(index) —— 返回对应索引的元素，且若索引越界则愤然报错  push(item)  insert(index, item) —— 在指定索引中插入元素，并把后面的元素依次后移  prepend(item) —— 可以使用上面的 insert 函数，传参 index 为 0  pop() —— 删除在数组末端的元素，并返回其值  delete(index) —— 删除指定索引的元素，并把后面的元素依次前移  remove(item) —— 删除指定值的元素，并返回其索引（即使有多个元素）  find(item) —— 寻找指定值的元素并返回其中第一个出现的元素其索引，若未找到则返回 -1  resize(new_capacity) // 私有函数 若数组的大小到达其容积，则变大一倍 获取元素后，若数组大小为其容积的1/4，则缩小一半  时间复杂度 在数组末端增加/删除、定位、更新元素，只允许占 O(1) 的时间复杂度（平摊（amortized）去分配内存以获取更多空间） 在数组任何地方插入/移除元素，只允许 O(n) 的时间复杂度  空间复杂度 因为在内存中分配的空间邻近，所以有助于提高性能 空间需求 = （大于或等于 n 的数组容积）* 元素的大小。即便空间需求为 2n，其空间复杂度仍然是 O(n) 链表（Linked Lists）  介绍：  单向链表（视频）  CS 61B —— 链表（视频）  C 代码（视频） 并非看完整个视频，只需要看关于节点结果和内存分配那一部分即可  链表 vs 数组： 基本链表 Vs 数组（视频） 在现实中，链表 Vs 数组（视频）  为什么你需要避免使用链表（视频）  的确：你需要关于“指向指针的指针”的相关知识：（因为当你传递一个指针到一个函数时，该函数可能会改变指针所指向的地址）该页只是为了让你了解“指向指针的指针”这一概念。但我并不推荐这种链式遍历的风格。因为，这种风格的代码，其可读性和可维护性太低。 指向指针的指针  实现（我实现了使用尾指针以及没有使用尾指针这两种情况）：  size() —— 返回链表中数据元素的个数  empty() —— 若链表为空则返回一个布尔值 true  value_at(index) —— 返回第 n 个元素的值（从0开始计算）  push_front(value) —— 添加元素到链表的首部  pop_front() —— 删除首部元素并返回其值  push_back(value) —— 添加元素到链表的尾部  pop_back() —— 删除尾部元素并返回其值  front() —— 返回首部元素的值  back() —— 返回尾部元素的值  insert(index, value) —— 插入值到指定的索引，并把当前索引的元素指向到新的元素  erase(index) —— 删除指定索引的节点  value_n_from_end(n) —— 返回倒数第 n 个节点的值  reverse() —— 逆序链表  remove_value(value) —— 删除链表中指定值的第一个元素  双向链表 介绍（视频） 并不需要实现 堆栈（Stack）  堆栈（视频）  使用堆栈 —— 后进先出（视频）  可以不实现，因为使用数组来实现并不重要 队列（Queue）  使用队列 —— 先进先出（视频）  队列（视频）  原型队列/先进先出（FIFO）  优先级队列（视频）  使用含有尾部指针的链表来实现: enqueue(value) —— 在尾部添加值 dequeue() —— 删除最早添加的元素并返回其值（首部元素） empty()  使用固定大小的数组实现： enqueue(value) —— 在可容的情况下添加元素到尾部 dequeue() —— 删除最早添加的元素并返回其值 empty() full()  花销： 在糟糕的实现情况下，使用链表所实现的队列，其入列和出列的时间复杂度将会是 O(n)。因为，你需要找到下一个元素，以致循环整个队列 enqueue：O(1)（平摊（amortized）、链表和数组 [探测（probing）]） dequeue：O(1)（链表和数组） empty：O(1)（链表和数组） 哈希表（Hash table）  视频：  链式哈希表（视频）  Table Doubling 和 Karp-Rabin（视频）  Open Addressing 和密码型哈希（Cryptographic Hashing）（视频）  PyCon 2010：The Mighty Dictionary（视频）  （进阶）随机取样（Randomization）：全域哈希（Universal Hashing）& 完美哈希（Perfect Hashing）（视频）  （进阶）完美哈希（Perfect hashing）（视频）  在线课程：  哈希函数的掌握（视频）  使用哈希表（视频）  哈希表的支持（视频）  哈希表的语言支持（视频）  基本哈希表（视频）  数据结构（视频）  电话薄问题（Phone Book Problem）（视频）  分布式哈希表： Dropbox 中的瞬时上传及存储优化（视频） 分布式哈希表（视频）  使用线性探测的数组去实现 hash(k, m) —— m 是哈希表的大小 add(key, value) —— 如果 key 已存在则更新值 exists(key) get(key) remove(key) 更多的知识 二分查找（Binary search）  二分查找（视频）  二分查找（视频）  详情  实现： 二分查找（在一个已排序好的整型数组中查找） 迭代式二分查找 按位运算（Bitwise operations）  Bits 速查表 你需要知道大量2的幂数值（从2^1 到 2^16 及 2^32）  好好理解位操作符的含义：&、|、^、~、>>、<<  字码（words）  好的介绍： 位操作（视频）  C 语言编程教程 2-10：按位运算（视频）  位操作  按位运算  Bithacks  位元抚弄者（The Bit Twiddler）  交互式位元抚弄者（The Bit Twiddler Interactive）  一补数和补码 二进制：利 & 弊（为什么我们要使用补码）（视频） 一补数（1s Complement） 补码（2s Complement）  计算置位（Set Bits） 计算一个字节中置位（Set Bits）的四种方式（视频） 计算比特位 如何在一个 32 位的整型中计算置位（Set Bits）的数量  四舍五入2的幂数： 四舍五入到2的下一幂数  交换值： 交换（Swap）  绝对值： 绝对整型（Absolute Integer） 树（Trees） 树 —— 笔记 & 背景  系列：基本树（视频）  系列：树（视频） 基本的树形结构 遍历 操作算法 BFS（广度优先检索，breadth-first search） MIT（视频） 层序遍历（使用队列的 BFS 算法） 时间复杂度： O(n) 空间复杂度： 最好情况： O(1) 最坏情况：O(n/2)=O(n) DFS（深度优先检索，depth-first search） MIT（视频） 笔记： 时间复杂度：O(n) 空间复杂度： 最好情况：O(log n) - 树的平均高度 最坏情况：O(n) 中序遍历（DFS：左、节点本身、右） 后序遍历（DFS：左、右、节点本身） 先序遍历（DFS：节点本身、左、右） 二叉查找树（Binary search trees）：BSTs  二叉查找树概览（视频）  系列（视频） 从符号表开始到 BST 程序  介绍（视频）  MIT（视频） C/C++:  二叉查找树 —— 在 C/C++ 中实现（视频）  BST 的实现 —— 在堆栈和堆中的内存分配（视频）  在二叉查找树中找到最小和最大的元素（视频）  寻找二叉树的高度（视频）  二叉树的遍历 —— 广度优先和深度优先策略（视频）  二叉树：层序遍历（视频）  二叉树的遍历：先序、中序、后序（视频）  判断一棵二叉树是否为二叉查找树（视频）  从二叉查找树中删除一个节点（视频）  二叉查找树中序遍历的后继者（视频）  实现：  insert // 往树上插值  get_node_count // 查找树上的节点数  print_values // 从小到大打印树中节点的值  delete_tree  is_in_tree // 如果值存在于树中则返回 true  get_height // 返回节点所在的高度（如果只有一个节点，那么高度则为1）  get_min // 返回树上的最小值  get_max // 返回树上的最大值  is_binary_search_tree  delete_value  get_successor // 返回给定值的后继者，若没有则返回-1 堆（Heap） / 优先级队列（Priority Queue） / 二叉堆（Binary Heap） 可视化是一棵树，但通常是以线性的形式存储（数组、链表）  堆  介绍（视频）  无知的实现（视频）  二叉树（视频）  关于树高的讨论（视频）  基本操作（视频）  完全二叉树（视频）  伪代码（视频）  堆排序 —— 跳到起点（视频）  堆排序（视频）  构建一个堆（视频）  MIT：堆与堆排序（视频）  CS 61B Lecture 24：优先级队列（视频）  构建线性时间复杂度的堆（大顶堆）  实现一个大顶堆：  insert  sift_up —— 用于插入元素  get_max —— 返回最大值但不移除元素  get_size() —— 返回存储的元素数量  is_empty() —— 若堆为空则返回 true  extract_max —— 返回最大值并移除  sift_down —— 用于获取最大值元素  remove(i) —— 删除指定索引的元素  heapify —— 构建堆，用于堆排序  heap_sort() —— 拿到一个未排序的数组，然后使用大顶堆进行就地排序 注意：若用小顶堆可节省操作，但导致空间复杂度加倍。（无法做到就地） 字典树（Tries） 需要注意的是，字典树各式各样。有些有前缀，而有些则没有。有些使用字符串而不使用比特位来追踪路径。 阅读代码，但不实现。  数据结构笔记及编程技术  短课程视频：  对字典树的介绍（视频）  字典树的性能（视频）  实现一棵字典树（视频）  字典树：一个被忽略的数据结构  高级编程 —— 使用字典树  标准教程（现实中的用例）（视频）  MIT，高阶数据结构，使用字符串追踪路径（可事半功倍） 平衡查找树（Balanced search trees） 掌握至少一种平衡查找树（并懂得如何实现）： “在各种平衡查找树当中，AVL 树和2-3树已经成为了过去，而红黑树（red-black trees）看似变得越来越受人青睐。这种令人特别感兴趣的数据结构，亦称伸展树（splay tree）。它可以自我管理，且会使用轮换来移除任何访问过根节点的 key。” —— Skiena 因此，在各种各样的平衡查找树当中，我选择了伸展树来实现。虽然，通过我的阅读，我发现在 Google 的面试中并不会被要求实现一棵平衡查找树。但是，为了胜人一筹，我们还是应该看看如何去实现。在阅读了大量关于红黑树的代码后，我才发现伸展树的实现确实会使得各方面更为高效。 伸展树：插入、查找、删除函数的实现，而如果你最终实现了红黑树，那么请尝试一下： 跳过删除函数，直接实现搜索和插入功能 我希望能阅读到更多关于 B 树的资料，因为它也被广泛地应用到大型的数据库当中。  自平衡二叉查找树  AVL 树 实际中：我能告诉你的是，该种树并无太多的用途，但我能看到有用的地方在哪里：AVL 树是另一种平衡查找树结构。其可支持时间复杂度为 O(log n) 的查询、插入及删除。它比红黑树严格意义上更为平衡，从而导致插入和删除更慢，但遍历却更快。正因如此，才彰显其结构的魅力。只需要构建一次，就可以在不重新构造的情况下读取，适合于实现诸如语言字典（或程序字典，如一个汇编程序或解释程序的操作码）。  MIT AVL 树 / AVL 树的排序（视频）  AVL 树（视频）  AVL 树的实现（视频）  分离与合并  伸展树 实际中：伸展树一般用于缓存、内存分配者、路由器、垃圾回收者、数据压缩、ropes（字符串的一种替代品，用于存储长串的文本字符）、Windows NT（虚拟内存、网络及文件系统）等的实现。  CS 61B：伸展树（Splay trees）（视频）  MIT 教程：伸展树（Splay trees）： 该教程会过于学术，但请观看到最后的10分钟以确保掌握。 视频  2-3查找树 实际中：2-3树的元素插入非常快速，但却有着查询慢的代价（因为相比较 AVL 树来说，其高度更高）。 你会很少用到2-3树。这是因为，其实现过程中涉及到不同类型的节点。因此，人们更多地会选择红黑树。  2-3树的直感与定义（视频）  2-3树的二元观点  2-3树（学生叙述）（视频）  2-3-4树 (亦称2-4树) 实际中：对于每一棵2-4树，都有着对应的红黑树来存储同样顺序的数据元素。在2-4树上进行插入及删除操作等同于在红黑树上进行颜色翻转及轮换。这使得2-4树成为一种用于掌握红黑树背后逻辑的重要工具。这就是为什么许多算法引导文章都会在介绍红黑树之前，先介绍2-4树，尽管2-4树在实际中并不经常使用。  CS 61B Lecture 26：平衡查找树（视频）  自底向上的2-4树（视频）  自顶向下的2-4树（视频）  B 树 有趣的是：为啥叫 B 仍然是一个神秘。因为 B 可代表波音（Boeing）、平衡（Balanced）或 Bayer（联合创造者） 实际中：B 树会被广泛适用于数据库中，而现代大多数的文件系统都会使用到这种树（或变种)。除了运用在数据库中，B 树也会被用于文件系统以快速访问一个文件的任意块。但存在着一个基本的问题，那就是如何将文件块 i 转换成一个硬盘块（或一个柱面-磁头-扇区）上的地址。  B 树  B 树的介绍（视频）  B 树的定义及其插入操作（视频）  B 树的删除操作（视频）  MIT 6.851 —— 内存层次模块（Memory Hierarchy Models）（视频） 覆盖有高速缓存参数无关型（cache-oblivious）B 树和非常有趣的数据结构 头37分钟讲述的很专业，或许可以跳过（B 指块的大小、即缓存行的大小）  红黑树 实际中：红黑树提供了在最坏情况下插入操作、删除操作和查找操作的时间保证。这些时间值的保障不仅对时间敏感型应用有用，例如实时应用，还对在其他数据结构中块的构建非常有用，而这些数据结构都提供了最坏情况下的保障；例如，许多用于计算几何学的数据结构都可以基于红黑树，而目前 Linux 系统所采用的完全公平调度器（the Completely Fair Scheduler）也使用到了该种树。在 Java 8中，红黑树也被用于存储哈希列表集合中相同的数据，而不是使用链表及哈希码。  Aduni —— 算法 —— 课程4（该链接直接跳到开始部分）（视频）  Aduni —— 算法 —— 课程5（视频）  黑树（Black Tree）  二分查找及红黑树的介绍 N 叉树（K 叉树、M 叉树） 注意：N 或 K 指的是分支系数（即树的最大分支数）： 二叉树是一种分支系数为2的树 2-3树是一种分支系数为3的树  K 叉树 排序（Sorting）  笔记: 实现各种排序 & 知道每种排序的最坏、最好和平均的复杂度分别是什么场景: 不要用冒泡排序 - 大多数情况下效率感人 - 时间复杂度 O(n^2), 除非 n <= 16  排序算法的稳定性 ("快排是稳定的么?") 排序算法的稳定性 排序算法的稳定性 排序算法的稳定性 排序算法的稳定性 排序算法 - 稳定性  哪种排序算法可以用链表？哪种用数组？哪种两者都可？ 并不推荐对一个链表排序，但归并排序是可行的. 链表的归并排序 关于堆排序，请查看前文堆的数据结构部分。堆排序很强大，不过是非稳定排序。  冒泡排序 (video)  冒泡排序分析 (video)  插入排序 & 归并排序 (video)  插入排序 (video)  归并排序 (video)  快排 (video)  选择排序 (video)  斯坦福大学关于排序算法的视频:  课程 15 | 编程抽象 (video)  课程 16 | 编程抽象 (video)  Shai Simonson 视频, Aduni.org:  算法 - 排序 - 第二讲 (video)  算法 - 排序2 - 第三讲 (video)  Steven Skiena 关于排序的视频:  课程从 26:46 开始 (video)  课程从 27:40 开始 (video)  课程从 35:00 开始 (video)  课程从 23:50 开始 (video)  加州大学伯克利分校（UC Berkeley） 大学课程:  CS 61B 课程 29: 排序 I (video)  CS 61B 课程 30: 排序 II (video)  CS 61B 课程 32: 排序 III (video)  CS 61B 课程 33: 排序 V (video)  - 归并排序:  使用外部数组  对原数组直接排序  - 快速排序:  实现  实现  实现:  归并：平均和最差情况的时间复杂度为 O(n log n)。  快排：平均时间复杂度为 O(n log n)。 选择排序和插入排序的最坏、平均时间复杂度都是 O(n^2)。 关于堆排序，请查看前文堆的数据结构部分。  有兴趣的话，还有一些补充 - 但并不是必须的:  基数排序  基数排序 (video)  基数排序, 计数排序 (线性时间内) (video)  随机算法: 矩阵相乘, 快排, Freivalds' 算法 (video)  线性时间内的排序 (video) 图（Graphs） 图论能解决计算机科学里的很多问题，所以这一节会比较长，像树和排序的部分一样。 Yegge 的笔记: 有 3 种基本方式在内存里表示一个图: 对象和指针 矩阵 邻接表 熟悉以上每一种图的表示法，并了解各自的优缺点 宽度优先搜索和深度优先搜索 - 知道它们的计算复杂度和设计上的权衡以及如何用代码实现它们 遇到一个问题时，首先尝试基于图的解决方案，如果没有再去尝试其他的。  Skiena 教授的课程 - 很不错的介绍:  CSE373 2012 - 课程 11 - 图的数据结构 (video)  CSE373 2012 - 课程 12 - 广度优先搜索 (video)  CSE373 2012 - 课程 13 - 图的算法 (video)  CSE373 2012 - 课程 14 - 图的算法 (1) (video)  CSE373 2012 - 课程 15 - 图的算法 (2) (video)  CSE373 2012 - 课程 16 - 图的算法 (3) (video)  图 (复习和其他):  6.006 单源最短路径问题 (video)  6.006 Dijkstra 算法 (video)  6.006 Bellman-Ford 算法(video)  6.006 Dijkstra 效率优化 (video)  Aduni: 图的算法 I - 拓扑排序, 最小生成树, Prim 算法 - 第六课 (video)  Aduni: 图的算法 II - 深度优先搜索, 广度优先搜索, Kruskal 算法, 并查集数据结构 - 第七课 (video)  Aduni: 图的算法 III: 最短路径 - 第八课 (video)  Aduni: 图的算法. IV: 几何算法介绍 - 第九课 (video)  CS 61B 2014 (从 58:09 开始) (video)  CS 61B 2014: 加权图 (video)  贪心算法: 最小生成树 (video)  图的算法之强连通分量 Kosaraju 算法 (video) 完整的 Coursera 课程:  图的算法 (video) Yegge: 如果有机会，可以试试研究更酷炫的算法:  Dijkstra 算法 - 上文 - 6.006  A* 算法  A* 算法  A* 寻路教程 (video)  A* 寻路 (E01: 算法解释) (video) 我会实现:  DFS 邻接表 (递归)  DFS 邻接表 (栈迭代)  DFS 邻接矩阵 (递归)  DFS 邻接矩阵 (栈迭代)  BFS 邻接表  BFS 邻接矩阵  单源最短路径问题 (Dijkstra)  最小生成树 基于 DFS 的算法 (根据上文 Aduni 的视频):  检查环 (我们会先检查是否有环存在以便做拓扑排序)  拓扑排序  计算图中的连通分支  列出强连通分量  检查双向图 可以从 Skiena 的书（参考下面的书推荐小节）和面试书籍中学习更多关于图的实践。 更多知识 递归（Recursion）  Stanford 大学关于递归 & 回溯的课程:  课程 8 | 抽象编程 (video)  课程 9 | 抽象编程 (video)  课程 10 | 抽象编程 (video)  课程 11 | 抽象编程 (video) 什么时候适合使用 尾递归会更好么?  什么是尾递归以及为什么它如此糟糕?  尾递归 (video) 动态规划（Dynamic Programming） This subject can be pretty difficult, as each DP soluble problem must be defined as a recursion relation, and coming up with it can be tricky. 这一部分会有点困难，每个可以用动态规划解决的问题都必须先定义出递推关系，要推导出来可能会有点棘手。 我建议先阅读和学习足够多的动态规划的例子，以便对解决 DP 问题的一般模式有个扎实的理解。  视频: Skiena 的视频可能会有点难跟上，有时候他用白板写的字会比较小，难看清楚。  Skiena: CSE373 2012 - 课程 19 - 动态规划介绍 (video)  Skiena: CSE373 2012 - 课程 20 - 编辑距离 (video)  Skiena: CSE373 2012 - 课程 21 - 动态规划举例 (video)  Skiena: CSE373 2012 - 课程 22 - 动态规划应用 (video)  Simonson: 动态规划 0 (starts at 59:18) (video)  Simonson: 动态规划 I - 课程 11 (video)  Simonson: 动态规划 II - 课程 12 (video)  单独的 DP 问题 (每一个视频都很短): 动态规划 (video)  Yale 课程笔记:  动态规划  Coursera 课程:  RNA 二级结构问题 (video)  动态规划算法 (video)  DP 算法描述 (video)  DP 算法的运行时间 (video)  DP vs 递归实现 (video)  全局成对序列排列 (video)  本地成对序列排列 (video) 组合（Combinatorics） (n 中选 k 个) & 概率（Probability）  数据技巧: 如何找出阶乘、排列和组合(选择) (video)  来点学校的东西: 概率 (video)  来点学校的东西: 概率和马尔可夫链 (video)  可汗学院: 课程设置:  概率理论基础 视频 - 41 (每一个都短小精悍):  概率解释 (video) NP, NP-完全和近似算法 知道最经典的一些 NP 完全问题，比如旅行商问题和背包问题, 而且能在面试官试图忽悠你的时候识别出他们。 知道 NP 完全是什么意思.  计算复杂度 (video)  Simonson:  贪心算法. II & 介绍 NP-完全性 (video)  NP-完全性 II & 归约 (video)  NP-完全性 III (Video)  NP-完全性 IV (video)  Skiena:  CSE373 2012 - 课程 23 - 介绍 NP-完全性 IV (video)  CSE373 2012 - 课程 24 - NP-完全性证明 (video)  CSE373 2012 - 课程 25 - NP-完全性挑战 (video)  复杂度: P, NP, NP-完全性, 规约 (video)  复杂度: 近视算法 Algorithms (video)  复杂度: 固定参数算法 (video) Peter Norvik 讨论旅行商问题的近似最优解: Jupyter 笔记本 《算法导论》的第 1048 - 1140 页。 缓存（Cache）  LRU 缓存:  LRU 的魔力 (100 Days of Google Dev) (video)  实现 LRU (video)  LeetCode - 146 LRU Cache (C++) (video)  CPU 缓存:  MIT 6.004 L15: 存储体系 (video)  MIT 6.004 L16: 缓存的问题 (video) 进程（Processe）和线程（Thread）  计算机科学 162 - 操作系统 (25 个视频): 视频 1-11 是关于进程和线程 操作系统和系统编程 (video) 进程和线程的区别是什么? 涵盖了: 进程、线程、协程 进程和线程的区别 进程 线程 锁 互斥 信号量 监控 他们是如何工作的 死锁 活锁 CPU 活动, 中断, 上下文切换 现代多核处理器的并发式结构 进程资源需要（内存：代码、静态存储器、栈、堆、文件描述符、I/O） 线程资源需要（在同一个进程内和其他线程共享以上的资源，但是每个线程都有独立的程序计数器、栈计数器、寄存器和栈） Fork 操作是真正的写时复制（只读），直到新的进程写到内存中，才会生成一份新的拷贝。 上下文切换 操作系统和底层硬件是如何初始化上下文切换的。  C++ 的线程 (系列 - 10 个视频)  Python 的协程 (视频):  线程系列  Python 线程  理解 Python 的 GIL (2010) 参考  David Beazley - Python 协程 - PyCon 2015  Keynote David Beazley - 兴趣主题 (Python 异步 I/O)  Python 中的互斥 系统设计以及可伸缩性，要把软硬件的伸缩性设计的足够好有很多的东西要考虑，所以这是个包含非常多内容和资源的大主题。需要花费相当多的时间在这个主题上。 系统设计、可伸缩性、数据处理 Yegge 的注意事项: 伸缩性 把大数据集提取为单一值 大数据集转换 处理大量的数据集 系统 特征集 接口 类层次结构 在特定的约束下设计系统 轻量和健壮性 权衡和折衷 性能分析和优化  从这里开始: HiredInTech：系统设计  该如何为技术面试里设计方面的问题做准备?  在系统设计面试前必须知道的 8 件事  算法设计  数据库范式 - 1NF, 2NF, 3NF and 4NF (video)  系统设计面试 - 这一部分有很多的资源，浏览一下我放在下面的文章和例子。  如何在系统设计面试中脱颖而出  每个人都该知道的一些数字  上下文切换操作会耗费多少时间?  跨数据中心的事务 (video)  简明 CAP 理论介绍  Paxos 一致性算法: 时间很短 用例 和 multi-paxos 论文  一致性哈希  NoSQL 模式  OOSE: UML 2.0 系列 (video)  OOSE: 使用 UML 和 Java 开发软件 (21 videos): 如果你对 OO 都深刻的理解和实践，可以跳过这部分。 OOSE: 使用 UML 和 Java 开发软件  面向对象编程的 SOLID 原则:  Bob Martin 面向对象的 SOLID 原则和敏捷设计 (video)  C# SOLID 设计模式 (video)  SOLID 原则 (video)  S - 单一职责原则 | 每个对象的单一职责 更多  O - 开闭原则 | 生产环境里的对象应该为扩展做准备而不是为更改 更多  L - 里氏代换原则 | 基类和继承类遵循 ‘IS A’ 原则 更多  I - 接口隔离原则 | 客户端被迫实现用不到的接口 5 分钟讲解接口隔离原则 (video) 更多  D -依赖反转原则 | 减少对象里的依赖。 什么是依赖倒置以及它为什么重要 更多  可伸缩性:  很棒的概述 (video)  简短系列: 克隆 数据库 缓存 异步  可伸缩的 Web 架构和分布式系统  错误的分布式系统解释  实用编程技术 extra: Google Pregel 图形处理  Jeff Dean - 在 Goolge 构建软件系统 (video)  可伸缩系统架构设计介绍  使用 App Engine 和云存储扩展面向全球用户的手机游戏架构实践(video)  How Google Does Planet-Scale Engineering for Planet-Scale Infra (video)  算法的重要性  分片  Facebook 系统规模扩展实践 (2009)  Facebook 系统规模扩展实践 (2012), "为 10 亿用户构建" (video)  Long Game 工程实践 - Astrid Atkinson Keynote(video)  30 分钟看完 YouTuBe 7 年系统扩展经验 video  PayPal 如何用 8 台虚拟机扛住 10 亿日交易量系统  如何对大数据集去重  Etsy 的扩展和工程文化探究 Jon Cowie (video)  是什么造就了 Amazon 自己的微服务架构  压缩还是不压缩，是 Uber 面临的问题  异步 I/O Tarantool 队列  什么时候应该用近视查询处理?  Google 从单数据中心到故障转移, 到本地多宿主架构的演变  Spanner  Egnyte: 构建和扩展 PB 级分布式系统架构的经验教训  机器学习驱动的编程: 新世界的新编程方式  日服务数百万请求的图像优化技术  Patreon 架构  Tinder: 推荐引擎是如何决定下一个你将会看到谁的?  现代缓存设计  Facebook 实时视频流扩展  在 Amazon AWS 上把服务扩展到 1100 万量级的新手教程  对延时敏感的应用是否应该使用 Docker?  AMP（Accelerated Mobile Pages）的存在是对 Google 的威胁么?  360 度解读 Netflix 技术栈  延迟无处不在 - 如何搞定它？  无服务器架构  是什么驱动着 Instagram: 上百个实例、几十种技术  Cinchcast 架构 - 每天处理 1500 小时的音频  Justin.Tv 实时视频播放架构  Playfish's 社交游戏架构 - 每月五千万用户增长  猫途鹰架构 - 40 万访客, 200 万动态页面访问, 30TB 数据  PlentyOfFish 架构  Salesforce 架构 - 如何扛住 13 亿日交易量  ESPN's 架构扩展  下面 『消息、序列化和消息系统』部分的内容会提到什么样的技术能把各种服务整合到一起  Twitter: O'Reilly MySQL CE 2011: Jeremy Cole, "Big and Small Data at @Twitter" (video) 时间线的扩展 更多内容可以查看视频部分的『大规模数据挖掘』视频系列。  系统设计问题练习：下面有一些指导原则，每一个都有相关文档以及在现实中该如何处理。 复习: HiredInTech 的系统设计 cheat sheet 流程: 理解问题和范围: 在面试官的帮助下定义用例 提出附加功能的建议 去掉面试官认定范围以外的内容 假定高可用是必须的，而且要作为一个用例 考虑约束: 问一下每月请求量 问一下每秒请求量 (他们可能会主动提到或者让你算一下) 评估读写所占的百分比 评估的时候牢记 2/8 原则 每秒写多少数据 总的数据存储量要考虑超过 5 年的情况 每秒读多少数据 抽象设计: 分层 (服务, 数据, 缓存) 基础设施: 负载均衡, 消息 粗略的概括任何驱动整个服务的关键算法 考虑瓶颈并指出解决方案 练习: 设计一个 CDN 网络 设计一个随机唯一 ID 生成系统 设计一个在线多人卡牌游戏 设计一个 key-value 数据库 设计一个函数获取过去某个时间段内前 K 个最高频访问的请求 设计一个图片分享系统 设计一个推荐系统 设计一个短域名生成系统 设计一个缓存系统 论文 有 Google 的论文和一些知名的论文. 你很可能实在没时间一篇篇完整的读完他们。我建议可以有选择的读其中一些论文里的核心部分。  1978: 通信顺序处理 Go 实现 喜欢经典的论文?  2003: The Google 文件系统 2012 年被 Colossus 取代了  2004: MapReduce: Simplified Data Processing on Large Clusters 大多被云数据流取代了?  2007: 每个程序员都应该知道的内存知识 (非常长，作者建议跳过某些章节来阅读)  2012: Google 的 Colossus 没有论文  2012: AddressSanitizer: 快速的内存访问检查器: 论文 视频  2013: Spanner: Google 的分布式数据库: 论文 视频  2014: Machine Learning: The High-Interest Credit Card of Technical Debt  2015: Continuous Pipelines at Google  2015: 大规模高可用: 构建 Google Ads 的数据基础设施  2015: TensorFlow: 异构分布式系统上的大规模机器学习  2015: 开发者应该如何搜索代码：用例学习  2016: Borg, Omega, and Kubernetes 测试 涵盖了: 单元测试是如何工作的 什么是模拟对象 什么是集成测试 什么是依赖注入  James Bach 讲敏捷软件测试 (video)  James Bach 软件测试公开课 (video)  Steve Freeman - 测试驱动的开发 (video) slides  测试驱动的开发已死。测试不朽。  测试驱动的开发已死? (video)  视频系列 (152 个) - 并不都是必须 (video)  Python：测试驱动的 Web 开发  依赖注入:  视频  测试之道  如何编写测试 调度 在操作系统中是如何运作的 在操作系统部分的视频里有很多资料 实现系统例程 理解你使用的系统 API 底层有什么 你能自己实现它们么? 字符串搜索和操作  文本的搜索模式 (video)  Rabin-Karp (videos): Rabin Karps 算法 预先计算的优化 优化: 实现和分析 Table Doubling, Karp-Rabin 滚动哈希  Knuth-Morris-Pratt (KMP) 算法: Pratt 算法 教程: Knuth-Morris-Pratt (KMP) 字符串匹配算法  Boyer–Moore 字符串搜索算法 Boyer-Moore字符串搜索算法 Boyer-Moore-Horspool 高级字符串搜索算法 (video)  Coursera: 字符串的算法 终面 这一部分有一些短视频，你可以快速的观看和复习大多数重要概念。 这对经常性的巩固很有帮助。 综述:  2-3 分钟的短视频系列 (23 个) Videos  2-5 分钟的短视频系列 - Michael Sambol (18 个): Videos 排序:  归并排序: https://www.youtube.com/watch?v=GCae1WNvnZM 书籍 Google Coaching 里提到的 阅读并做练习:  算法设计手册 (Skiena) 书 (Kindle 上可以租到): Algorithm Design Manual Half.com 是一个资源丰富且性价比很高的在线书店. 答案: 解答 解答 勘误表 read and do exercises from the books below. Then move to coding challenges (further down below) 一旦你理解了每日计划里的所有内容，就去读上面所列的书并完成练习，然后开始读下面所列的书并做练习，之后就可以开始实战写代码了（本文再往后的部分） 首先阅读:  Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition 然后阅读 (这本获得了很多推荐， 但是不在 Google coaching 的文档里):  Cracking the Coding Interview, 6th Edition 如果你看到有人在看 "The Google Resume", 实际上它和 "Cracking the Coding Interview" 是同一个作者写的，而且后者是升级版。 附加书单 这些没有被 Google 推荐阅读，不过我因为需要这些背景知识所以也把它们列在了这里。  C Programming Language, Vol 2 练习的答案  C++ Primer Plus, 6th Edition  《Unxi 环境高级编程》 The Unix Programming Environment  《编程珠玑》 Programming Pearls  Algorithms and Programming: Problems and Solutions 如果你有时间  Introduction to Algorithms  Elements of Programming Interviews 如果你希望在面试里用 C++ 写代码，这本书的代码全都是 C++ 写的 通常情况下能找到解决方案的好书. 编码练习和挑战 一旦你学会了理论基础，就应该把它们拿出来练练。 尽量坚持每天做编码练习，越多越好。 编程问题预备:  不错的介绍 (摘自 System Design 章节): 算法设计:  如何找到解决方案  如何剖析 Topcoder 题目描述  Topcoders 里用到的数学  动态规划 – 从入门到精通 MIT 面试材料 针对编程语言本身的练习 编码练习平台: LeetCode TopCoder Project Euler (数学方向为主) Codewars HackerRank Codility InterviewCake InterviewBit 模拟大公司的面试 当你临近面试时  搞定代码面试 (videos): Cracking The Code Interview Cracking the Coding Interview - 全栈系列 Ask Me Anything: Gayle Laakmann McDowell (Cracking the Coding Interview 的作者) 你的简历 10 条小贴士让你写出一份还算不错的简历 这是搞定面试的第一个关键步骤 当面试来临的时候 随着下面列举的问题思考下你可能会遇到的 20 个面试问题 每个问题准备 2-3 种回答 准备点故事，不要只是摆一些你完成的事情的数据，相信我，人人都喜欢听故事 你为什么想得到这份工作？ 你解决过的最有难度的问题是什么？ 面对过的最大挑战是什么? 见过的最好或者最坏的设计是怎么样的? 对某项 Google 产品提出改进建议。 你作为一个个体同时也是团队的一员，如何达到最好的工作状态? 你的什么技能或者经验是你的角色中不可或缺的?为什么？ 你在某份工作或某个项目中最享受的是什么? 你在某份工作或某个项目中面临过的最大挑战是什么? 你在某份工作或某个项目中遇到过的最蛋疼的 Bug 是什么样的？ 你在某份工作或某个项目中学到了什么？ 你在某份工作或某个项目中哪些地方还可以做的更好？ 问面试官的问题 我会问的一些：(可能我已经知道了答案但我想听听面试官的看法或者了解团队的前景): 团队多大规模? 开发周期是怎样的? 会使用瀑布流/极限编程/敏捷开发么? 经常会为 deadline 加班么? 或者是有弹性的? 团队里怎么做技术选型? 每周平均开多少次会? 你觉得工作环境有助于员工集中精力吗? 目前正在做什么工作? 喜欢这些事情吗? 工作期限是怎么样的? 当你获得了梦想的职位 我还能说些什么呢，恭喜你！ 我希望在 Google 的第一天就知道的 10 件事 坚持继续学习。 得到这份工作只是一个开始。 ***************************************************************************************************** ***************************************************************************************************** 下面的内容都是可选的。这些是我的推荐，不是 Google 的。 通过学习这些内容，你将会得到更多的有关 CS 的概念，并将为所有的软件工程工作做更好的准备。 ***************************************************************************************************** ***************************************************************************************************** 原文发布时间为：2016年10月12日 本文来自云栖社区合作伙伴掘金，了解相关信息可以关注掘金网站。