Gentoo Archives: gentoo-dev

From: Ciaran McCreesh <ciaran.mccreesh@××××××××××.com>
To: gentoo-dev@l.g.o
Subject: Re: [gentoo-dev] Portage QOS
Date: Fri, 10 Jan 2014 18:30:31
In Reply to: Re: [gentoo-dev] Portage QOS by "René Neumann"
1 On Fri, 10 Jan 2014 14:18:24 +0100
2 René Neumann <lists@××××××.eu> wrote:
3 > And again: What is needed is streamlining the algorithms (discussion
4 > on that already started as far as I could notice). An algorithm in
5 > O(n³) is always¹ worse than O(n). The constant factor added by the
7 Full dependency resolution is NP-hard... If you really wanted to
8 streamline the algorithms, you'd change the inputs slightly. Most of
9 the complexity of doing a decent job of dependency resolution comes from
10 dealing with crap input.
12 > ¹ For a large enough n.
14 ...which could be larger than the number of atoms in the universe.
15 There are real world cases where an algorithm has an O(n^3) step that
16 takes a day, and a O(2^n) step that takes a second for most inputs. You
17 shouldn't be using O() to make performance comparisons.
19 --
20 Ciaran McCreesh


File name MIME type
signature.asc application/pgp-signature


Subject Author
Re: [gentoo-dev] Portage QOS "René Neumann" <lists@××××××.eu>