如何构建Queue的更快实现？

Question

我注意到queue.ml往往是相当缓慢，因为它基于链表（具有可变字段）的实现

是否有可能建立一个快速结构的队列，例如数组？

还是有办法获得更好的表现，但仍然在功能方面？

编辑：我想要实现与数以万计的排队和在小于一毫秒提供操作（图形交互应用）发布 - 订阅解决方案，所以我需要的东西非常快，ocaml的队列实现没”满足我的性能需求

Answer 1

知道为什么您认为基于链表的实现速度很慢会很有趣。这是队列的经典实现。插入和删除的速度与我想象的一样快（更新一个或两个参考字段）。请注意，我没有看过你正在谈论的代码。

您可以使用数组实现环形缓冲区。对于某些事情（比如遍历所有元素）可能会更快，但会有最大的大小（对于最直接的实现）。初始化数组也有复杂性。

一般而言，数据结构的功能（不可变）实现比相应的命令式（可变）版本稍慢。有一个非常好的功能队列实现具有很好的性能。基本技巧是保持队列的一半为正向顺序（用于快速移除）和一半为反向顺序（用于快速插入）。正如我所说的那样，额外的逆转通过了一个小小的惩罚。

如果您正在查看内存（分配和GC），不可变的方法将分配最多，经典的方法一个中等数量，并且环缓冲区将分配很少。但是一个好的FP实现（如OCaml）使分配内存的速度非常快，而且如果对象寿命较短，回收速度也不会太慢。

编辑：对于它的价值，我只是跑在我的笔记本电脑（3.06 GHz的英特尔Core 2 Duo）特粗计时测试，我可以排队，并使用标准的OCaml队列模块中70出队一百万值毫秒。那么大概0.7毫秒就可以做10,000（如果我有这个权利的话）。如果你的CPU不比我的速度快，那么你不想做你想做的事。

编辑2：我只是手写了一些代码，假设您的值中有一个预先存在的引用字段，可用于将它们排队。这样可以避免在排队代码中执行任何分配，但在其他方面与标准队列模块类似（尽管远不那么优雅）。在上面的同一台笔记本电脑上，一百万个队列和出队需要大约48毫秒。所以它快一点。

编辑3：很可能你已经被现在得到你的答案，但我只是用我上面列出的纯队列实现跑粗计时测试，我看到大约18毫秒做一百万队列和出列。所以它比较快。这是有道理的，因为OCaml被调整为纯粹的计算。这是我的代码;你可以检查任何错误。

type q = { 
    head: int list; 
    tail: int list; 
} 

let q_add q i = 
    { q with tail = i :: q.tail } 

let q_take q = 
    match q.head with 
    | [] -> 
     begin 
     match List.rev q.tail with 
     | [] -> raise Not_found 
     | h :: t -> (h, { head = t; tail = [] }) 
     end 
    | h :: t -> (h, { head = t; tail = q.tail }) 

let main() = 
    let q = q_add { head = []; tail = [] } 0 
    in let now = Unix.gettimeofday() 
    in let rec go q i = 
     if i > 1_000_000 then 
      q 
     else 
      let (_, q') = q_take (q_add q i) 
      in 
       go q' (i + 1) 
    in let _ = go q 1 
    in let duration = Unix.gettimeofday() -. now 
    in 
     Printf.printf "%f\n" duration 

let() = main() 

就像我说的，这是一个粗略的测试。队列长度在1到2个元素之间交替。我不确定结果会在你的环境中出现。但它很有趣。

Answer 2

您需要测量操作以真正量化队列操作的任何给定实现的低效率。

也就是说，有不同的队列情况的替代数据结构。特别是如果你对持久或纯队列或并发队列感兴趣，那么你有几个选择。基于二项堆http://hackage.haskell.org/package/pure-priority-queue

渐近最优的，可证明正确的队列，http://hackage.haskell.org/package/meldable-heap

队列：

纯数据结构

• 指基于树的队列：http://hackage.haskell.org/package/fingertree-psqueue
• 纯优先级队列http://hackage.haskell.org/package/pqueue

个

并发队列

• 基于STM-队列，http://hackage.haskell.org/package/bounded-tchan
• 基于STM-界队列，http://hackage.haskell.org/package/rolling-queue

发布订阅

如果你正在寻找一个发布/订阅机制，也许考虑绑定到zeromq：

• http://www.zeromq.org/

它肯定是针对高频率操作，甚至已经背上FP社区，http://www.zeromq.org/bindings:haskell

有两种不同的OCaml的绑定ZeroMQ：http://www.zeromq.org/bindings:ocaml