როგორ მუშაობს სიმრავლე განსხვავებულად

სიმრავლეები: წევრობის კითხვებისთვის აგებული

სიმრავლე ინახავს უნიკალური ელემენტებს მეთოდის გამოყენებით, რომელსაც ჰეშირება ეწოდება. როდესაც თქვენ ელემენტს დოამატებთ, კომპიუტერი ითვლის ჰეშს (ციფრული თითის ანაბეჭდი), რომელიც ზუსტად გეუბნება სად შეინახოს ეს ელემენტი.

რა დროსაც შეამოწმებთ წევრობას, კომპიუტერი ითვლის იგივე ჰეშს & გადახტება უშუალოდ სწორ ადგილზე. რთიმე ღრმა.

# A set of pets
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — duplicates removed
print(len(pets)) # 3 — only unique items

შენიშვნა სამი განსხვავება სიისგან:

1. რა დუბლიკატი. "cat" ორჯერ ჩნდება შეყვანაში მაგრამ სიმრავლე ინახავს მხოლოდ ერთ ასლს.

2. დალაგებული თანმიმდევრობა გარანტირებული არაა. სიმრავლე შეიძლება დაბეჭდოს ელემენტები ნებისმიერი განხედვით.

3. არა ინდექს დაშვება. თქვენ არ შეგიძლიათ დაწერით pets[0] — სიმრავლეებს პოზიციები არ აქვთ.

სამაგალითო: თქვენ კარგავთ თანმიმდევრობას & დუბლიკატებს. თქვენ მიიღებთ O(1) წევრობის ღრმა — იმის შემოწმება, არის თუ არა ელემენტი, მოითხოვს იგივე დროს მხოლოდ 5 ელემენტი ან 5 მილიონი.

# Membership check — is "fish" in the set?
if "fish" in pets:    # hash("fish") → jump to bucket → found
    print("found!")   # checked exactly 1 spot, not 4

სიმრავლე vs სია წევრობა

თქვენ გაქვთ 500 მოსწავლის სახელი დაწერილი სიმრავლეში იმის ნაცვლად სიაში.

students = {"Alex", "Maria", ..., "Zara", ...}  # 500 names
if "Zara" in students:
    print("enrolled")

გვერდითი მხარეს შედარება

ოპერაციები წელი ფურცელი

გამოიყენეთ სია როდესაც გჭირდებათ:

- ელემენტები კონკრეტული თანმიმდევრობით (პლეილისტი, რეცეპტი, სწორი)

- წვდომა პოზიციით (items[3])

- დუბლიკატები შენარჩუნებული ("cat" ჩნდება 3-ჯერ = 3 კატა)

გამოიყენეთ სიმრავლე როდესაც გჭირდებათ:

- სწრაფი წევრობის შემოწმება ("აქ მე ხომ თქვენი ხართ?")

- ავტომატური დუბლიკატი ამოღება

- თანმიმდევრობის შესახებ არ დაინტერესებული

გამოიყენეთ ორივე როდესაც გჭირდებათ თანმიმდევრობა და სწრაფი ღრმა:

seen = set()     # O(1) membership checks
result = []      # preserves insertion order
for item in data:
    if item not in seen:  # O(1) check
        seen.add(item)    # O(1) add
        result.append(item)  # O(1) append
# Total: O(N) — one pass, each step O(1)

ეს "სიმრავლე + სია" ნიმუში გვაძლევს საუკეთესოს ორივე: დალაგებული შედეგი სწრაფი დუბლიკატი აღმოჩენით.

აირჩიეთ სწორი სტრუქტურა

სამი პრობლემა. თითოეულთან გადაწყვიტეთ: სია, სიმრავლე, ან ორივე?

1. თქვენ უნდა შეინახოთ სიმღერების პლეილისტი იმ თანმიმდევრობით, რომელიც მომხმარებელმა დაამატა.

2. თქვენ უნდა შეამოწმოთ სწრაფი რომელი მომხმარებელი სახელი უკვე აღებული.

3. თქვენ უნდა ამოაჭრათ დუბლიკატი ელფოსტა იმეილი სიდან მაგრამ მათი შენახვა იმ თანმიმდევრობით, რომელიც დაკანიკულდა.

დუბლიკატი ამოღების პრობლემა

პრობლემა: ამოაჭრეთ დუბლიკატი, შეინახეთ თანმიმდევრობა

თქვენ იღებთ ელფოსტა დარეგისტრირების სიას. ზოგიერთმა ადამიანმა ორჯერ დაკანიკულდა. თქვენ გჭირდებათ ერთი ელფოსტა ადამიანზე, იმ თანმიმდევრობით რომელიც პირველად დაკანიკულდა.

მცდელობა 1: მხოლოდ სია (ნელი)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
    if email not in unique:  # O(N) scan of unique list
        unique.append(email)
# Works! But: O(N) check × N items = O(N²)

100 დაკანიკულებით, ეს აკეთებს ~5,000 ამოწმება. 10,000 დაკანიკულებით: ~50,000,000 ამოწმება.

მცდელობა 2: სიმრავლე + სია (სწრაფი)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
    if email not in seen:   # O(1) hash lookup
        seen.add(email)     # O(1) add to set
        unique.append(email) # O(1) append to list
# O(1) check × N items = O(N)

იგივე შედეგი. იგივე თანმიმდევრობა. მაგრამ: 10,000 დაკანიკულება ახლა მოითხოვს ~10,000 ამოწმება იმის ნაცვლად ~50,000,000.

დახრელის სიჩქარე

სიის-მხოლოდ ვერსია გაშვებული O(N²). სიმრავლე+სია ვერსია გაშვებული O(N).

თქვენ გაქვთ 10,000 ელფოსტა დაკანიკულება დუბლიკატი ამოღების.

საერთო ელემენტის ძებნა

პრობლემა: იპოვნეთ ელემენტი ორ სიაში

თქვენ გაქვთ ორი კლასის სია. თქვენ გჭირდებათ მოსწავლე დაკანიკულდა ორ კლასებში.

ნელი მიდგომა: მობილური მარყუჟი O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N iterations
    if student in class_b:     # M scans each time
        both.append(student)
# O(N × M) — each student scanned against all of class_b

სწრაფი მიდგომა: გადააკეთოთ ერთი სია სიმრავლეში O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) to build
both = []
for student in class_a:        # N iterations
    if student in class_b_set: # O(1) each time
        both.append(student)
# O(N + M) — build the set once, check N times at O(1) each

ან კი უფრო მარტივი Python-ის აგებული სიმრავლე კვეთა გამოყენებით:

both = set(class_a) & set(class_b)  # O(N + M)

& ოპერატორი პოულობს ყველა ელემენტი, რომელიც ჩნდება ორ სიმრავლეში.

გადაწერეთ სიჩქარე

სკოლას აქვს ორი კლუბი 200 წევრი. ეს კოდი პოულობს მოსწავლე ორ კლუბებში:

chess_club = [...]   # 200 names
art_club = [...]     # 200 names
both_clubs = []
for student in chess_club:
    if student in art_club:
        both_clubs.append(student)

გადაწყვეტილების ჩარჩო

თქვენი მონაცემთა სტრუქტურა გადაწყვეტილების ჩარჩო

ყოველ დროს თქვენ დაწერთ კოდი რომელიც ინახავს ელემენტის კოლექცია, აკითხვა:

1. გჭირდებათ ელემენტი თანმიმდევრობით? → სია

2. გჭირდებათ სწრაფი წევრობის შემოწმება? → სიმრავლე

3. გჭირდებათ ორივე თანმიმდევრობა და სწრაფი შემოწმება? → სიმრავლე + სია ერთად

4. გჭირდებათ დუბლიკატი? → სია (სიმრავლეები დაბრუნებას დუბლიკატი)

---

ამ გაკვეთილის მთავარი სხვაობა: იგივე პროგრამა, ერთი პრობლემის გადაჭრა, შეგიძლიათ გაშვება 1,000× მდე 1,000,000× სწრაფი მხოლოდ არჩევა სწორი მონაცემთა სტრუქტურა. რთიმე სერვილი. რთიმე რთული მათემატიკა. მხოლოდ აკითხვა: რა ოპერაციები ჩემი კოდი აკეთებს ყველაზე ხშირი? შემდეგ აირჩიეთ სტრუქტურა სადაც იმ ოპერაციები ღირს O(1) ნაცვლად O(N).

ეს გაკვეთილი დაფიქრებული სიები & სიმრავლეები. სხვა მონაცემთა სტრუქტურა გამოჩნდება (ლექსიკონი, ხეები, გროვები) რომელი ხელმისაწვდომი სხვა პრობლემა. გადაწყვეტილების ჩარჩო რჩება იგივე: გაიმეორეთ თქვენი ოპერაციები, შემდეგ აირჩიეთ სტრუქტურა რომელიც აყოფს მათ იაფი.

---

გსურთ უფრო ღრმა? ჩემთი Big O გაკვეთილი დაფიქრებული ზრდის ყვავილი & დაკვების გამოთვლა დეტალი. იხილეთ Big O: როგორ სწრაფი არის სწრაფი საკმარი?. ჩემთი unhamming კურსი დაფიქრებული რეალური-სამყაროს დეფექტი (MOAD-0001) რადგან ეს ზუსტი სია-რომელი სიმრავლე ფიქსი გამოთავო 1,000× დახრელი წარმოების პროგრამა. იხილეთ გამოტოვებული თავი: ალგორითმული კომპლექსურობა.

ამან კოდი

მოსწავლე დაწერა ეს კოდი რომელი რაოდენობა უნიკალური სიტყვა გამოჩნდება წიგნი:

words = book.split()           # list of all words
unique_count = 0
checked = []
for word in words:             # N words
    if word not in checked:    # scans checked list
        checked.append(word)
        unique_count += 1
print(unique_count)

წიგნი გაქვთ 100,000 სიტყვა.