C++ map ve unordered_map veri yapıları - Performans kıyaslaması

Map C++ standart kütüphanesinde bulunan bir veri yapısıdır ve ilişkisel verileri saklamak için kullanılır. Yani sırasıyla key (anahtar) ve bu anahtarın değerini ifade eden value elemanları saklanır.

typedef pair<const Key, T> value_type;

map içerisindeki elemanlar key değerine göre eşsizdir ve tüm elemanlar sıralanmış vaziyettedir. 

Yukarıdaki örnekte string key tipinde bir map tanımladık ve sırasıyla G,C,B ve A key değerleri ile birlikte integer değerleri map'e ekledik. Eğer bu bir dizi olsaydı, dizi elemanlarını ekrana yazdırdığımızda eklediğimiz sıraya göre elemanların saklandığını görecektik. Burada ise aşağıda gördüğünüz ekran çıktısına göre, elemanlar key değerlerine göre otomatik olarak sıralanıyor.

Eğer map yerine unordered_map kullanmış olsaydık, veriler eklediğimiz sıraya göre tutuluyor olacak idi. Aşağıdaki örneği inceleyecek olursanız, unordered_map'te elemanların sıralı olarak saklanmadığını göreceksiniz. Eğer map kullanmış olsaydık tüm elemanlar sıralı olacak idi.

map ile unordered_map arasındaki temel farkı görmüş olduk. Şimdi bir örnek üzerinden her ikisi arasında performans kıyaslaması yapalım. Gerçekleştireceğimiz örneği basitçe özetleyecek olursak; bir string dizisinde tekrar eden elemanların sayısını bulan bir program yazmak istiyoruz. String dizimiz nükleotit kodlarından (A,C,T,G) oluşuyor ve bunların sıralı hali biyolojik veriler içeriyor. 

Mesela TACAGAT.... şeklindeki devam eden bir nükleotit dizimiz var, biz de k=3 için her bir elemanın frekansını bulmak istiyoruz. TAC=1, ACA=1, CAG=1 gibi. Bu işlem literatürde k-mer (counting) sayma işlemi olarak geçiyor ve çoooook büyük boyutlu dosyalar için farklı k değerlerine göre bu işlemi yapmak zaman ve hafıza açısından problem teşkil edebiliyor. Konuyu çok dağıtmadan, bahsettiğim şekilde nükleotit kodlarından oluşan bir dosyayı okuyup map ve unordered_map ile nükleotit dizilim frekanslarını bulacağız. 

İlgilendiğimiz dosyada(.fastq uzantılı) ayrı sequence ler şeklinde binlerce nükleotit dizilimi bulunuyor. Dosyadan her bir sequence'i aşağıdaki gibi okuyabiliyoruz. İlgili dosyadan verilerin okunması kısmını es geçiyorum, çünkü bu yazıdaki odak noktamız bu değil.

Aşağıdaki kodda, dosyadan her bir sequence' i okuyup, k değerine göre eklenecek/aranacak nükleotit dizilimini çıkartıyoruz ve map'e yerleştiriyoruz. Aslında yapılan işlem çok basit,  Örneğin;

temp = "CAT" dizilimi geldiğini farzedersek, bunu map içerisinde arıyoruz, eğer bulamazsak yeni bir eleman olarak veri yapımıza ekliyoruz, şayet bulursak ilgili key'e karşılık gelen integer değerini bir artırıyoruz.

it = my_map.find(temp);

// Bulundu ise it my_map in son elemanını göstermiyor olacak!!!!

if (it != my_map.end())

   my_map[temp]++; // count k-mers (update k-mer count)

else

   my_map[temp]=1; // add new k-mer

int main(int argc, char *argv[]) { chrono::time_point<std::chrono::system_clock> start, end; start = std::chrono::system_clock::now(); gzFile fp; kseq_t *seq; int l; if (argc == 1) { fprintf(stderr, "Usage: %s <in.seq>\n", argv[0]); return 1; } fp = gzopen(argv[1], "r"); cout<<"Processed File Name: "<< argv[1] <<endl; int kmersize = stoi(argv[2]); //int topcount = stoi(argv[3]); map <string, unsigned int> my_map; map <string,unsigned int>::iterator it; seq = kseq_init(fp); while ((l = kseq_read(seq)) >= 0) { string str = seq->seq.s; //cout<<"seq: "<<str<<endl; for (int i=0; i<str.size()-kmersize+1; i++) { string temp = str.substr(i,kmersize); //cout<<temp<<endl; it = my_map.find(temp); // If that element is already added before, increment its count if (it != my_map.end()) my_map[temp]++; // count k-mers (update k-mer count) else my_map[temp]=1; } } kseq_destroy(seq); gzclose(fp); end = std::chrono::system_clock::now(); chrono::duration<double> elapsed_seconds = end-start; time_t end_time = std::chrono::system_clock::to_time_t(end); cout << "elapsed time: " << elapsed_seconds.count() << "s\n"; return 0; }


Yukarıda verdiğim kod içerisinde, map yazılan kısmı unordered_map ile değişirsek aynı işlem unordered_map veri yapısına göre de yapılacaktır. Her iki veri yapısı için kodu çalıştırıp, yüzbinlerce nükleotit dizisi içeren bir dosya ile test edince elde edilen sonuçlar aşağıdaki gibidir.

Map kullandığımızda işlemler 21 saniye sürerken, unordered_map ile aynı işlem sadece 9 saniye sürdü. Bunun sebebi map ile her bir eleman eklememizde verilerin sıralanıyor olması ve arama kompleksliğinin unordered_map den daha performanssız olması.

http://en.cppreference.com/w/cpp/container/map map de ağaç yapısı kullanılıyor ve arama kompleksliği O(logN) . 

http://en.cppreference.com/w/cpp/container/unordered_map Unordered_map 'de ise sabit zaman kompleksliği var ve veriye erişim daha hızlı. O(1), en kötü durumda ise O(N).