Fast Sequences

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Fast Sequences

Jim Apple-4
The proposed Data.Sequence (
http://www.soi.city.ac.uk/~ross/software/html/Data.Sequence.html ) has
O(n) reverse. Section 6 of http://citeseer.ist.psu.edu/560336.html
claims that it can be faster.

Also, according to http://citeseer.ist.psu.edu/kaplan96purely.html ,
there is a sequence type with (><) of O(log log n).

The latter one of these doesn't support the stated time bounds for
different versions of the same structure. Do 2-3 finger trees support
that?

Jim
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Ross Paterson
On Sun, Mar 26, 2006 at 04:11:13PM -0500, Jim Apple wrote:
> The proposed Data.Sequence (
> http://www.soi.city.ac.uk/~ross/software/html/Data.Sequence.html ) has
> O(n) reverse.

Now at

http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.html

> Section 6 of http://citeseer.ist.psu.edu/560336.html
> claims that it can be faster.

The same trick would work with Data.Sequence, but it would double the
size of the code.  It's not clear that it's worth it, especially since
the cost of reverse can only be observed by traversing the whole sequence.

> Also, according to http://citeseer.ist.psu.edu/kaplan96purely.html ,
> there is a sequence type with (><) of O(log log n).

I don't think K&T provide enough details to establish the amortization
argument for that representation.  I understand that they're working
on a new version, though.

> The latter one of these doesn't support the stated time bounds for
> different versions of the same structure.

I'm not sure what this sentence means.

> Do 2-3 finger trees support that?

They don't support O(log log (min(m,n))) append.  On the other
hand, it's quite hard to tell the difference in a lazy language,
e.g. building a sequence with appends costs O(n) whether append is
O(1) or O(log(min(m,n))).

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Jim Apple-4
On 3/26/06, Ross Paterson <[hidden email]> wrote:
> the cost of reverse can only be observed by traversing the whole sequence.

So, head . reverse is . . . O(1)?

> > The latter one of these doesn't support the stated time bounds for
> > different versions of the same structure.
>
> I'm not sure what this sentence means.

I'm paraphrasing from the first section of the paper that has Okasaki
as a co-author.

Jim
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Ross Paterson
On Sun, Mar 26, 2006 at 06:35:14PM -0500, Jim Apple wrote:
> On 3/26/06, Ross Paterson <[hidden email]> wrote:
> > the cost of reverse can only be observed by traversing the whole sequence.
>
> So, head . reverse is . . . O(1)?

Certainly.  The middle subtree, containing all but 2 to 8 of the elements,
is unused.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Jim Apple-4
On 3/26/06, Ross Paterson <[hidden email]> wrote:
> > So, head . reverse is . . . O(1)?
>
> Certainly.  The middle subtree, containing all but 2 to 8 of the elements,
> is unused.

Ah, of course. Let me try to ask a better question:
How about

(flip index i) . reverse

Is that O(i)?

Jim
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Ross Paterson
On Sun, Mar 26, 2006 at 10:54:59PM -0500, Jim Apple wrote:
> How about
>
> (flip index i) . reverse
>
> Is that O(i)?

index i is O(log(min(i,n-i))), because the index operation skips many
subtrees on the way.  This skipping will also mean that putting a
reverse first won't change the big-O complexity.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Jim Apple-4
On 3/27/06, Ross Paterson <[hidden email]> wrote:

> On Sun, Mar 26, 2006 at 10:54:59PM -0500, Jim Apple wrote:
> > How about
> >
> > (flip index i) . reverse
> >
> > Is that O(i)?
>
> index i is O(log(min(i,n-i))), because the index operation skips many
> subtrees on the way.  This skipping will also mean that putting a
> reverse first won't change the big-O complexity.

Ok, so, let my try once more:

Are there any operations f such that f . reverse has a worse big-O
time bound than f does alone?

Jim
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Ross Paterson
On Thu, Mar 30, 2006 at 04:08:23PM -0500, Jim Apple wrote:

> On 3/27/06, Ross Paterson <[hidden email]> wrote:
> > On Sun, Mar 26, 2006 at 10:54:59PM -0500, Jim Apple wrote:
> > > How about
> > >
> > > (flip index i) . reverse
> > >
> > > Is that O(i)?
> >
> > index i is O(log(min(i,n-i))), because the index operation skips many
> > subtrees on the way.  This skipping will also mean that putting a
> > reverse first won't change the big-O complexity.
>
> Ok, so, let my try once more:
>
> Are there any operations f such that f . reverse has a worse big-O
> time bound than f does alone?

The big-O will be the same in all cases, but the constant factor will
be a little larger, because reverse does a constant amount of work on
each node, if that node is demanded.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Josef Svenningsson
On 3/31/06, Ross Paterson <[hidden email]> wrote:

> On Thu, Mar 30, 2006 at 04:08:23PM -0500, Jim Apple wrote:
> > Ok, so, let my try once more:
> >
> > Are there any operations f such that f . reverse has a worse big-O
> > time bound than f does alone?
>
> The big-O will be the same in all cases, but the constant factor will
> be a little larger, because reverse does a constant amount of work on
> each node, if that node is demanded.
>
This seemed very mysterious to me at first. It seemed to imply that
one couldn't observe the linear behaviour of reverse. In fact it
seemed like in any program that we could write, any call to reverse
would only contribute a constant amount of work. After discussing this
with NilsAnders Danielsson and Ulf Norell today we came up with the
following program:
index i . reverse . reverse .... reverse
where you compose reverse k times.
Now, if reverse were really constant time then it would have
complexity O(k) + O(log(min(i,n-i))). But when we actually try took
look up one element we must perform k reversals at each level in the
finger tree. Each reversal is a constant amount of work since we won't
force anything else but the thunks in path to the index we're
interested in. This gives that the actual complexity of the above
program is O(k log(min(i,n-i))). So reverse is costlier than a
constant factor but it still seems difficult to write a program which
demonstrates the claimed linearity of the reverse operation(*).

Oh, the complexity of the complexities of lazy data structures.

All this really begs to ask the question: Is reverse really linear
then? I guess the floor is open for a formalism to precisely state the
complexity of lazy algorithms.

But for the practially minded I can only say: If you don't use reverse
too often it can be considered a constant time operation.

Does this make sense to you Ross? I'd really like to hear your comments on this.

Cheers,

/Josef

(*) Yes, I know that O(n) means that reverse has *at most* linear
complexity. But we typically mean big-Theta when we write big-O and I
believe that was the intended meaning of the authors as well.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Ross Paterson
On Tue, Apr 04, 2006 at 09:27:56PM +0200, Josef Svenningsson wrote:

> On 3/31/06, Ross Paterson <[hidden email]> wrote:
> > On Thu, Mar 30, 2006 at 04:08:23PM -0500, Jim Apple wrote:
> > > Ok, so, let my try once more:
> > >
> > > Are there any operations f such that f . reverse has a worse big-O
> > > time bound than f does alone?
> >
> > The big-O will be the same in all cases, but the constant factor will
> > be a little larger, because reverse does a constant amount of work on
> > each node, if that node is demanded.
> >
> This seemed very mysterious to me at first. It seemed to imply that
> one couldn't observe the linear behaviour of reverse. In fact it
> seemed like in any program that we could write, any call to reverse
> would only contribute a constant amount of work. After discussing this
> with NilsAnders Danielsson and Ulf Norell today we came up with the
> following program:
> index i . reverse . reverse .... reverse
> where you compose reverse k times.
> Now, if reverse were really constant time then it would have
> complexity O(k) + O(log(min(i,n-i))). But when we actually try took
> look up one element we must perform k reversals at each level in the
> finger tree. Each reversal is a constant amount of work since we won't
> force anything else but the thunks in path to the index we're
> interested in. This gives that the actual complexity of the above
> program is O(k log(min(i,n-i))). So reverse is costlier than a
> constant factor but it still seems difficult to write a program which
> demonstrates the claimed linearity of the reverse operation(*).

I think that's consistent with what I said: reverse increases the
constant factor; k reverses increase it k times.  The constant amount
of work is at each node, not in the structure overall.  The increase is
approximately the constant amount of work done at each node.  index i
visits O(log(min(i,n-i))) nodes, forcing each of the k reverses on each
of those nodes.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Fast Sequences

Josef Svenningsson
On 4/4/06, Ross Paterson <[hidden email]> wrote:

> On Tue, Apr 04, 2006 at 09:27:56PM +0200, Josef Svenningsson wrote:
> > On 3/31/06, Ross Paterson <[hidden email]> wrote:
> > > On Thu, Mar 30, 2006 at 04:08:23PM -0500, Jim Apple wrote:
> > > > Ok, so, let my try once more:
> > > >
> > > > Are there any operations f such that f . reverse has a worse big-O
> > > > time bound than f does alone?
> > >
> > > The big-O will be the same in all cases, but the constant factor will
> > > be a little larger, because reverse does a constant amount of work on
> > > each node, if that node is demanded.
> > >
> > This seemed very mysterious to me at first. It seemed to imply that
> > one couldn't observe the linear behaviour of reverse. In fact it
> > seemed like in any program that we could write, any call to reverse
> > would only contribute a constant amount of work. After discussing this
> > with NilsAnders Danielsson and Ulf Norell today we came up with the
> > following program:
> > index i . reverse . reverse .... reverse
> > where you compose reverse k times.
> > Now, if reverse were really constant time then it would have
> > complexity O(k) + O(log(min(i,n-i))). But when we actually try took
> > look up one element we must perform k reversals at each level in the
> > finger tree. Each reversal is a constant amount of work since we won't
> > force anything else but the thunks in path to the index we're
> > interested in. This gives that the actual complexity of the above
> > program is O(k log(min(i,n-i))). So reverse is costlier than a
> > constant factor but it still seems difficult to write a program which
> > demonstrates the claimed linearity of the reverse operation(*).
>
> I think that's consistent with what I said: reverse increases the
> constant factor; k reverses increase it k times.  The constant amount
> of work is at each node, not in the structure overall.  The increase is
> approximately the constant amount of work done at each node.  index i
> visits O(log(min(i,n-i))) nodes, forcing each of the k reverses on each
> of those nodes.
>
Oh, I didn't mean to suggest that what you said was wrong. What I was
trying to say was that I initially misinterpreted your statement and
thought that it implied that reverse was a constant time operation.
Our analysis is indeed consistent with what you said. And I'm happy to
hear that you agree with our reasoning.

All the best,

/Josef
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries