Array#sort! does not scale either
Last time we saw that Array#bsearch is a lot faster than Array#find. But keeping a large array sorted could become really slow.
Fortunately, SortedContainers has been published recently. Let's see how it compares to Array#sort! in the case we need to ensure an array is always sorted: see image 1.
Of course, it's unfair because calling sort on each insertion is probably the worst algorithm. Indeed, the issue is not the sort method but calling it so often. But that is the cost of maintaining a sorted array.
Whereas SortedArray ensures new items are added at the right position to keep the array sorted. Instead of sorting at each insertion, it shifts the array. I encourage you to go to the README for more details and benchmarks against a tree structure.
However, I noticed that SortedArray#bsearch is slower than Array#bsearch: see image 2.
So for data that can be eager loaded, a basic array and calling sort once is the best choice. But for data that cannot be eager loaded, then SortedArray sounds like a good choice.
Last time we saw that Array#bsearch is a lot faster than Array#find. But keeping a large array sorted could become really slow.
Fortunately, SortedContainers has been published recently. Let's see how it compares to Array#sort! in the case we need to ensure an array is always sorted: see image 1.
Of course, it's unfair because calling sort on each insertion is probably the worst algorithm. Indeed, the issue is not the sort method but calling it so often. But that is the cost of maintaining a sorted array.
Whereas SortedArray ensures new items are added at the right position to keep the array sorted. Instead of sorting at each insertion, it shifts the array. I encourage you to go to the README for more details and benchmarks against a tree structure.
However, I noticed that SortedArray#bsearch is slower than Array#bsearch: see image 2.
So for data that can be eager loaded, a basic array and calling sort once is the best choice. But for data that cannot be eager loaded, then SortedArray sounds like a good choice.
Finally let's see a more real example. The idea is to wrap all the mechanism into an object in order to have a simple interface to use.
• • •
Missing some Tweet in this thread? You can try to
force a refresh
