Array#find does not scale
Because scanning sequentially becomes linearly slower as the array grows. But looking for data through an ordered array is extremely fast!
Indeed, it allows to search via dichotomy. At each step it splits the array in half, then splits in half again and so on. It avoids scanning sequentially all entries. The complexity is less: O(log(n)) instead of O(n).
It's much faster. It's like an index. It's possible because data are sorted.
We are lucky because Ruby provides Array#bsearch. Let's compare it with Array#find against 1 million entries from 1 to 1_000_000.
123_456 is a little after the beginning of the array and 654_321 is a little after the half. To be fair we will look for both values and see the difference at the end.
See code in 1st image.
Bsearch is always a lot faster. It's impossible to tell of how much, because it depends of the size of the array and where is the data. Do not forget that the array must be sorted and the condition cannot change.
Moreover the execution time of bsearch does not vary too much. Whereas for Array#find(654321) is a lot slower than Array#find(123456) because the former is further in the array. That is why, Array#find does not scale 😉
Looking through an array of numbers is not real use case. Let's see how we can create an index for real data. Note that, as a database index, it's relevant only if you have more reads than writes.
See code in 2nd image.
#rubyonrails #highspeedror
Because scanning sequentially becomes linearly slower as the array grows. But looking for data through an ordered array is extremely fast!
Indeed, it allows to search via dichotomy. At each step it splits the array in half, then splits in half again and so on. It avoids scanning sequentially all entries. The complexity is less: O(log(n)) instead of O(n).
It's much faster. It's like an index. It's possible because data are sorted.
We are lucky because Ruby provides Array#bsearch. Let's compare it with Array#find against 1 million entries from 1 to 1_000_000.
123_456 is a little after the beginning of the array and 654_321 is a little after the half. To be fair we will look for both values and see the difference at the end.
See code in 1st image.
Bsearch is always a lot faster. It's impossible to tell of how much, because it depends of the size of the array and where is the data. Do not forget that the array must be sorted and the condition cannot change.
Moreover the execution time of bsearch does not vary too much. Whereas for Array#find(654321) is a lot slower than Array#find(123456) because the former is further in the array. That is why, Array#find does not scale 😉
Looking through an array of numbers is not real use case. Let's see how we can create an index for real data. Note that, as a database index, it's relevant only if you have more reads than writes.
See code in 2nd image.
#rubyonrails #highspeedror
• • •
Missing some Tweet in this thread? You can try to
force a refresh
