* Re: [gentoo-dev] Portage QOS
@ 2014-01-10 19:06 99% ` René Neumann
0 siblings, 0 replies; 1+ results
From: René Neumann @ 2014-01-10 19:06 UTC (permalink / raw
To: gentoo-dev
Am 10.01.2014 19:19, schrieb Ciaran McCreesh:
> On Fri, 10 Jan 2014 14:18:24 +0100
> René Neumann <lists@necoro.eu> 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³) is always¹ worse than O(n). The constant factor added by the
>
> Full dependency resolution is NP-hard...
Though NP-hard does not necessarily mean 'unfeasible in practice'.
> 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.
My intention really was not to tell anybody how the depres algorithms
should be improved. I just wanted to make a point against the 'Python is
the root of all the bad performance'.
>> ¹ 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.
>
Point taken. I should've use 'in general' instead of 'always'. What I
had in mind when writing this were more smaller problems, where a good
algorithm exists but people use their own naïve implementation/data
structure.
- René
^ permalink raw reply [relevance 99%]
Results 1-1 of 1 | reverse | options above
-- pct% links below jump to the message on this page, permalinks otherwise --
2014-01-09 7:24 [gentoo-dev] Portage QOS LTHR
2014-01-09 8:12 ` Alec Warner
2014-01-09 12:44 ` Igor
2014-01-09 14:12 ` Christopher Schwan
2014-01-09 15:26 ` Igor
2014-01-10 0:16 ` heroxbd
2014-01-10 12:30 ` Igor
2014-01-10 12:39 ` Patrick Lauer
2014-01-10 13:05 ` Igor
2014-01-10 13:18 ` René Neumann
2014-01-10 18:19 ` Ciaran McCreesh
2014-01-10 19:06 99% ` René Neumann
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox