Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Complexity of current implementation is too high #1

Closed
safareli opened this issue Feb 1, 2017 · 6 comments
Closed

Complexity of current implementation is too high #1

safareli opened this issue Feb 1, 2017 · 6 comments

Comments

@safareli
Copy link

safareli commented Feb 1, 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
Copy link
Owner

pelotom commented Feb 1, 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
Copy link
Author

safareli commented Feb 1, 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
Copy link
Owner

pelotom commented Feb 1, 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
Copy link
Author

safareli commented Feb 1, 2017

didn't saw that in "burrido"

@pelotom
Copy link
Owner

pelotom commented Feb 1, 2017

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

@pelotom
Copy link
Owner

pelotom commented Feb 1, 2017

Issue moved to pelotom/burrido #2 via ZenHub

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants