2.5 效率
本书中的接口的大多数实现所使用的算法和数据结构，其平均情况运行时间不会超过N（输入规模）的线性函数，大多数算法都能够处理大量的输入。无法处理大量输入的接口，或者性能可能成为重要影响因素的接口，可以规定性能标准（performance criteria）。实现必须满足这些标准，客户程序可以预期性能能够达到标准的规定（但不会比标准好上多少）。
本书中所有的接口都使用了简单但高效的算法。在N较大时，更复杂的算法和数据结构可能有更好的性能，但N通常比较小。大多数实现都只使用基本的数据结构，如数组、链表、哈希表、树和这些数据结构的组合。
本书中的ADT，除少量之外全部使用了不透明指针，因此需要使用诸如Stack_empty之类的函数来访问隐藏在实现背后的字段。调用函数而不是直接访问字段会带来开销，但它对实际应用程序性能的影响通常都是可忽略的。这种做法在可靠性和捕获运行时错误的机会方面带来的改进是可观的，远超性能方面的轻微代价。
如果客观的测量表明确实有必要改进性能，那么这种改进不应该改变接口，例如，可通过定义宏进行。当这种方法不可行时，最好创建一个新接口并说明其性能方面的优势，而不是改变现存的接口（这将使所有的客户程序无效）。#
时间： 2024-10-25 09:32:47