[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: Speed query**
**From**: Frédéric van der Plancke <fvdp@...>
**Date**: Wed, 26 Mar 2008 14:31:34 +0100

Geoff Leyland wrote:

`Good question. I just tested (b) vs a pure lua binary heap and the
``binary heap is so much better (the sort version still hasn't finished)
``that I think I must have got (b) wrong
`

Well, not necessarily.

`On a queue of n items, an insertion or removal costs O(log n) (at worst)
``with a binary heap, O(n log n) (on average) with quicksort. O(x) roughly
``means "proportional to x".
`

`That makes the quicksort implementation about n times slower (x some
``constant value). That factor n may overhelm the advantage of
``quicksorting in C instead of in Lua.
`

`Also, if the quicksort is naively implemented, you may be hitting a
``weakness of the algorithm, such that the sorting time becomes O(n^2)
``instead of O(n log n) : nearly another factor n. (Someone else already
``pointed that out.)
`
Frédéric