3 ms·
I’m surprised no one has brought up the fact that this code has quadratic time complexity when the underlying algorithm could be linear. And the fact that it’s
by kannanvijayan 3y ago
I’m surprised no one has brought up the fact that this code has quadratic time complexity when the underlying algorithm could be linear.
And the fact that it’s allocation behaviour is horrible, leaving behind ‘count-1’ garbage objects, count-squared garbage memory, and forcing the GC to chase after the algorithm.
I can accept this example as a contrived scenario to talk about TCO… but even in the presence of TCO one would not want to implement the function this way.
- djur 3y agoThe article doesn't explain why (and it should) but it does mention that this version is very slow and offers a version that doesn't have the same problems.
- reactordev 3y agoI wasn’t even going to dive into the allocations and garbage this style brings but it’s orders of magnitude slower, with more garbage created, disposed of, than a simple if statement. I’m glad you opened the can of worms. There are times when this doesn’t matter. Reading a config json, or performing your startup bootstrap, but if this was executed during a request or during a frame then you’re going to have a bad time.
- nsonha 3y agolooks linear to me? Takes n calls, each is O(1). > the fact that it’s allocation behaviour is horrible, leaving behind ‘count-1’ garbage objects Topic is TCO, which is kinda about that.
- eddd-ddde 3y agoThe array spreads mean that each step has to do linear work to create the next array