Forum: D Programlama Dili RSS
Permutation Sort algoritmasi cok yavas mi calisiyor?
agora #1
Üye Tem 2013 tarihinden beri · 221 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Permutation Sort algoritmasi cok yavas mi calisiyor?
Selam şöyle bir kod var

import std.stdio, std.algorithm;
 
void permutationSort(T)(T[] items) pure nothrow {
    while (items.nextPermutation) {}
}
 
void main() {
    auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
    data.permutationSort;
    data.writeln;
 
}

Bu kod Visual D ile derlenip çalıştırıldığında ya da bağımsız çalıştırıldığında dahi çok uzun sürede çalışıyor yani program başladıktan 4-5 saniye sonra sıralamayı yazdırıyor acaba neden?

Çalışma zamanını nasıl öğrenebilirim? Kaç saniyede istediğimi vermiş diye yani.
Avatar
Salih Dinçer #2
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Sanırım -1 işleri karıştırıyor!

Üstelik T == byte[] olduğu zaman bile süre aynı. Yani diyeceğim o ki veri türünün içerebileceği tüm olasılıkları hesaplıyor ama byte ile 127 ile sınırlamama rağmen değişen bir şey olmadı. Tabi -1 değerini kaldırırsanız normalleşiyor.

Sebebini ben bilmiyorum :p
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
agora #3
Üye Tem 2013 tarihinden beri · 221 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Dlang forumlarından Chris cevapladı hocam

One of the main reasons is because the number of permutations an array has is n!. Thus the expected runtime is O(n!). That's a slow, slow algorithm in general. In particular, your array with length 11 has 39,916,800 permutations (although it, obviously, doesn't have to go through *all* of those to get the sorted sequence in this case).

You might be able to come up with a faster way to permute, but it's mostly pointless because it will always be very slow. Use std.algorithm.sort if you want to sort quickly, as that uses an algorithm that is O(n log n)

Compare:
11! = 39,916,800
11 log_2 11 = ~38

So the best you could really expect to do is be around a million times slower than a regular sort.


Kısacası daha hızlı olabilir ama en hızlı hali bile yavaş olacak bu algoritma genelde de yavaş çalışıyor demiş. 11! = 39,916,800

demiş yani bu hız normal demiş.

Windows için kodladığım timer'da programın çalışma süresine baktım da

 
//başlangıç 1:10:52,69
//sonuç [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
//bitiş 1:11:04,14 
acehreli (Moderatör) #4
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Algorithmic complexity denen kavramın bir örneğini yaşıyorsun. O(log N) karmaşıklıkta sıralama algoritmaları varken daha yavaşına gitmeye gerek yok. :)

Ali
agora #5
Üye Tem 2013 tarihinden beri · 221 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Hocam bu O(log N), Big O Notation mu oluyor. Dün bir arkadaşımla bunu konuşuyorduk o da bunu tavsiye etti bana.

Aslında o direkt Big O Notation olarak belirtmedi

Asymptotic Notation duydun mu dedi aklima bu geldi.

Öneriniz olan algoritmalar var mı?

Ben aşağıdakileri çözdüm. Ama sadece sıralama algoritmaları istemiyorum mesela çok farklı algoritmalar da istiyorum örneğin genetic algoritmalar, yapay zeka algoritmalari gibi programlamada çok iyi olduğumdan istemiyorum kendimi geliştirmek için :)

Bogo Sort
Bubble Sort
Coctail Sort
Counting Sort
Gnome Sort
Heap Sort
Merge Sort
Pancake Sort
Permutation Sort
Quick Sort
Radix Sort
Shell Sort
Sleep Sort
Stooge Sort
Strand Sort
Josephus Problem
Fast Fourier Transform

Bunlar çözüp bitirdiklerim
Bu mesaj agora tarafından değiştirildi; zaman: 2014-06-08, 05:57.
Avatar
Salih Dinçer #6
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Demek eleman sayısı 11 olunca farkedilir derecede artıyor, iyimiş :)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
agora #7
Üye Tem 2013 tarihinden beri · 221 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Bir sürü algoritma araştırdım bulduklarımı çözdüm hala arıyorum :d
acehreli (Moderatör) #8
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bogo sort'un bir şaka olduğu açık, değil mi?
void main() {
    auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
    while (!isSorted(data))
        randomShuffle(data);
    data.writeln;
}
Diziyi rasgele karıştır, belki sıralanmış olur. Olmazsa tekrarlar. :)

Haber gruplarında bir de miracle sort çıktı:
void main() {
    import core.thread;
    immutable period = 1.seconds;
    auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];
 
    while (!isSorted(data)) {
        Thread.sleep(period);
    }
 
    data.writeln();
}
Onda da hiçbir şey yapmadan sıralanmış mı diye bakıyorsun. Belki bir mucize olur ve sıralanır. :p

Ali
acehreli (Moderatör) #9
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #5
agora:
bu O(log N), Big O Notation mu oluyor.

Evet, büyük O harfiyle ifade idelen ve bir algoritmanın karmaşıklığı ile ilgili bilgi veren gösterime Big O notation deniyor.

N, işlenecek eleman sayısını ifade eder. O(N^2) olduğunda eleman sayısının karesine bağlı bir zaman tutacak demektir. Örneğin, O(N^2) olan bir algoritma tek eleman için t zaman alıyorsa, 1000 eleman için t'nin 1000x1000=1_000_000 katı kadar zaman alır demektir.

O(lg N) ise N'nin logaritmasına bağlı bir zaman alır demek. lg 1000 kabaca 10 olduğundan, 1000 elemanın işlenmesi tek elemanın işlenmesinin yalnızca 10 katı zaman alır. Bir milyon nerede, 10 nerede. :)

Eleman sayısı olarak 1000 yerine daha büyük sayılar seçince fark daha da açık hale gelir.

Ali
agora #10
Üye Tem 2013 tarihinden beri · 221 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Evet hocam Bogo Sort şaka yani aslında buna saçma sıralama demişler :)

void bogoSort(T)(T[] data) {
    while (!isSorted(data))
        randomShuffle(data);
}
 
void main() {
    auto array = [2, 7, 41, 11, 3, 1, 6, 5, 8];
    bogoSort(array);
    writeln(array);
}
 
//Saçma Sıralama 

Ayrica hocam Miracle Bogo Sort icin birisi grafik tarzi bir sey yapmis SWF ile :)

http://wonderfl.net/c/gT9W/read

Bu ne kadar doğru bilmiyorum ama input'a 4 yerine 6 yazdım 10 dakikadır uğraşıyo düzelmeye :)

Belki ilgilenen olabilir diye söyleyeyim benim en çok ilgimi çeken Miracle Numbers diye bir algoritma oldu :)
agora #11
Üye Tem 2013 tarihinden beri · 221 mesaj
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #9
Big O Notation kavramini yeni yeni duyuyorum. Arkadasimin tavsiyesi yani ama sanirim cozebilecek bir zeka yapim yok :/
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:
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-11-22, 05:10:38 (UTC -08:00)