xindoo_社区达人页

2023年11月

• 11.01 15:53:01
  发表了文章 2023-11-01 15:53:01

  布隆过滤器(BloomFilter)原理 实现和性能测试

  可以看出，在同等数据量的情况下，BloomFilter的存储空间和ln(fpp)呈反比，所以增长速率其实不算快，即便误判率减少9个量级，其存储空间也只是增加了10倍。
• 11.01 15:49:41
  发表了文章 2023-11-01 15:49:41

  用正则表达式匹配3的任意倍数

  正则表达式能匹配3的任意倍数?(注意是任意倍数) ，我曾经也很震惊，但确实可以。我5年多前练习正则表达式，在Regex Golf这个正则表达式测试网站上发现了这个题，当时完全没有任何头绪，于是我在知乎提问正则表达式如何匹配 3 的倍数 ，但是得到了好多知乎大佬的关注，也上了当天的热榜。 排名第一的答主已经给出了答案和思路，但这么多年来我一直都没看懂，最近学习编译原理，看到正则表达式和DFA，于是仔细研究了一下这个问题，并将问题扩展至匹配N的倍数，最后给出通用解法和代码。
• 11.01 15:38:34
  发表了文章 2023-11-01 15:38:34

  一文告诉你CPU分支预测对性能影响有多大

  CPU分支预测本身是为了提升流水线下避免流水线等待的手段，其实本质上是利用了局部性原理，因为局部性的存在，大多数情况下这个技术本身给性能带来的是正向的(要不然它今天也不会存在了)，所以我们大多数情况下都不需要关注它的存在，还是放心大胆的写代码吧，不要因为我们这篇博客就把所有的if改成?:三目运算，可能对代码可读性的影响远大于性能提升的收益。再次强调下，我今天只是构造了一个极端的数据来验证其性能差异，因为局部性的存在大多数情况下分支预测都是对的。
• 11.01 14:15:42
  发表了文章 2023-11-01 14:15:42

  Java自制简易线程池(不依赖concurrent包)

  实时上如上文中好几次提到，java.util.concurrent包里已经帮大家实现了一个很健壮、功能强大的线程池，大家不必再去造轮子了，使用不同的BlockingQueue就可以实现不同功能的线程池。举个栗子，比如使用DelayedWorkQueue就可以实现可以定期执行的线程池了。 甚至Executors为大家封装了更为简易的线程池创建接口，但是《Alibaba Java开发手册》强制不允许使用 Executors 去创建线程池，而是通过 ThreadPoolExecutor 的方式，这样的处理方式让写的同学更加明确线程池的运行规则，规避资源耗尽的风险。
• 11.01 14:13:16
  发表了文章 2023-11-01 14:13:16

  Alfred上可提高工作效率的Workflow推荐（2）

  common searh封装了有些快速搜索的快捷方式，比如通过gh关键词快速搜索github上的内容。当然这个也可以通过alfred的web search也可以快速设置，这个workflow只是替你封装好了知乎、淘宝、掘金、github的快速搜索。
• 11.01 14:10:49
  发表了文章 2023-11-01 14:10:49

  Alfred上可提高工作效率的Workflow推荐（1）

  后来我跳槽后自己买了Macbook pro，在努力把笔记本打造成高效开发工具时，又重新发现了这个app，又毫不犹豫的购买了Powerpack，结合一些workflow，很多繁琐的工作变得非常简单，比如之前百度搜索一个东西，需要打开浏览器，然后打开百度，再输入要搜的词，再点搜索一套组合拳下来几十秒就过去了，有了Alfred 快捷键+触发词+搜索词+回车 几秒钟搞定。下图是我最近一月来每天的Alfred的使用频率，工作日平均每天有30+次的使用率。
• 11.01 14:06:10
  发表了文章 2023-11-01 14:06:10

  局部性原理——各类优化的基石（2）

  CDN的全称是Content Delivery Network，即内容分发网络(图片来自百度百科) 。CDN常用于大的素材下发，比如图片和视频，你在淘宝上打开一个图片，这个图片其实会就近从CDN机房拉去数据，而不是到阿里的机房拉数据，可以减少阿里机房的出口带宽占用，也可以减少用户加载素材的等待时间。
• 11.01 14:04:46
  发表了文章 2023-11-01 14:04:46

  局部性原理——各类优化的基石（1）

  学过计算机底层原理、了解过很多架构设计或者是做过优化的同学，应该很熟悉局部性原理。即便是非计算机行业的人，在做各种调优、提效时也不得不考虑到局部性，只不过他们不常用局部性一词。如果抽象程度再高一些，甚至可以说地球、生命、万事万物都是局部性的产物，因为这些都是宇宙中熵分布布局、局部的熵低导致的，如果宇宙中处处熵一致，有的只有一篇混沌。
• 11.01 14:00:58
  发表了文章 2023-11-01 14:00:58

  浮点数美丽的表象(为什么要慎用浮点数)

  这其实是float累加过程中精度丢失导致的，要理解这点我们首先要理解什么是浮点数。首先我们了解数在计算机中是如何表示的，因为计算机只能理解0和1两个数，所以一切信息都是用二进制表示的。如何保存更多的信息就是计算机设计者面临的挑战。
• 11.01 13:58:44
  发表了文章 2023-11-01 13:58:44

  Ehcache食用指南

  可以使用CacheConfigurationBuilder来创建cache配置，分别用heap() 和offheap()来指定堆存储和堆外存储配置，这两个方法都支持指定存储实例数或者存储空间的大小。上面代码中1指定最大存储2gb，2表最多存储10个实例，超过了就会用默认的LRU策略往下层淘汰。
• 11.01 13:56:39
  发表了文章 2023-11-01 13:56:39

  Java中的String、StringBuffer和StringBuilder

  其实可以看出，java底层实现字符串+的时候其实是用StringBuilder的append()来实现的，如果有字符串的连续+，jvm用StringBuilder append也可以实现优化。
• 11.01 13:54:29
  发表了文章 2023-11-01 13:54:29

  LinkedHashMap源码解析

  上文提到多次LRUCache，其中LRU是Least Recently Used的缩写，其实就是想在有限的存储空间里保留更多有价值数据的一种方式。其实现的依旧就是最佳被使用的数据将来还被使用的概率更高，这个现象在计算机领域非常明显，很多优化就是基于此的。LRUCache就是这样一种存储的实现，它的难点就在于如何高效地剔除掉最旧的数据，以及如何维护数据的新旧度。
• 11.01 13:50:07
  发表了文章 2023-11-01 13:50:07

  PriorityQueue 源码分析

  这两个函数其实就是首先将其他集合转化为连续的array，再将其堆化。
• 11.01 13:47:05
  发表了文章 2023-11-01 13:47:05

  ThreadLocal Java多线程下的影分身之术

  后来，我把c删掉，变成了下面这样。如果我现在想查h，按照上面getEntry的逻辑，是不是遍历到3就停了，所以找不到h了？ getEntry的逻辑表面确实是这样，但实际上getEntryAfterMiss、remove、gets时都会直接或者间接调用expungeStaleEntry会对表里的数据做整理。expungeStaleEntry()除了利用弱引用的特性对tab中Entry做清理外，还会对之前Hash冲突导致后移的Entry重新安放位置。所以不可能出现下面这种tab排放的。
• 11.01 13:42:10
  发表了文章 2023-11-01 13:42:10

  Java WeakHashMap

  put方法也很简单，用key的hashcode在tab中定位，然后判断是否是已经存在的key，已经存在就替换旧值，否则就新建Entry，遇到多个不同的key有同样的hashCode就采用开链的方式解决hash冲突。注意这里和HashMap不太一样的地方，HashMap会在链表太长的时候对链表做树化，把单链表转换为红黑树，防止极端情况下hashcode冲突导致的性能问题，但在WeakHashMap中没有树化。
• 11.01 13:40:01
  发表了文章 2023-11-01 13:40:01

  用fbprophet预测北京未来一个月的气温

  fbprophet是facebook开源的时序数据预测包，提供了简洁的python和R api，可以对时序数据做一些预测，也提供了有些简单的趋势分析。更多细节可以看下官方文档。官方doc中给了一个数据集作为prophet的入门，这里我也只是按照官方的入门文档编写了的代码，很简单，只是把数据集换成了北京这8年来的每日温度数据，温度数我从网上爬取的，爬虫源码和数据可以从我github上找到。
• 11.01 13:33:10
  发表了文章 2023-11-01 13:33:10

  我常用的一些linux命令

  之前做过两年的运维，用过很多命令，深切体会到某些linux命令熟练掌握后对效率提升有多大。举个简单的例子，在做了研发后经常会有跑一些数据，对于结果数据的处理，我们的产品同学一般都习惯于用excel做统计，把数据复制到excel里，然后数据分列，排序………… 最后得出某些简单的结论，我只需要cat, sort, uniq, awk, grep 这几个命令挥手间完成相同的操作。
• 11.01 13:31:52
  发表了文章 2023-11-01 13:31:52

  OSI七层网络协议

  在前一篇博客运维往事 一次负载均衡坏点检测事故中我提到了在生产环境中在第四层和第七层做healthCheck，这个第四层和第七层到底是什么意思呢？除了第四层第七层之外，其他的几层到底是什么？这几层到底做了啥？
• 11.01 13:29:52
  发表了文章 2023-11-01 13:29:52

  运维往事 一次负载均衡坏点检测事故

  之前做运维，有一些印象很深的事故，今天来讲其中一个，为了大家能理解，先说一些背景。现在因为流量巨大，单台机器肯定不足以为所有用户提供服务，所以大公司几乎任何一个服务的背后都是一套集群，然而任意一台机器不是100%可靠，如果你想让你服务尽可能接近100%可靠，你的集群就得具备检测和剔除坏点的能力。
• 11.01 13:27:45
  发表了文章 2023-11-01 13:27:45

  死锁的原理

  之前在学校学习过程中，很少写多进程的代码，虽然操作系统中学过死锁相关的内容，但考试过后也基本就忘记了，后来自己也遇到过有些多进程死锁的情况，再加上看了有些资料，对死锁才算是有了有些深入的理解。
• 11.01 13:25:48
  发表了文章 2023-11-01 13:25:48

  Java HashMap源码浅析

  大体上就是新建一个newTab，是原来table大小的两倍，然后把原有数据做放到newTab中。先不管Tree是怎么裂变的（还没搞懂），我们来看下单链表怎么裂变的。 这里直接把一个单链表裂变成了两个。在odltab中第j位置的单链表，裂变成两条单链表，一条放newtab中j位置，另一条放newtab中i+oldcap的位置，每个j都是这么做的，就是这么神奇， 很长时间我一直没理解这么简单处理，如何保证在同一条链表中的节点都有相同的hash值？
• 11.01 13:22:12
  发表了文章 2023-11-01 13:22:12

  java.util.Random和concurrent.ThreadLocalRandom对比

  起始ThreadLocalRandom是对每个线程都设置了单独的随机数种子，这样就不会发生多线程同时更新一个数时产生的资源争抢了，用空间换时间。
• 11.01 10:14:10
  发表了文章 2023-11-01 10:14:10

  Leetcode contests 95 题解

  用容斥原理可以计算出一个数字Num之下有多少个A或B的倍数cnt，我们从最大值二分这个数字Num，拿cnt和N做比较来决定二分的走向，最终l和r肯定会收敛到一起，这就是我们要的结果了。 这道题的数值范围不是特别大 ，用long就可以完全满足需求了。
• 11.01 10:12:35
  发表了文章 2023-11-01 10:12:35

  Leetcode contests 93 题解

  870. Advantage Shuffle 起始就是hdoj 1502田忌赛马，但要求的结果不一样而已。这里我用了个pair来记录B中每个数字对应的位置。
• 11.01 10:10:38
  发表了文章 2023-11-01 10:10:38

  面试题精选:Rand10()实现Rand7()

  前两天在刷leetcode的时候，遇到了一题Implement Rand10() Using Rand7()，rand7()可以给你等概率返回1-7的任意一个数，让你用rand7()实现一个rand10()，rand()可以等概率返回1-10的任意一个数。后来又在上网中不经意看到了另一题rand5()实现rand7()，更早些，我自己面试的过程中也遇到过类似的题。再早些在大二的时候，有个学姐在群里问过的一道她遇见的一道类似的面试题，我们先来从这道题开始，逐步剖析这种randX()–>randY()的题目怎么做。
• 11.01 10:07:55
  发表了文章 2023-11-01 10:07:55

  Java生产者消费者的三种实现

  Java生产者消费者是最基础的线程同步问题，java岗面试中还是很容易遇到的，之前没写过多线程的代码，面试中被问到很尬啊，面完回来恶补下。在网上查到大概有5种生产者消费者的写法，分别如下。
• 11.01 10:05:46
  发表了文章 2023-11-01 10:05:46

  大数据下的实时热点功能实现讨论（实时流的TopN）

  我司内部有个基于jstorm的实时流编程框架，文档里有提到实时Topn，但是还没有实现。。。。这是一个挺常见挺重要的功能，但仔细想想实现起来确实有难度。实时流的TopN其实离大家很近，比如下图百度和微博的实时热搜榜，还有各种资讯类的实时热点，他们具体实现方式不清楚，甚至有可能是半小时离线跑出来的。今天不管他们怎么实现的，我们讨论下实时该怎么实现（基于storm）。
• 11.01 10:03:21
  发表了文章 2023-11-01 10:03:21

  OpenTSDB简介

  这个时候OpenTSDB就应运而生。 首先它做了数据存储的优化，可以大幅度提升数据查询的效率和减少存储空间的使用。其次它基于hbase做了常用时序数据查询的API，比如数据的聚合、过滤等。另外它也针对数据热度倾斜做了优化。接下来挨个说下它分别是怎么做的。
• 11.01 09:59:07
  发表了文章 2023-11-01 09:59:07

  Leetcode 295. Find Median from Data Stream

  在一个有序数组中找中位数，但需要支持再数组中添加新的元素。本来是有序里的，可以很轻易就查到中位数，但如果添加新数字后，不一定有序。如果先对数组排序，那代价就比较大了，每次排序时间复杂度O(n*log(n))，看discuss发现了一种很巧妙的解法，可以把添加数据的时间复杂度降低到O(log(n)) ，查询中位数O(1)。
• 11.01 09:58:05
  发表了文章 2023-11-01 09:58:05

  python tsfresh特征中文详解

  tsfresh.feature_extraction.feature_calculators.count_above_mean(x) 大于均值的数的个数
• 11.01 09:56:08
  发表了文章 2023-11-01 09:56:08

  Springboot 中同时使用mybatis注解和springbean-xml配置方式

  因为自己新建了一个应用，为了开发的速度，直接选用了springboot，但后来发现大部分读库的代码和同事已有的代码重复， 索性直接拿过来用。但问题是我已有的代码是通过纯注解的方式使用mybatis，同事代码是spring+xml来使用mybatis，经过几天的探索，发现一种两种方式结合使用的方法。
• 11.01 09:54:41
  发表了文章 2023-11-01 09:54:41

  Leetcode 236. Lowest Common Ancestor of a Binary Tree

  根据LCA的定义，二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点，LCA的定义没什么好解释的，主要是这道题的解法。
• 11.01 09:53:36
  发表了文章 2023-11-01 09:53:36

  Leetcode 4. Median of Two Sorted Arrays

  题目描述很简单，就是找到两个有序数组合并后的中位数，要求时间复杂度O(log (m+n))。 如果不要去时间复杂度，很容易就想到了归并排序，归并排序的时间复杂度是O(m+n)，空间复杂度也是O(m+n)，不满足题目要求，其实我开始也不知道怎么做，后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
• 11.01 09:52:39
  发表了文章 2023-11-01 09:52:39

  最小二乘法的极大似然解释

  在真实数据中，一个x值可能对应多个y值，因为实际y值可能是受多种因素影响，所以我们可以假设任意一个x对于的y的真实值服从正态分布。我们什么时候可以认为模型 hθ(x)hθ(x) 拟合出来的点最好？当然是 hθ(x)hθ(x) 取值概率最大的时候。
• 11.01 09:51:27
  发表了文章 2023-11-01 09:51:27

  Leetcode 19.Remove Nth Node From End of List

  删除单链表中的倒数第n个节点，链表中删除节点很简单，但这道题你得先知道要删除哪个节点。在我的解法中，我先采用计数的方式来确定删除第几个节点。另外我在头节点之前额外加了一个节点，这样是为了把删除头节点的特殊情况转换为一般情况，代码如下。
• 11.01 09:50:09
  发表了文章 2023-11-01 09:50:09

  Leetcode 6.ZigZag Conversion

  如上所示，这就是26个小写字母表的5行曲折变换。 其中在做这道题的时候把不需要我们构造出这样五行字符，然后拼接。其实你把字母换成1-n的数字，很容易找到每个位置的字母在原字符串中的位置。
• 11.01 09:48:40
  发表了文章 2023-11-01 09:48:40

  Leetcode 24.Swap Nodes in Pairs

  　给你一个链表，交换相邻两个节点，例如给你 1->2->3->4，输出2->1->4->3。 　　我代码里在head之前新增了一个节点newhead，其实是为了少写一些判断head的代码。
• 11.01 09:47:31
  发表了文章 2023-11-01 09:47:31

  记一次mysql线上问题排查

  背景是这样的，我们有个系统每天都会调起多个定时任务，首先quartz每分钟会调起一次检查时间的任务，如果发现时间到达设定的任务执行时间，java代码会向数据库里写入一条记录，然后有另外一个系统就会根据这条记录执行相应的任务，有天有同事反馈说有条定时任务没执行。。
• 11.01 09:45:45
  发表了文章 2023-11-01 09:45:45

  Leetcode 623. Add One Row to Tree

  题目很简单，在树的第d层加一层，值为v。递归增加一层就好了。代码如下
• 11.01 09:44:41
  发表了文章 2023-11-01 09:44:41

  Leetcode 516. Longest Palindromic Subsequence

  找到一个字符串的最长回文子序列，这里注意回文子串和回文序列的区别。子序列不要求连续，子串（substring）是要求连续的。leetcode 5. Longest Palindromic Substring就是求连续子串的。
• 11.01 09:43:32
  发表了文章 2023-11-01 09:43:32

  Leetcode 582. Kill Process 题解

  大概说下题意，给出n个进程，每个进程都有一个唯一的进程号，每个进程只有一个父进程，但一个进程可能有多个子进程，我们用pid和ppid两个list来保存所有的进程和其父进程。每当杀死一个进程的时候，其全部子进程都必须被杀死，现在给出一个进程pid，让你找出杀死它时候必须杀死哪些进程？以list返回。
• 11.01 09:41:21
  发表了文章 2023-11-01 09:41:21

  kubernetes简介

  service是提供用户发现你服务的模块， 其实上面跑着上文中提到的label selector。因为某个pod并不稳定，可能随时新建随时删除，serives出现屏蔽掉了pod变动对服务调用方带来的影响。顺便说一句，service是长期存活的。 　当一个请求过来的时候，他先到proxy service，proxy service通过label selector找到对应的pod，将请求转发过去。如果有多个pod提供同一种服务，proxy service会采用轮询的方式转发请求。
• 11.01 09:39:25
  发表了文章 2023-11-01 09:39:25

  Java线程的使用方法

  在上面的demo中，当执行到new Thread(futuretask).start()的时候，后台就会新建一个线程异步去执行call函数，而不等call执行完，当前代码会继续执行下去。但是特别需要注意的一点是，当你用futuretask.get()来获取线程执行结果的时候，如果此刻call() 还没执行完，futuretask.get()会一直阻塞下去等待返回结果。
• 11.01 09:37:00
  发表了文章 2023-11-01 09:37:00

  面试题：如何找出数组里出现次数超过总数1/3的数

  如果你每次从nums中拿出3个不一样的数作为一组，肯定会出现两种情况。一，nums被取空了，那么nums中每个数出现次数最多占总次数的1/3，写代码很好处理吧！！ 二，还有剩余，这个情况就复杂了，有可能剩余多个，但是……但是，最多只可能剩余两种数。 为什么？ 3个不同的数凑一组才能删掉，所以不可能删掉超过1/3的数。所以超过1/3的数肯定被剩下来，但是，剩下来的俩数并不一定都是超过1/3的，这点额外注意。
• 11.01 09:35:26
  发表了文章 2023-11-01 09:35:26

  Leetcode 114. Flatten Binary Tree to Linked List

  思路也很简单，先把root的左子树（如有）变成单链表 leftlinkedlist，把root的右子树（如有）变成单链表 rightlinkedlist，再把root的右节点变成leftlikedlist，再把rightlinkedlist接到leftlinkedlist后面，代码如下。
• 11.01 09:33:44
  发表了文章 2023-11-01 09:33:44

  Leetcode 365. Water and Jug Problem

  一句话理解题意：有容积为x和y升的俩水壶，能不能量出z升的水。 我刚开始看到这题，立马就想了下暴力搜索的可能性，但考虑了下数据大小，立马放弃这个暴力的想法，于是意识到肯定有比较简单的数学方法，其实我自己没想到，后来看还是看了别人的代码，很多博客都直接给出了解法， 但没介绍为什么能这么解。所以我决定解释下我自己的思路。
• 11.01 09:32:31
  发表了文章 2023-11-01 09:32:31

  Leetcode 62. Unique Paths & 63. Unique Paths II

  原谅我重新贴一遍题目描述，不是为了凑字数，而是为了让搜索引擎能索引到这篇文章，其实也是算一种简单的SEO。 简单描述下题目，有个机器人要从左上角的格子走到右下角的格子，机器人只能向下或者向右走，总共有多少种可能的路径?
• 11.01 09:30:54
  发表了文章 2023-11-01 09:30:54

  机器学习算法——线性回归

  最近一直在学机器学习，但感觉学习效率低，理解不深入，所以想通过写博客总结来加深自己的理解，写一下我的理解过程， 也希望能帮到其他人。
• 11.01 09:28:48
  发表了文章 2023-11-01 09:28:48

  Leetcode 467. Unique Substrings in Wraparound String

  大概翻译下题意，有个无限长的字符串s，是由无数个「abcdefghijklmnopqrstuvwxy」组成的。现在给你一个字符串p，求多少个p的非重复子串在s中出现了？
• 11.01 09:27:43
  发表了文章 2023-11-01 09:27:43

  树莓派从温度传感器DHT11读取数据

  这里有个校验位，是为了确保数据传输的准确性的。如果byte1+byte2+byte3+byte4 == byte0，数据传输就是正确的。不过DHT11小数位是不工作的，所以只需要考虑byte2+byte4就行了。