That's also slower than the original. shift cost O(m) some costs O(m) and reduce Costs O(n) where m is the length of orderedList2 and n the length of orderedList1 so I can cost as much as O(n*m*m)
Yep, I tried to remember it, yet had made a basic mistake of assuming that Array.prototype.shift() is O(1), yet it is O(n) in its most common implementations, including the one specified in the ECMAScript 2015 spec. The code would be O(n1+n2) if it used orderedList2[index_of_first_not_yet_merged_element] instead of shift.
A very good point about the complexity of shift! I missed that one. some is not as bad, since it quits on first true, and the next loop it continues where it left off, so orderedList2 is scanned at most once in total, not each time. I could not figure out a simple way to maintain the starting index in orderedList2 during the merge, to avoid actually removing elements from it, while keeping the code to a single statement.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
That's also slower than the original. shift cost O(m) some costs O(m) and reduce Costs O(n) where m is the length of orderedList2 and n the length of orderedList1 so I can cost as much as O(n*m*m)
Seems easy to forget that the elegant new collection operators are still O loops under the hood.
Yep, I tried to remember it, yet had made a basic mistake of assuming that Array.prototype.shift() is O(1), yet it is O(n) in its most common implementations, including the one specified in the ECMAScript 2015 spec. The code would be O(n1+n2) if it used orderedList2[index_of_first_not_yet_merged_element] instead of shift.
As much as we have to consider big-o, I'm surprised someone hasn't rebuilt pgsql as a wasm 😂
Just... Whatever, batch insert and order by lol
Hah. An inverse of this?
I actually ported a legacy C code to wasm/emscripten, but source debugging sucks with wasm, so dropped that effort.
A very good point about the complexity of shift! I missed that one. some is not as bad, since it quits on first true, and the next loop it continues where it left off, so orderedList2 is scanned at most once in total, not each time. I could not figure out a simple way to maintain the starting index in orderedList2 during the merge, to avoid actually removing elements from it, while keeping the code to a single statement.