[Haskell-cafe] Re: Updating doubly linked lists
Apfelmus, Heinrich
apfelmus at quantentunnel.de
Wed Jan 7 04:55:26 EST 2009
Dan Weston wrote:
>
> I hope the code is better than my description! :) The structure is more
> like
>
> Nothing(RK 0 _)
> Nothing(RK 1 _)
> A(RK 2 4)
> B(RK 3 6)
> C(RK 2 0)
>
>> The root of the tree is the center and you can descend on the right.
>> But with this structure, walking from A to B is O(d) = O(n)
>> (where d is the distance from the origin,
>> n the side length of the grid) instead of O(1).
>
> No. The tree is [[Node]], where the outer list has one element for each
> radius that has an occupied node and each inner list has the number of
> nodes at the given radius.
>
> You descend the spine of the outer list radially in O(deltaR) time,
> which for incremental moves is O(1).
>
> Then you search for an existing inner list element in O(nk(r)), which
> stays fairly constant for reasonable paths (basically, the width of a
> path swath).
Ah, so you're using a sparse representation for grids. That's a good
idea! Unfortunately, it doesn't help when the grid is a full rectangle,
i.e. when nk(r) becomes proportional to r.
The (most likely unattainable) goal I had in mind is to create a zipper
for the full grid that supports O(1) operations.
>> I mean, O(d) may be fine for you, but it's not O(1) for everything as
>> advertised. :)
>
> d is not the distance from the origin, it is nk(r), the number of nodes
> at a given radius: d(2) = 2, d(3) = 1.
Oh, right.
> An outward radial path will only expand the tree linearly, not
> quadratically, in size.
Well, that's still linear in the side length of a full grid. Directly using
Data.Map (Integer,Integer) a
would improve that to a logarithm. Of course, your structure can be
enhanced by using a Data.Map instead of a linked list for each ring à la
[Data.Map Integer a]
This will give O(log nk(r)) movements, but that's still not constant time.
Regards,
H. Apfelmus
More information about the Haskell-Cafe
mailing list