3 ms·
Comparing lookup time of unsorted vector and sorted set is unfair. The vector should be sorted and then we might compare plain binary search against BST perform
by wmu 8y ago
Comparing lookup time of unsorted vector and sorted set is unfair. The vector should be sorted and then we might compare plain binary search against BST performance.
- recentdarkness 8y agoIt is not unfair, and there is a comparison with A sorted vector as well. And the author correctly indicated the reason as of why the sorted vector is performing better than the unsorted vector. The cache friendliness is key. And it shows that for small sizes of elements an array or vector would perform better. It simply depends on your needs. I would be interested in comparing an stack based array with integers to the sets as well.
- wmu 8y agoMy fault, I just skimmed through the article and missed that comparison.
- iainmerrick 8y agoThe article includes binary search of sorted vectors.