string’deki tüm karakterler eşsiz mi?

Elimizde std::string sınıfı türünden bir nesne var. Bu string nesnesinin tuttuğu yazının tüm karakterlerinin eşsiz (unique) olup olmadığını sınayan bir işlev yazmamız isteniyor. İşlevimiz gönderilen yazıda yinelenen bir karakter yok ise true değere aksi halde false değere geri dönecek. Programcılarla yapılan mülakatlarda sık sorulan bu sorunun çözümlerini incelerken STL‘in araçlarını da hatırlamamız gerekecek. Önce aklımıza ilk gelen çözüm ile başlayalım:

char türü en fazla 256 farklı değer taşıyabileceğinden yazımız 256 karakterden daha uzun ise tüm karakterlerin eşsiz olmasına olanak yok. İlk if deyimiyle bu durum sınanıyor. Daha sonra yer alan iç içe for döngüleriyle yazının i indisli öğesi olan karakterden yazının geri kalan kısmında bir tane daha bulunup bulunmadığına bakılıyor. Yazıda bir karakterden ikinci bir tane bulunduğunun anlaşılması durumunda işlev yine false değeriyle geri dönüyor. İşlevin akışı for döngülerinden çıkarsa yazının her karakteri eşsiz demektir.
Yazının uzunluğuna bağlı olarak dönen iç içe iki döngü olduğundan algoritmanın karmaşıklığının O(n2) olduğunu söyleyebiliriz. Öte yandan algoritmamız yazımızın kullandığı bellek alanı dışında ek bir bellek alanı kullanmıyor.

Şimdi de aşağıdaki çözümü inceleyelim:

İşlevimiz alacağı yazının bir kopyasını çıkartacağından referansla çağrı (call by reference) yerine değerle çağrıyı (call by value) tercih ettik. Eğer işlevi

imzasıyla tanımlasaydık sıralama işlemini yapabilmek için parametre referansa çekilen stringin yine yerel bir kopyasını çıkartmak zorunda kalacaktık. İşlevimizin parametresi bir string nesnesi olduğundan derleyici gereken durumlarda kopyalamayı elimine edebilecek ayrıca işlevimize çağrı yapan kod taşıma semantiğinden faydalanabilecek.
İşlevimizde yalnızca üç deyim var. Yazı 256 karakterden daha uzun ise işlevimiz yine false değerle geri döndü. Standart kütüphanenin sort algoritmasıyla stringimizdeki karakterleri küçükten büyüğe sıraladık:

Şimdi return deyiminde çağrılan adjacent_find algoritmasına bir göz atalım:

adjacent_find algoritması ile bir aralıkta (range) tutulan değerlerden aynı değerde olan ardışık öğelerin ilkini bulabiliyoruz. İşlevin geri dönüş değeri ardışık olarak yinelenen ilk öğenin konumu. Eğer peş peşe aynı değerde olan hiçbir öğe yoksa işlevimiz kendisine gönderilen end konumunu geri döndürüyor. Aşağıdaki örnek kodu inceleyin:

Algoritmamızı sıralanmış bir kap için çalıştırdığımızda eğer kaptaki tüm öğeler eşsiz ise aramanın başarısız olması gerekiyor:

Peki kullandığımız algoritmanın karmaşıklığı ne?

kopyalama işlemi O(n)
sıralama işlemi O(n * log(n))
adjacent_find O(n)

Bu durumda algoritmamızın karmaşıklığı O(n * log(n)). Sınanacak stringin bir kopyasını çıkarttığımızdan yazı uzunluğu kadar ek bir bellek alanı kullanmış olduk.

Şimdi de şu çözüme bakalım:

std::set kabında bir değerden yalnızca bir tane tutabiliyoruz. Aynı değerden ikincisi sete sokulmak istendiğinde ekleme işlemi başarılı olmuyor. std::set kabında değerle arama ve değerle ekleme işlemleri logaritmik karmaşıklıkta. Algoritma son derece basit: Yazımızı dolaşıp yazımızın her karakterini bir sete koymaya çalışıyoruz. Eğer aynı karakterden bir ikincisi ile karşılaşırsak bu değer zaten daha önce set‘e koyulmuş olacağından ikinci ekleme işlemi başarısız olacak.
set sınıfın insert üye işlevinin geri dönüş değeri ile ekleme işleminin başarısını sınayabiliyoruz. İşlevin geri dönüş değeri:

türünden. Eğer ekleme işlemi gerçekleşirse geri dönüş değeri olan pair‘in second isimli öğesi false değerinde olacak.

ifadesi doğru ise yazımızdaki tüm karakterler eşsiz değildir.

Yazıyı uzunluğu boyunca dolaşma işlemi O(n),
set’e ekleme işlemleri O(log(n))
karmaşıklığında olduğundan algoritmamızın O(n) karmaşıklığında olduğunu söyleyebiliriz. Bellek kullanımı açısından baktığımızda da oluşturulan set‘in kullandığı ek bir bellek alanı var.

char türü 256 farklı değerden birini tutabileceğine göre 256 öğeye sahip bir kabı (container) hangi karakterlerin stringde olduğu bilgisini tutmak için kullanabiliriz, değil mi? Standart kütüphanenin bitset sınıfı ile 256 ayrı bayrak değerini bir arada bit seviyesinde tutmak  mümkün. Yeni çözümümüzü inceliyoruz:

Yukarıdaki kodda bir bayrak dizisi olarak görev yapan bset isimli bitset nesnesinin 256 biti var. Sınıfın varsayılan kurucu işlevi 256 biti de 0 değeriyle başlatıyor. Sınıfın test isimli üye işleviyle indisi verilen bir bitin 1 olup olmadığını sınayabiliyoruz. Sınıfın set isimli işleviyle de indisi verilen bir biti birleyebiliyoruz. Aralık tabanlı for döngüsü ile yazıyı dolaştık ve bset‘in yazının karakteri indisli bitinin 1 olup olmadığına baktık. Eğer bu bit 0 ise bu biti birledik. Döngünün herhangi bir turunda bset‘in c indisli biti eğer 1 ise aynı karakterden ikincisiyle karşılaşmışız demektir.
Bu algoritmanın da karmaşıklığımnın O(n) olduğu açık. bitset nesnesi için ise yalnızca 32 byte’lık bir bellek alanı kullanılıyor.

Necati Ergin

C ve Sistem Programcıları Derneğinde eğitmen olarak çalışıyor.

Bunlar da ilginizi çekebilir

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Kod Eklemek İçin Okuyun