课程主页: https://www.coursera.org/learn/io-efficient-algorithms
课程概述
I/O高效算法（I/O-efficient algorithms），也称为外存算法或缓存无关算法，是一种旨在有效处理超出计算机主存（RAM）容量的数据的算法。这些算法在处理大型数据集时特别有用，例如大规模数据处理、数据库管理和文件系统等领域。
当数据项位于内存阶层的较高位置时，对数据的操作变得更加昂贵，因此掌握I/O高效算法对于处理大型数据集至关重要。
课程大纲
课程包括多个模块，主要内容如下：
- 引言：介绍I/O模型，其中包括有限的内部存储器和无限的外部存储器，以及两者之间以给定大小块进行数据传输的方式。
- 设计缓存感知和缓存无关算法：讨论两种设计I/O高效算法的技术，以矩阵转置问题为例，分别介绍“基于块”的缓存感知算法和递归的缓存无关算法。
- 置换策略：介绍在内部存储器满时如何根据置换策略选择需要驱逐的块，分析LRU和其他一些常见的置换策略的I/O效率。
- I/O高效排序：分析MergeSort的I/O效率，并讨论如何对其进行改进以提高I/O效率。
- I/O高效数据结构：介绍一些I/O高效的数据结构，如B树与缓冲树，以及基于缓冲树的I/O高效优先队列。
- 时间前向处理：讨论时间前向处理的技术，可用于在有向无环图上评估所谓的局部函数。
课程评价
这门课程为学习和理解I/O高效算法提供了全面的视角，从基础概念引入，到具体算法的设计与分析，再到数据结构的应用，内容体系丰富，且具有较强的实践性。在每个模块中，理论与实际案例相结合，帮助学生更好地掌握课程内容。
特别是对于数据科学家、软件工程师，以及从事数据处理工作的人士，这门课程无疑是提高工作效率、优化算法性能的重要学习资源。
课程主页: https://www.coursera.org/learn/io-efficient-algorithms