阶梯访问表

最后更新于:2022-04-02 04:16:20

[TOC] ## 概述 ![](https://files.catbox.moe/uumgkt.png) 阶梯结构的基本想法是表中的记录对于**不同的数据范围有效,而不是对不同的数据点有效**。这种方法不像索引结构直接,但是要比索引访问节省空间。 ## 示例 ### 分数 bad ``` let level = '优' if(score <60 ){ level = '差' }else if(score < 70) { level = '一般' }else if(score < 80) { level = '中' }else if(score < 90) { level = '良' } ``` good ``` const levelTable = ['差', '中', '良', '优'] const scoreCeilTable = [60, 80, 90, 100] function getLevel(score) { const len = scoreCeilTable.length for(let i = 0; i < len; i++) { const scoreCeil = scoreCeilTable[i] if(score <= scoreCeil) { return levelTable[i] } } return levelTable[len - 1] } // 如果需要加一个 60-70 阶段 const levelTable = ['差', '一般', '中', '良', '优'] const scoreCeilTable = [60, 70, 80, 90, 100] ``` ### 阶梯访问表需要注意几个问题 1. 留心端点 2. 二分查找替代顺序查找:上面例子用了顺序查找,当数据比较大时,查找成本还是比较大的,应该考虑用二分查找替代顺序查找 3. 考虑用索引访问来取代阶梯技术,阶梯查找比较耗时,如果速度非常重要,可以用索引访问来取代阶梯,用空间换时间,但也要分情况,因为离散空间是不能够完全替代连续空间的 4. 把阶梯表查询操作提取成单独的子程序
';