Haftalık C++ yazılarımın bir diğeri ile tekrar birlikteyiz, sevgili yazılımperver dostlarım. Bu çok uzun olmayan yazım ile birlikte, bir kod parçasının/problemin yeni gelen C++ kabiliyetleri ile nasıl geliştiğine, farklı perspektiflerden bakıyor olacağız.
Bu bağlamda bakacağımız kod parçası, “quicksort” ile ilgili olacak. “Quicksort” ‘a ilişkin bir fikriniz yok ise hemen bir göz atmak ya da hatırlamak için, şu sayfaya, göz atabilirsiniz. Aslına bakarsanız, ilk C++ sürümleri (C++ 98), <algorithm> başlık dosyası aracılığı ile bu tarz sıralama API’leri sunuyorlardı. Bu API’ler ile birlikte hem dizi hem de konteynerleri sıralayabiliyorduk:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <algorithm> int vals[] = {5, 10, 0, -5, 42}; // İşaretçiler üzerinden, başlangıç ve bitişleri veriyoruz ve küçükten büyüğe doğru sıralanıyor std::sort(vals, vals + 5); // Konteynerler için de benzer şekilde ilgili iterator'ler ile bunu yapabiliyorduk std::vector<int> numbers; // Bu da varsayilan olan küçükten büyüğe doğru sıralamakta std::sort(numbers.begin(), numbers.end()); |
Eğer hala C++ 98 kullanıyor, çok performans kritik bir ihtiyacınız yok ve de tekerleği baştan icat etmek istemiyorsanız bu API’yi kullanabilirsiniz. Bu bize ne sağlıyor:
- Kolay ve anlaşılır kullanım,
- Derleme zamanı kontroller,
- Ortalama O(nlg(n)) karmaşıklık,
- Peki sadece bu sıralama API’si mi sunuluyordu, hayır. Aşağıdakiler de C++ 98 ile sunulan diğer API’ler
- stable_sort(), partial_sort(), nth_element(), partition(), stable_partition().
Şimdi gelelim C++ 11’e. Daha önce sizlerle de işlediğimiz std::array ve std::initializer_list ile yukarıdaki kodu artık aşağıdaki gibi yazabiliyoruz.
|
1 2 3 4 5 6 7 |
#include <algorithm> std::array<int, 5> numbers{5, 10, 0, -5, 42}; std::sort(numbers.begin(), numbers.end()); std::vector<int> numbers{5, 10, 0, -5, 42}; std::sort(numbers.begin(), numbers.end()); |
Aslına bakarsanız işlevsel çok bir farklılık olmasa da, artık API’lerin kullanımı ortaklandı. Normal diziler yerine, daha önce de bahsettiğim gibi, aksi bir ihtiyaç olmadığı müddetçe daha kullanışlı olan std::array kullanımına geçtik ve vektör konteyneri için de tek tek veri eklemek zorunda kalmadık. Her iki veri yapısını da std::initializer_list ile oluşturur oluşturmaz ilklendirebildik. Peki bitti mi?
Elbette hayır. Şimdi C++ 17’e gelelim. Peki C++ 17 bize ne sağlıyor. “Class Template Argument Deduction/CTAD” kabiliyeti ile birlikte (biliyorum bu konuyu henüz işlemedik ama artık işlemek farz oldu 🙂 ), template’lar için tip ve adet bilgisini (yani “<int>” ve 5’i) de yazmamıza gerek kalmıyor (tabi burada tiplerin çıkarılabiliyor olması lazım). Şimdi ne oldu kodumuz:
|
1 2 3 4 5 6 7 |
#include <algorithm> std::array numbers{5, 10, 0, -5, 42}; std::sort(numbers.begin(), numbers.end()); std::vector numbers{5, 10, 0, -5, 42}; std::sort(numbers.begin(), numbers.end()); |
Ve son olarak C++ 20 ile birlikte, sunulan “ranges” kütüphanesi ile, begin()/end()’leri de yazmamıza gerek kalmıyor :D. Ne oluyor bu durumda:
|
1 2 3 4 5 6 7 |
#include <algorithm> std::array numbers{5, 10, 0, -5, 42}; std::ranges::sort(numbers); std::vector numbers{5, 10, 0, -5, 42}; std::ranges::sort(numbers); |
Evet arkadaşlar, kullanılabilirlik perspektifinden ilk kodun, C++ 20’ye kadar nasıl bir değişim geçirdiğini, bu basit kullanımda görmüş olduk. Elbette, her yeni kabiliyet için bu mümkün ya da bu kadar açık olmayabilir.
Bunun ile birlikte, yeni C++ kabiliyetlerini kullanırken, özellikle okunabilirlik ve kullanım kolaylığı anlamında fark yaratacak kabiliyetlere öncelik vermekte fayda olduğuna inanıyorum.
Şimdi, yine bu örnek üzerinden bize performans anlamında yeni C++ kabiliyetleri ne sunabilir ona bakalım. Bunun için de, yukarıdaki tam sayılar yerine basit bir veri yapısı tanımlayalım:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <algorithm> class Person { std::string mName; std::vector<double> mValues; ... // Bu sınıfı sıralamada kullanabilmek için < operatörünün tanımlanmış olduğundan emin olalım }; std::vector<Person> ademoglu; std::sort(ademoglu.begin(), ademoglu.end()); |
C++ 98 durumunda, burada kullandığımız veri yapısından ötürü, konteyner içerisindeki ilgili nesneler sıralama esnasında kopyalanmak durumundaydı.
C++ 11 ile bunun önüne geçebildik, peki bunu ne ile sağladık? Elbette “move semantics” ile (hemen yazımızı da referans olarak ekleyelim, boşuna mı yazdık 😉 ) Peki, bu durumda kod içerisinde ne gibi güncellemeler yaptık. İşte, en güzel tarafı burada. Hiç bir değişiklik yapmadan, C++ 11 desteği olan bir derleyici ile yukarıdaki kodu, sadece yeniden derlediğinizde, neredeyse 10 kat performans kazancı sağlamış oluyorsunuz. O la la.
Burada bitti mi? Elbette hayır. C++ 17′ de ise gelen paralel STL algoritmaları ile de (ki bu konuda sonraki işlenecekler konusu listesinin üst sıralarında), olay bambaşka bir boyut kazanıyor. Hemen koda bakalım, sonra çayımızı alıp yorumlayalım 🙂
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <algorithm> class Person { std::string mName; std::vector<double> mValues; ... // Bu sınıfı sıralamada kullanabilmek için < operatörünün tanımlanmış olduğundan emin olalım }; std::vector<Person> ademoglu; std::sort(std::execution::par, ademoglu.begin(), ademoglu.end()); |
Normal şartlarda aslında, bu tarz sıralama algoritmalarını hızlandırmak için birden fazla thread kullanıp, farklı koşum mekanizmaları ile paralellik sağlayabilirsiniz ama bunun için elinizi biraz kirletmeniz gerekiyor. İşte STL, sizleri bundan kurtarıyor, kurtarmakla da kalmıyor bir çok opsiyon da sunuyor. Çok detayına girmeden burada kullanılabilecek yöntemleri şu şekilde özetleyebiliriz:
- Sıralı (Sequential Execution): Sıra korunarak, normal çalışma prensibi, varsayılan yaklaşım.
- Sıralı Paralel (Parallel Sequenced Execution): Mümkünse, işlem farklı thread’lere dağıtılsın ama sıra da gözetilsin, std::execution::par kullanımı.
- Sırasız Paralel (Parallel Unsequenced Execution): Aslında, ilgili algoritmanın SIMD, vektörizasyonuna karşılık gelen kullanıma karşılık geliyor ki, uygun algoritmalar için oldukça fazla performans kazancı sağlayabilir ama algoritmanın buna uyumlu olması gerekir elbette. Bu kullanım için de std::execution::par_unseq kullanılmalıdır.
Aşağıda, bu üç yönteme ilişkin güzel bir gösterimi bulabilirsiniz:
Burada dikkat edilmesi gereken, özellikle sırasız paralel kullanımına ilişkin şu an bir kontrol bulunmamaktaymış, fakat ileride buna ilişkin de bir takım güncellemeler gelebilir.
Bu kütüphane ve VS’de kullanımına ilişkin https://devblogs.microsoft.com/cppblog/using-c17-parallel-algorithms-for-better-performance/ kaynağına göz atabilirsiniz.
Evet arkadaşlar, yazımı bitirmeden önce, bu yazıyı yazmaya beni iten ve ana kaynağım olan videoya da (ve de başlığın kaynağına 🙂 ) kısaca değineyim. Açıkçası bir süre önce, QT ile ilgili bir video izlerken denk geldim bu videoya (otomatik izlemeden düştü diyebilirim, sağolasın youtube), ilk başta haftalık video yazısı olarak paylaşacaktım ama açıkçası içerik olarak çok hoşuma gittiği için yazıya döküp sizler ile paylaşmak istedim.
Bu video içerisinde Nicolai (ki kendisinin C++ile ilgili bir çok kitabı var ve benim de başvuru kaynaklarımdan birisidir), C++’ın, C++98’den, C++ 20’ye kadar olan gelişimini üç temel perspektiften; kullanılabilirlik, performans ve uyarlanabilirlik açısından, örnek kodlar üzerinden aktarıyor. Bu yazımda ilk ikisine değindim. Açıkçası çok uzatmamak adına, uyarlama ile ilgili kısma yazımda değinmedim ama hızlıca özetleyeyim (yine dayanamdım 🙂
- Yeni tanımladığımız sınıfı sıralamada kullanmak için eklediğimiz < operatör yanında, karşılaştırma anlamında tam bir destek sunmak için diğer altı karşılaştırma operatörü tanımlama gerekliliği, fakat bunun da C++ 20 ile gelen uzaygemisi operatörü ile çözümlenebileceğine değiniyor. Bu konuya da, önceki yazımda değinmiştim.
- Bir diğer konu, daha karmaşık sıralama için bir kriter kullanımı ihtiyacı:
- C++ 98’de bunu, std::sort’a geçirilen ve dışarıda tanımlanmış bir fonksiyon ile (ya da fonksiyon nesneleri ile) gerçekleştirebilirken, C++ 11’de bunu lambda tanımlamaları ile kullanıldığı yerde (“on the fly”), hatta çalışma zamanı girdileri ile tanımlayabiliyorsunuz,
- C++ 14 ile gelen jenerik lambda’lar ile tipten de soyutlayabiliyorsunuz,
- Ve son olarak C++ 20 ile gelen “Concepts” ile geçirilen argümanlara/template’lara ilişkin gereksinim/kısıt tanımlayabiliyorsunuz.
Bir sonraki yazımda görüşmek dileğiyle, kendinize iyi bakın ve sağlıkla kalın.
Kaynaklar
- https://youtu.be/ZQWg1koOKy8
- https://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm
- https://en.cppreference.com/w/cpp/language/class_template_argument_deduction
- https://en.cppreference.com/w/cpp/algorithm/ranges/sort
- https://en.cppreference.com/w/cpp/ranges
- https://devblogs.microsoft.com/cppblog/using-c17-parallel-algorithms-for-better-performance/