On: I almost failed to search a 37 GB text file in und...

[le-mark]

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.

[Retric → le-mark]

Sure, 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 → Retric]

>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 → coldtea]

Preprocessing 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 → le-mark]

it is a factor - you calculate the amortized cost of calculating the hashes (using the total access count as the amortization count).

[HyperSane → chii]

For any indexing operation that is always assumed to be asymptotically zero.