4 ms·
If the list doesn't change that often, then sort the list and do a binary search for a worst case of O(log n) time.
by lsllc 8y ago
If the list doesn't change that often, then sort the list and do a binary search for a worst case of O(log n) time.
- viraptor 8y agoAnd save on some cache misses as well.
- loeg 8y agoBinary search is cache and branch-predictor inefficient, although certainly not as bad as linear scan (over large datasets).
- darkarmani 8y agoIf it is only for lookups and is static, why not do a dictionary with perfect hashing? You recalculate the hash each time you need to change the input. (same as the postgres keyword lookup posted last week to HN using perfect hashing)