2

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

是否可以构建具有更快结构的队列，例如数组？

或者有没有办法实现更好的性能但仍然以功能的方式？

编辑：我想在不到一毫秒的时间内实现具有数万个排队和交付操作的发布-订阅解决方案（对于图形交互式应用程序），所以我需要一些非常快速的东西，而 ocaml 队列实现并没有满足我的性能需求

4

2 回答 2

5

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

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

一般来说，数据结构的函数式（不可变）实现比相应的命令式（可变）版本要慢一些。有一个非常好的功能队列实现，它具有出色的性能。基本技巧是将队列的一半保持在前向顺序（用于快速删除），另一半保持在反向顺序（用于快速插入）。反转的额外传球引入了一个小惩罚，就像我说的那样。

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

编辑：对于它的价值，我刚刚在我的笔记本电脑（3.06 GHz Intel Core 2 Duo）上运行了一个异常粗略的时序测试，我可以使用标准 OCaml Queue 模块在 70 毫秒内将一百万个值入队和出队。因此，完成 10,000 次大约需要 0.7 毫秒（如果我做对了）。如果您的 CPU 不比我的快，它似乎还不够快，无法满足您的要求。

编辑 2：我刚刚手写了一些代码，假设您的值中有一个预先存在的参考字段，可用于将它们排队。这避免了在排队代码中进行任何分配，但在其他方面类似于标准 Queue 模块（尽管远没有那么优雅）。在与上述相同的笔记本电脑上，一百万个队列和出队大约需要 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 个元素之间交替。我不确定结果是否会在您的环境中成立。但这很有趣。

于 2012-05-06T14:55:44.700 回答
4

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

也就是说，对于不同的队列场景，有替代的数据结构。特别是如果您对持久队列或纯队列或并发队列感兴趣，那么您有几个选择。

纯数据结构

并发队列

发布订阅

如果您正在查看发布/订阅机制，或许可以考虑绑定到 zeromq：

它绝对是针对高频操作的，甚至支持 FP 社区，http: //www.zeromq.org/bindings:haskell

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

于 2012-05-06T17:37:07.803 回答