Forum: Projeler Genel RSS
Sözcükleri, uzunluğuna göre yerleştirme!
Avatar
Salih Dinçer #1
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Sözcükleri, uzunluğuna göre yerleştirme!
Merhaba,

Acil bir uygulama geliştirmem gerekiyor. Hemen kolları sıvayacağım ama 24 saat içinde gelen fikir ve küçük kod örnekleri işimi kolaylaştırabilir. Tıpkı Google'da görsel ararken, resimleri ekrana yerleştiren algoritmanın yaptığı gibi alanı en iyi (optimisation) şekilde kullanmak istiyorum.

Bu konuda, sırasıyla yapılacak 2 temel görev var ve gerisi teferruat:
  • Sözcükleri genişliklerine göre gruplandırmak ve
  • Her gruptan eşit miktarda sözcük yerleştirmek.

Geliştirme yapılırken console ortamı kullanılacağından (defaultMaxLength = 80) ilk görevin çözünürlüğünü arttırmak gerekiyor. Çünkü ileride grafik ekranında belli bir font kullanılacağından, bazı harfler küçük olacak. Ama bu kolay çünkü uzunluğu veren işlev, sonucu 100 ile çarpar, hepsi bu...:)

Ancak ikinci görevde, gruplarda 1-2 tane sözcük kalacak kadar yerleştirme yapmak yeterli olmayabilir. Özellikle en küçük sözcükleri belki de hiç yerleştirme yapmadan 2. aşamada boşlukları tamamlamak için kullanmak akıllıca olabilir. Ama yetmez çünkü sayısı az gruplardaki sözcüklere de dokunmamak gerekebilir.

Farkındayım; biraz basit, leziz ama kritik hassasiyette bir olay...:)

Neyse, ilginizi çekerse yazabilirsiniz. Sınıf, varsayılan genişlik, yükseklik ile ayraç (separator) ve yerleştirilecek sözcük dizisini alacak. Geriye ise sadece bir dizge döndürecek.

Teşekkürler...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4513 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Şöyle bir şey denedim:
import std.stdio;
import std.range;
import std.algorithm;
import std.random;
 
auto rasgeleSözcükler(size_t adet, size_t enKısa, size_t enUzun)
{
    static immutable dstring alfabe = "abcçdefgğhıijklmnoöprsştuüvyz";
 
    return
        iota(adet)
        .map!(_ => iota(uniform(enKısa, enUzun + 1))
                   .map!(_ => alfabe[uniform(0, alfabe.length)])
                   .array);
}
 
struct Histogram
{
    // Sözcük uzunluğundan o uzunluktaki sözcüklere bir eşleştirme
    dstring[][size_t] gruplar;
 
    // Sözcük ekler
    void ekle(dstring sözcük)
    {
        gruplar[sözcük.length] ~= sözcük;
    }
 
    // Her gruptan belirtilen adette (o kadar yoksa daha az) sözcük çeker
    auto dengeliÇek(size_t adet) const
    {
        return gruplar.byValue.map!(grup => grup.take(adet));
    }
}
 
void main()
{
    auto histogram = Histogram();
 
    // 100 adet 1-4 arası uzunlukta sözcük
    auto sözcükler = rasgeleSözcükler(100, 1, 4);
 
    foreach (sözcük; sözcükler) {
        histogram.ekle(sözcük);
    }
 
    writeln(histogram.dengeliÇek(2));
}
Son satırda her gruptan 2 adet çekmek istediğimiz için çıktıda her uzunluktaki sözcükten 2 adet beliriyor:

[["jü", "gh"], ["k", "e"], ["ılf", "hjd"], ["ozçü", "zçaş"]]

Ali
Avatar
Salih Dinçer #3
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Teşekkürler hocam zahmet etmişsin...

Ben aslında fikir babında ve/veya küçük zihin açıcı bir örnek bekliyorum çünkü yerleştirme aşamasında işler karışacak gibime geliyor. Yine de Histogram sınıfı ve yaptığınız diğer şeyler bana bir kaç fikir getirdi bile...:)

Bu arada memdict.words isminde bir sınıfım var. Bunu bir ara paylaşırım. Kurarken dosya ismi ve türü parametre olarak veriliyor ve sahip olduğu üye dizilere sözcükleri dosyadan yüklüyor. Dosya türü olarak, simple TXT'yi desteklediği gibi CSV ve JSON dosyalarından da veri alabiliyor. Belki sadeleştirip buraya bile nakledebilirim.

Sevgiler, saygılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #4
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Bugün şöyle bir şey yaptım. Ama şöyle geçen zamana baktım da daha henüz yerleştirmeye geçememişim...:(

Aşağıda, Histogram isminde gereksiz bir yapı var. Çünkü tek elamanlı ve çok boyutlusunu beceremedim. Kolayıma kaçanı yeğledim. Sanırım pek leziz gözükmüyor değil mi? Ama çalışıyor...:)
import std.stdio; // memdict.words;
 
struct Histogram {
  size_t[] wordId;
}
 
void main() {
  auto words = new Words!DPs1("memdict/test55.txt", "TEXT");
  //auto slice = words.get(55);/*
  auto slice = ["idiot", "beyond", "effort", "consolidated", "epaulette",
   "modern", "banderole", "ceremony", "hurtle", "meditation", "despair",
   "hurt", "element", "concert", "parcel", "sophisticate", "therapy",
   "cliche", "retain", "maintainability", "combo", "sustainability",
   "miniature", "exhaust", "pilot", "imbecile", "controversial",
   "monitor", "accreditation", "confetti", "success", "mat",
   "eccentric", "convey", "decorative", "cheque", "polemic",
   "combine", "flag", "critic", "sensation", "manual", "standard",
   "myth", "critical", "trend", "cabin", "membrane", "fling", "museum",
   "centrifuge", "hurl", "symphony", "parachute", "mechanical"];//*/
 
  Histogram[] test;
//  v------^  Histogram.index == groups.value
  size_t[ubyte] groups; // ubyte: word.length;
 
  foreach(i, word; slice) {
    auto wordLength = cast(ubyte)word.length;
    if(wordLength in groups) {
      auto newIndex = groups.get(wordLength, 0);
      test[newIndex].wordId ~= i;
    } else {
      test ~= Histogram();
      auto newIndex = test.length - 1;
      test[newIndex].wordId ~= i;
      groups[wordLength] = newIndex;
    }
  }
 
  foreach(id; groups.keys) {
    auto index = groups[id];
    writef("%s:%s\t", id, index);
    foreach(word; test[index].wordId) {
      slice[word].write(" ");
    }
    writeln;
  }
}/* Çıktısı:
12:2    consolidated sophisticate 
8:4    ceremony imbecile confetti standard critical membrane symphony 
4:7    hurt flag myth hurl 
5:0    idiot combo pilot trend cabin fling 
9:3    epaulette banderole miniature eccentric sensation parachute 
13:10    controversial accreditation 
6:1    beyond effort modern hurtle parcel cliche retain convey cheque critic manual museum 
10:5    meditation decorative centrifuge mechanical 
14:9    sustainability 
7:6    despair element concert therapy exhaust monitor success polemic combine 
15:8    maintainability 
3:11    mat 
*/
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #5
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Şu şekilde 2'den fazla elemanı bulunan grupları listeleyecek şekilde işlem yapmak mümkün:
  foreach(id; groups.values) {
    if(test[id].wordId.length > 2) {
      foreach(word; test[id].wordId) {
        slice[word].write(" ");
      }
      writeln;
    }
  }
Bu durumda sıra geldi yerleştirmeye. Çünkü elimizde joker olarak kullanılabilecek potansiyel gruplar var. Öte yandan, yukarıdaki gibi filitreleme yaparak bir kısmını da yerleştirirsem, farklı boyutlarda yeni joker sözcüklere sahip olacağım. Geriye bir tek boşluk doldurma kalıyor ki belki sandığımdan kolay olacak.

Ne dersiniz, fikri olan?

Dip Not: Önceki iletimdeki Words sınıfının tanıtıldığı satırı gizlemeniz gerekiyor. Çünkü sınıf olmadan pratik bir şekilde derlenebilen halini tam olarak düzeltmemişim.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #6
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4513 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bütün sözcükler slice dizisinde duruyor. Ek olarak, onları gösteren indeks değerleri tutuyorsun. Yani dizgileri kopyalamak yerine indekslerini saklıyorsun. Önce indeksi elde edip sonra slice'ın o indeksli sözcüğüne erişiyorsun.

Başka bir yol, indeks saklamak yerine string saklamak olurdu. Özellikle kopyalanmasını gerektiren bir duruma yoksa string de zaten sözcüklerin kopyaları değildir de tek sözcüğü gösteren iki üyeli yapıdır.

Dolayısıyla, sen iki üyeli string yerine tek indeks sakladığın için bellek açısından tutumlu davranıyorsun ama öte yandan dizgiyi bulmak için bir kaç adım atman gerekiyor.

Yanlış veya düzeltilsin demiyorum tabii ki. Benim gördüğüm o... :)

Ali
Avatar
Salih Dinçer #7
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Haklısın hocam, aynı izah ettiğin gibi. Zaten senin yaptığın daha leziz ki...:)

Sanırım bana biraz daha "bir taşla bir kaç kuş vurulacak" bir şey lazım. Örneğin:

Sözcükleri yerleştirirken yine aynı yapıyı (Histogram) kullanmaya başladım çünkü içerik aynı. Zaten sözcükler sınıfın kurulduğu andan itibaren hep aynı bellek bölgesinde duracaklar. Geriye kalan sadece onları temsil eden kimliklerin (wordId) oradan buraya bir yaprak gibi uçuşacak (uzunluğa göre yerleştirme işlemi) ve yere konduklarında nihai yerleştirme bitmiş olacak...

Yapıyı azıcık geliştirmeliyim çünkü istediğim zaman temsil edilen sözcüklerin toplam genişliğini bilmeliyim. İlk aşamada sözcüklerin hepsi aynı grupta olduğu için basit bir çarpım ile bulunabiliyor ama sonra işler karıştı...:(
struct Histogram {
  size_t[] wordId;
  size_t eachSize;
 
  auto length() {
    return eachSize * wordId.length;
  }
/*  //static:
  string[] source; // <-- sözcüklerin olduğu diziyi temsil edecek bir dilim tanımlamak istedim!
  auto len(){
    size_t result;
    foreach(word; wordId) {
      result += source[word].length;
    }
    return result;
  }//*/
}
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #8
Üye Ock 2012 tarihinden beri · 1908 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Bu arada güzel pratik bir şekilde kodu (çekirdek kısımı) optimize ettim:
  foreach(i, word; slice) {
    auto wordLength = cast(ubyte)word.length;
    auto newIndex = groups.get(wordLength, 0);
    if(!newIndex) { //wordLength in groups
      test ~= Histogram();
      newIndex = test.length - 1;
      groups[wordLength] = newIndex;
    }
    with(test[newIndex]) {
      wordId ~= i;
      eachSize = wordLength;
    }
  }
Çünkü 2 satırda benzer şeyler yapıyormuşum. Dikkat ederseniz, eşleme tablolarında (çağrışımsal dizi) "in" işleçi ile sorguladığımız, aslında "get" ile yaptığımızdan çok farklı değil. Hatta get() özelliği çok daha akıllı. Zaten 0 boyutlu sözcük olamayacağı için pratik bir şekilde sadeleştirme yaptım ve var olan satırların yerlerini değiştirdim.

Şimdi daha hızlı ve küçük (if'i else'den kurtardım) bir kod oldu. Ayrıca küçük bir ekleme (with bloğu) yaptım...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Forum: Projeler Genel RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-10-22, 08:23:40 (UTC -07:00)