简单快速的伪Fractional Cascading
Fractional Cascading算法是用于将零散的多个数组（亦可理解成比较高维的空间）中的数据的二分查找速度增加，用的是空间换时间的方法。然而这种方法并不是很好懂，而且中文文献很少。在这里介绍一种简单的伪Fractional Cascading算法。其实它与Fractional Cascading并没有任何关系，这里提到只是借个名声罢了。
假设这些数据是二维的。即：有k个一维数组，其中一共存储了n个元素。要实现快速查找的目的，一般都会先进行排序，然后每次对于每个数组进行二分查找。时间复杂度为
。考虑极限情况，即k=n时，显然，时间复杂度会退化到
，显然不是一个好办法。
现在就要谈我们的“伪Fractional Cascading”了。我们可以按照类似的思想，以空间换时间，建立一个大数组存储所有的键值对，顺带坐标信息。搜索时只需在这个大数组内进行，时间复杂度稳定为
，且无退化情况。
顺便我做了一个实际时间的对比表，结果如下（在Win10下，CPU:E3 1230V2，g++5.1.0编译，编译优化开关“-O3”，表中n,k如上文所述，查询重复times次）：
| # | n | k | times | 朴素二分查找(ms) | 伪Fractional Cascading(ms) |
| 1 | 1000000 | 200 | 10000 | 163 | 9 |
| 2 | 1000000 | 20000 | 10000 | 5763 | 8 |
| 3 | 10000000 | 200 | 10000 | 311 | 13 |
| 4 | 10000000 | 20000 | 10000 | 14433 | 20 |
对比1,2与3,4可以明显看出，朴素二分查找的速度与k即数组的个数的关系很大。所以在k大的时候，伪Fractional Cascading更能发挥出优势。
对比1,3与2,4可以明显看出，朴素二分查找的速度受n的影响也是随着k的增大而增大的。
现在讲讲实现。STL很好的支持了数据检索这个需求，在朴素二分查找中可以直接使用binary_search函数查找。但是在伪Fractional Cascading算法中，不仅要保存值，还要保存坐标，这时候使用关联容器map系列更加方便。然而，在这个测试中同一个随机数可能分布在多个数组内，所以我还是用了multi_map。测试时间的样例程序可以在这里下载：FakeFractionalCascading.cpp（使用了一些c++11特性，编译时请加上相应的编译开关）
Updated 2015-12-5 18:11:
这里把文下的一个评论提前：“@Antineutrino忘了在文章里写了，其实这就是为什么称为“伪Fractional Cascading”的原因。Fractional Cascading使用树结构，插入删除后调整也是对数级别的复杂度。然而像你所看到的，这个伪算法显然不能满足这个需求，所以就称它为离线结构吧。虽然 离线结构看起来没有什么意义，但是在一次性查询次数与修改次数差距悬殊时，对于程序的效率提升还是很明显的。”
是的，这个结构有一个致命的弱点就是不支持动态修改（或者说很慢）。
最新文章
- 用CSS开启硬件加速来提高网站性能
- Python的平凡之路（21）
- Unity3d 在不同设备中的文件读写 的路径
- 【转】如何修改Chrome缓存目录的地址
- Java Hour2
- SSH超时断开(ClientAliveInterval和ClientAliveCountMax )的使用
- BZOJ 1231: [Usaco2008 Nov]mixup2 混乱的奶牛
- windows下如何设置mysql环境变量
- Uber到底挣钱不挣钱，听听司机怎么说
- 左右GNU Linux企业加密文件系统 eCryptfs简介
- 结束《Java编程思想》（Thinking in Java）自学的读后感（2017.10.15）
- TypeScript入门知识三（函数新特性）
- Babel插件开发入门指南
- shell模板变量替换
- sqoop连接SqlServer2012示例
- Kotlin中var和val的区别
- Winfrom 嵌入word、excel实现源码
- Scala学习——Scala By Example——to be continued
- IE安全系列之——RES Protocol
- 变动性算法源代码分析与使用示例（copy_backward、 transform、 replace_copy_if 等）