public inbox for gentoo-dev@lists.gentoo.org
 help / color / mirror / Atom feed
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é


  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