Complexity of current implementation is too high about immutagen HOT 6 CLOSED

Issue moved to pelotom/burrido #2 via ZenHub

from immutagen.

Doing concat on normal js Array has quadratic complexity,

Hm, I don't think you're right about that. Concatenating 2 arrays of length n and m would be O(n + m), but appending a single element to the end of an array, as we're doing here, is just O(n). Using a cons-list for the history would make appending an element constant time, but because of the map the overall complexity of a single yield would remain O(n).

from immutagen.

Correct, so concat will be O(n) + map O(n) so single yield will stay O(n), i.e. we can't fix it.

But I still think that, it should be noted in readme, as users of immutagen and burrido might not be aware of this.

from immutagen.

Quoting from the current README:

Note also that there is inherent inefficiency in this technique, because every yield expression requires replaying the entire history up to that point. For this reason it's advisable to keep expensive computations to a minimum inside immutable generators, particularly as the number of yield expressions in the generator grows. Even if there isn't a lot of expensive computation, the runtime complexity will be quadratic in the number of yield expressions to be evaluated, so be careful.

Is that not sufficiently clear?

from immutagen.

didn't saw that in "burrido"

from immutagen.

I'd be happy to review a PR on the burrido repo that adds wording to that effect.

from immutagen.