public inbox for gentoo-dev@lists.gentoo.org
 help / color / mirror / Atom feed
Search results ordered by [date|relevance]  view[summary|nested|Atom feed]
thread overview below | download: 
* Re: [gentoo-dev] Portage QOS
  @ 2014-01-10 18:19 99%                   ` Ciaran McCreesh
  0 siblings, 0 replies; 1+ results
From: Ciaran McCreesh @ 2014-01-10 18:19 UTC (permalink / raw
  To: gentoo-dev

[-- Attachment #1: Type: text/plain, Size: 853 bytes --]

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... 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.

> ¹ 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.

-- 
Ciaran McCreesh

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

^ 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 99%                   ` Ciaran McCreesh

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox