标签: 算法

2022
技术

Go二分查找sort.Search

之前对Go sort包的印象一直是只能做排序，毕竟包名就叫sort嘛。后来在一次刷leetcode的时候，发现官方题解做二分搜索的时候用了sort包里的Search函数，惊讶sort包还封装了二分查找功能。于是看了下sort.Search的源码，发现源码其实也写的很简单，就是一个普通的二分： 12345678910111213141516func Search(n int, f func(int)

2020
技术

记一道动态规划+数学期望的算法题

最近碰到一个算法题，开始觉得很简单，后来觉得有点难，后来做了做发现其实没有那么难，感觉有点意思。在这里分享一下这道题和解题思路。这道题的题目如下： 一个n*m的网格，每个格子上有三个参数pD,pR,pS。pD表示下一步走到下方格子的概率，pR表示下一步走到右方格子的概率，pS表示下一步仍然在原地的概率。0<= pD, pR, pS <=1，pD+pR+pS = 1。从左上角格子到右下

技术

如何设计一个分布式限流器（distributed rate limiter）

Rate Limiter限流器（rate limiter）是一种在实际工程中广泛应用的组件，其主要作用就是限制上游服务的请求量。比如一个公司有两个服务：服务A和服务B，服务A需要经常请求服务B，那么服务B为了保证自己不被来自A的异常高的请求打挂（即是现在分布式系统时代做自动扩容很快，但对于TPS较大的服务来说这些异常高的请求量仍然是有显著影响的），就会和服务A协商，定一个服务A的TPS阈值，设置限

2019
技术

初探Uber H3原理

2018年初，Uber正式开源了他们自己的一种空间索引算法H3（H3项目地址：h3）。最近偶然得知了这个算法，于是Google了一下，发现Uber还是比较良心地在其官网上给出了很多算法原理的讲解：简略版：H3: Uber’s Hexagonal Hierarchical Spatial Index详细版：H3 introdutction。如果英文还不错的话，建议直接看官方的介绍，我这里只是大致翻译

技术

轨迹压缩算法(Polyline encoding algorithm)探究

前言文中的代码表达采用Java，如果不想看原理，可以直接跳到博客末尾，有我写的一个Java版的demo一般来说，轨迹是由若干个轨迹点组成的数组来表达的，每个轨迹点可以表达为 $p = (x, y, t, A)$。其中 $x, y$ 是其空间坐标（一般来说，空间坐标用经纬度表示，即$x$一般对应经度(longitude)，$y$一般对应纬度(latitude)），$t$是记录这个轨迹点的时间戳(Ti

技术

Google s2 lib研究之空间覆盖

本文适合于对Google s2有一定了解或对空间索引有一定了解的读者。 空间索引常用的方法是空间填充曲线，比如Hilbert, Geohash等，被用于许多查询场景中。Google也推出了自己的空间索引——Google s2，这个项目是一个开源项目，有兴趣的可以直接看Google s2 java版源码和官方文档。对Google s2的介绍可以看Google’s S2, geometry on th