From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) by finch.gentoo.org (Postfix) with ESMTP id 6D600138247 for ; Fri, 10 Jan 2014 18:30:31 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 09077E0E56; Fri, 10 Jan 2014 18:30:26 +0000 (UTC) Received: from mail-wi0-f180.google.com (mail-wi0-f180.google.com [209.85.212.180]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id EC61CE0E4D for ; Fri, 10 Jan 2014 18:30:24 +0000 (UTC) Received: by mail-wi0-f180.google.com with SMTP id hn9so1683319wib.13 for ; Fri, 10 Jan 2014 10:30:23 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20120113; h=date:from:to:subject:message-id:in-reply-to:references:mime-version :content-type; bh=OaDx2hGlNFv9XGvPLLhzs/uUHA5OTtDiSdzfDjvhMIE=; b=uPVVTLTwq2kEHoG1wRhN/KwoJ0mxlJaJ8QUTWuEqh7CXPMvWj7qwLdHY8KsL+PrFCK Ye+XBUMtmJbBiaCQI7D/PFQ+fsIfv5qk0PTEaRVPiYOLLThTvSnD5km5saaFB498L7SP shQy4A78KrW58+V2Zu02/rAjwMMiG+4lwh6W2MrQh/RuYBBC0HWmQqbb6RzJsmDdui0A avYdJtWR2m85mHBeH4I1l+ZDzVsc1CxoEchoVExnamam9+QBWsBfI7iO09uE4yTcx7ph Dw9hLyfzIBvn0YyL4rfYLnsv2f3AgGKffdd4A6on93Mkb1CiMNGP7BwWFBfl7CpBFQy4 wk1g== X-Received: by 10.180.188.169 with SMTP id gb9mr4050039wic.41.1389378623790; Fri, 10 Jan 2014 10:30:23 -0800 (PST) Received: from localhost (cpc3-broo7-2-0-cust157.14-2.cable.virginm.net. [86.30.224.158]) by mx.google.com with ESMTPSA id dd3sm4806909wjb.9.2014.01.10.10.30.23 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 10 Jan 2014 10:30:23 -0800 (PST) Date: Fri, 10 Jan 2014 18:19:13 +0000 From: Ciaran McCreesh To: gentoo-dev@lists.gentoo.org Subject: Re: [gentoo-dev] Portage QOS Message-ID: <20140110181913.6a0ece9a@googlemail.com> In-Reply-To: <52CFF320.70800@necoro.eu> References: <52ce4eab.463f700a.4b43.16bd@mx.google.com> <52ce9994.24f5980a.0660.342e@mx.google.com> <6345949.JsNcU8lWSX@cschwan-laptop> <52cebfa2.aa78980a.7a02.42e5@mx.google.com> <86r48g8zdc.fsf@moguhome00.in.awa.tohoku.ac.jp> <52cfe7d2.0813980a.6b2c.ffff9681@mx.google.com> <52CFEA1F.8050802@gentoo.org> <52cfeffd.6d2a700a.56f3.ffff9763@mx.google.com> <52CFF320.70800@necoro.eu> X-Mailer: Claws Mail 3.9.3 (GTK+ 2.24.22; x86_64-pc-linux-gnu) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@lists.gentoo.org Reply-to: gentoo-dev@lists.gentoo.org MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; boundary="Sig_/RcjYBAD_BW/6pysC0tWOt4n"; protocol="application/pgp-signature" X-Archives-Salt: 955197ed-6fef-47c5-9150-6fb9255bed0b X-Archives-Hash: 470c5f5c8b63adbb083e1d40bfe1deb3 --Sig_/RcjYBAD_BW/6pysC0tWOt4n Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Fri, 10 Jan 2014 14:18:24 +0100 Ren=C3=A9 Neumann wrote: > And again: What is needed is streamlining the algorithms (discussion > on that already started as far as I could notice). An algorithm in > O(n=C2=B3) is always=C2=B9 worse than O(n). The constant factor added by = the Full dependency resolution is NP-hard... If you really wanted to streamline the algorithms, you'd change the inputs slightly. Most of the complexity of doing a decent job of dependency resolution comes from dealing with crap input. > =C2=B9 For a large enough n. ...which could be larger than the number of atoms in the universe. There are real world cases where an algorithm has an O(n^3) step that takes a day, and a O(2^n) step that takes a second for most inputs. You shouldn't be using O() to make performance comparisons. --=20 Ciaran McCreesh --Sig_/RcjYBAD_BW/6pysC0tWOt4n Content-Type: application/pgp-signature; name=signature.asc Content-Disposition: attachment; filename=signature.asc -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (GNU/Linux) iEYEARECAAYFAlLQOaQACgkQ96zL6DUtXhHG/QCeP2u6S9nA00fN6a38b9BXW7mE zrEAoIo47DFmsKhlDoB2G/wZxYPezjqo =eHtw -----END PGP SIGNATURE----- --Sig_/RcjYBAD_BW/6pysC0tWOt4n--