4 ms·
How is making a returning a new dynamic array worse than doing a O(n^2) implementation? The former would be perfectly fine in production, the slight increase in
by poikniok 12y ago
How is making a returning a new dynamic array worse than doing a O(n^2) implementation? The former would be perfectly fine in production, the slight increase in memory use is negligible, the n^2 solution would lead to me wanting to fire said person.
Edit:
In addition if the O(n) in place solution that I am thinking of is the same as what you are thinking of, the downside is that the remaining even elements do not remain in the same order. So overall it is hard to imagine ever wanting to use this solution over the standard create new array with just the even elements.
- Klockan 12y agoYou can easily make an O(n) solution without reordering them by using two pointers; one to read numbers and the other to keep track of where to put the next even number.
- yoklov 12y ago> How is making a returning a new dynamic array worse than doing a O(n^2) implementation Avoiding unnecessary allocations can easily mean the difference between missing a frame and not. Keep in mind that we frequently have to deal with bad mallocs and OSes/hardware without virtual memory capabilities. The main reason I'd prefer O(n^2) vs O(n)+allocation is that I asked for an in-place solution, and there are definitely situations where you'd need to be able to do this (because of pointers to the array base, or because the caller doesn't have access to the allocator to release it, or you're using an arena and then allocating a new array means wasting the memory of the old one...). Another reason that's a bit more subtle is that the O(n^2) is that it's much more likely to show up when profiling, unlike the allocation which will likely just make everything else slightly slower due to fragmentation.