İki Farklı Dosyadaki Ortak Kelimeleri Bulma – Algoritma

Bazılarınız “Bu kadar uzun başlık mı olur?” diye sorabilir , gayet normal fakat birazdan anlatacaklarımı kapsayan en uygun başlık buydu.

 

– – – – – –

Elimizde 2 adet dosya var. Bu dosyaların içinde geçen ortak kelimeleri bulmak istiyoruz. İlk aklımıza gelen genelde şunlar olur: – İlk dosyayı bir listede tutup ikinci dosyadaki kelimeleri okurken tek tek listenin içerinden karşılaştırmak olur.

– Dosyaları belleğe aktarmayız. İlk dosyadan bir kelime okuduğumuzda , ikinci dosyayı baştan sona dolaşıp bu kelimenin ikinci dosyada geçip geçmediğini kontrol ederiz.

– – – – – –

 

Zaman karmaşıklığı(Time Complexity) açısından bakacak olursak yukarıdakilerin ikisi de tek tek tüm elemanları karşılaştıracağından O(n2) karmaşıklığa sahip. Elimizdeki verilerin çok olması durumunda ciddi bir zaman kaybı oluyor.

Peki bir de şu şekilde düşünsek. İki dosyanın ilkini okuduk belleğe aldık (ki bunu hertürlü yapacağız) , ikinci dosyayı da kelime kelime okurken , bellekteki veriler üzerinde dizideki gibi O(1)’de erişim yapacak bir mekanizma olsa.

HashTable O(1)**’de erişim yapma imkanı sunduğu için , ilk dosyadaki kelimeleri HashTable da tutup , ikinci dosyayı kelime kelime okuyup karşılaştırmak , zaman karmaşıklığını O(n) e düşürüyor.

** Under reasonable assumptions , the average time to search for an element in a hash table is O(1)  [Introduction to Algorithms , 3rd edition]

Tabi burada şunu da söylemek lazım, HashTable’ın ek bir lookup table kullanacağımız için yer karmaşıklığı(space complexity) bakımından ve hash fonksiyonunda belli bir süre kaybetme bakımından bir takım eksileri var.

Neyse konuyu fazla dağıtmadan şundan bahsetmek istiyorum. C#’ta buna benzer bir şekilde çalışan bir method olarak ***Intersect*** methodu var.

Aşağıdaki resimden örnek koda ve farklı 2 methoda ait çalışma zamanı(tick cinsinden) bilgilerine ulaşabilirsiniz.

 

[![](http://www.onurbaysan.com/blog/wp-content/uploads/2011/10/test1-1024×645.png “test”)](http://www.onurbaysan.com/blog/wp-content/uploads/2011/10/test1.png)

355 Words

Pointer

                                         ![xkcd](http://imgs.xkcd.com/comics/pointers.png)

                                                                                                      *xkcd’den alıntıdır.

14 Words