C dilinde birbirinden farklı random sayılar atama (3. sayfa)

Hala bu konuda tartışma dönüyor. Sonunda çözümünü yazmışsın, bu çözüm ne zaman yavaş çalışıyor sana açıklayayım  

Soruda verilen sayılara N=50, K=20 diyelim. List uzerinde pop işleminin average time complexitysi O(N) dir. Dediğin çözüm O(N*K) olacak. N sayısını artırınca bu çözüm yavaş çalışır. Buna karşılık N=1e6 iken basit bir hashmap kullanırsan milyon kat daha hızlı çalışan bir sonuç elde edebilirsin çünkü N sayısının bir etkisi olmaz. Bu yüzden sana soruya göre çözüm yazılır dedim.

Ufak bir meselede beni biri şikayet ettiğinde dakikasında ceza veriyorlar. şimdi ise saatler geçti halen çıt yok! Yazıklar olsun böyle foruma!

Mesele sorunun genel ve doğru çözümü. Hızlı ama tartışmalı çözümü değil! şu hashmap örneğini gönder de bir bakalım.

hashmap, O() notasyonunda rahatlatıcı gözükse da hashmap hesaplaması, instruction cycle olarak biraz maliyetli bir iş. lose lose, sdbm gibi hash fonksiyonların implementation'larında hep rahatsız edici bir while() loop vardır :)

Birader o kadar boş ve insanlara yukardan bakan yorumlar yapmışsın ki, gülsem mi sinirlensem mi bilemedim. Bu kadar ego iyi değil, özgüven sorunların olduğunu çok belli ediyor dışarıya. Bi psikoloğa görünmeni öneririm. Selam ve dua ile <3

Konunun tamamını okumadım ancak şöyle basit bir algoritma yazılabilir:

0-X aralığındaki sayılardan, rastgele Y uzunlukta bir dizi oluşturmak ve birbirinin aynısı olan iki eleman içermesini istemiyoruz diyelim.

X+1 uzunluğunda bir dizi oluşturup (z diyelim ismine), her olası elemanı bu diziye atarız sırasıyla

z=[]

for i in range(X+1):

z.append(i)

sonra 0-X arasında rastgele sayı üretmek yerine, 0-len(z) arasında rastgele sayı üretiriz ve Z listesinde bu rastgele sayıya denk gelen sayıyı alıp asıl listemize ekleriz.

y_list = []

for i in range(Y):

a = random.randrange(len(z)) // Z listesindeki rastgele bir sayının indisini seçiyoruz

y_list.append(z[a]) // seçtiğimiz elemanı asıl listeye ekliyoruz

z.pop(a) //eklediğimiz elemanı Z listesinden çıkarıyoruz

Okuduğunu anlayamayan, okumayan veya okuyup da okumadı ayağına yatan kişilik!

İşte yıllardır senin gibilere laf anlatmaya çalışıyoruz! Yaşım da çıkacak ortaya!

Orta yere atlamadan önce keşke sunulan çözüme bir baksaydın. Zaten aynı şeyi yapıyor  

Kod 
Yığını:
#include <cstdio>
#include <cstdlib>
#include <unordered_map>
#include <vector>


int fe(){
    int ayni= 0;
    std::vector<int> a(20);
    std::unordered_map<int, int> b;
    for(int i=0;i<a.size();i++){
        a[i]=rand()%1000000;
        while(b[a[i]]){
            a[i]=rand()%1000000;
            ayni++;
        }
        b[a[i]]=1;
	
    }
    return ayni;
}




int main(int argc, char **argv){
    int ct = 0;
    srand(time(NULL));
    for(int i=0;i<1000000;i++)
        ct += fe();
    printf("%d\n",ct);
    return 0;
}

Önceki çözümü düz array olarak değil hashmap olacak şekilde değiştirdim sadece, bir de bunu C'ye çevirmesi zor olur. Milyon kat değil bin kat falan hızlı oldu belki hash kullandığım içindir. Python çözümü N=1e9da çalışmıyor galiba memory yetmediği için.

Bu çözümde de N ile K birbirine çok yakın olursa çakışma sayısı fazla olacak, o zaman python daha iyi olur.

Kod 
Yığını:
const nums = new Set();
while(nums.size !== 8) {
  nums.add(Math.floor(Math.random() * 100) + 1);
}

console.log([...nums]);

Js in gözünü sevem

https://stackoverflow.com/questions/1608181/unique-random-number-generation-in-an-integer-array senin sorunda burda knk

"a" vectorünün boyutu arttırdığında maalesef işler karışıyor. Ki zaten gerçekte böyle durumlardan bahsediyoruz. Yani 20 farklı sayı için değil çok daha fazlası için!

Örneğin yüzbin (100.000) farklı değer için bahsettiğimiz ilk yöntem bende 1.2 saniyede tamamlanırken, bu hash şeklinde tamamlanamadı. 10 bin bile tamamlanamadı!

Zahmet önceki edip yazılanları bi okumayı deneseydin keşke... Bu yöntem de "brute force" dur.

Ulan bi bitmediniz gitti!

Benim kodda hızlı çalıştığını göstermek için mainde bir milyon kere çalıştırmıştım, asıl kod fe fonksiyonunda.

Maindeki for loopu kaldırırsan yine çoğu değer için pythondan hızlı çalışıyor ama K N'nin yarısından büyük olmaya başlarsa fazla yavaşlıyor.

Stack overflowdaki gibi orada Kya M, Nye N demişler, daha iyi çözümler de var.

Şöyle bir şey yapsam peki O(N) complexity'sinden kurtulabilir miyim?

Kod 
Yığını:
import random
sayılar = [*range(50)]




cevap = []
for i in range(20): 
	index = random.randint(0, len(sayılar) - 1)
	cevap.append(sayılar[index])
	sayılar[index], sayılar[len(sayılar) - 1] = sayılar[len(sayılar) - 1], sayılar[index]
	sayılar.pop()

indexlerin sayılarla bir bağlantısı olmadığı için sayıları istediğimiz gibi karıştırabiliriz. Gerçi burada swap işleminin time complexity'si ne bilmiyorum.

Bu arada soru çok basit bir soru, bence ilk söylenen yöntemler de gayet çalışırdı niye bu kadar tartışıldı anlamadım.

Önceki O(NK) idi bu O(N+K) oluyor " sayılar = range(50)" den dolayı. Şimdi yine N, K dan çok büyük olursa yavaş çalışır yani. Benimki de N ile K yakın olunca çalışmıyor.

Bu arada bence de hiçbir çözümde sorun yok ama sizinki yanlış benimki doğru denince bizimki de farklı inputlarla çalışıyor diye göstermek istedim. Boşa uzattık ama haklısın  

Birinci sınıf BM öğrencisiyim ve konuyu şöyle okudum:

----

Hocamız yüksek performanslı algoritma geliştirmenin herkesi harcı olmadığını ve çok nadir bulunduğunu söyledi. Bulanlar da isim alıp markalaşıyormuş. Bizim yapacağımız sıfırdan yüksek performanslı algoritma geliştirmek yerine best practices dedikleri yöntemleri araştırıp mantığını anlayıp uygulamak. Bu problem özelinde şöyle ilerlememiz gerekmez miydi?

[1]: Problemi anla.

[2]: Best practices araştırması yap.

[3]: Probleme uygulama.

[4]: Test et.

Hocamız yanılıyor bu noktada?

Yine derste sürekli algoritma analizi yapıyoruz. Aynı bu tür sorular soruluyor ve ilk biz aklımıza gelen yöntemi söylüyoruz. Hoca hiç eleştiri yapmadan onu yazıyor. Sonra sürekli onun üzerinden iyileştirme yapmaya çalışıyoruz. Stack hocanın sanırım vurgulamak istediği buydu. Performans odaklı olması lazım çözümlerin.

Ben de hobi olarak retro emulatör geliştirmiştim bir ara. Makinanın ses üreteci çipi noise üretmek için random sayı oluşturması gerekiyordu. Tabi o ilkel cihazlarda şimdiki gibi kompleks trng donanımları olmadığı için basitçe iki biti xor yapıp msb'e kopyalıyordu. Bir kere de sağa iteleyince rastgele bit elde ediliyordu. Eski sistemlerle uğraşmak çok zevkli. Belki de basit oldukları içindir. Modern mimarileri anlamaya ömür yetmez.