一张图看明白麻省理工课程的高级数据结构

19-05-30 banq
              

数据结构在现代计算机科学中发挥着核心作用。与算法相比,您更频繁地与数据结构进行交互(想想Google,您的邮件服务器,甚至您的网络路由器)。此外,数据结构是获得有效算法的基本构建块。麻省该课程涵盖数据结构的主要成果和当前研究方向

  1. TIME TRAVEL时间旅行:我们可以有效地记住过去(一种称为持久性的技术),但总的来说,很难改变过去并看到现在的结果(追溯性)。回归未来真的不可能。
  2. GEOMETRY:当数据有多个维度时(例如map映射,数据库表)。
  3. DYNAMIC OPTIMALITY动态最优:是否有一个二元搜索树与其他搜索树一样好?我们仍然不知道,但我们很接近。
  4. MEMORY HIERARCHY记忆层次:真正的计算机是有多级缓存,我们可以优化缓存未命中数,通常甚至不知道缓存的大小。
  5. HASHING哈希:它是计算机科学中最常用的数据结构。它仍然是一个活跃的研究领域。
  6. INTEGERS:对数时间太容易了。通过仔细分析您正在处理的信息,您通常可以大幅减少操作时间,有时甚至可以减少操作时间。我们还将介绍说明何时无法实现的下限。
  7. DYNAMIC GRAPHS动态图:当网络链接已关闭,或者您刚刚添加或删除了社交网络中的朋友,我们仍然可以在这些发生变化时保持有关连接的基本信息。
  8. STRINGS:搜索巨型文本中的短语(想想Google或DNA)。
  9. SUCCINCT简洁:您知道的大多数“线性大小”数据结构比它们需要的大得多,通常是一个数量级。一些数据结构几乎不需要原始数据之外的空间,但仍然很快(想想堆,但更酷)。

大多数材料都包含在 2012年录制的视频讲座中(已经有超过10万人观看),您可以方便地以比实时更快的速度播放。为了促进协作,我们将使用一个 名为Coauthor的新 开源软件平台,以及用于(可选)编码的Github

              

4