We consider the problem of computing a sequence of range minimum queries. We assume a sequence of commands that contains values and queries. Our goal is to quickly determine the minimum value that exists between the current position and a previous position $i$. Range minimum queries are used as a sub-routine of several algorithms, namely related to string processing. We propose a data structure that can process these commands sequences. We obtain efficient results for several variations of the problem, in particular we obtain $O(1)$ time per command for the offline version and $O(\alpha(n))$ amortized time for the online version, where $\alpha(n)$ is the inverse Ackermann function and $n$ the number of values in the sequence. This data structure also has very small space requirements, namely $O(\ell)$ where $\ell$ is the maximum number active $i$ positions. We implemented our data structure and show that it is competitive against existing alternatives. We obtain comparable command processing time, in the nano second range, and much smaller space requirements.


翻译:我们考虑的是计算一系列最小范围查询的问题。 我们假设一系列包含值和查询的命令。 我们的目标是快速确定当前位置和先前位置之间的最低值。 最小范围查询被作为数种算法的子常规, 即与字符串处理有关。 我们提出一个能够处理这些命令序列的数据结构。 我们为问题的若干变异获得高效的结果, 特别是我们为离线版本获得每个命令的O(1)美元时间, 为在线版本获得美元( ALpha(n) ) 的摊销时间, 以美元( $) 为反阿尔法( n) 函数和序列中的数值。 这个数据结构的空间要求也非常小, 即$( ell), 美元是最大活动值为美元的位置。 我们实施了我们的数据结构, 并显示它与现有的替代方法相比具有竞争力。 我们获得了可比的指令处理时间, 在纳米第二范围, 并且空间要求要小得多。

0
下载
关闭预览

相关内容

多标签学习的新趋势(2020 Survey)
专知会员服务
40+阅读 · 2020年12月6日
【干货书】机器学习速查手册,135页pdf
专知会员服务
120+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
143+阅读 · 2019年10月12日
MIT新书《强化学习与最优控制》
专知会员服务
269+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
将门创投
4+阅读 · 2018年5月31日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
Arxiv
0+阅读 · 2021年4月8日
Learning to Importance Sample in Primary Sample Space
Arxiv
3+阅读 · 2018年1月31日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
已删除
将门创投
4+阅读 · 2018年5月31日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
Top
微信扫码咨询专知VIP会员