旧金山大学制作的系列算法可视化交互动图，包括常见的堆、栈、队列等。学习算法数据结构的时候，如果能图示化的展现其变化过程，理解起来就会更顺畅，在学习B+Tree算法的时候，我就用过这里的演示来理解流程。 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html #推荐 #算法 #数据结构
#算法
HyperLogLog算法是被广泛使用来估算一组数据里有多少不相同值（distinct value）的算法，可以参考这里的讲解：https://www.yuque.com/abser/aboutme/nfx0a4
它用较小的数据量实现了不差的预估准确率。
比如要估算一天有多少不同的页面被访问（注意不是被访问的次数），这个算法就派上了用场。
在数据库里，要优化一个查询计划时，也需要知道被访问的表里每一列有多少不同的值来指定查询计划，于是也需要用到这个这个算法。
但是原始的HyperLogLog实现并不支持删除数据，比如一个表每一列原先的预估是一个值，但是也得考虑这个表被删除一些数据之后算一个新的预估值。
论文《Every Row Counts: Combining Sketches and Sampling for
Accurate Group-By Result Estimates》给出了一个大体的解决思路：
* 可以在每个值加一个计数器（counter）。
* 但是如果每个值的计数器是8Byte的话，就需要新增30KB的容量来存储计数，违背了HyperLogLog的初衷：小代价实现估算。
* 于是论文里提出这个计数器只需要1Byte，这1Byte的前128的值是精确存储，后128存的只是概率值。换成1Byte之后，成本从30KB降到了3.6KB。
我把Rust的HyperLogLog库streaming_algorithms fork下来在其基础上提供了delete的实现，diff见：https://github.com/datafuse-extras/streaming_algorithms/commit/762a59c5e65b36797a1ee1cad6fc410c62c9a8b9
貌似这应该是业内第一份不限语言的hll delete实现：）
HyperLogLog算法是被广泛使用来估算一组数据里有多少不相同值（distinct value）的算法，可以参考这里的讲解：https://www.yuque.com/abser/aboutme/nfx0a4
它用较小的数据量实现了不差的预估准确率。
比如要估算一天有多少不同的页面被访问（注意不是被访问的次数），这个算法就派上了用场。
在数据库里，要优化一个查询计划时，也需要知道被访问的表里每一列有多少不同的值来指定查询计划，于是也需要用到这个这个算法。
但是原始的HyperLogLog实现并不支持删除数据，比如一个表每一列原先的预估是一个值，但是也得考虑这个表被删除一些数据之后算一个新的预估值。
论文《Every Row Counts: Combining Sketches and Sampling for
Accurate Group-By Result Estimates》给出了一个大体的解决思路：
* 可以在每个值加一个计数器（counter）。
* 但是如果每个值的计数器是8Byte的话，就需要新增30KB的容量来存储计数，违背了HyperLogLog的初衷：小代价实现估算。
* 于是论文里提出这个计数器只需要1Byte，这1Byte的前128的值是精确存储，后128存的只是概率值。换成1Byte之后，成本从30KB降到了3.6KB。
我把Rust的HyperLogLog库streaming_algorithms fork下来在其基础上提供了delete的实现，diff见：https://github.com/datafuse-extras/streaming_algorithms/commit/762a59c5e65b36797a1ee1cad6fc410c62c9a8b9
貌似这应该是业内第一份不限语言的hll delete实现：）
👍17
#算法
《Computer Scientists Establish the Best Way to Traverse a Graph》：Dijkstra算法，被证明是解决单源最短路径问题（Single-Source Shortest-paths Problem，简称SSSP）的最优算法。
算法一开始是Dijkstra陪老婆逛街购物时想出来的：
文章中列出的相关论文：
*《Universally-Optimal Distributed Algorithms for Known Topologies》
*《Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps》
*《Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation》
《Computer Scientists Establish the Best Way to Traverse a Graph》：Dijkstra算法，被证明是解决单源最短路径问题（Single-Source Shortest-paths Problem，简称SSSP）的最优算法。
算法一开始是Dijkstra陪老婆逛街购物时想出来的：
In 1956, the 26-year-old Dutch computer scientist Edsger Dijkstra wanted to write a program that would show off the capabilities of a brand-new computer called the ARMAC. While shopping with his fiancée in Amsterdam, he stopped in at a café for a break. That’s when he hit on the idea for the algorithm (opens a new tab) that now bears his name. He didn’t have writing materials on hand, so over the course of 20 minutes he worked out the details in his head.
文章中列出的相关论文：
*《Universally-Optimal Distributed Algorithms for Known Topologies》
*《Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps》
*《Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation》
Quanta Magazine
Computer Scientists Establish the Best Way to Traverse a Graph | Quanta Magazine
Dijkstra’s algorithm was long thought to be the most efficient way to find a graph’s best routes. Researchers have now proved that it’s “universally optimal.”
❤2🥰2
#算法
经过这一周密集的刷力扣题目，以及看别人总结讲解思路，我感觉编程能力是有长进的，有些题目我之前做过，现在掌握了套路之后再看以前的做法惨不忍睹。
例如：https://leetcode.cn/problems/longest-substring-without-repeating-characters/ ，左边是以前的实现（大概35行），右边是我掌握了思路之后的实现（大概20行），明显简洁了很多。
我打算以后即便不准备面试了，也把做算法题当成一个智力游戏来经常玩玩。
经过这一周密集的刷力扣题目，以及看别人总结讲解思路，我感觉编程能力是有长进的，有些题目我之前做过，现在掌握了套路之后再看以前的做法惨不忍睹。
例如：https://leetcode.cn/problems/longest-substring-without-repeating-characters/ ，左边是以前的实现（大概35行），右边是我掌握了思路之后的实现（大概20行），明显简洁了很多。
我打算以后即便不准备面试了，也把做算法题当成一个智力游戏来经常玩玩。
🤓14👍6🥰3