MOAD-0001-ის ხუთი ფორმა

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

ხუთი ფორმა

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

სკანირების საკვანძო სიტყვების სია

MOAD-0001-ის აუდიტი ნიშნავს წევრობის შემოწმების საკვანძო სიტყვების მოძებნას ციკლებში:

- Python: in list ცვლადთან ერთად, .count(), list.index()

- Java: ArrayList.contains(), List.contains(), LinkedList.contains()

- JavaScript: Array.includes(), Array.indexOf(), Array.find()

- C++: std::vector::find(), ხელით დაწერილი ციკლი == შედარებით [BLOCK_TYPE SECTION/STEP]

- Go: slices.Contains(), ხელით დაწერილი ციკლი slice-ზე [BLOCK_TYPE SECTION/STEP]

ყველა შემთხვევაში გამოსწორება: თანმიმდევრული კონტეინერის ჩანაცვლება ჰეშ-კონტეინერით. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}. [BLOCK_TYPE SECTION/STEP]

ერთი საკვანძო სიტყვა. ერთი ჩანაცვლება. ქცევის ნულოვანი ცვლილება. 1,000× აჩქარება N=1,000-ზე. [BLOCK_TYPE SECTION/STEP]

კოდის ფრაგმენტის აუდიტი [BLOCK_TYPE SECTION/STEP]

MOAD-0001 შაბლონის ამოცნობის გამოყენება რეალურ კოდის ფრაგმენტზე. [BLOCK_TYPE SECTION/STEP]

ერთი ხაზი, ოთხი ენა

MOAD-0001-ის გამოსწორება ოთხ ენაზე:

# Python
visited = []       # BEFORE: O(N) წევრობა
visited = set()    # AFTER:  O(1) membership

// Java
List<Node> visited = new ArrayList<>();    // BEFORE
Set<Node> visited = new HashSet<>();       // AFTER

// JavaScript
const visited = [];      // BEFORE: Array.includes() O(N)
const visited = new Set(); // AFTER: Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)

// Go
visited := []NodeID{}              // BEFORE: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // AFTER: map lookup O(1)
// _, ok := visited[n]  for membership check
// visited[n] = struct{}{}  for insertion

ყველა შემთხვევაში: იგივე ქცევა, იგივე შედეგი, იგივე ტესტები გადის. იცვლება მხოლოდ ზრდის სიჩქარე.

რას არ ცვლის გამოსწორება

- ალგორითმის ლოგიკური ქცევა: სიღრმის-პირველი მაინც სიღრმის-პირველად მოინახულებს

- გამომავალი სისწორე: იგივე კვანძები ივლის იმავე თანმიმდევრობით (DFS-ის ფარგლებში)

- ტესტის შედეგები: ნებისმიერი ტესტი, რომელიც ამოწმებს სისწორეს, კვლავ გაივლის

რას ცვლის გამოსწორება

- წევრობის შემოწმება: O(N) → O(1)

- მარყუჟის ჯამური დრო: O(N²) → O(N)

- N=1,000-ზე: 1,000-ჯერ უფრო სწრაფი

- N=10,000-ზე: 10,000-ჯერ უფრო სწრაფი

ერთი შეზღუდვა: თანმიმდევრობა

ჰეშ კონტეინერები (set, HashSet, unordered_set) არ ინარჩუნებენ ჩასმის თანმიმდევრობას. Python 3.7+-ში dict ინარჩუნებს ჩასმის თანმიმდევრობას; ჩვეულებრივი set არა. Java-ში HashSet არ ინარჩუნებს თანმიმდევრობას; LinkedHashSet ინარჩუნებს.

თუ თანმიმდევრობა მნიშვნელოვანია წევრობასთან ერთად: შეინახეთ ორი სტრუქტურა. set (ან HashSet) O(1) წევრობის შემოწმებისთვის. ცალკე list (ან ArrayList) მოწესრიგებული გავლისთვის. ან გამოიყენეთ LinkedHashSet Java-ში, რომელიც ორივეს უზრუნველყოფს.

MOAD-0001-ისთვის გრაფის გავლაში: visited პასუხობს ორობით კითხვას (უკვე ნანახია თუ არა ეს კვანძი?). თანმიმდევრობა არ არის მნიშვნელოვანი წევრობის კითხვისთვის. გავლის თანმიმდევრობა მოდის სტეკიდან ან რიგიდან, არა visited-დან.

წევრობა vs თანმიმდევრობა

ტარჯანის ძლიერად დაკავშირებული კომპონენტების ალგორითმში onStack აკონტროლებს, რომელი კვანძები რჩება მიმდინარე DFS გამოძახების სტეკზე. მან უნდა უპასუხოს ორ კითხვას: (1) წევრობა — არის თუ არა ეს კვანძი ამჟამად სტეკზე? (2) DFS გზის ბოლოს, ამოიღოს კვანძები თანმიმდევრობით, სანამ ეს კვანძი არ გამოჩნდება.

ნაივური იმპლემენტაცია იყენებს List-ს onStack-ისთვის და წევრობის კითხვას პასუხობს contains()-ით — O(N) თითო შემოწმებაზე, O(N²) საერთო დიდი გრაფებისთვის.

რატომ არის ეს გამჟღავნება და არა პაჩი

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

ყველა საიტი: სწორი კოდი. ყველა საიტი: O(N²) ზრდა, რომელიც ელოდება N-ის გადაკვეთას გარკვეულ ზღვარს.

გამჟღავნების მილსადენი

პაჩი ზემოთგამჟღავნების გარეშე ასწორებს მხოლოდ ერთ საიტს. შაბლონი მეორდება შემდეგ ვერსიაში, შემდეგ ბიბლიოთეკაში, შემდეგ ენობრივ პორტში. გამჟღავნება: დაასახელეთ შაბლონი, დააფიქსირეთ როგორც CWE-407 (ალგორითმული სირთულე: არაეფექტური ალგორითმული სირთულე), გამოაქვეყნეთ ამოცნობის ევრისტიკები და ერთსტრიქონიანი გამოსწორება. შემდეგ ყველა დეველოპერს, ვინც წაიკითხავს გამჟღავნებას, შეუძლია ამოიცნოს და გამოასწოროს საკუთარი შემთხვევა.

ჰამინგი ამას უწოდებდა „თევზის მიცემა თევზაობის სწავლების წინააღმდეგ“. პაჩი იძლევა თევზს. გამჟღავნება — MOAD-0001 დასახელებული, შაბლონი დოკუმენტირებული, გამოსწორება განზოგადებული — ასწავლის ევრისტიკას.

პერმაკომპიუტერის გაფართოება

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

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

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