Week 11 — Sets, dictionaries, and preparing once

The big question

How can we answer many membership questions without scanning the same list every time? A set organizes values for membership. A dictionary organizes values under keys. The important decision is whether either structure preserves the meaning of your data.

This week, learn to distinguish membership from counting, keys from values, and insertion order from sorted order. Trace a small hash-table model, include the cost of building an index, and explain average-case O(1) without promising constant time in every possible situation.

Türkçe: Amaç yalnızca list yerine set yazmak değildir. Önce soruyu belirleriz: “Bu değer var mı?”, “Kaç defa var?” veya “Bu kimliğe ait bilgi nedir?” Bu üç soru aynı değildir. Veri yapısı seçimi hem süreyi hem de cevabın anlamını etkiler.

Prerequisite warm-up, with answers

Suppose visits = ["Ada", "Cem", "Ada"]. How many visits occurred? How many different people visited? If you search this list for missing name “Ece”, how many entries must be checked?

Answers: There are three visits, two different people, and three checks for the missing name. Converting to a set keeps information about the two people but loses the fact that Ada visited twice. The duplicates are useful data when counting visits.

Now suppose there are n = 100 known addresses and q = 20 missing query addresses. A scan for every query performs 100 × 20 = 2,000 equality checks. Here n describes stored data and q describes the number of questions. Keep both symbols until you know how they relate.

Slow concept — Three containers, three kinds of question

A list preserves sequence and allows duplicates. Its index answers “what is at position i?” A set keeps distinct hashable values and answers “is x present?” It supplies no index-based or sorted ordering guarantee. A dictionary associates each unique key with a value: “what is the score for this name?” Different keys may have equal values.

Creating {} makes an empty dictionary. Creating set() makes an empty set. In name in grades, Python checks the dictionary's keys, not its scores. grades[name] raises KeyError if the key is absent; grades.get(name, 0) returns zero in that case without adding the key.

Dictionary insertion order is preserved. It is not automatic sorting. Updating a key's value does not create a second key or move it to the end. Deleting and reinserting a key adds it at the end. A set should not be used to request insertion or sorted order. These are language-level distinctions in Python's container documentation.

Worked example 1 — Count visits slowly enough to see each update

Process Ada, Cem, Ada, Ece, Ada, Cem. Begin with no stored counts. For each name, read its current count, using zero if it has not appeared, then add one.

visits = ["Ada", "Cem", "Ada", "Ece", "Ada", "Cem"]
counts = {}
for name in visits:
    counts[name] = counts.get(name, 0) + 1
assert counts == {"Ada": 3, "Cem": 2, "Ece": 1}
assert sum(counts.values()) == len(visits)
print(counts)

The sum check gives 3 + 2 + 1 = 6, agreeing with six input visits. This is a useful conservation check: every visit contributes to exactly one count. There are n updates for n visits. Under ordinary hashing assumptions, time is O(n) on average. If u is the number of different names, the dictionary stores u entries: O(u) extra space.

Counter(visits) expresses the same counting job. setdefault is useful for grouping: “obtain the existing group, or create its initial empty list.” Neither changes the need to understand what the output represents. Also, Counter(...).most_common() may perform additional ordering work; tallying and ranking all counts are separate tasks.

Türkçe: get(name, 0) sayacı sıfırlamaz. İsim varsa mevcut sayıyı, yoksa sıfırı verir. Sonra bir eklenir. set kullansaydık Ada'nın üç ziyaretini tek değere indirirdik. Daha az veri saklamak her zaman doğru bir iyileştirme değildir; bazen gerekli bilgiyi silmektir.

Slow concept — Hashing narrows the search

A hash function computes a number from a key. The table uses this number to choose where to begin looking. It then checks key equality, because different keys can have the same hash location. Such a meeting is a collision, not proof that the keys are equal.

The lesson's bucket-and-chain picture is a teaching model. Real Python sets and dictionaries use a different internal collision-resolution layout. You need the model's lesson: a calculated starting location avoids scanning unrelated entries, while collisions can cause extra work.

Keys must be hashable: their hash must stay consistent while used as keys, and equal keys must have equal hashes. Ordinary numbers and strings qualify. Lists do not. A tuple qualifies only if all its components are hashable; a tuple containing a list does not become safe merely because its outer container is a tuple.

Türkçe: Hash değeri bir “başlangıç adresi” gibidir, kimlik belgesi değildir. İki farklı anahtar aynı yere yönlendirilebilir. Bu durumda eşitlik kontrolü hâlâ gerekir. Çakışma gerçekleşince eski verinin üzerine yazılması gerekmez; veri yapısı farklı anahtarları ayırt ederek saklar.

Worked example 2 — Trace collisions with remainder arithmetic

Use eight buckets numbered 0 through 7 and the teaching rule bucket = key % 8. Insert [10, 18, 3, 26, 7].

Bucket 2 now holds [10, 18, 26]. Finding 26 computes remainder two and checks three keys in that chain. Searching for 99 computes 99 = 12 × 8 + 3, visits bucket 3, checks its sole value 3, and concludes “absent.” It does not inspect the other chains.

If all n keys landed in one chain, a missing lookup could inspect n keys. This explains the difference between O(1) average lookup and O(n) worst-case lookup. Resizing maintains space for ordinary workloads but does not turn the worst case into a universal constant-time guarantee.

The simple cost model also assumes bounded-size keys and cheap hashing/equality. Hashing a newly created long string depends on its character count. “Independent of the number of stored keys” does not mean independent of everything.

Prepare once, then count the whole job

Let n be known addresses and q be incoming queries. Scanning the list for every missing query costs n × q checks. Building a set once and performing q lookups has average cost O(n + q), with O(n) additional storage in the all-distinct case.

For the lesson's values n = 100,000 and q = 10,000, the scan model gives 100,000 × 10,000 = 1,000,000,000. A simplified unit-cost build-and-query model gives 100,000 + 10,000 = 110,000. Their ratio is about 9,091. This is a comparison of model work units, not a predicted measured speedup: hashing and equality have different constants.

If the set is rebuilt inside the query loop, construction alone becomes O(nq). Moving preparation outside the loop is part of the algorithm, not a minor formatting change.

For one query, both a list scan and set construction followed by lookup are O(n). Neither Big-O nor a slogan determines the winner on a particular small input. A list may find the target immediately, and the set needs extra memory. A build cost becomes useful when enough later work can reuse it.

Türkçe: Toplam maliyet “hazırlık + sorgular” şeklindedir. Yalnızca hazır kümedeki aramayı ölçüp kümenin kurulmasını unutmamalıyız. Hazırlığı her soruda yeniden yaparsak kazancı kaybederiz. Bir kez sorulan soruyla binlerce kez sorulan soru için aynı tercih zorunlu değildir.

Three graduated practice problems

Problem 1 — Keys, values, and order

Start with scores = {"Ada": 88, "Cem": 72}. Assign Ada's score to 91, then add Ece with score 91. What are the dictionary length, key order, and result of 91 in scores?

Solution 1 — Updating a key is not adding a duplicate

There are three keys, in order Ada, Cem, Ece. Ada's old value is replaced, so there is no fourth entry. Both Ada and Ece can have value 91. 91 in scores is False, because 91 is not a key. Checking 91 in scores.values() would be True but requires a value search, O(n) in the worst case.

Problem 2 — Preserve the meaning of “common”

For a = [2, 2, 3, 4] and b = [2, 4, 4], find every entry from a whose value appears in b, preserving a's order and repeats. Explain why set(a) & set(b) is a different answer.

Solution 2 — Index the second list, retain the first list

a = [2, 2, 3, 4]
b = [2, 4, 4]
lookup = set(b)
answer = [value for value in a if value in lookup]
assert answer == [2, 2, 4]
assert sorted(set(a) & set(b)) == [2, 4]
print(answer)

The required answer is [2, 2, 4]. The intersection returns distinct common values, losing one required 2. Sorting that intersection cannot restore a removed duplicate. Build cost is O(m) average for m entries in b; scanning a costs O(n) average, giving O(n + m) average time. Output storage is O(r), where r is the number of retained entries. Set storage depends on the distinct values in b.

Problem 3 — Calculate a preparation break-even point

A measured workload needs 0.08 ms for each list query. Building its set takes 3 ms; each set query takes 0.002 ms. Assuming these averages remain applicable, how many queries make set preparation worthwhile?

Solution 3 — Solve the inequality, including units

Let q count queries. List time is 0.08q ms; set time is (3 + 0.002q) ms. We want 3 + 0.002q < 0.08q. Subtract 0.002q to obtain 3 < 0.078q. Divide by 0.078: q > 38.4615.... The first integer meeting the condition is 39 queries.

At q = 38, list time is 3.04 ms and set time is 3.076 ms, so preparation loses narrowly. At q = 39, the times are 3.12 ms and 3.078 ms, so it wins narrowly. Real measurement noise may exceed that difference; repeat measurements before making a precise operational decision. This threshold belongs to these measured constants, not every Python program.

Misconceptions, glossary, and readiness

“Sets are sorted” is false. “Dictionaries lose insertion order” is false. “Hash lookup is always O(1)” omits worst cases and key costs. “A larger text always makes list-based counting quadratic” also needs a qualifier: if the vocabulary stays fixed at u words, that method costs O(nu), which is linear in n for fixed u.

You are ready when you can trace a count update, explain why duplicate removal can be incorrect, state hash lookup's average and worst cases, and include construction in a total cost. Repair a gap by rebuilding the six-visit table, drawing the eight buckets, or repeating the break-even calculation with twice the build cost.

The next bridge is an order question: “How many observations lie between these two limits?” A set alone does not preserve the ordering or multiplicities needed for that answer. Week 12 uses sorted sequences and carefully maintained search boundaries.

Prepare once to answer many searches

A set lets you check whether a value is present without scanning the whole list each time. Building it still takes work and memory. It also loses the original order and repeat counts. Use it only if that fits the answer you need.

Draw or trace. Draw two routes: q queries each scan n values, or one preparation scan followed by q set lookups. Label preparation separately from query work.

Predict before checking. Is preparation automatically worthwhile for one query? What if the question asks how many times a reading occurred?

Worked reasoning

Suppose each comparison and hash calculation takes constant time. A hash calculation chooses where to look for a key. If each of q list searches misses, it checks all n items: nq checks in total. Building a set and doing q searches takes expected O(n + q) time and up to O(n) extra storage under the usual hashing assumptions. Bad collisions can make lookup slower. For just one search, scanning may be cheaper than preparation. Use a dictionary of counts if you need to know how often each value appears.

values = [3, 1, 3, 8]
queries = [3, 7, 8]
prepared = set(values)
assert [q in values for q in queries] == [q in prepared for q in queries]
assert len(prepared) == 3 and len(values) == 4
print("Membership agrees; multiplicity is not preserved.")

Change one thing. Make the data change after every query. Decide whether rebuilding or maintaining the prepared structure must now enter the work you count.

Türkçe: Hazırlık maliyeti ve bellek ücretsiz değildir. Küme varlık sorusunu yanıtlar; tekrar sayısını ve sırayı korumaz.

Additional analysis laboratory

Sets and dictionaries are not magic speed buttons. They are prepared structures with assumptions and trade-offs.

Extra exam-style prompt: For left = [2, 2, 5] and right = [2, 9], the required output is values from left that appear in right, preserving order and repeats. Why is set intersection incomplete?

Solution: set(left) & set(right) gives {2}, which loses the second 2 and the list order. Build right_lookup = set(right), then scan left and append each value that appears in the lookup. The output is [2, 2].

Turkce: Kume tekrar sayisini saklamaz. Hiz kazanirken cevabin anlamini degistiriyorsan algoritma daha iyi degil, farkli bir sorunun cevabidir.