From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) by finch.gentoo.org (Postfix) with ESMTP id C98E3138010 for ; Wed, 5 Sep 2012 11:25:27 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id BBED8E07D2; Wed, 5 Sep 2012 11:24:58 +0000 (UTC) Received: from mail-wg0-f53.google.com (mail-wg0-f53.google.com [74.125.82.53]) by pigeon.gentoo.org (Postfix) with ESMTP id E4B2DE07A4 for ; Wed, 5 Sep 2012 11:24:00 +0000 (UTC) Received: by wgbfm10 with SMTP id fm10so407545wgb.10 for ; Wed, 05 Sep 2012 04:24:00 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date :x-google-sender-auth:message-id:subject:to:content-type :x-gm-message-state; bh=qh/O4fxT+7WmAcvhWrZXJPaRBPgFhm7k+eueXRQ4RX8=; b=TsIpHoXVI2V6rTQS8c9cv+zsvT6s+dBHjBz0alCd2bBv9rzLIlkHbWs1M85VFcHt9h QKQh1diZ6/YzTWP9d+pzX9CmuHFCVpboCvY4sM0GrX/JRlluKfuOPA3kzByvo+2/1zbh DTtWZ6c/9xJ88wx/ozBkdkkPccXoDh/p8swVHJo6PAkB9YrjdY7GAIh02l+ugKGdLlwO UFFZGo267O8Q+OI8lqhuWL+A52bJMXhuM9njCXCSPUOWrdt4zZkDf173ItQecgCRm08+ MuyFFqf64SEsHbV9wGhHNLZczKqpizAaPF59sY/uGkE8JRbU/3ckCJxGELj+DjrPAW8p 1yRA== Received: by 10.216.237.161 with SMTP id y33mr12804803weq.62.1346844240027; Wed, 05 Sep 2012 04:24:00 -0700 (PDT) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@lists.gentoo.org Reply-to: gentoo-dev@lists.gentoo.org MIME-Version: 1.0 Sender: lxnay@sabayonlinux.org Received: by 10.223.86.71 with HTTP; Wed, 5 Sep 2012 04:23:19 -0700 (PDT) In-Reply-To: References: <50411874.4060204@gentoo.org> <20120831214611.088b3f50@googlemail.com> <50469795.2070901@gentoo.org> From: Fabio Erculiani Date: Wed, 5 Sep 2012 13:23:19 +0200 X-Google-Sender-Auth: dLNnHZH6HlBZJEm269iLXWfj9Xc Message-ID: Subject: Re: [gentoo-dev] HDEPEND (host dependencies for cross-compilation) for EAPI 5? To: gentoo-dev@lists.gentoo.org Content-Type: text/plain; charset=UTF-8 X-Gm-Message-State: ALoCoQmdwThJguolCAn/uvcwD/jWhenfojnHiKZYGap1mBfN37BV+l0NZbGySiZ+LO6KKHkrUh/h X-Archives-Salt: 825b1620-9303-4a7b-b03d-a86582279aee X-Archives-Hash: 80029fa53e9b5c2a466f94714cecd753 On Wed, Sep 5, 2012 at 12:44 PM, Rich Freeman wrote: > On Wed, Sep 5, 2012 at 3:19 AM, Fabio Erculiani wrote: >> The complexity would become: >> O((b + r + p) * P) >> b = amount of buildtime dependencies >> r = amount of runtime dependencies >> p = amount of post-dependencies >> P = amount of packages i need to apply the filter to >> >> Instead of just: >> O(b * P) > > Well, actually, in both cases the complexity is O(n), assuming you > only need to make a constant number of passes through the deps per > package. > > The whole point of O notation is that it is about how it scales, not > how long it takes. An O(n) algorithm can actually be slower than an > O(n^n) algorithm even on a large dataset. However, the key is that at > some point if the dataset gets large enough the O(n) algorithm will > always become faster. > > I tend to agree with Cirian though - the time for some code to run > through the dependencies array and do something isn't going to be very > high. If a piece of code has to do it many times there is nothing > that says the package manager can't index it. I don't want to diverge (again) from the main topic, but I think that you're just oversimplifying it. If you consider parsing an ebuild something hidden behind a lot of abstraction layers, O(n) vs O(n/2) is a big difference, even if both, normalized, are still O(n). And I would never design an API which assumes that O(n/2) equals to O(n), because you don't know how that is going to be used in upper layers, today, tomorrow and in 5 years. > > Rich > -- Fabio Erculiani