3 ms·
If the size of the data is small, a linear search through a contiguous array is going to be far faster than anything more complex.
by orf 2y ago
If the size of the data is small, a linear search through a contiguous array is going to be far faster than anything more complex.
- emn13 2y agoYep; though we'd have to test a few cases to figure out what the cutoffs are here, and if there's any middle ground left for a divide-and-conquer strategy. It's also definitely going to depend on the cost of the hash function and comparison function - for something like strings, where those can be quite expensive, binary search probably has a better chance of applicability than for guid's say.
- kllrnohj 2y agoFor things with non-trivial comparison functions you're all but certainly better off with those in something else like a hashmap. After all, the more expensive the compare, the more expensive the sort & reordering that a binary search requires. And then for trivial comparison objects, binary searching is still slower even at "huge" sizes like 10,000. It's really hard to find a good use of binary searching an array on modern CPUs.
- eru 2y agoWell, it depends on how expensive your comparison is compared to a cache miss.