雪花算法的原始版本是scala版,用于生成分布式ID(纯数字,时间顺序),订单编号等。
### 算法描述
- 最高位是符号位,始终为0,不可用。
- 41位的时间序列,精确到毫秒级,41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。
- 10位的机器标识,10位的长度最多支持部署1024个节点。
- 12位的计数序列号,序列号即一系列的自增id,可以支持同一节点同一毫秒生成多个ID序号,12位的计数序列号支持每个节点每毫秒产生4096个ID序号。
```
package main
import (
"errors"
"fmt"
"sync"
"time"
)
const (
wo ......
### 定义
将用户的各种纬度的数据,做成向量。在向量空间内计算,两个向量的相似度,实现近似比较和分类。
### 应用场景
推荐系统
### 两种推荐方式
基于用户相似度做推荐
基于内容相似度做推荐
### 算法
欧几里得距离:d=根号下(x1-y1)平方+(x2-y2)平方
### 应用
基于用户相似度正推
基于内容相似度反推 ......
###算法描述
trie树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起。 时间复杂度:构建O(n),查询O(k)
### 算法步骤
根节点/ 什么都不表示
做一个字典比如a-z 字母表
没一个节点包含这26个字母的字典表,每个位置保存下个节点的指针。
### 算法分析
##### 缺点:
trie树比较消耗内存:因为他没一层都保存一个字典表,就算这层的节点只有一个也要有一组表
使用的是指针类型,内存不连续对存储不友好,性能打折扣
##### 优点:
查询效率比较高,对于一些范围较小的或者内存不敏感的应用可以使用
特别适用自动补全类应用
```
package main
import "fmt"
type TrieNode str ......
### 定义
在一组数据中,按照一定规则对数据创建层级索引,通过自上至下的索引查询查找数据位置
### 特点
二分查找针对数组,为了实现不使用针对数组二分查找,产生了跳跃表
跳跃表使用链表
有多级索引
### 时间复杂度
修改(增删改)时间复杂度 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 ......
### 链表分类
- 单链表
- 双链表
- 环链表
### 时间复杂度
- 修改(增删改)时间复杂度 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, ......