Dosyadan Ayni Olan Satirlari Eleme

Aşağı Git Tüm Forumlar Web Tasarım - Programlama Yazılım Geliştirme Delphi / C++ /Vb Dosyadan Ayni Olan Satirlari Eleme

Bu konudaki kullanıcılar: 1 misafir

8
Cevap 835
Tıklama 0
Öne Çıkarma

1. sayfa

Dosyadan Ayni Olan Satirlari Eleme

Cevap Yaz

qamyoncu

12 yıl (504 mesaj)

Yüzbaşı

Konu Sahibi

Merhabalar,

Asagida bahsedecegim konuyla iligli beyin firtinasi yapalim istiyorum. Fikirlerinizi merakla bekliyorum.

1) Elimizde bir metin dosyasi var ve icerisinde satir satir yazilar var. Bu dosyadan, satirlarin sirasi bozulmayacak sekilde, ayni olan satirlarin kopyasini nasil silersiniz? Bir ornek:

Forum 
  Donanim 
  Haber 
  Forum 
  Haber 
  Donanimhaber 
  Haber 
   
  >>> 
   
  Forum 
  Donanim 
  Haber 
  Donanimhaber

2) Ya dosyanin boyutu 500TB olsaydi?

DH forumlarında vakit geçirmekten keyif alıyor gibisin ancak giriş yapmadığını görüyoruz.

Üye olduğunda özel mesaj gönderebilir, beğendiğin konuları favorilerine ekleyip takibe alabilir ve daha önce gezdiğin konulara hızlıca erişebilirsin.

Üye Ol Şimdi Değil

Bir Daha Gösterme

lavara123

12 yıl (388 mesaj)

Yüzbaşı

C++ önce mesela '\n' karakterine göre ayrıştırıp(split) set (include = set) ile yapabilrsin benzersiz olur :)

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

fishkopf

12 yıl (2212 mesaj)

Yüzbaşı

Excel'de direk istediğinizi yapan fonksiyon var. Programını yazmak istiyorsanız de üstteki arkadaşın dediği gibi her satır bir eleman olacak şekilde bir dizi oluşturup sırayla her elemanın kendinden sonraki elemanlarla eşitliğini karşılaştırmanız lazım.

Bu mesaja 1 cevap geldi.

lavara123

12 yıl (388 mesaj)

Yüzbaşı

aslında kontrol etmemize gerek yok set'in görevi bu :)

örnk:http://ideone.com/k5FTL9

< Bu mesaj bu kişi tarafından değiştirildi lavara123 -- 13 Şubat 2015; 19:41:20 >

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @fishkopf

Mephalay

12 yıl (5771 mesaj)

Yarbay

quote:

Orijinalden alıntı: lavara123

aslında kontrol etmemize gerek yok set'in görevi bu :)

örnk:http://ideone.com/k5FTL9

Set ordered olarak implemente edilmemisse sira bozulabilir ama diger turlu set kullanmak mantikli. Sifirdan algoritmasini yazmak icin de once hizli bir hash algoritmasi olusturmak gerekli ki set de bunu yapiyor.

< Bu ileti mobil sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

qamyoncu

12 yıl (504 mesaj)

Yüzbaşı

Konu Sahibi

quote:

C++ önce mesela '\n' karakterine göre ayrıştırıp(split) set (include = set) ile yapabilrsin benzersiz olur :)

Sirasinin bozulmamasi sorunun kisitlamalarindan bir tanesi, set bildigim kadariyla sirayi bozabiliyor :)

quote:

Excel'de direk istediğinizi yapan fonksiyon var. Programını yazmak istiyorsanız de üstteki arkadaşın dediği gibi her satır bir eleman olacak şekilde bir dizi oluşturup sırayla her elemanın kendinden sonraki elemanlarla eşitliğini karşılaştırmanız lazım.

Excel'deki o fonksiyonun complexity'si kactir acaba? Nasil bir algoritma kullaniyorlar merak ettim dogrusu. Ikinci onerdigin yontem ise O(n^2), pek verimli degil gibi.

quote:

Set ordered olarak implemente edilmemisse sira bozulabilir ama diger turlu set kullanmak mantikli. Sifirdan algoritmasini yazmak icin de once hizli bir hash algoritmasi olusturmak gerekli ki set de bunu yapiyor.

Hadi olusturalim. :)

Isterseniz kod da paylasabilirsiniz, 2. soruya da cevaplarinizi bekliyorum. :)

Bu tarz beyin firtinasi yapabilecegimiz sorulari keske sik sik sorsak da herkesi dusunmeye itsek bu konularda.

Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @fishkopf , @Mephalay , @lavara123

lavara123

12 yıl (388 mesaj)

Yüzbaşı

hmm arkadaşın sorusunda oraya dikatte etmemişim aynen set küçükten büyüğe doğruda bir sıralama yapar(yani sıra bozulur :) )

@qamyoncu yarın bi bakayım şuan bilgisayar başında değilim. Bilgisayar başındayken ve en çok tuvaletteyken garip çözümler gelebiliyor aklıma :)

< Bu ileti mini sürüm kullanılarak atıldı >

Bu mesajda bahsedilenler: @qamyoncu , @Mephalay

fishkopf

12 yıl (2212 mesaj)

Yüzbaşı

evet verimsiz.

http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array

şurda sayılar üzerinde biraz tartışmışlar.

Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @qamyoncu

Mephalay

12 yıl (5771 mesaj)

Yarbay

String hash metodu kullanmak gerekiyor dedigim gibi.

String icerisindeki char array inin her degernin int karsiliginin herhangi bir prime sayi ile carpilmasi ve bunlarin toplanmasi yeterince unique bir yontem olarak gibi duruyor. Bu kritik bir nokta ama mukemmellestirmek cok uzun zaman aliyor, iyi bir hash metodu yazmak CS icin en onemli calisma alanlarindan bir tanesi.

Pseudocode olarak soyle bir sey:

 
  long hash(){ 
    final int prime = 31; 
    long hash = 0; //initial 
    for( char : chars ) 
      hash += prime * char + hash; 
   return hash; 
  }

Daha sonra Her hash degeri icin tutacagimiz tablonun ( aslinda bir array ) size ini dusunmemiz gerekecek. O nu genis tutarak hash collision ini dusurmus oluruz, ancak memory kullanimi artacak. Buna da guzel bir deger verip ( 2^32 olabilir ) her degeri ve one denk gelen String value sunu eslestirecegiz. KeyValue gibi.

Hashlenen degerin array'de nereye denk gelecegini bilmek icin bitwise islem yapilir. ( Bitwise AND ).

 
   
   boolean addTable(String s){ 
     long hash = hash(s); 
     int final tableSize = 0xffffffff; //default 
     int tablePosition = hash & tableSize; 
     if(table[tablePosition] == null ) 
       return true; 
     elseif( table[tablePosition] is a list ) 
         //Collision olmus olabilir, list e uzerinde gezip bu entry daha once kaydedilmis mi diye kontrol edilmeli 
         if(collusion) 
            return false; 
     else 
        return false; 
   
  }

Normal akista, RAM'de hash ve ona denk gelen String degerlerini tutmak yeterli olacaktir. Ancak tablo sinirli oldugundan cok uzun iki string collusion yaratacaktir. Bu sebeple yalnizca bu cozum yeterli olmayacak.

500 TB lik bir dosya uzerinde islem yapma durumu icin de, HDD alaninin yeterli oldugu varsayimi ile, Divide And Conquer algoritmalari uygulayarak dosya 1GB lik 500000 dosyaya bolunur. Her dosya kendi icinde kontrol edilip ikiser ikiser birlestirilip tekrar kontrol edilir. Recursive bir dynamic programlama uygulanabilir burada. Siranin kaybolmamasi icin tablomuza ilgili kayitlar eklenmeli.

Son olarak eklemek istedigim bir nokta da su, String keyfi olarak farklilastirabilecegimiz bir yapida. Bu sebeple 500 TB bir dosya icindeki her satirin birbirinden farkli olmasi gayet mumkun.
n uzunlugunda bir listede tekrar var mi diye kontrol eden algoritmanin memory complexity'si O(n) den daha dusuk olamaz.
Bu sebep, bu soruyu cozmek icin "teorik" olarak 500TB RAM ihtiyacimizin olmasi da gayet mumkun.

< Bu mesaj bu kişi tarafından değiştirildi Mephalay -- 14 Şubat 2015; 10:57:31 >

Cevap Yaz

1. sayfa

Tüm Forumlar Web Tasarım - Programlama Yazılım Geliştirme Delphi / C++ /Vb Dosyadan Ayni Olan Satirlari Eleme