Count the dedup savings

Background

With shared memory, a query is only actually searched the first time it's seen; later repeats are cache hits. Replaying the sequence of queries the executors issued tells you how much retrieval was saved.

Problem statement

Implement dedup_savings(queries) returning (searches_performed, cache_hits).

Input

• queries — the ordered list of search queries the executors issued.

Output

Returns a tuple (searches_performed, cache_hits):

• searches_performed — number of distinct queries (first occurrences),
• cache_hits — number of repeats served from cache (len(queries) - searches_performed).

Examples

Example 1

Input:  ["AlphaCode", "AlphaCode", "Codex", "AlphaCode"]
Output: (2, 2)

Explanation: searched AlphaCode and Codex once each (2); the two repeat AlphaCode lookups are cache hits (2).

Example 2 — all unique

Input:  ["a", "b", "c"]
Output: (3, 0)

Constraints

• A query is searched only on its first occurrence; later ones are hits.
• searches_performed + cache_hits == len(queries).

Notes

• This is the post-mortem number: shared memory turns N issued queries into searches_performed real retrievals.