张晗的个人博客

技术的价值是业务

描述

  • 只能在末尾插入数据;
  • 只能在开头读取数据;
  • 只能移除开头的数据;

总之,栈是一种先进先出的数据结构。

补充

队列可以保证请求的顺序,因此可以用来处理异步请求。此外,也能模拟有序事件的处理。

示例代码

golang

java

描述

  • 只能在末尾插入数据;
  • 只能在末尾读取数据;
  • 只能移除末尾的数据;

总之,栈是一种先进后出的数据结构。

补充

栈用于递归,递归是其他高级算法的基础。

示例代码

golang

java

Redis 地理坐标可以存储经纬度格式的地理坐标,并对这些坐标执行距离计算、范围查找等操作。

基本命令

GEOADD

将一个或多个地理坐标添加或更新到有序集合中,返回插入元素个数。

1
2
3
4
5
6
7
8
9
-- 返回 1.添加 qingyuan 到 Guangdong-cities 中
GEOADD Guangdong-cities 113.2099647 23.593675 Qingyuan
-- 返回 4.添加 guangzhou fuoshan dongguan 和 shenzhen 到 Guangdong-cities 中
GEOADD Guangdong-cities 113.2278442 23.1255978 Guangzhou 113.106308 23.0088312 Foshan 113.7943267 22.9761989 Dongguan 114.0538788 22.5551603 Shenzhen

-- 返回 1.添加 Zhongshan 到 Guangdong-cities 中
GEOADD Guangdong-cities 113 22 Zhongshan
-- 返回 0. 由于 Guangdong-cities 已有 Zhongshan 所以更新 Zhongshan 信息
GEOADD Guangdong-cities 113.4060288 22.5111574 Zhongshan

时间复杂度:O(logn * m). n 为集合中已有元素的个数,m 是需要添加地理坐标的个数。

GEOPOS

获取给定位置的坐标,包含经度和纬度,集合中不存在返回 nil。

1
2
3
4
5
6
-- 113.40603142976761 22.511156445825442
GEOPOS Guangdong-cities Zhongshan
-- 按顺序返回
-- 114.0538814663887 22.555159205151575 Shenzhen
-- 113.22784155607224 23.125598202060807 Guangzhou
GEOPOS Guangdong-cities Shenzhen Guangzhou

时间复杂度:O(logn * m). n 为集合中已有元素的个数,m 是需要查询地理坐标的个数。

GEODIST

计算两个位置之间的直线距离,单位默认是米,集合中元素不存在返回 nil。

1
2
3
4
5
6
7
8
9
10
11
12
-- 127364.5547 米
GEODIST Guangdong-cities Zhongshan Guangzhou

-- 使用指定单位。 M KM MI FT
-- 127364.5547 米
GEODIST Guangdong-cities Zhongshan Guangzhou M
-- 127.3646 千米
GEODIST Guangdong-cities Zhongshan Guangzhou KM
-- 79.1409 英里
GEODIST Guangdong-cities Zhongshan Guangzhou MI
-- 417862.7122 英尺
GEODIST Guangdong-cities Zhongshan Guangzhou FT

时间复杂度:O(logn)

GEORADIUS

返回以经纬度为中心,指定半径内的地理坐标。

默认情况下,返回结果是无序的,ASC 或 DESC 可以使结果有序返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- 以 113.4060288 22.5111574 为中心,查询半径为 200km 的地理元素
GEORADIUS Guangdong-cities 113.4060288 22.5111574 200 KM

-- 以 113.4060288 22.5111574 为中心,查询半径为 200mi 的地理元素
GEORADIUS Guangdong-cities 113.4060288 22.5111574 200 MI

-- 以 113.4060288 22.5111574 为中心,查询半径为 200mi 的地理元素,同时返回距离
GEORADIUS Guangdong-cities 113.4060288 22.5111574 200 KM WITHDIST
-- 以 113.4060288 22.5111574 为中心,查询半径为 200mi 的地理元素,同时返回坐标
GEORADIUS Guangdong-cities 113.4060288 22.5111574 200 KM WITHCOORD
-- 以 113.4060288 22.5111574 为中心,查询半径为 200mi 的地理元素,同时返回 GEOHASH(数字 HASH)
GEORADIUS Guangdong-cities 113.4060288 22.5111574 200 KM WITHHASH
-- 以 113.4060288 22.5111574 为中心,查询半径为 200mi 的地理元素,同时升序返回距离
GEORADIUS Guangdong-cities 113.4060288 22.5111574 200 KM WITHDIST ASC
-- 以 113.4060288 22.5111574 为中心,查询半径为 200mi 的地理元素,返回 2 个的同时升序返回距离
GEORADIUS Guangdong-cities 113.4060288 22.5111574 200 KM WITHDIST ASC COUNT 2

时间复杂度:O(n)

GEORADIUSBYMEMBER

同 GEORADIUS,只是中心为地理坐标中的一个元素。

1
2
-- 以 Guangzhou 为中心,查询半径为 150km 的地理元素,返回 2 个的同时升序返回距离
GEORADIUSBYMEMBER Guangdong-cities Guangzhou 150 KM WITHDIST ASC COUNT 2

时间复杂度:O(n)

GEOHASH

传入一个或多个位置,返回这些位置的字符串 GEOHASH 值。

不存在则返回 nil。

1
2
3
4
5
-- ws0w0phgp70
GEOHASH Guangdong-cities Qingyuan

-- ws0w0phgp70 ws0e89curg0
GEOHASH Guangdong-cities Qingyuan Guangzhou

时间复杂度:O(n)

总结

  • Redis的GEO特性允许用户将经纬度格式的地理位置存储到Redis中,并对这些位置执行距离计算、范围查找等操作;
  • GEORADIUSBYMEMBER 和 GEORADIUS 命令的作用一样,但前者使用位置,后者使用经纬度;
  • Geohash 将用户给经度和纬度转换成单个Geohash值;
  • 可以使用有序集合来操作地理坐标;

模式描述

享元模式通过共享多个对象所共有的相同状态或是不可变对象,用来复用对象、节省内存。

优点

1.

缺点

1.

应用场景

  1. 仅在程序必须支持大量对象且没有足够的内存容量时使用享元模式;
阅读全文 »

描述

将一个元素插入到已经有序的列表中,从而完成排序。

补充

对于平均情况(数组里的值随机分布),选择排序、冒泡排序和插入排序性能相近。

如果数组是大致有序的,那么插入排序比较好。如果是大致逆序,则选择排序更快。如果你无法确定数据是什么样,插入排序和选择排序都可以。

时间复杂度

O(n^2)

示例代码

golang

java

0%