如何构建更快的Queue实现？

Question

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

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

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

编辑:我想实现一个发布 - 订阅解决方案,成千上万的人在不到一毫秒的时间内排队并提供操作(对于图形交互式应用程序),所以我需要一些非常快的东西并且ocaml队列实现没有满足我的性能需求

Answer 1

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

您可以使用数组实现环形缓冲区.某些事情可能会更快(比如遍历所有元素),但会有最大的大小(对于最简单的实现).初始化阵列也有复杂性.

一般而言,数据结构的功能(不可变)实现比相应的命令式(可变)版本慢一点.有一个非常好的功能队列实现,具有很好的性能.基本技巧是将队列的一半保持在正向顺序(快速删除),将一半保持在相反的顺序(快速插入).逆转的额外传球引入了一个小的惩罚,就像我说的那样.

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

编辑:为了它的价值,我只是在我的笔记本电脑(3.06 GHz英特尔酷睿2双核处理器)上进行了非常粗略的定时测试,我可以使用70毫秒的标准OCaml队列模块将一百万个值排队并出列.那么大约需要.7毫秒来做10,000(如果我做对了).如果你的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个元素.我不确定结果会在您的环境中保持不变.但它很有趣.