Go-算法-雪花算法

雪花算法的原始版本是scala版,用于生成分布式ID(纯数字,时间顺序),订单编号等。 ### 算法描述 - 最高位是符号位,始终为0,不可用。 - 41位的时间序列,精确到毫秒级,41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。 - 10位的机器标识,10位的长度最多支持部署1024个节点。 - 12位的计数序列号,序列号即一系列的自增id,可以支持同一节点同一毫秒生成多个ID序号,12位的计数序列号支持每个节点每毫秒产生4096个ID序号。 ``` package main import ( "errors" "fmt" "sync" "time" ) const ( wo ......

Go-算法-向量空间

### 定义 将用户的各种纬度的数据,做成向量。在向量空间内计算,两个向量的相似度,实现近似比较和分类。 ### 应用场景 推荐系统 ### 两种推荐方式 基于用户相似度做推荐 基于内容相似度做推荐 ### 算法 欧几里得距离:d=根号下(x1-y1)平方+(x2-y2)平方 ### 应用 基于用户相似度正推 基于内容相似度反推 ......

Go-算法-字典树

###算法描述 trie树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起。 时间复杂度:构建O(n),查询O(k) ### 算法步骤 根节点/ 什么都不表示 做一个字典比如a-z 字母表 没一个节点包含这26个字母的字典表,每个位置保存下个节点的指针。 ### 算法分析 ##### 缺点: trie树比较消耗内存:因为他没一层都保存一个字典表,就算这层的节点只有一个也要有一组表 使用的是指针类型,内存不连续对存储不友好,性能打折扣 ##### 优点: 查询效率比较高,对于一些范围较小的或者内存不敏感的应用可以使用 特别适用自动补全类应用 ``` package main import "fmt" type TrieNode str ......

Go-算法-跳跃表

### 定义 在一组数据中,按照一定规则对数据创建层级索引,通过自上至下的索引查询查找数据位置 ### 特点 二分查找针对数组,为了实现不使用针对数组二分查找,产生了跳跃表 跳跃表使用链表 有多级索引 ### 时间复杂度 修改(增删改)时间复杂度 O(lgn) 查询时间复杂度O(lgn) ### 空间复杂度 空间复杂度根据索引生成方法有关,例子中的大概是O(n) n/2+n/4+....+4+2 等比求和 Sn=(a1-anq)/1-q O(n-2) 约等于 O(n) ``` package skipList import "fmt" type Node struct { Data int NextPoint *Node ......

Go-算法-链表

### 链表分类 - 单链表 - 双链表 - 环链表 ### 时间复杂度 - 修改(增删改)时间复杂度 O(1) - 查询时间复杂度O(n) ``` package linkedList import "fmt" type Node struct { Data int NextPoint *Node PrePoint *Node } type LinkedList struct { head *Node current *Node tail *Node } func CreatLinkedList() { data := []int{1, 21, ......