那些有趣的数据结构与算法(05)--限流
有时候限流也可以称为防刷,这两者的界定并不是很明显,常用的限流算法包括固定窗口,滑动窗口,漏桶以及令牌桶算法,它们都有各自的优势与最适合的使用场景,算法不分好坏,只分场景。 »
有时候限流也可以称为防刷,这两者的界定并不是很明显,常用的限流算法包括固定窗口,滑动窗口,漏桶以及令牌桶算法,它们都有各自的优势与最适合的使用场景,算法不分好坏,只分场景。 »
树型结构由于其良好的递归特性, 高效的查询效率, 在软件系统设计中有着非常广泛的使用。 IO多路复用的epoll实现采用红黑树组织和管理sockfd, 以支持快速的增删改查; Golang中的Timer采用多叉堆实现; Java中的TreeMap以及TreeSet同样采用红黑树实现…而在MySQL中, 索引的构建同样采用树结构实现。 »
在《算法》(第四版)的第一章最后一小节中, 也就是”案例研究: union-find算法”这一小节, 我看到了并查集。 在我完整的阅读了所有的算法内容之后, 脑子里只剩下两个字: 优美。 »
在我刚接触Python这门开发语言时, 并没有想用它做Web后端开发, 而是拿来写爬虫。 第一个接触的爬虫框架就是Scrapy。 网络爬虫绕不开的一个话题就是URL去重问题。 在Scrapy原生框架下, 使用的是集合来对URL进行去重的。 集合本身采用哈希表实现, 是一种典型的以空间换时间的数据结构, 当URL数量极为庞大时, 使用这种策略的去重很有可能导致内存溢出而造成服务器宕机的问题。 此时, Bitmap走进了我的视线。 »
优先队列为动态变化的数据赋予了高效且准确的排序能力, 尽管有非常大规模的数据, 二叉堆所实现的优先队列依然能够表现出色。 »
Java中的各种容器类是对基本数据结构, 如顺序表, 链表, 平衡二叉树, 红黑树等最直接的体现, 容器在使用时最重要的就是其在不同的应用场景下的时间复杂度。 例如, 需要一个有序的容器, 需要频繁的向其头部和尾部分别执行删除和插入操作, 此时选择数组所实现的容器就非常的不明智。 所以, 如果想要彻底理解Java中的容器, 首先要理解计算机世界中的基础数据结构。 另外需要说明的是, 本篇博文没有任何代码, 只对各种容器的原理进行说明。 »