Mark's Blog

算法专栏 (五)：链表（下）Go 语言实现链表的技巧链表的定义是不是很好去理解？但写起来很费劲。这篇文章就结合Go语言和你探讨一下如何写好链表代码，最后用一道经典的链表反转代码来收尾。 写好链表代码需要一些方法和技巧。我根据自己的学习经历和工作经验，总结了几个写链表代码技巧。 技巧一：理解指针或引用的含义事实上，看懂链表的结构并不是很难，但是一旦把它和指针混在一起，就很容易让人摸不着头脑。所以，要想写对链表代码，首先就要理解好指针。 我们知道，有些语言有“指针”的概念，比如 Go 语言；有些语言没有指针，取而代之的是“引用”，比如 Java、Python。不管是“指针”还是“引用”，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。 接下来，我会拿 Go 语言中的“指针”来讲解，如果你用的是 Java 或者其他没有指针的语言也没关系，你把它理解成“引用”就可以了。 实际上，对于指针的理解，你只需要记住下面这句话就可以了： 将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。 这句话听 ...

算法专栏 (四)：链表（上）链表有啥用？为啥要学它，数组不够吗？首先要提起兴趣就要知道链表的应用场景，LRU 缓存淘汰算法就是经典的链表（Linked list）应用场景。 缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。 如何用链表来实现LRU我放在最后。 链表结构相比数组，链表是一种稍微复杂一点的数据结构。对于初学者来说，掌握起来也要比数组稍难一些。这两个非常基础、非常常用的数据结构，我们常常将会放到一块儿来比较。所以我们先来看，这两者有什么区别。 我们先从底层的存储结构上来看一看。 为了直观地对比，我画了一张图。从图中我们看到，数组需要一块连续的内存空间来存储，对内存的要求比较高。 ...

算法专栏 (三)：数组在每一种编程语言中，基本都会有数组这种数据类型。不过，它不仅仅是一种编程语言中的数据类型，还是一种最基础的数据结构。尽管数组看起来非常基础、简单，但是我估计很多人都并没有理解这个基础数据结构的精髓。 定义及如何实现随机访问？数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 这个定义里有几个关键词： 第一是线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。 而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。 第二个是连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。 说到数据的访问，那你知道数组是如何实现根据下标随机访问数组元素的吗？ 我们拿一个长 ...

算法专栏 (二)：算法复杂度 数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。 为什么需要复杂度分析？你可能会有些疑惑，我把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确吗？ 首先，我可以肯定地说，你这种评估算法执行效率的方法是正确的。很多数据结构和算法书籍还给这种方法起了一个名字，叫事后统计法。但是，这种统计方法有非常大的局限性。 测试结果非常依赖测试环境测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样一段代码，分别用 Intel Core i9 处理器和 Intel Core i3 处理器来运行，不用说，i9 处理器要比 i3 处理器执行的速度快很多。还有，比如原本在这台机器上 a 代码执行的速度比 b 代码要快，等我们换到另一台机器上时，可能会有截然相反的结果。 测试结果受数据规模的影响很大后面我们会讲排序算法，我们先拿它举个例子。对同一个排序算法，待排序数据的有序度不 ...

算法专栏 (一)：构建自己的算法体系 为什么要写这个算法专栏的文章呢？ 因为自己一直在断断续续的学习算法但发现一旦在很忙时放下了一段时间，很多知识点就会遗忘，我本来天真的以为如果完全理解就会完全掌握甚至融汇贯通，现在看来是自己 too young 了。 所有的知识都需要构建自己的体系这样才能记得牢固。所以这个专栏就是通过一些市面上我认为不错的算法资料进行自己的算法体系构建及知识记录。这个专栏是基于 极客时间中 王争老师 的《算法与数据结构之美》写下的，其中我把代码的用例都换成了Go语言，以及添加了Go语言对应数据机构算法的一些说明，还有Go语言对应算法的习题讲解 体系什么是体系体系就是在规定范围内，不同单位个体依照某种规律或秩序联系在一起的整体，是不同却又在某范围内的独立个体因为他们之间的联系而组成的一个系统。 为什么要建立体系其实从小到大我们总会发现有些人就是神一般的存在着，让我们感觉无法超越，他们知识广博且又深入。以前我觉得是天赋，但在我认为不是。他们是有一套建立知识体系的学习方法。当你建立起了某个知识的自己的体系的时候这个知识就很难忘记了。为什么？因为类型相似的知识之间建立起了 ...

如何处理一组并发任务 这片文章是承接上一篇 聊聊 ErrorGroup 的用法和拓展 ErrorGroup 官方包的创建初衷就是给我们提供一个正确的处理一组任务的并发方式，经过拓展，我们还可以控制最大并发任务量，之后进一步拓展 Group 的用法更加多样，适用业务也更加多元，所以我这片文章题目就扩大到了处理一组并发任务。本文将从多个 Group 的多元拓展包入手，对并发处理任务的要点及实际处理方式进行总结和提炼，力求看后可以掌握处理并发任务的核心要点。 Facebook 拓展：facebookgo/errgroup这个 face book 的拓展包实际是对 waitgroup 的拓展，这个包不但可以用来记录并发控制并发协程的生命周期，还可以对所有并发任务的错误进行处理及记录。 Group 结构12345678// Group is similar to a sync.WaitGroup, but allows for collecting errors.// The collected errors are never reset, so unlike a sync.WaitGrou ...

聊聊 ErrorGroup 的用法和拓展 在写业务代码时经常碰到需要将一个通用的父任务拆成几个小任务并发执行的场景。此时需要将一个大的任务拆成几个小任务并发执行，来提高程序效率。 那我是怎么做的呢，我会在一个函数中启动我需要的协程来并发完成任务，每个协程构建一个管道进行结果传输，最后起一个for select 收集每个不同的管道任务。使用wait group来控制每个协程生命周期。 其实类似的业务场景已经有很多大神进行了抽象并形成了简单易用的代码框架，本文将以 go 官方的 ErrGroup 库为切入点对各路大佬的拓展库进行分析。 为什么要写这个文章呢，因为我在看这些库时发现，在这个基础上大佬们约拓展越丰富，把这些代码看下来感觉自己对业务场景的抽象能力以及处理能力增加了很多，但这些必须总结下来！因为一定会忘记，尤其是长时间不用，一旦出现相似的场景，那么很难直接回忆起来，所以提笔写了这篇文章。有各路大佬保驾护航那一定能快速形成没有坑的优秀代码。 官方 ErrorGroup 介绍ErrGroup 是 Go 官方提供的一个同步扩展库。接下来，我来给你介绍一下 ErrGroup 的基本用法和 ...

用 go 处理1分钟百万请求 这是 Marcio Castilho 在 MBAM 时产生的一个需求，我在读后发现他们在处理百万请求时设计的并发池是非常巧妙的，在这里把这篇文章和代码做一个解析，原文在这里。 这篇文章不是单纯的翻译，主要是对他们在处理问题时不同版本的代码进行一个分析，原文中有很多作者的心路历程，大家感兴趣的可以去看原文。 背景Marcio Castilho 在处理他们的匿名数据统计和分析系统时遇到一个需求：我们的目标是能够处理来自数百万个端点的大量 POST 请求。Web 处理程序将接收一个 JSON 文档，该文档可能包含需要写入 Amazon S3 的许多有效负载的集合，以便我们的 map-reduce 系统稍后对这些数据进行操作。S3就是亚马逊的一个对象存储服务，其实他们的主要业务逻辑很简单，难就难在控制并发。最开始他们按照自己以往的经验想要建立一个worker层架构，使用： Sidekiq Resque DelayedJob Elasticbeanstalk Worker Tier RabbitMQ and so on… 建立两个集群，一个是前端集群进行请求消 ...

go语言设计模式（Map-Reduce）我理解的设计模式说到设计模式，多数人想到的都是 1995 年 GoF 提出的 23 种设计模式 他通常被定义为： 设计模式（Design Pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结，使用设计模式是为了可重用代码、让代码更容易被他人理解并且保证代码可靠性。 从定义上看，设计模式其实是一种经验的总结，是针对特定问题的简洁而优雅的解决方案。我认为只要是优雅的，简洁的，可进行多业务场景问题解决的，易于理解使用的一套行之有效的代码编写模式都可以称为设计模式或是编程模式。 既然是经验总结的编程模式，那么学习它的最直接的好处就在于可以站在巨人的肩膀上解决软件开发过程中的一些特定问题。 我写编程模式这个模块也是为了将好的模式收集积累，在遇到相似的问题场景，可以拿来主义。哈哈哈，听起来有些不动脑子的愚蠢。但你想想我们这个世界不就是这样在前人的肩膀上一步步的发展进步的。你如果做什么都要自己思考，总结，设计都要从0到1这本身就不太现实，即使是你做到了，那也一定不够优雅或是错误百出。 设计模式这个大标签下，我将把我阅读他人总结 ...

go 语言中的 range 真的影响性能吗 是不是有人告诉你，range 每次循环都进行一次值拷贝，非常影响性能。今天来揭秘 range 到底有多”坑“ range 的简单介绍Go 语言中，range 可以用来很方便地遍历数组(array)、切片(slice)、字典(map)和信道(chan) array/slice12345words := []string{"Go", "语言", “很”, "棒"}for i, s := range words { words = append(words, "test") fmt.Println(i, s)} 输出结果如下： 12340 Go1 语言2 很3 棒 变量 words 在循环开始前，仅会计算一次，如果在循环中修改切片的长度不会改变本次循环的次数。 迭代过程中，每次迭代的下标和值被赋值给变量 i 和 s，第二个参数 s 是可选的。 针对 nil 切片，迭代次数为 0。 range 还有另一种只遍历 ...