Hacker News Reader

Comment by mrec | Hacker News Reader

You're not wrong, but IMHO the proper place for that sort of optimization is inside the dictionary class/module/whatever. It knows why the optimization is there and the conditions under which it makes sense.

For application code it's probably better to express clearly what you're trying to do, in this case keyed lookup. Throwing in a linear search at that level isn't just dangerous, it's potentially confusing to people reading the code later.

View on HN

Depends. Sometimes the key isn't easily hash or comparable. For example, I know of a few case where the keys looks something like "if (a > b and c < d) or (a < b and d == b)".

Now, that doesn't mean you can't hash a, b, c, and d. It just means that the logic around doing the lookups is nontrivial.

When you are talking about < 100 elements, sometimes the consideration is "Welp, this is < 100, so lets just n^2 it".

> where the keys looks something like "if (a > b and c < d) or (a < b and d == b)"

Confused, what do you mean when you say the key is an "if" statement?

He probably meant, the lookup in the list is a conditional lookup based on a logic, instead of a simple key string.

I'm confused what the variables are in this example—what's already in the container vs. what is being looked up. If we conceptually don't even have a proper mapping to begin with, then it doesn't make sense to ask whether it's hashable or comparable or not in the first place. If we do—then what is the "key" in this example?

Let me preface this by saying I work in finance and rules are weird.

This comes up frequently when looking for fuzzy "duplicates".

For example, sometimes you get data from 2 sources, one will send it through with 0.01 precision. Another will send it through with 0.001 precision. You can't hash or compare that.

Things get more tricky when different finance institutes used different terms for the same entity.

That doesn't mean you can't avoid n^2 duplicate searches. It just means you have to be smart about how you group things.

Right, so you have an application where you don't genuinely have a dictionary -- e.g., inserting items in a different order can result in a very different outcome even when all the keys are distinct, or even worse, inserting two keys and then removing a third can give entirely different results depending on the order in which you inserted the first two. (Or other arbitrary things depending on your application.) That can of course come up; it's just been quite confusing for me to see a fuzzy search scenario like this presented as a counterexample when (at least to me) the discussion seemed to be about proper mappings.

Reply on news.ycombinator.com