un — ალგორითმები პრაქტიკაში: კოდის მიმოხილვა & სირთულის ხარვეზები

un

სტუმარი

1 / ?

კოდის წაკითხვა ზრდის მაჩვენებლებისთვის

კოდის მიმოხილვა სისწორის და კოდის მიმოხილვა სირთულის თვალსაზრისით

სისწორის კოდის მიმოხილვა აჭერს ლოგიკის შეცდომებს: არასწორი პირობები, ინდექსის შეცდომები, დაკარგული null შემოწმებები. სირთულის ცნობიერი კოდის მიმოხილვა ხვდება ხარვეზის განსხვავებულ კლასს: კოდი რომელიც სწორად მუშაობს N = 100 დროს, მაგრამ კატასტროფულად იზრდება N = 100,000 დროს.

MOAD-0001 ნიმუში: list seen O(N²) vs set seen O(N) — ერთი სტრიქონის შესწორება

ეს გაკვეთილი უკავშირდება უფრო ღრმა კვლევას unhamming კურსში: გამოტოვებული თავი: ალგორითმული სირთულე მოიცავს Big O-ს სამუშაო ხარვეზების კონტექსტში, & MOAD-0001: ნალექიანი ხარვეზი აკავშირებს ნიმუშს 60+ პროგრამული უზრუნველყოფის ეკოსისტემის მიხედვით.

ორი მიმოხილვის ევრისტიკა

ერთმანეთში ჩასმული ციკლები ზრდის სირთულეს. ორი ერთმანეთში ჩასმული ციკლი N ელემენტზე ქმნის O(N²). სამი ქმნის O(N³). რეცენზირებისას: პირველად დაითვალეთ ციკლის გადაჩეხის სიღრმე.

თანმიმდევრობითი კონტეინერი ცხელი ციკლის შიგნით. ნებისმიერი .contains(), .includes(), .find(), ან in list შემოწმება ციკლის შიგნით ღირს O(N) თითო შემოწმებაზე. N გამეორების დროს: ჯამში O(N²). ეს ნიმუში ჩნდება სამუშაო კოდში ათობით ეკოსისტემაში — GHC Haskell კომპილატორი, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. იგივე შეცდომა, განსხვავებული კოდექსები.

მიმოხილვა: find_duplicates

გადახედეთ შემდეგ Python ფუნქციას სირთულის თვალსაზრისით:

def find_duplicates(items):
    seen = []
    duplicates = []
    for item in items:
        if item in seen:
            duplicates.append(item)
        else:
            seen.append(item)
    return duplicates

ჩაატარეთ სირთულის ცნობიერი კოდის მიმოხილვა: (a) რა არის ამ ფუნქციის დროის სირთულე? (b) რატომ? გამოთვალეთ ზუსტი სტრიქონი რომელიც ამას იწვევს. (c) გადაწერეთ ის O(N) სირთულით.

MOAD-0001: ნალექიანი ხარვეზი

იგივე ხარვეზი, სამოცი ეკოსისტემა

ნიმუში if x not in list: list.append(x) ციკლის შიგნით ჩნდება — იყო — სამუშაო კოდში ათობით პროგრამული უზრუნველყოფის ეკოსისტემაში:

- GHC (Haskell კომპილატორი): დამოკიდებულების გადამხსნელი, O(N²) N = 50,000 პაკეტზე, 17-წუთის აგება

- Python pip: დამოკიდებულების კონფლიქტის გადაწყვეტა

- Apache Maven: კლასის ბილიკის დუბლიკატების მოხსნა

- Rust Cargo: ფიჩურის ერთიანობა

- TypeScript კომპილატორი: მოდულის გადაწყვეტა

- Godot / Redot თამაშის ძრავი: კვანძის გრაფიკის გავლა

არცერთი ეს გუნდი შეცდომაში არ აღმოჩნდა. მათ სწორი კოდი დაწერეს მცირე N-ზე. N გაიზრდა. კოდი გამკრთალდა. ნიმუშს აქვს სახელი: MOAD-0001, ნალექიანი ხარვეზი. ნალექი: სწორი, უვნებელი თხელ ფენებში. დროთ, ფენები ჯამდებიან და გამკრთალდებიან.

შესწორება

ყველა შემთხვევაში: ჩანაცვლება თანმიმდევრობითი კონტეინერი ჰეშ კონტეინერით. ერთი სტრიქონი. ნულოვანი ქცევის ცვლილება სწორ შეყვანზე. 100–1,000× დაჩქარება რეალური N-ზე.

შესწორება ფუნქციონირებს, რადგან ორი ოპერაცია უნდა დარჩეს სწრაფი:

1. წევრობის შემოწმება: ეს ელემენტი რამდენჯერ იქნა ნახული მანამდე?

2. უკმყოს გამოშვება: ელემენტების დაბრუნება იმ თანმიმდევრობით, რომელიც მოჩნდა (ზოგჯერ საჭირო, ზოგჯერ არა).

set აკმენდებს (1)-ს O(1)-ში. თუ (2) ასევე მნიშვნელოვანია, შეინახეთ ცალკე სია უკმყოს გამოშვებისთვის და set წევრობის შემოწმებისთვის. ორი მონაცემთა სტრუქტურა, თითოეული ერთი ამოცანა აკეთებს.

რეცენზენტის პასუხი

pull request-ი ასწორებს MOAD-0001-ს პროექტის გრაფიკის გავლის ფუნქციაში. რეცენზენტი კომენტარს აკეთებს:

> "Set-ები არ ინახავენ ჩამატების თანმიმდევრობას — ეს ცვლის ქცევას."

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

ინტერვიუს ანალიზის ნიმუში

მოსალოდნელი ფორმატი

ალგორითმული სირთულის ანალიზი ჩნდება პროგრამული ინჟინერიის ინტერვიუებში. ძლიერი პასუხი მოყვება ოთხ-ნაწილის ნიმუშს:

1. აცნობეთ ამჟამინდელი სირთულე — O(?) დროისთვის, O(?) სივრცისთვის.

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

3. შემოთავაზეთ ოპტიმიზაცია — დაასახელეთ ცვლილება და მონაცემთა სტრუქტურა ან ალგორითმი რომელსაც ის წარმოადგენს.

4. აცნობეთ ახალი სირთულე — შესწორების შემდეგ რა არის დროის & სივრცის სირთულე?

მაგალითი:

კოდი: [ფუნქცია რომელიც ამოწმებს წევრობას სიაში ციკლის შიგნით]
ამჟამინდელი: O(N²) — `item in seen_list` არის O(N) თითო შემოწმებაზე × N გამეორება
ოპტიმიზაცია: ჩანაცვლება seen_list ის seen_set-ით (ჰეშ set)
შემდეგ: O(N) — set წევრობის შემოწმება არის O(1)

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

ეს გაკვეთილი უკავშირდება unhamming კურსს რომელიც ამ ზუსტ ნიმუშს ვრცელდება სამუშაო ხარვეზის გამოკვლევაზე 60+ ღია კოდის პროექტებში.

ინტერვიუ: has_common_element-ის ანალიზი

გამოიყენეთ ოთხ-ნაწილის ინტერვიუს ფორმატი ამ ფუნქციაზე:

def has_common_element(list_a, list_b):
    for item in list_a:
        for other in list_b:
            if item == other:
                return True
    return False

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