当前位置: 首页 > news >正文

互联网工具型网站网络销售挣钱吗

互联网工具型网站,网络销售挣钱吗,淘宝客网站如何做SEO,十堰吧前言: 在上一篇文章GeoHash——滴滴打车如何找出方圆一千米内的乘客主要介绍了GeoHash的应用是如何的,本篇文章我想要带大家探索一下使用什么样的数据结构去存储这些Base32编码的经纬度能够节省内存并且提高查询的效率。 前缀树、跳表介绍: …

前言:

在上一篇文章GeoHash——滴滴打车如何找出方圆一千米内的乘客主要介绍了GeoHash的应用是如何的,本篇文章我想要带大家探索一下使用什么样的数据结构去存储这些Base32编码的经纬度能够节省内存并且提高查询的效率。


前缀树、跳表介绍:

什么是前缀树:

针对于没有接触过前缀树或者不熟悉前缀树的同学,我先简单介绍一下其基本原理。

前缀树 其主要就是分为两个部分 前缀 + 树

树大家肯定不陌生,比如二叉搜索树这样的数据结构就可以将查询效率降低至O(logn),
而前缀树不同之处在于它的节点的核心数据结构是这样的:

`

type Trie struct {child [26]*TrieisEnd bool
}

首先 child [26]*Trie主要作用就是存放子节点的,而isEnd作用就是去判断当前节点是否存在有一个完整的元素的结尾。光说原理比较枯燥,举例图示说明:

不知道大家是否了解过web后端路由是有哪些存储方式的,在golang语言中gin框架就是基于前缀树去存储路由的,比如:

假设我们要使用前缀树去存储
/ /ag /c /e这四个路由

那么存储过程就是应该这样的

image.png

每一个节点是一个Trie数据结构的节点,每个数组节点对应的是需要存储数据的单个字符,这样做的好处就是当我们需要存放的数据如果有相同前缀那么就不需要重复存储,节省空间,例如app、approach。那么app就只需要存储一次即可。

为了更方便理解,这里放一下插入元素、搜寻元素是否存在的代码:

func (this *Trie) Insert(word string)  {cur:=thisfor i:=0;i<len(word);i++{idx:=word[i]-'a'if cur.child[idx]==nil{cur.child[idx]=&Trie{}}cur=cur.child[idx]}cur.isEnd=true
}func (this *Trie) Search(word string) bool {cur:=thisfor i:=0;i<len(word);i++{if cur.child[word[i]-'a']==nil{return false}cur=cur.child[word[i]-'a']}return cur.isEnd
}

而GeoHash得到的字符串其实正好满足大量相同前缀的特性,因此使用前缀树去存储GeoHash是相对比较合适的。


对于前缀树的补充

上述讲的其实是最基础版的前缀树,我们还可以对此进行一些魔改来优化存储与查询。

比如在Go/gin框架中的路由存储就是用的压缩前缀树

首先该树中当一个节点它仅有一个子节点时就会对树的结构进行一个压缩

image.png

/egg这个节点,e下子节点只有g,g下子节点就只有g,因此它们都会被合并到一起

其次句柄数量更多的 child node 摆放在 children 数组更靠前的位置.

如egg句柄数量更多,那么它就将会更靠前,以便于更早被遍历到


跳表原理简单介绍

其实用上述数据结构已经非常合适了,但是我为什么还要介绍一下SkipList这种数据结构呢,因为Redis中GEO 本身并没有设计新的底层数据结构,而是直接使用了 Sorted Set 集合类型。而Sorted Set底层其实就是跳表,那么就简单介绍一下。


链表在查找元素的时候,因为需要逐一查找,所以查询效率非常低,时间复杂度是O(N),于是就出现了跳表。跳表是在链表基础上改进过来的,实现了一种「多层」的有序链表,这样的好处是能快读定位数据。

如图所示

image.png

  • L0 层级共有 5 个节点,分别是节点1、2、3、4、5;
  • L1 层级共有 3 个节点,分别是节点 2、3、5;
  • L2 层级只有 1 个节点,也就是节点 3 。

如果我们要在链表中查找节点 4 这个元素,只能从头开始遍历链表,需要查找 4 次,而使用了跳表后,只需要查找 2 次就能定位到节点 4,因为可以在头节点直接从 L2 层级跳到节点 3,然后再往前遍历找到节点 4。

可以看到,这个查找过程就是在多个层级上跳来跳去,最后定位到元素。当数据量很大时,跳表的查找复杂度就是 O(logN)


想要自己简单动手去实现一下跳表可以刷一下对应的题(力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台)

这里贴一下自己写的跳表代码

type Node struct {Val  intNext *NodeDown *Node
}type Skiplist struct {head *Node
}func Constructor() Skiplist {return Skiplist{head:&Node{Val:-1,Next:nil,Down:nil} }
}func (this *Skiplist) Search(target int) bool {curr:=this.headfor curr!=nil{for curr.Next!=nil&&curr.Next.Val<target{curr=curr.Next}if curr.Next != nil&&curr.Next.Val==target{return true}curr=curr.Down}return false
}func (this *Skiplist) Add(num int) {curr:=this.headisInsert:=truedown:=&Node{Val:-1,Next:nil,Down:nil}deque:=[]*Node{}for curr!=nil{for curr.Next!=nil&&curr.Next.Val<num{curr=curr.Next}deque=append(deque,curr)curr=curr.Down}for len(deque)>0&&isInsert{curr=deque[len(deque)-1]deque=deque[:len(deque)-1]if down.Val==-1{curr.Next=&Node{Val:num,Next:curr.Next,Down:nil}}else{curr.Next=&Node{Val:num,Next:curr.Next,Down:down}}down=curr.NextisInsert=rand.Float64()>0.5}if isInsert{this.head=&Node{Val:-1,Next:nil,Down:this.head}}
}func (this *Skiplist) Erase(num int) bool {curr, isFound := this.head, falsefor curr != nil {for curr.Next != nil && curr.Next.Val < num {curr = curr.Next}if curr.Next != nil && curr.Next.Val == num {isFound = truecurr.Next = curr.Next.Next}curr = curr.Down}return isFound}
http://www.hrbkazy.com/news/7963.html

相关文章:

  • html导航网站源码免费一键生成个人网站
  • 网上那个网站做席子批发免费seo网站
  • 自己怎么做淘宝客网站吗百度竞价sem入门教程
  • 阿里巴巴的网站建设与维护福州百度推广排名
  • 深圳市建设集团有限公司招聘sem和seo的区别
  • 营销类网站建设抖音排名优化
  • 昆明网站设计制造关键字排名优化工具
  • 一个产品有两个品牌怎么做网站聊城seo整站优化报价
  • 做a免费网站网上推广产品怎么做
  • 汕头中小企业网站制作网上接单平台
  • 如何做美女图片网站seo工作是什么意思
  • 福州外文网站建设产品软文模板
  • 重庆旅游网站建设seo服务商排名
  • 中国容桂营销网站建设百度搜题
  • 酒业公司网站模板第一接单网app地推和拉新
  • 网站建设合作合同模板下载线上销售平台有哪些
  • seo整站优化什么价格百度人工服务24小时
  • 广告片精彩花絮广州seo优化
  • 网站维护与优化教程单页网站制作教程
  • 专用车网站建设价格购物网站推广方案
  • 单页网站怎么优化厦门网络推广外包多少钱
  • 旅游网站首页设计模板腾讯广告
  • 国内网站建设发展系统设置友情链接有什么作用
  • 个人网站数据库怎么做天津提升专业关键词排名
  • 新开的网站怎么做推广郑州网站seo外包公司
  • 网站建设选超速云建站线上卖护肤品营销方法
  • 网站建设与管理课程设计论文宁德市市长
  • 做网站work什网址提交百度收录
  • 苏州做网站的公司哪家好注册城乡规划师报考条件
  • 公司网站宣传自己做的灯展搜索引擎有哪些类型