利用质数随机遍历集合的一种实现

有个随机遍历数据集合的需求,描述如下: ① 从集合的某个随机位置开始遍历 ② 随机获取集合中剩余数据 ③ 重复步骤②,直到遍历完整个集合 当看到这个需求时,不知道你是否会想到什么实现方式? 最近在追溯go底层源码时发现,在调度器从其他 P 中 steal 可用 goroutine 时利用质数的特性,采用了一种特殊算法随机遍历 allp 数组。觉得很是经典,特此记录一下。 例如:通过下标随机遍历数组中的 8 个元素,则最终遍历数组的下标可能是 [0,1,2,3,4,5,6,7] 中的任意一种随机排列。 遍历步骤: ① 计算小于等于 count (这里是8) 的所有质数,得到数组 [1,3...

Golang,算法技巧 2022/05/10 237℃ 0条

指数退避算法设计与原理

重试 在业务开发过程中,经常会听到有人说:xx 问题在失败的情况下,可以进行重试,就能增加成功的概率。 那么,重试是什么? 举个现实中的小例子: 时间: 古时候某个朝代的某一天 事情: 妈妈让小明去叔叔家找叔叔问件事情 问题: 小明去叔叔家后发现家里没人。那么,小明应该怎么办? 方案: ① 在叔叔家门口一直等到他回来 ② 先回自己家,等段时间再去叔叔家,看看他回来没 ③ 留个字条贴到叔叔家门上,等他回来看到后,来找自己 为什么设定为古时候? 是因为设定在当代的话,可能有人会说给叔叔打个电话不就行了。这里仅仅是为了设定某种场景来抛出问题 映射到实际开发中,分别对应: ① 阻塞等待 ② ...

Golang,编程原理 2022/01/29 746℃ 0条

Golang中Fisher–Yates shuffle算法的使用

Golang中rand.Shuffle 从go1.10开始,math包新增了rand.Shuffle方法。 data := []int{1,2,3,4,5,6,7,8} rand.Seed(time.Now().UnixNano()) rand.Shuffle(len(data), func(i, j int) { data[i], data[j] = data[j], data[i] }) fmt.Println(data) // [1 2 6 4 5 3 7 8] or other,每次执行结果都不一样 通过,该方法可以实现随机打散功能(一般用于切片、数组)。 rand....

Golang,算法技巧 2021/11/19 462℃ 0条

经典算法:无序数组寻找第K大数值

1. 寻找第K大数值 题意 有一个无序整数数组,请你根据排序思路,找出数组中第K大的数。 给定一个整数数组a, 请返回第K (1<=K<=n) 大的数(包括重复的元素,不用去重),保证答案存在。 示例 输入 [3,2,1,5,6,4] , 2 返回值 5 2. 常规思路 先对无序数组进行排序,然后对有序数组进行查找。 至于选择什么排序算法,有待确定。 先看一下,各种排序算法的复杂度以及稳定性。 看完上面比较之后,可能你心中已经有了自己的答案。 3. 解题思路 常规思路需要两大步: 先整体排序 在有序中查找目标值 那么,针对这道题,我们能不能在排序的过程中就确定目标值呢?...

算法技巧 2021/11/18 397℃ 0条

经典算法:大数乘法的分析与实现

1. 大数乘法 在算法中有这么一道经典题:大数乘法。 题意 以字符串的形式读入两个数字,编写一个函数计算它们的乘积,以字符串形式返回。(字符串长度不大于10000,保证字符串仅由'0'~'9'这10种字符组成) 示例 输入:"456","123" 返回值:"56088" 说明:456*123=56088 2. 乘法运算规则 按照我们从小学习的乘法运算规则可知:两个数相乘时,可以用其中一个数的每一位与另一个数相乘,然后把相乘结果相加即可得出运算结果。大致如下图所示: 但是,如果把这个运算规则映射到代码中,你会怎么写呢? 从现在开始,给你20分钟的时间写出一个实现算法(20分钟是字节跳动在...

算法技巧 2021/11/16 388℃ 0条