scala – 在O(1)中是否有一个带有Peek()的有界队列的纯函数实现
发布时间:2020-12-16 08:55:31 所属栏目:安全 来源:网络整理
导读:我想维护一个不可变的有界FIFO队列,我可以在一段时间后删除最旧的值.在 Scala中,immutable.Queue适用于大小有限的队列(.size似乎是O(N),因为它在内部基于List,但我可以单独维护大小),但似乎没有便宜的访问方式head元素用比O(N)便宜的东西来测试最旧值的年龄,
我想维护一个不可变的有界FIFO队列,我可以在一段时间后删除最旧的值.在
Scala中,immutable.Queue适用于大小有限的队列(.size似乎是O(N),因为它在内部基于List,但我可以单独维护大小),但似乎没有便宜的访问方式head元素用比O(N)便宜的东西来测试最旧值的年龄,所以我无法测试最老的条目的到期状态.任何指向纯函数(不可变)实现的指针?
解决方法
这篇文章,Haskell: Queues without pointers,
描述了具有O(1)摊销成本的纯函数队列(编辑:用于添加和删除元素).我认为数据结构来自Chris Okasaki,更多细节见于 his book. 基本思想是将队列分解为两个列表,一个用于前面,一个用于后面.新元素被添加到“前面”. “Back”以相反的顺序存储,以便于弹出元素.当“后退”的所有元素都消失时,“前面”被反转并重新识别为“后退”.这种数据结构对这些操作具有O(1)摊销成本,但显然有一些工作可以减少到O(1),这是正确的. 编辑:Okasaki’s paper描述了一个优雅,纯粹功能的队列和双端队列(deques)实现. Deques允许从任一端添加或删除元素.所有这些操作都是O(1),最坏的情况. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- ionic中实现从相册中选择图片并一次上传多张图片
- angularjs – Angular JS和partials
- 如何在{{}} AngularJS中使用JavaScript
- CXF WebService 7 - Spring整合CXF,发布RSETful 风格WebSe
- 使用AngstJS的Bootstrap-select
- angularjs – Angular ui-select不包含在包含在角ui-bootst
- bash – 如何在tmux窗格标题中显示当前命令
- 为什么反应式控件的更改事件不会在Jasmine Angular单元测试
- 如何打开emacs里面bash
- Angular 2 + 折腾记 :(7) 初步了解表单:模板驱动及数据驱