From: "René Neumann" <lists@necoro.eu>
To: gentoo-dev@lists.gentoo.org
Subject: Re: [gentoo-dev] Portage QOS
Date: Fri, 10 Jan 2014 20:06:10 +0100 [thread overview]
Message-ID: <52D044A2.1000208@necoro.eu> (raw)
In-Reply-To: <20140110181913.6a0ece9a@googlemail.com>
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é
next prev parent reply other threads:[~2014-01-10 19:06 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
2014-01-10 19:06 ` René Neumann [this message]
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=52D044A2.1000208@necoro.eu \
--to=lists@necoro.eu \
--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