|
|
|
前言，Google的厕所
Google厕所里马桶前会贴着B+ 树和哈希表的对比等数据结构对比表。很多去过Google参观的人上完厕所后会惊诧不已。"是用来搞笑的吗？我感觉数据结构只有在面试的时候会问，工作后从来不需要用数据结构的呀”。"
不懂数据结构引发的血案
但硅谷某一线互联网公司主持研发机器学习在生物医疗领域中的产品应用的蔡元楠会告诉你，他在Google实际工作中发现数据结构的重要性。
蔡元楠会给你讲一个他工作里由于"不懂数据结构引发的血案“。
”清楚记得刚开始工作时，我临危受命负责解决我们组的一个重大性能 Bug，当时影响了多个核心用户的体验。经过深入地排查后才发现，在一个关键 RPC 的代码逻辑中大量使用了一个自定义树，这个树的数据结构实现，正是这个系统的瓶颈。这个数据结构的改写把我们 RPC 的 90 分位延时从 800ms 优化到了 200ms 以下。"由于一个数据结构的优化，提高了系统4倍的效率。
所以，只有和真正的应用场景相结合，才能深刻理解数据结构的原理和性能影响。
专栏有趣讲解形式
在这个由蔡元楠来主讲的数据结构专栏里，他用原理结合真实大厂案例和开源框架的方式，来加深你对于数据结构的理解和应用能力，学完后可以应用到具体的工作中。
这个专栏史无前例地将多个国际知名大厂和多个开源项目结合进来。
结合 8 个硅谷一线大厂的最佳实践，以及 15 个顶级开源软件的应用来解读数据结构在实战工程中如何应用，如何通过优化一个核心数据结构来达到优化整个系统的功能。搞清楚这些数据结构原理后，相信你也能拥有造轮子的能力，而不是只能借助其他人的开源框架了。
8 个硅谷一线大厂包括 Facebook、Instagram、GitHub、Amazon、Uber、Twitter、Airbnb 和 Pinterest。
15 个顶级开源软件包括 Redis、Kafka、MySQL、SQLite、 MongoDB、Spark、TensorFlow、Nginx、Memcached、LevelDB、RocksDB、HBase、Cassandra、Elastic Search 和 Solr。
说的太多，下面举个例子让大家感性认识下。
位图数组在 Redis 中的应用，结合实践来学习数据结构
其实，普通程序员一直在浪费内存空间。为什么这么说？
下面以 Java 为例，假设我们要声明一个大小为 2 的“比特数组”，其代码如下所示。
int d = new int;
根据上面的声明，我们可以利用这个数组来表示两种不同的状态。但是这种方法有一个很明显的缺点，那就是消耗了过多的存储空间。无论是在 32 位还是 64 位的机器上，int 这种基本类型在 Java 中的大小都是占 4 个字节空间的，即总共占有 4 × 8 = 32 个比特位。从理论上来说，我们只是需要其中的一个比特位来记录状态，所以在这里整个数组浪费掉了 31 / 32 = 96.875% 的内存空间。
如何来高效率记录数据，提高存储效率呢？
可以把数组中一个 int 类型的元素当作是可以表达布尔状态的 32 个比特位元素。这种将每个元素中的每一个比特位都作为状态信息存储的数组称之为位数组（Bit Array）或者位图（Bit Map）。
实际应用中，大家都用得滚瓜烂熟的Reids就是用了——Bitmap才实现的高效率运算。
并且，Redis 的操作之所以强大，是因为所有操作都是位运算以及发生在内存中，所以速度极快。
有兴趣数据结构学习的，可以关注我，发消息，获取免费学习机会。 |
|
发表于 2020-9-29 15:36:09
