On Wednesday, 19 February 2014 at 19:45:39 UTC, Ali Çehreli wrote:
On 02/19/2014 01:46 AM, Gopan wrote:
> uint among(T, Us...)(T v, Us vals)
> {
> foreach (i, U; Us)
> {
> writeln("checking ", v, " == ", vals[i]);
> if (v == vals[i])
> return i + 1;
> }
> return 0;
> }
>
> void main()
> {
> uint index = among(3, 1,2,5,3);
> writeln("Index of 3 in (1,2,5,3) is ", index);
> }
>
> outrput of running the app:
> checking 3 == 1
> checking 3 == 2
> checking 3 == 5
> checking 3 == 3
> Index of 3 in (1,2,5,3) is 4
>
> Or, is my undertanding about Big-O notation of complexity
wrong?
You get that output only because you have inserted the
writeln() expressions in there.
That foreach over variadic template arguments is a
"compile-time foreach"[1]. For example, if v were 2 and vals
were "1, 2, 3", the original code would be expanded to the
following:
if (2 == 1) return 1; // i == 0
if (2 == 2) return 2; // i == 1
if (2 == 3) return 3; // i == 3
Since all of those conditions is known to be true or false at
compile time, the compiler will reduce the code to the
following:
return 2;
Ali
Great !! Thank you Ali. I am convinced.
You have just taught me my first lesson of CTFE.
After removing writeln() from the template, the following
statements compiled without error, which means 'n' got computed
at compile time.
const uint n = among(3, 1,2,5,3); //no error
int[n] arr; //no error.
And,
int v = 3;
const uint n = among(v, 1,2,5,3); //Error: variable v cannot be
read at compile time
int[n] arr; Error: Integer constant expression expected instead
of among(v, 1, 2, 5, 3)
My conclusion is that when both 'v' and 'vals' are known at
compile time, the complexity is perfectly O(1). I would even
like to say O(0) at runtime :)
And, when either 'v' or 'vals' is not known at compile time, the
complexity is O(vals.length) because the computation happens at
runtime.
[1] http://ddili.org/ders/d.en/tuples.html
I have already started learning your tutorial. It is great !!
Thanks all who posted. I learnt from every post. I love this
forum.
