Birden fazla şehir arasında bir gezi planlıyorsanız ve en kısa rotayı bulmak istiyorsanız, iyi tanımlanmış bir deterministik işlemler dizisi olan algoritmalara başvurursunuz. Bu makale şehirler arasındaki en kısa rotaları bulan bir algoritma geliştirme sürecini takip ediyor. İlk çizimden Matplotlib ve NetworkX ile test ve görselleştirmeye, uygun veri yapılarını kullanarak optimizasyona kadar adım adım yolu gösterir. Bu, yalnızca işlevsel olarak doğru şekilde çalışan değil, aynı zamanda yüksek performanslı bir program oluşturur.
Duyurudan sonra devamını okuyun
Michael Inden, yirmi yılı aşkın mesleki deneyime sahip bir Java ve Python meraklısıdır. Halen Geliştirme Müdürü olarak çalışıyor, konferanslarda konuşuyor ve Java ve Python üzerine teknik kitaplar yazıyor.
Amaç, şehirleri en kısa yoldan birbirine bağlayan yol ağındaki rotaları bulmaktır. Grafikler modelleme için kullanılabilir. Şekil 1'de etiketli daireler şehirleri, numaralı bağlantı hatları ise mesafeli rotaları temsil etmektedir.
Bir grafik şehirler arasındaki mesafeleri görüntüler; sayılar mesafeleri temsil eder (Şekil 1).
Bu basitleştirilmiş harita için A'dan D'ye en kısa rotayı bulmak istiyoruz. Yalnızca birkaç şehir ve bağlantıyla tüm seçenekleri deneyebilirken, şehirler ve bağlantı sayısı arttıkça yaklaşım daha karmaşık hale gelir. 13'ün en kötü ve 6'nın en iyi olduğu aşağıdaki bağlantılar mümkündür:
A -> B -> C -> D => 5 + 1 + 7 = 13
A -> C -> B -> D => 2 + 1 + 3 = 6
A -> C -> D => 2 + 7 = 9
A -> B -> D => 5 + 3 = 8O notasyonuyla verimliliği anlamak
Hesaplamaların ve işlemlerin gerçekleştirilme hızı, programların iyi kullanılabilirliğiyle ilgilidir. Bu özellikle büyük miktarda veri için geçerlidir. O gösterimi, algoritmaların sınıflandırılmasına ve giriş kümesi arttıkça bir algoritmanın yürütme süresinin (veya bellek gereksiniminin) büyümesinin tanımlanmasına yardımcı olur. Bu, örneğin bir listenin artık 10 veya 20 yerine 100.000 veya daha fazla veri noktası içermesi durumunda etkileri tahmin etmenin mümkün olduğu anlamına gelir.
Duyurudan sonra devamını okuyun
O gösterimi, işlemlerin yürütme süresinin tahmin edilmesine yardımcı olur. Algoritma ve fonksiyonları karmaşıklık sınıflarına göre sınıflandırır. AO(n³) adım sayısı giriş miktarının küpü kadar artar. 100 giriş verisi ile çaba 100'dür3 hesaplama için, yani 1.000.000 adım. Karmaşıklık sınıfı ne kadar düşük olursa o kadar iyidir. “Karmaşıklık sınıflarına bölünmüş algoritmalarla O-gösterimi” tablosu diğer sınıfları gösterir; Şekil 2'de etkiler görselleştirilmiştir.
|
Karmaşıklık sınıflarına bölünmüş algoritmalarla O gösterimi |
||
|
gösterim |
anlamı, büyüme |
Örnek |
|
Ç(1) |
devamlı |
Bir liste öğesine erişme |
|
O(log n) |
logaritmik |
İkili arama |
|
AÇIK) |
doğrusal |
tüm elemanlarda basit döngü |
|
O(n log n) |
doğrusal-logaritmik |
verimli sıralama algoritmaları (birleştirme sıralaması gibi) |
|
O(n²) |
kare |
çift iç içe döngü |
|
AÇIK3) |
küp |
üçlü iç içe döngü |
Grafikler, girişin boyutuna bağlı olarak işlem sayısını göstermektedir (Şekil 2).
O notasyonunu kullanan bir sınıflandırma, donanım ekipmanı, uygulama ayrıntıları ve seçilen programlama dillerinden bağımsız olarak yürütme sürelerini ölçeklenebilirlik özelliklerine göre karşılaştırmak için özellikle önemlidir.
Basitleştirilmiş değerlendirme için, küçük sabitler veya daha küçük terimler ve faktörler büyük girdiler için ihmal edilebilir olduğundan, değerlendirmede yalnızca baskın terim dikkate alınır. hayır formülünde3 + 4n² + 3n + 7, basitleştirmeler nedeniyle çalışma zamanı sınıfı O(n)'yi takip eder3).
Fikirden programa
Sistematik bir yaklaşım, daha küçük programlar ve özellikle karmaşık yazılım projeleri için bile işlevsel, bakımı yapılabilir, yüksek performanslı kod elde etmenin anahtarıdır.
1. Sorunu anlayın ve analiz edin
- hangi sorunun çözülmesi gerektiğini netleştirin ve onu alt görevlere bölün;
- Alt görevler için kanıtlanmış çözümlerin mevcut olup olmadığını kontrol edin; sıralanmış veritabanlarında yüksek performanslı aramalar için ikili arama, en kısa yollar için Dijkstra algoritması;
- giriş ve çıkış verilerini tanımlayın;
- Sınır koşullarını ve özel durumları göz önünde bulundurun.
2. Kaba bir yapı planlayın ve geliştirin
- sorunu alt görevlere ayırın;
- süreçleri doğal dilde formüle etmek veya özetlemek;
- Uygun veri yapılarını seçin (listeler, sözlükler, yığınlar).
3. Uygulama
- Kaynak kodunu açıkça ayrılmış işlevler veya sınıflar halinde düzenleyin;
- Okunabilirlik ve anlaşılırlığa dikkat edin, anlamlı isimler ve (eğer uygunsa) ek yorumlar kullanın;
- Geliştirme süresinden tasarruf etmek için mevcut kütüphaneleri kullanın (örn. görselleştirme için Matplotlib).
4. Test (kanıt testi ve birim testleri)
- Nasıl çalıştığını deneyin;
- İşlevselliği doğrulamak ve kenarları ve özel durumları kapsamak için birim testleri yazın.
5. Performansı ölçün
- 100, 10.000 ve 1.000.000 veri seti gibi küçük, orta ve büyük veri setleri üzerinde ölçümler gerçekleştirin;
- Darboğazların belirlenmesi, ancak bunlar genellikle yalnızca çok büyük veri kümelerinde belirginleşir.
6. Optimize edin
5. adımda zayıflıklar keşfedilirse alt problemler için uygulamaya ve seçilen algoritmalara daha yakından bakmalısınız.
- Karmaşıklığı resmi olarak değerlendirmek için O notasyonunu kullanın: hangi döngüler? Arama nasıl ve nerede gerçekleşiyor: doğrusal mı yoksa ikili aramayla mı? Farklı eylemler için yürütme süresi O(1) olabilir
O(log n) veya O(n)Anlam. - Daha uygun algoritmalar veya daha verimli veri yapıları kullanın.
Dağıtımı ve testi bir arada yapın
Pratikte 3. ve 4. adımlar her zaman birbirinden bağımsız olarak gerçekleştirilmez. Sonuçları iyi tahmin edebiliyorsanız test senaryoları oluşturmaya başlamanız mantıklı olacaktır. Ancak bazen uygulamak için önce bir fikre ve prototipe ihtiyacınız olur. Özellikle büyük programlama projelerinde uygulama ve test aşamasında ek gereksinimler ortaya çıkar.
Aşağıdaki süreç pratikte kendini kanıtlamıştır ve bir algoritma geliştirirken de kullanılabilir.
Bir yanıt yazın