我在python中有一个嵌套的r-tree（列表列表）。钥匙是一个大数字（约10位数字）。在每个级别上，列表中大约有x个项目数（例如：10）。然后在每个列表中，它递归并具有X项目，依此类推。树的高度为H水平（例如：5）。每个级别还表明其包含的键范围（例如R-Tree）。
对于给定的键，我需要在树中找到相应的条目。这可以通过扫描每个级别来琐碎地完成，请检查给定的键是否位于该范围内。如果是这样，请逐步进入该层，然后重复直至到达叶子。
这也可以通过将密钥除以x并将商作为列表索引来完成。
所以问题是，什么更有效：依次浏览列表（复杂性= depth * x（例如：50））或依次将大数字除以x以获取实际列表索引（复杂性= hdivisions（例如，：5个部门））。
（即）50个范围检查或5个部门？
这需要可扩展。因此，如果大量用户在云中访问此代码，什么有效？可能是划分比范围检查更昂贵的？
您需要在某种现实的情况下对代码进行基准测试。
很难说的原因是您不仅在比较划分（顺便说一句，现代编译器避免使用大量技巧的划分）。在现代CPU上，您有较大的缓存，因此列表可能适合L2或L3，从而大大降低了运行时。还有花哨的矢量/SIMD指令，可以用来加快线性案例中的所有检查。
我猜想依次浏览列表会更快，此外，代码将更简单。
，但不要相信我的话，以一个真实的例子并根据结果进行基准选择。特别是如果这对您的系统的性能至关重要。