İPUCU

Algoritma Algoritma geliştirme için gerekli tekniklerin paylaşıldığı alandır.

Seçenekler

Algoritma Challanges | #1

26-01-2019 23:09
#1
kondanta - ait Kullanıcı Resmi (Avatar)
Üye
Üyelik tarihi:
07/2017
Nereden:
$ebp
Mesajlar:
908
Teşekkür (Etti):
33
Teşekkür (Aldı):
262
Konular:
36

Merhabalar, şu aralar leetcode, hackerrank gibi sitelerdeki challengeları çözmeye adadım kendimi. Daha sonrasında, bunu neden forumda bir chain haline getirmeyeyim ki diye. Öncelikli olarak not düşeyim; Problemlerde aksi iddia edilmediği sürece time complexity üzerine odaklı çözüm yapmaya çalışacağım.

Gelelim problemimize. Çözmeye çalıştığım problem diyor ki: "Elimizde bir array olduğunu varsayalım. İçerisinde random rakamlar bulunmakta. Bu array ile birlikte size bir de hedef rakam vereceğiz. Amacınız, arraydaki elemanları kullanarak toplamları verilen hedef sonuca ulaşan 2 değeri return etmek. Kısıtılama olarak, her rakam sadece bir kez kullanılacaktır ve sadece 2 indis return edeceksiniz diye iki ibare mevcut. İndisden kasıt ise, rakamın array içerisinde bulunduğu yer. Soru ne kadar kolay görünse de en sondaki ulaştığım sonuca kadar toplam 37 dakika 44 saniye harcamışım.

Çözüm
Çözüm için ilk yaklaşımım tabii ki de brute force oldu. Yani ilk önce çalışan bir algoritma oluşturmam gerekliydi. Dil olarak C++ kullandım, bilginize.
Not: Tavsiyem, önce kendiniz uğraşın birazcık. Daha sonrasında buradan çözüme bakarsınız.
İlk aklıma gelen çözüm yöntemleri tabii ki başarısızlık ile sonuçlandı. Akabinde ise aklıma gelen ve ilk çalışan algoritmam şu şekildeydi:
Kod:
vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            for(int j = i+1; j < nums.size(); j++){
                if(nums[j] == target - nums[i]){
                    res.push_back(i);
                    res.push_back(j);
                    return res;
                }
                    
            }
        }
        return nums;
    }
Burada ne yaptığımdan kısaca bahsedecek olursam, array içerisindeki ilk indis için i değişkenini, bir sonraki indis için ise j değişkenini kullandım. Bu şekilde "target" değere ulaşana kadar arrayin içerisindeki tüm elemanları bir kez ziyaret etmiş oldum. Bu da bana run time olarak O(N^2)'e patlıyor. Bilmiyor iseniz, Big O notasyonu nedir diye araştırınız.


Şimdi gelelim çözümün geri kalan optimizasyon kısmınaa. Evet elimizde bir çözüm var, lakin pek de optimal değil yukarıdaki resimde gördüğünüz gibi. Şimdi burada ki asıl trick ise, böyle bir algoritmayı nasıl optimize edebiliriz sorusu. Şöyle biraz düşündükten sonra aklıma hashmap geldi. Tabii ki veri yapılarına ne kadar aşina iseniz o kadar kardasınız burada. Şuraya şöyle de küçük bir bilgi düşeyim.

Kod:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> m;
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            int result = target - nums[i];
            if(m.count(result)) {
                res.push_back(m[result]);
                res.push_back(i);
                return res;
            }
            m.insert (std::pair<int, int>(nums[i], i));
        }
        return nums;
    }


Yeni çözümümüz ise O(1) de çalışmakta yani performans bazında çok yüksek bir artış söz konusu. Lakin bu artış tabii ki bedavaya gelmiş bir şey değil, memoryde kullandığımız alan da bir artış söz konusu. Buradaki olay ise, elimizdeki hashmap'i doldururken her seferinde toplamı bize verecek olan rakamın hashmap girdisi olup olmadığını kontrol etmek. Ve yukarıdaki diagramında gösterdiği gibi, unordered_list üzerinde yaptığımız arama işlemleri constant, yani sabit zaman almakta.



Performans ölçütü olarak, şu resmi gösterebilirim. Elimizdeki arraylerin içerisinde maximum 10-15 eleman olduğunu varsayarak düşünebilirsiniz. Bu eleman sayısının milyonlarca olduğunu hayal ettiğinizde aradaki farkı hayal bile etmek istemezsiniz diye düşünüyorum.


Umarım bir şekilde faydalı olmuştur, forumda bu tarz paylaşımları arttırmayı hedefliyorum. Bir sonraki problem ve çözümüyle görüşmek dileğiyle

Kullanıcı İmzası

許可水月

26-01-2019 23:29
#2
Üyelik tarihi:
09/2018
Mesajlar:
1.017
Teşekkür (Etti):
590
Teşekkür (Aldı):
207
Konular:
15
Uğraşılmış bir konu gibi duruyor.
Kullanıcı İmzası

Son ırmak kuruduğunda, son ağaç kesildiğinde, son balık tutulduğunda, beyaz adam paranın yenmeyecek bir şey olduğunu anlayacak.
27-01-2019 15:43
#3
Heaven - ait Kullanıcı Resmi (Avatar)
Üye
Üyelik tarihi:
01/2016
Mesajlar:
1.240
Teşekkür (Etti):
131
Teşekkür (Aldı):
244
Konular:
49
Harika konu! Elinize sağlık.
Kullanıcı İmzası
Ankara hareketlerine dikkat edsin

˜”*°•.Bir yıldızın yarısı, biri sensin biri ben˜”*°•.
★-léonαrdo★
27-01-2019 15:46
#4
asdzekee - ait Kullanıcı Resmi (Avatar)
Üye
Üyelik tarihi:
01/2019
Nereden:
Tümen
Mesajlar:
413
Teşekkür (Etti):
12
Teşekkür (Aldı):
47
Konular:
35
Emek var eline sağlık . .
Kullanıcı İmzası
Arsızlık Kazanır
-MrX

byZehirX <3
27-01-2019 16:15
#5
"P4RS - ait Kullanıcı Resmi (Avatar)
Bilgi Teknolojileri Ekibi
Üyelik tarihi:
01/2017
Nereden:
Balkes
Yaş:
18
Mesajlar:
3.245
Teşekkür (Etti):
332
Teşekkür (Aldı):
679
Konular:
239
Ellerinize sağlık komutanım. Güzel bir konu olmuş.
Kullanıcı İmzası
SolidStar


27-01-2019 23:19
#6
LEOHUNTERA - ait Kullanıcı Resmi (Avatar)
Yazılımcı
Üyelik tarihi:
12/2018
Mesajlar:
57
Teşekkür (Etti):
64
Teşekkür (Aldı):
66
Konular:
9
Öncelikle elinize sağlık, Hashmap kullandığınız algoritmanın O(1) seviyesinde çalıştığını söylemişsiniz ama O(n) seviyesinde çalışmıyor mu?
28-01-2019 00:46
#7
kondanta - ait Kullanıcı Resmi (Avatar)
Üye
Üyelik tarihi:
07/2017
Nereden:
$ebp
Mesajlar:
908
Teşekkür (Etti):
33
Teşekkür (Aldı):
262
Konular:
36
Alıntı:
LEOHUNTERA´isimli üyeden Alıntı Mesajı göster
Öncelikle elinize sağlık, Hashmap kullandığınız algoritmanın O(1) seviyesinde çalıştığını söylemişsiniz ama O(n) seviyesinde çalışmıyor mu?
https://stackoverflow.com/a/1055337

buradan detayli okuyabilirsin neden hashmapin highly O(1) de calistigini. Uzun uzun matematiksel cozumunu yazmak zor geldi acikcasi
Kullanıcı İmzası

許可水月
28-01-2019 01:03
#8
LEOHUNTERA - ait Kullanıcı Resmi (Avatar)
Yazılımcı
Üyelik tarihi:
12/2018
Mesajlar:
57
Teşekkür (Etti):
64
Teşekkür (Aldı):
66
Konular:
9
Hashmap in neden O(1) de çalıştığını biliyorum ama sonuçta hashmap li çözüm içinde her bir elemanın gezilmesi gerekiyor mu, yani tasarladığınız algoritma genel olarak O(n) mertebesinde mi çalışıyor (Sadece hashmap kısmını söylemiyorum, genel olarak algoritmanın çalışma zamanını soruyorum)
28-01-2019 01:19
#9
kondanta - ait Kullanıcı Resmi (Avatar)
Üye
Üyelik tarihi:
07/2017
Nereden:
$ebp
Mesajlar:
908
Teşekkür (Etti):
33
Teşekkür (Aldı):
262
Konular:
36
Alıntı:
LEOHUNTERA´isimli üyeden Alıntı Mesajı göster
Hashmap in neden O(1) de çalıştığını biliyorum ama sonuçta hashmap li çözüm içinde her bir elemanın gezilmesi gerekiyor mu, yani tasarladığınız algoritma genel olarak O(n) mertebesinde mi çalışıyor (Sadece hashmap kısmını söylemiyorum, genel olarak algoritmanın çalışma zamanını soruyorum)
Worst case senaryoda evet N elemani gezmek zorunda. Ama secilen hash fonskiyonuna gore Average case de near constant calismakta. Yani burada mevzu senaryonun ne oldugu biraz da.
Kullanıcı İmzası

許可水月

Bookmarks


« Önceki Konu | Sonraki Konu »
Seçenekler

Yetkileriniz
Sizin Yeni Konu Acma Yetkiniz var yok
You may not post replies
Sizin eklenti yükleme yetkiniz yok
You may not edit your posts

BB code is Açık
Smileler Açık
[IMG] Kodları Açık
HTML-Kodları Kapalı
Trackbacks are Kapalı
Pingbacks are Kapalı
Refbacks are Kapalı