From: Ciaran McCreesh <ciaran.mccreesh@googlemail.com>
To: gentoo-dev@lists.gentoo.org
Subject: Re: [gentoo-dev] Portage QOS
Date: Fri, 10 Jan 2014 18:19:13 +0000 [thread overview]
Message-ID: <20140110181913.6a0ece9a@googlemail.com> (raw)
In-Reply-To: <52CFF320.70800@necoro.eu>
[-- 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 --]
next prev parent reply other threads:[~2014-01-10 18:30 UTC|newest]
Thread overview: 57+ messages / expand[flat|nested] mbox.gz Atom feed top
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-09 15:55 ` Jeroen Roovers
2014-01-09 16:37 ` Igor
2014-01-10 0:27 ` heroxbd
2014-01-10 12:41 ` Igor
2014-01-10 13:51 ` Rich Freeman
2014-01-10 0:16 ` heroxbd
2014-01-10 0:31 ` Patrick Lauer
2014-01-10 1:19 ` Tom Wijsman
2014-01-10 1:52 ` Patrick McLean
2014-01-10 2:40 ` Tom Wijsman
2014-01-10 6:17 ` Brian Dolbec
2014-01-10 18:14 ` Ciaran McCreesh
2014-01-10 7:54 ` heroxbd
2014-01-10 18:11 ` Ciaran McCreesh
2014-01-11 3:57 ` Patrick Lauer
2014-01-10 1:02 ` Tom Wijsman
2014-01-10 9:10 ` heroxbd
2014-01-10 14:54 ` Tom Wijsman
2014-01-10 12:23 ` Igor
2014-01-10 12:30 ` René Neumann
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 [this message]
2014-01-10 19:06 ` René Neumann
2014-01-10 14:05 ` heroxbd
2014-01-12 10:47 ` [gentoo-dev] " Steven J. Long
2014-01-10 13:10 ` [gentoo-dev] " Igor
2014-01-10 14:02 ` Rich Freeman
2014-01-10 15:16 ` Tom Wijsman
2014-01-10 18:12 ` Ciaran McCreesh
2014-01-09 15:49 ` Ben Kohler
2014-01-09 16:11 ` Igor
2014-01-09 17:59 ` [gentoo-dev] " Duncan
2014-01-09 20:42 ` Igor
2014-01-09 21:08 ` Chris Reffett
2014-01-10 12:10 ` Igor
2014-01-10 12:26 ` René Neumann
2014-01-10 12:52 ` Igor
2014-01-10 12:57 ` René Neumann
2014-01-10 15:39 ` Tom Wijsman
2014-01-10 16:36 ` Mike Frysinger
2014-01-10 18:17 ` Greg KH
2014-01-10 19:38 ` Duncan
2014-01-10 22:36 ` heroxbd
2014-01-11 1:28 ` Duncan
2014-01-09 19:35 ` [gentoo-dev] " yac
2014-01-11 15:00 ` Naohiro Aota
2014-01-12 10:28 ` Igor
2014-01-12 19:31 ` Igor
2014-01-12 19:31 ` Igor
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20140110181913.6a0ece9a@googlemail.com \
--to=ciaran.mccreesh@googlemail.com \
--cc=gentoo-dev@lists.gentoo.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox