《C語言接口與實作：建立可重用軟體的技術》一2.5 效率

本節書摘來自異步社群《c語言接口與實作：建立可重用軟體的技術》一書中的第2章，第2.5節，作者 傅道坤，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視

本書中的接口的大多數實作所使用的算法和資料結構，其平均情況運作時間不會超過n（輸入規模）的線性函數，大多數算法都能夠處理大量的輸入。無法處理大量輸入的接口，或者性能可能成為重要影響因素的接口，可以規定性能标準（performance criteria）。實作必須滿足這些标準，客戶程式可以預期性能能夠達到标準的規定（但不會比标準好上多少）。

本書中所有的接口都使用了簡單但高效的算法。在n較大時，更複雜的算法和資料結構可能有更好的性能，但n通常比較小。大多數實作都隻使用基本的資料結構，如數組、連結清單、哈希表、樹和這些資料結構的組合。

本書中的adt，除少量之外全部使用了不透明指針，是以需要使用諸如stack_empty之類的函數來通路隐藏在實作背後的字段。調用函數而不是直接通路字段會帶來開銷，但它對實際應用程式性能的影響通常都是可忽略的。這種做法在可靠性和捕獲運作時錯誤的機會方面帶來的改進是可觀的，遠超性能方面的輕微代價。

如果客觀的測量表明确實有必要改進性能，那麼這種改進不應該改變接口，例如，可通過定義宏進行。當這種方法不可行時，最好建立一個新接口并說明其性能方面的優勢，而不是改變現存的接口（這将使所有的客戶程式無效）。#