我试图弄清楚如何在函数式编程中实现对大型集合的非破坏性操作,即.如何在不必创建全新集合的情况下更改或删除单个元素,其中所有元素(即使未修改的元素)将在内存中重复.(即使原始集合是垃圾收集的,我也希望这样的集合的内存占用和一般性能很糟糕.)
使用F#,我想出了一个函数insert,它将列表分成两部分,并在中间引入一个新元素,似乎没有克隆所有未更改的元素:
// return a list without its first n elements:
// (helper function)
let rec skip list n =
if n = 0 then
list
else
match list with
| [] -> []
| x::xs -> skip xs (n-1)
// return only the first n elements of a list:
// (helper function)
let rec take list n =
if n = 0 then
[]
else
match list with
| [] -> []
| x::xs -> x::(take …performance f# functional-programming memory-footprint data-structures
我一直在寻找持久的实时可连接deques的工作.有各种方法具有用于连接deques的对数复杂性,有些方法具有摊销的常数时间实施,但实时(非摊销)具有恒定时间连接的deques少得多.
众所周知的实时可连接deque是1999年由Haim Kaplan和Robert Tarjan撰写的文章,Purely Functional,Real-Time Deques with Catenation.然而,关于deques 的维基百科页面和这个梦幻般的StackOverflow答案都提到了Robert Tarjan和Radu Mihaescu最近的工作(显然是2003年),这应该更简单.
有没有人链接到Robert Tarjan和Mihaescu关于这项工作的出版物？我在浏览网页时唯一能找到的就是一个.doc文档,显然是某些课程笔记的一部分,而且这种格式既不舒服,也不够可靠,无法实现.
有些网页将第二作者称为"Mihaesau",这似乎是一个错误.我找到了一个DBLP的出版物列表,更近期,没有提及可连接的队列,以及一个微薄的网页,没有链接到出版物部分.
我打算写一个游戏(如果你听说过它叫做"Qwirkle"),其中一个二维游戏场存储玩家放入其中的宝石的位置.第一个玩家将石头放在任何地方,其他玩家可以从任何一侧(左/右/上下)连接到它.游戏领域本身不限于固定大小,这会破坏游戏理念.但是,宝石的数量限制为玩家在开始时可以定义的值.
由于游戏逻辑,我需要通过索引循环穿过石头.但是,由于玩家可以从任何一侧添加石头,我需要一个可扩展到任何方向的列表(例如,进入负向和正向索引方向).
性能并不重要,因为我需要一次检查几块石头.
当然,最好的方法是使用像_stones [-3,5]这样的石头来访问位于-3,5位置的石头.
我认为可以从任何一侧推送和弹出的堆栈(如PushBack/PushFront)对此有用,但我不太确定如何在C#中实现它.
是否有预先实现的列表/堆栈,就像我正在考虑的那样,或者我的方法是否完全奇怪？
哪些C#集合最适合零索引插入和追加到最终？
我想这很简单LinkedList,但考虑到我对大字节缓冲区的兴趣,我怀疑每个节点的内存成本可能对我的需求而言过于昂贵.
我的理解是法线List具有缓冲支持,其容量通常大于实际数据.当数据填充缓冲区时,将创建一个新缓冲区,并将旧内容传输到新缓冲区.这对于追求结束非常有用,但对于一开始的增长却是可怕的.我的测试,附加/插入一百万个随机整数到List: