"in" everywhere
Tomek Sowiński
just at ask.me
Thu Oct 7 16:22:47 PDT 2010
Simen kjaeraas napisał:
> Tomek Sowiński <just at ask.me> wrote:
>
>> __traits(getAttribute, opIn, @complexity).bigOh == O.constant
>
> How does this test for things like N log M?
>
> __traits(getAttribute, opIn, @complexity).bigOh == tuple( O.linear,
> O.logarithmic )
Or:
__traits(getAttribute, opIn, @complexity).bigOh = O.linear * O.log
bigOh could be e.g. a struct with an overloaded multiplier.
But you brought up something interesting -- how to bind N, M with different properties of
function arguments; big oh expressions can get quite complex, e.g.
void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1,
Range2)(SortedRange!(Range1,less) lhs, Range2 rhs);
"[...] Performs Ο(lhs.length + rhs.length * log(rhs.length)) (best case) to Ο((lhs.length +
rhs.length) * log(lhs.length + rhs.length)) (worst-case) evaluations of swap."
Even if the attribute properties could see the arguments, how to deal with things like
lhs.length + rhs.length? It has to be inspectable at compile-time. One idea is to store the
expression's abstract syntax tree (we want AST macros in D3 anyway)... But I got a feeling
we're heading for an overkill :)
--
Tomek
More information about the Digitalmars-d
mailing list