Complexity of current implementation is too high

[pelotom]

@safareli commented on Wed Feb 01 2017

Doing concat on normal js Array has quadratic complexity, plus doing map on the history is linear.
So I belive complexity this far is O(n^2 + n). but this is for nth yield, if i'm correct, using this for some program With n yield, will have complexity of O(n * (n^2 + n)) i.e. O(n^3+n^2). and I think this should be at least noted in readme.

btw the O(n^2 + n) part could be optimised to O(n) by using some some sequence structure which has constant time push (as you push one element only), you could even use normal Lined list for it (List = Nil | Cons a (List a)). this way complexity for some program With n yield will be O(n * n) i.e. O(n^2).

---

@pelotom commented on Wed Feb 01 2017

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).

---

@safareli commented on Wed Feb 01 2017

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.

---

@pelotom commented on Wed Feb 01 2017

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?

---

@safareli commented on Wed Feb 01 2017

didn't saw that in "burrido"

---

@pelotom commented on Wed Feb 01 2017

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

[safareli]

🌮