[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Gnu-arch-users] Re: situations where cached revisions are not so go
From: |
Robert Collins |
Subject: |
Re: [Gnu-arch-users] Re: situations where cached revisions are not so good |
Date: |
Mon, 29 Sep 2003 07:36:25 +1000 |
On Mon, 2003-09-29 at 05:50, Jason McCarty wrote:
> Furthermore, you're no longer looking for a single path. You may have
> multiple pristines and revlib entries (from multiple versions, due to
> continuations) on hand, and you want to find the shortest path to
> _any_one_ of them, which just multiplies the amount of traversal you
> need to do. You almost need to build a spanning tree to find the optimal
> solution.
Well. That is the worst case behaviour of SPF, yes. (A minimal spanning
tree in fact). in terms of finding the shortest path to any element of a
set: this doesn't change the SPF algorithm's loop or search behaviour.
It simply changes the test for 'finished'. Rather than 'a path to X', it
becomes 'a path to any of [set]'.
> I believe that a near-optimal layout of summaries for SPF will also be
> near-optimal for my algorithm, with the difference that mine won't have
> to perform nearly so much remote traversal, and has no need for an index
> to achive good results.
I think that yours will need to perform the -same- remote traversal in
that near-optimal case.
> Reverse patching wouldn't really complicate SPF any, but it would also
> only give a 2x speedup on average, so is it worthwhile vs. my simpler
> solution?
It's likely not even worth it for SPF. but: it's optional.
> > Oh, and lastly: SPF is a well known, many times coded, generic solution,
> > as opposed to a custom roll our own solution to the problem. All we need
> > is a traversal cost algorithm for a link, and that is needed regardless.
>
> A generic solution which IMO is unsuited to this problem, at least
> until the cost metric is very cheap to calculate, which it currently
> isn't.
Hmm. Well the thing I have about your algorithm is that it depends on
very careful placement of summaries and full revs into the archive.
Rob
--
GPG key available at: <http://members.aardvark.net.au/lifeless/keys.txt>.
signature.asc
Description: This is a digitally signed message part
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, (continued)
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Robert Collins, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Tom Lord, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Tom Lord, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Jason McCarty, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Tom Lord, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Robert Collins, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Robert Collins, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Jason McCarty, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good,
Robert Collins <=
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Jason McCarty, 2003/09/28
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Jason McCarty, 2003/09/27
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Alexander Deruwe, 2003/09/24
- [Gnu-arch-users] Re: situations where cached revisions are not so good, Miles Bader, 2003/09/24
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Robert Anderson, 2003/09/24
- [Gnu-arch-users] Re: situations where cached revisions are not so good, Miles Bader, 2003/09/24
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Tom Lord, 2003/09/24
- [Gnu-arch-users] Re: situations where cached revisions are not so good, Miles Bader, 2003/09/24
- [Gnu-arch-users] Re: situations where cached revisions are not so good, Tom Lord, 2003/09/24
- Re: [Gnu-arch-users] Re: situations where cached revisions are not so good, Jason McCarty, 2003/09/24