performance - 如何构建更快的 Queue 实现？

Question

我注意到 queue.ml 由于其基于链表(具有可变字段)的实现而趋向于相当慢

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

或者有没有一种方法可以实现更好的性能，但仍然是功能性的？

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

Answer 1

了解您认为基于链表的实现速度慢的原因会很有趣。这是队列的经典实现。插入和删除与我想象的一样快(更新一两个引用字段)。请注意，我没有查看您所说的代码。

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

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

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

编辑:不管怎样，我只是在我的笔记本电脑(3.06 GHz Intel Core 2 Duo)上运行了一个异常粗略的计时测试，我可以使用标准 OCaml 入队和出队一百万个值在 70 毫秒内排队模块。那么完成 10,000 次大约需要 0.7 毫秒(如果我没记错的话)。如果您的 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 个元素之间交替。我不确定结果是否适用于您的环境。但这很有趣。