We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I think to force deque use there should be a test for the worst case (decreasing array). Using quick-bench.com you can see that although with a random array the int algorithm is between roughly 1.3x and 6x faster than the deque implementation, when the values in the array are always decreasing, the complexity quickly becomes closer to 0(n* k) in the int implementation. Meaning that the bigger the k the slower the code relative to the deque implementation and in my test up to 270x slower for a decreasing array from 4999 to 0 and a k of 2000. If you want to play around here's the benchmark I used https://github.com/cegranger/statquest-cpp/blob/main/benchmarks/bench_moving_max.cpp
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Deque-STL
You are viewing a single comment's thread. Return to all comments →
I think to force deque use there should be a test for the worst case (decreasing array). Using quick-bench.com you can see that although with a random array the int algorithm is between roughly 1.3x and 6x faster than the deque implementation, when the values in the array are always decreasing, the complexity quickly becomes closer to 0(n* k) in the int implementation. Meaning that the bigger the k the slower the code relative to the deque implementation and in my test up to 270x slower for a decreasing array from 4999 to 0 and a k of 2000. If you want to play around here's the benchmark I used https://github.com/cegranger/statquest-cpp/blob/main/benchmarks/bench_moving_max.cpp