Re: [gentoo-dev] HDEPEND (host dependencies for cross-compilation) for EAPI 5?

[Fabio Erculiani]

On Wed, Sep 5, 2012 at 12:44 PM, Rich Freeman <rich0@g.o> wrote:
> On Wed, Sep 5, 2012 at 3:19 AM, Fabio Erculiani <lxnay@g.o> 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