0x3f 第42天 黑马点评lua脚本加阻塞队列优化秒杀以及redis数据结构常用场景 + 二分查找二维矩阵
1.搜索二维矩阵
简单的方法，排除法，从右上角往左下角找，时间复杂度m+n
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m,n = len(matrix),len(matrix[0]) i,j = 0,n-1 while i<m and j >=0: if matrix[i][j]==target: return True if matrix[i][j]<target: i+=1 else: j-=1 return False使用二分法的话，其实相当于把二维矩阵拉开变成一维的一个数组，毕竟顺序都排好了，直接二分就完事了，时间复杂度m*n
利用一个技巧：不用变成一维，先求得mid，mid在二维矩阵中的行就是 mid//n
列就是mid%n
然后lowerbound就行
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m,n = len(matrix),len(matrix[0]) left,right = 0,m*n-1 while left<=right: mid = (left+right)//2 x = matrix[mid//n][mid%n] if x == target: return True elif x > target: right = mid -1 else: left = mid + 1 return False2.有效的括号
核心思路，遍历所有的字符串，如果是( [ {，新建一个栈，存入),] }
如果不是 那就判断栈是否为空
解决的就是第一个字符串就是) ] },那肯定无效啊
接着判断是否和栈里的一样，一样就说明可以和之前的匹配上
elif not st or st.pop()!=c:拦截无匹配或者右括号和左括号不匹配的错误
但是没有拦截最终左括号多于右括号的情况
所以最后是return not st 只有st为空，匹配完毕，才说明完事
否则证明左括号还有剩余，那也是错误的
黑马点评
redission看门狗的机制不是基于trylock，而是基于lock或者ttrylock或者各种锁的leasetime，只要没有设定leasetime，自动开启看门狗机制，每隔一段时间就会去续期，解决了即使因为网络延迟错过了续期，后面还有容错机会，避免了业务还没完成，却因为固定的过期时间而释放掉锁，出现的并发错误。
看门狗的实现原理，看门狗的调度给予的是Netty的时间轮处理大量的续期任务，基于pexpire毫秒级的过期时间进行续期
今天学习了如何优化秒杀的业务场景，我们使用lua脚本+阻塞队列，这样可以使原先的串行单行的业务流程，变成异步的流程，在redis里完成用户是否有秒杀的资格的判断，再新开一个线程异步独立的完成用户下单的写操作进数据库。使用lua脚本保证原子性的看库存是否充足并查看用户id判断是否下过单，然后将消费券id和用户id封装给阻塞队列，进行下单写操作
阻塞队列有基于list的，有基于stream的，基于list的就是使用LPUSH和BLPOP模拟阻塞队列，缺点单消费者，信息丢失，基于stream可以使用xread，xread参数有count，id$，block，block=0可以实现永久阻塞，直到来新消息，count可以实现一次取多条信息，起始id$查询历史信息，读取最新消息，缺点 会丢失信息，在引入了消费者组，消费者组的原理是将多个消费者组织成一个组，共享一个消息stream，可以实现漏读，因为每个消息都会分配给至少一个消费者，负载均衡，消息会平均的分配给每个消费者，对于消费失败的消息，全部放入pending列表中，每隔一段时间会重新分配给其他消费者重试，如果还是多次失败，最后进入死信队列，交由人工处理，pending列表加上ACK确认，可以防止消息丢失
redis的数据结构，string可以实现短信登录共享session，基础版的setnx的分布式锁，还可以实现原子性的自增，用于查询网站访问量
list可以实现阻塞队列，简单的朋友圈，用户id为key，朋友圈消息为value
哈希结构可以实现redission的可重入，锁名称为key，线程唯一标识为field，可重入次数为value，购物车，用户id为key，商品id为field，商品数据为value
set可以实现秒杀这个业务场景中，用户下单的用户id存入set，因为set是不可重复的，就可以避免一人多单，set可以共同好友，共同关注，key是用户id，value是朋友id，取交集，还可以抽奖系统，把奖品放入set集合，直接pop或者srandommember
zset可以实现排行榜之类，比如步数排行榜，score是步数，value是用户id，也可以实现浏览记录时间戳是 score，用户id是key，帖子是member