Beş MOAD-0001 Formu

MOAD-0001, 60'dan fazla yazılım ekosistemlerinde beş belgelendirme formunda görüldü. Yapı: Bir dizi üyelik testi, aynı veya ilgili koleksiyon üzerinde bir döngelin içinde.

Beş Form

| Alan | Desen | Dizi Container | Doğru Container |

|--------|---------|---------------------|-------------------|

| Grafov seyr | if (!stack.contains(n)) in DFS/Tarjan | ArrayList | HashSet |

| Yolu/olayı tekrarsızlaştırma | TAILQ_FOREACH strcmp her talep için | bağlı liste | HashMap |

| Çarpışma izlemesi | findLinearSearch() her fizik saniyesi için | dizi | unordered_set |

| Kaynak ayırma filtresi | List.contains() stream filtresi içinde | ArrayList | HashSet |

| A* yol bulma açık listesi | LocalVector::find() her komşı için | vector | saklanan heap index |

Beşinde de aynı yapı var: Üyelik kontrolü, bir döngenin içinde, bir kaba container kullanarak ve bu soruyu yanıtlamak için kaba bir tarama gerektiğinde.

Tarama Anahtar Kelime Listesi

MOAD-0001 arama, üyelik testi anahtar kelimeleri iç döngilerde greplenebilecek demektir:

- Python: in bir list değişkeni ile, .count(), list.index()

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

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

- C++: std::vector::find(), manuel döngü ile == karşılaştırma

- Go: slices.Contains(), bir dizi üzerinde manuel döngü

Her durumda düzeltilen şey: Dizi containerını bir hash container ile değiştirin. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Bir anahtar kelime. Bir değiştirme. Nihai davranış değişikliği yok. N=1.000 için 1.000 kat hıza artış.

Kod Parçasını Denetle

Gerçek bir kod parçicasına MOAD-0001 desen tanımı uygulayın.

Bir Satır, Dört Dil

MOAD-0001 için düzelme dört dilde:

# Python
visited = []       # ÖNCE: O(N) üyelik
visited = set()    # SONRA: O(1) üyelik

// Java
List<Node> visited = new ArrayList<>();    # ÖNCE
Set<Node> visited = new HashSet<>();       # SONRA

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

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

Her durumda: aynı davranış, aynı çıktı, aynı testler geçer. Sadece büyüme oranı değişir.

Değişimin Yapmadığı Şeyler

- Algoritmanın mantıklı davranışı: derinlemesine ilk olarak derinlemesine ziyaret edilir

- Çıktı doğruluğu: DFS içinde aynı düğümlerin aynı sırasıyla ziyaret edildiği (aynı düğüm seti)

- Test sonuçları: doğruluk kontrolü yapan herhangi bir test devamla geçer

Değişimin Yaptığı Şeyler

- Üyelik testi: O(N) → O(1)

- Döngü toplamı: O(N²) → O(N)

- N=1.000'de: 1.000 kat hızlı

- N=10.000'de: 10.000 kat hızlı

Bir Sınırlama: Sıra

Hash konteynırlar (set, HashSet, unordered_set) sıralı ekleme sırasını koruma. Python 3.7+ 'da dict ekleme sırasını korur; basit set koruma. Java'da HashSet sıralı ekleme sırasını koruma; LinkedHashSet yapar.

Eğer üyelik ile birlikte sıralama önemliyse: iki yapı koruyun. O(1) üyelik testleri için set (veya HashSet). Dikdörtgen gezinti için ayrı bir list (veya ArrayList). Ya Python'da LinkedHashSet kullanın, Java'da, hem üyelik hem de sıralama sağlar.

MOAD-0001 grafolama gezinti için visited: bu düğümün önce görülüp görülmediği sorusunu yanıtlar. Sıra önemli değil üyelik sorunsal. Dikdörtgen gezinti sırası sıradan stack veya queue'dan, değil visited'den gelir.

Üyelik vs Sıralama

Tarjan'ın güçlü bağlı bileşen algoritmasında, onStack şu iki soruyu yanıtlar: (1) üyelik - şu an bu düğüm stack üzerinde mi? (2) DFS yolunun sonunda, bu düğüm görünene kadar stack'tan düğüm çıkar.

Naif bir uygulama List kullanarak onStack'ı üyelik sorusunu contains() ile yanıtlar - O(N) her kontrol, büyük grafikler için O(N²) toplam.

Bu, Bir Patch Değil, Bir Açıklama Nedeniyle

MOAD-0001, 60'dan fazla yazılım ekosistemindeki 1.000'den fazla doğrulanmış siteye sahiptir. Yapı araçlarında grafolar izlemesi, ağ yönlendiricilerinde yoldur tekrarlayan çıkarılması, oyun motorlarında çarpışma algılama, işletim sistemi planlayıcılarında kaynak tahsisi.

Her site: doğru kod. Her site: N eşişe ulaşana kadar O(N²) büyüme bekliyor.

Açıklama Akışı

Bir patch, üst düzey açıklama olmadan bir siteyi düzeltir. Oynak, bir sonraki sürümde, bir sonraki kütüphanede, bir sonraki dil sürümünde yine ortaya çıkar. Açıklama: Oynakı adlandırın, CWE-407 (Algoritmik Kararlılık: Yetersiz Algoritmik Kararlılık) olarak belgelendirin, tanıyıcı heuristikleri ve bir satır fixi yayınlayın. Sonra her geliştirici, açıklamayı okuyarak kendi örneklerini tanımlayabilir ve düzeltebilir.

Hamming bu durumu 'balık vermek vs. balık avlamanı öğretmek' olarak adlandırdı. Patch balık verir. Açıklama - MOAD-0001 adlandırıldı, oynak belgelendirildi, fix genelleştirildi - heuristiki öğretir.

Permacomputer Uzantısı

Hamming, nokta çözümleri üzerinde çalıştı: bu filtreyi düzeltin, bu kodu iyileştirin. Unhamming, açıklama katmanını ekler: oynakı adlandırın, heuristiki yayınlayın ve ortak alanına verin.

Bu, ekosistem ölçekli karma bilgi ilkesine uygulandığında daha etkili hale gelir. Bir araştırmacı, bir oynak adlandırır. Yüz geliştirici, kendi kod tabanlarında onu tanımlar. Bin satır O(N²) kod, O(N) hale gelir. Tüm onu kullanan altyapı daha hızlı olur.

Bu, dragon büyüyen (önemli problemlere çalışma, bilgiyi birleştirmeye çalışma, sistemler düşünme) gibi aynı ateşle (açıklama, ortak alan sahipliği, bir patrona ihtiyaç duymadan), farklı uçuş (açıkça açıklama, ortak alan mülkiyeti, bir patrona ihtiyaç duymadan) ile aynı uçar.