"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