弄懂难缠的BFS算法和相关变种(Python实现)
前言这段时间频繁刷题,leetcode真的好难啊!!每次都他娘的做不出来,除了刷题,最近还在复习各种架构,或者是完成公司的开发。这些占据了我过多时间,所以blog其实一直想写,但是实在腾不出时间,今天在针对性刷leetcode的时候,对BFS/DFS有了一点别的感悟,所以就写一篇博客,作为自己的笔记,在记录的同时,也帮助其他兄弟少走弯路,希望,能够帮到大家。 什么是BFS算法?这些百度谷歌都搜的到,不过这里还是简单说一下吧 首先,BFS的全名,叫做广度优先搜索算法 搜索,顾名思义,是找寻某个东西,所以叫搜索,在写代码的时候,搜索,其实等同遍历,只是这个遍历是有条件的。 相对于BFS,它的条件是什么呢? 举个例子,有个迷宫,有两个点,你要从A 移动到..
更多TypeScript 小技巧:校验 i18n 参数
最近我们的某个项目需要支持多语言了。作为一个从 Entry Task 开始就与多语言打过交道的人,我已经对这里面的套路很是熟悉。但是作为一个工程师,还是想着能不能做的更好一些。我们是怎么做国际化的对于大部分场景来说,国际化都相当简单:有若干语言包,每个语言包中是一堆 Key 和对应的文字模板,模板中可能会有占位符。一个语言包可能长这样:{ "user_setting.list.total_users": "共 {count} 个用户。", "user_setting.edit.confirm": "确认修改?", }代码中的用法可能是这样:const { t } = useTranslation(); return ( <div className="total-users"..
更多树莓派初次使用小记
树莓派官方说明Our mission is to put the power of computing and digital making into the hands of people all over the world. We do this so that more people are able to harness the power of computing and digital technologies for work, to solve problems that matter to them, and to express themselves creatively. 之前只听说过树莓派是个微型电脑,没上手玩过,上次突然想起来买了一个丐版4B,没有买内存卡,过年回家才把家里的内..
更多在树莓派上面搭建Samba服务
在树莓派3b安装系统中我们已经讲了如何在树莓派上面安装操作系统并且如何通过SSH连接到树莓派,在这篇文章中我们将介绍一下如何通过树莓派搭建一个Samba文件共享服务。首先我们先在树莓派上安装Samba服务sudo apt-get updatesudo apt-get install samba之后我们在用户pi的home目录中创建一个用于共享的文件夹,并修改其权限为777mkdir Sharechmod 777 Share随后我们修改Samba的配置文件sudo vi /etc/samba/smb.conf在配置文件的底部添加如下配置[pi] path = /home/pi/Share public = yes writable = yes create mask = 0777 force cr..
更多为什么 OLAP 需要列式存储
为什么这么设计(Why’s THE Design)是一系列关于计算机领域中程序设计决策的文章,我们在这个系列的每一篇文章中都会提出一个具体的问题并从不同的角度讨论这种设计的优缺点、对具体实现造成的影响。如果你有想要了解的问题,可以在文章下面留言。ClickHouse 是最近比较热门的用于在线分析处理的(OLAP)1数据存储,与我们常见的 MySQL、PostgreSQL 等传统的关系型数据库相比,ClickHouse、Hive 和 HBase 等用于在线分析处理(OLAP)场景的数据存储往往都会使用列式存储。图 1 - OLAP 和 OLTP对数据库稍有了解的读者都知道,在线事务处理(Online Transaction Processing、OLTP)2和在线分析处理(Online Analytical..
更多数据中心的电力超售 · OSDI '20
『看看论文』是一系列分析计算机和软件工程领域论文的文章,我们在这个系列的每一篇文章中都会阅读一篇来自 OSDI、SOSP 等顶会中的论文,这里不会事无巨细地介绍所有的细节,而是会筛选论文中的关键内容,如果你对相关的论文非常感兴趣,可以直接点击链接阅读原文。本文要介绍的是 2020 年 OSDI 期刊中的论文 —— Thunderbolt: Throughput-Optimized, Quality-of-Service-Aware Power Capping at Scale1,该论文实现的 Thunderbolt 可以在数据中心实现电力资源的超售,电子资源的超售可以使同一个数据中心运行更多的服务器,从而提高数据中心的整体性能并减少日常的维护开销、降低成本。超售系统的目的都是降低成本并提高利用率,但是也都..
更多Facebook 集群调度管理系统 · OSDI '20
『看看论文』是一系列分析计算机和软件工程领域论文的文章,我们在这个系列的每一篇文章中都会阅读一篇来自 OSDI、SOSP 等顶会中的论文,这里不会事无巨细地介绍所有的细节,而是会筛选论文中的关键内容,如果你对相关的论文非常感兴趣,可以直接点击链接阅读原文。本文要介绍的是 2020 年 OSDI 期刊中的论文 —— Twine: A Unified Cluster Management System for Shared Infrastructure1,该论文实现的 Twine 是 Facebook 过去十年生产环境中的集群管理系统。在该系统出现之前,Facebook 的集群由为业务定制的独立资源池组成,因为这些资源池中的机器可能有独立的版本或者配置,所以无法与其他业务共享。Twine 的出现解决了不同资源..
更多漫谈编程语言
编程语言,一种特殊的语言。前言本文来自于 我在公司内部的一次分享。主要简述了编程语言的阵营,语义的表达形式,不同的思维范式,以及常见规范和执行机制。正文编程语言三种阵营学术派You are a poet and a mathematician. Programming is your poetry语言代表:Haskell Lisp Scala Closure学术阵营认为编程语言是一种思想的表达。这些语言往往是从上向下去设计,从一个纯粹的理想角度对语言建模,它们充斥着各种概念: 函数式,类型系统,模式匹配… 它们痛斥操作系统,编译器带来的各种缺陷,所以在设计时 很少去考虑,甚至有的学术派语言 完全找不到相应概念的映射(Lisp)。虽然它们的结构精妙 概念完美,但从实用角度上 完全不占优势。主要原因有二:如果..
更多纳秒级高性能日志系统 · ATC '18
『看看论文』是一系列分析计算机和软件工程领域论文的文章,我们在这个系列的每一篇文章中都会阅读一篇来自 OSDI、SOSP 等顶会中的论文,这里不会事无巨细地介绍所有的细节,而是会筛选论文中的关键内容,如果你对相关的论文非常感兴趣,可以直接点击链接阅读原文。本文要介绍的是 2018 年 ATC 期刊中的论文 —— NanoLog: A Nanosecond Scale Logging System1,该论文实现的 NanoLog 是高性能的日志系统,与 C++ 社区中的其他日志系统,例如:spdlog、glog 和 Boost Log 相比,它的性能可以高出 1 ~ 2 个数量级,我们在这篇文章中来简要分析 NanoLog 的设计与实现原理。日志是系统可观测性的重要一环,相信很多工程师都有线上出问题临时加日..
更多数据中心的容错时钟对时 · OSDI '20
『看看论文』是一系列分析计算机和软件工程领域论文的文章,我们在这个系列的每一篇文章中都会阅读一篇来自 OSDI、SOSP 等顶会中的论文,这里不会事无巨细地介绍所有的细节,而是会筛选论文中的关键内容,如果你对相关的论文非常感兴趣,可以直接点击链接阅读原文。本文要介绍的是 2020 年 OSDI 期刊中的论文 —— Sundial: Fault-tolerant Clock Synchronization for Datacenters1,该论文实现的 Sundial 可以在数据中心提供高精度的、容错的对时机制。在数据中心发生故障时,它也能够保证不同服务器的绝对时间差小于 ~100ns,比行业内的其他的系统好一到两个数量级,这里的 ~100ns 也被称为时间不确定性上限(Time-uncertainty B..
更多