如果我有一大组连续范围(例如[0..5],[10..20],[7..13],[ - 1..37])并且可以将这些集合安排到任何数据结构中我喜欢,测试特定test_number属于哪个集合的最有效方法是什么？
我已经考虑过根据集合的低数量将集合存储在平衡二叉树中(并且每个节点将具有与其集合的最低数量相同的所有集合).这将允许您根据您针对集合测试的test_number是否小于集合的最小数量来有效地修剪集合的数量,然后修剪该节点和该节点右侧的所有节点(其范围内的数字较小,大于test_number).我认为这将平均修剪大约25%的集合,但是我需要线性地查看二叉树中的所有其余节点以确定test_number是否属于这些集合.(我可以通过按集合中的最大数字对任何一个节点上的集合列表进行排序来进一步优化,这将允许我在特定列表中进行二进制搜索,以确定哪个集合(如果有)包含test_number.不幸的是,我将要处理的大多数集合没有重叠的集合边界.)
我认为这个问题已经在图形处理中得到了解决,因为他们已经找到了有效测试整个模型中哪些多边形对特定像素有贡献的方法,但我不知道该类型算法的术语.
您对问题与图形的相关性的直觉是正确的.考虑构建和查询分段树.它特别适合您想要的计数查询.另请参阅计算几何中的描述.
京公网安备 11010802040832号 | 京ICP备19059560号-6 