• via Digitalmars-d-bugs (48/48) Dec 19 2014 https://issues.dlang.org/show_bug.cgi?id=13877

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=13877

          Issue ID: 13877
           Summary: Problem with map+join
           Product: D
           Version: D2
          Hardware: x86
                OS: Windows
            Status: NEW
          Severity: normal
          Priority: P1
         Component: Phobos
          Assignee: nobody puremagic.com
          Reporter: bearophile_hugs eml.cc

This shows a different computational complexity using apparently equivalent
range-based code:


import std.stdio: writeln;
import std.algorithm: map, join;

uint count1, count2;

const(int)[] foo1(in int[] data, in int i, in int max) {
    count1++;

    if (i < max) {
        typeof(return) result;
        foreach (immutable n; data)
            result ~= foo1(data, i + 1, max);
        return result;
    } else {
        return data;
    }
}

const(int)[] foo2(in int[] data, in int i, in int max) {
    count2++;

    if (i < max) {
        return data.map!(n => foo2(data, i + 1, max)).join;
    } else {
        return data;
    }
}

void main() {
    const r1 = foo1([1, 2, 3, 4, 5], 1, 7);
    writeln(count1); // 19531
    const r2 = foo2([1, 2, 3, 4, 5], 1, 7);
    writeln(count2); // 1111111
    assert(r1 == r2); // Results are equally correct.
}


I think such performance traps should not be present using ranges.


The right complexity is restored using:

return data.map!(n => foo2(data, i + 1, max)).cache.joiner.array;

--