3 ms·
You are being down voted because although your point is valid, it has zero relevance because the goal is fast lookup. Preprocessing cost is not a factor.
by le-mark 4y ago
You are being down voted because although your point is valid, it has zero relevance because the goal is fast lookup. Preprocessing cost is not a factor.
- deleted 4y ago[deleted]
- Retric 4y agoSure, my point was if prepossessing is allowed then arguably so should having a hot cache. It’s an arbitrary problem, so you could argue that pre computation is fine but you need to assume a cold cache or whatever.
- coldtea 4y ago>Sure, my point was if prepossessing is allowed then arguably so should having a hot cache. Preprocessing is always an option: just needs some ahead of time effort. A hot cache for a 37GB file is not always an option.
- Retric 4y agoPreprocessing isn’t an option if you’re given the file at the same time you get the list to check. Aka are you building a service or grep.
- chii 4y agoit is a factor - you calculate the amortized cost of calculating the hashes (using the total access count as the amortization count).
- HyperSane 4y agoFor any indexing operation that is always assumed to be asymptotically zero.