From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from lists.gentoo.org ([140.105.134.102] helo=robin.gentoo.org) by nuthatch.gentoo.org with esmtp (Exim 4.54) id 1Erdu2-0001QB-F1 for garchives@archives.gentoo.org; Wed, 28 Dec 2005 16:11:50 +0000 Received: from robin.gentoo.org (localhost [127.0.0.1]) by robin.gentoo.org (8.13.5/8.13.5) with SMTP id jBSGAeYV025591; Wed, 28 Dec 2005 16:10:40 GMT Received: from psmtp01.wxs.nl (psmtp01-real.wxs.nl [195.121.247.14]) by robin.gentoo.org (8.13.5/8.13.5) with ESMTP id jBSG7pvR005932 for ; Wed, 28 Dec 2005 16:07:51 GMT Received: from pavlvs2.devrieze.net (ip5457f303.direct-adsl.nl [84.87.243.3]) by psmtp01.wxs.nl (8.12.10/8.12.10) with ESMTP id jBSG7pkh028641 for ; Wed, 28 Dec 2005 17:07:51 +0100 Received: from hex.local.devrieze.net (hex.local.devrieze.net [192.168.1.7]) by pavlvs2.devrieze.net (Postfix) with ESMTP id 043581004C for ; Wed, 28 Dec 2005 17:07:50 +0100 (CET) From: Paul de Vrieze To: gentoo-dev@lists.gentoo.org Subject: Re: [gentoo-dev] Multiple Repo Support Date: Wed, 28 Dec 2005 17:07:44 +0100 User-Agent: KMail/1.9 References: <43A235AD.6030604@leetworks.com> <200512281636.45418.pauldv@gentoo.org> <20051228154258.0d8d984c@snowdrop.home> In-Reply-To: <20051228154258.0d8d984c@snowdrop.home> X-Face: #Lb+'V@sGJ;ptgo5}V"W+5OCoo{LZv;bh,s,`WKLi/J)ed1_$0;6X<=?utf-8?q?700LVV/=3BLqPhiDP=5E=0A=09=27f=5Dfnv?=@%6M8\'HR1t=aFx;ePfp{ZQoBe+e)JOQ8T5*(_;mHY+cltLGq<;@$Y,=?utf-8?q?O=5C=24=0A=09Tm=23G6M?=,g![Q62J{na*S9d;R[^8pc%u\aiLqU@`kJtYl"^6pxdW Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@gentoo.org Reply-to: gentoo-dev@lists.gentoo.org MIME-Version: 1.0 Content-Type: multipart/signed; boundary="nextPart1967450.QOPJcJZqKB"; protocol="application/pgp-signature"; micalg=pgp-sha1 Content-Transfer-Encoding: 7bit Message-Id: <200512281707.50785.pauldv@gentoo.org> X-Archives-Salt: 72ef406e-01fd-4df9-92a5-ad0c5d9751fa X-Archives-Hash: d503abf4b9e624dd709456a3acf84553 --nextPart1967450.QOPJcJZqKB Content-Type: text/plain; charset="iso-8859-6" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline On Wednesday 28 December 2005 16:42, Ciaran McCreesh wrote: > On Wed, 28 Dec 2005 16:36:28 +0100 Paul de Vrieze > > wrote: > | The problem is caused by packages being dependencies from multiple > | sides. The trick is that if a package is pulled in by one side it > | should be taken for granted by the other side if it satisfies it's > | dependencies. Detecting that can be done by hashtables which have > | O(log n) complexity on the number of packages in the tree. In any > | case not that expensive. > > Lookups against the tree can be done in O(1) time. That isn't the > issue. The issue is that as soon as you introduce backtracking, you go > to O(n!) with a general "try stuff in order" algorithm like the one > you proposed, which for 1000 packages is utterly unusable. Only O(n!) in the worst case. As currently the algorithm does not do=20 backtracking it has a O(n) complexity in the number of packages. With the=20 current tree, backtracing should never be needed, so in practice nothing is= =20 left from that O(n!) complexity. The only case for worst case complexity is= =20 when the matching doesn't work. What we need for that is smart backtracking= =2E=20 We should recognize that if version A fails the dependency check, then=20 version B can only fix that if it's dependencies differ. And only for those= =20 dependencies that are different. I'm not clear yet exactly how to do it, bu= t=20 it should go along those lines. Paul =2D-=20 Paul de Vrieze Gentoo Developer Mail: pauldv@gentoo.org Homepage: http://www.devrieze.net --nextPart1967450.QOPJcJZqKB Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2-ecc0.1.6 (GNU/Linux) iD8DBQBDsrhWbKx5DBjWFdsRAthWAJ9dPKUKG565vUza22YjBXVRLBQFygCg1K5g hP+BgxqYJzd05oP8j2o1BkI= =AFkD -----END PGP SIGNATURE----- --nextPart1967450.QOPJcJZqKB-- -- gentoo-dev@gentoo.org mailing list