En kısa kod satırı kullanımı ile asal sayıları bulma

Python
21

Benim gordugum, bir suru ogrencinin/yeni baslayanin eksik oldugu bir konu: Karmasik ve akis degistiren kosullar, icice loop’lar.

Mesela asal ornegindeki gibi:

#sayi loop'u:
    ...
    # asal loop'u:
    asal = true
    for div in range(2,sayi):
        if sayi % div == 0:
            asal = false
            break

Fonksiyonel programlamadaki any/all kadar kolay degil. Birim eleman atamasi (asal = true) ic loop’un icine veya dis loop’un disina kayabiliyor. Kosulla De Morgan karsiti arasinda kararsiz kalinabiliyor, veya ikisi karistirilabiliyor (if sayi % div != 0: asal = true). break unutuluyor…

Cozumu ise hem cok basit hem de yazilim muhendisligi nedzinde daha guzel: Yardimci fonksiyon.

def is_prime(n):
    for div in range(2, n):
        if n % div == 0:
            return false
    return true

Erken donus icin state tutup break kullanmak yerine dogrudan return koyabiliyoruz. Kod hem yazmasi, hem de okumasi daha kolay bir hale geliyor. Ustelik kisa devre yapmasi da garanti oluyor!

Simdi ogrencim olsa bu tur egzersizler veririm, her noktada yardimci fonksiyon kullanilmasini kafaya kazirim.

1 Beğeni
22

Elbette, illa bi fibonacci ve faktöriyel çözdürürüm bu konuda.

Haklısın aslında, ama fonksiyonlar bu konudan sonra geliyordu normalde. Bu yıl değişiklik yapacağım ve atamalar işlemler vs den sonra hemen fonksiyonlara geçeceğim. Sonra karşılaştırma ve döngülere gireceğim. Bakalım böyle deneyelim bu yıl.

1 Beğeni
23

Merhaba,
konu hakkında biraz uğraşmışlığım var, en yukardaki örneklerde belirtildiği gibi, Eratosthenes kalburu ile (tabi ben kalbur malbur bilmez idim, programı yazdıktan sonra bunu fi tarihinde birilerinin bu yöntemle çözdüğünü öğrendim, neyse). bayağa bir uğraştıktan sonra yazdığım programla, aldığım çıktı şı şekilde

1 ile 1,000,000,000 arasındaki Asal sayılar:
kullanıcı asal sayıları yazdırmamayı tercih etti

1 ile 1,000,000,000 arasında. 50,847,534 tane asal sayı buldum

bulunan en son asal sayı: 999,999,937

Hesaplama zamanları özeti:
477 elemanlı vektör aç : 0.041sn.
Asal sayıların hesaplanması : 1.769sn.
Asal ayıklama + dosyalara yazılması: 0.598sn.
toplam geçen süre : 2.408sn.

süre gerçekten 2.4 sn.
bunu c++ ile yazmıştım. Sonra pascal ile de yazdım, paskal program yaklaşık 5sn de yanıt veriyor.

yazdığım programda bir kaç püf noktası var.

1-kalbur için çok büyük bir RAM gerekiyor. kodu ilk yazdığımda, 3 küsur milyona kadar asalları bulabiliyordum. daha büyük dizi açınca çekirdek dökülüyordu. Sonra hafızada daha az yer tutması için, önce diziyi bit olarak açtım. yani her bit ilk başta 1 olarak girildi, asal değilse 0 yapıldı. öyle olunca bir integer sayı hafızada 4-8 byte tutuyor, ben her sayıyı 1 bit olarak kaydettim, sayının ne olduğu, elimdeki dizideki, o bitin sıralaması veriyordu. Sonra çift sayıları da eledim, sadece tek sayıları içeren bir dizi yaptım, böylece 1 byte’lık veriye, 16 adet sayıya ilişkin bilgi sakladım. Böylece, RAM sorununu aştım, ilk versiyonda 16 adet sayı, 8’er byte’dan hafızada 16x8=128Byte yer kaplıyordu, şimdi 16 adet sayı 1 Byte yer kaplıyor.Böyle olunca daha büyük sayılara kadar kalburu çalıştırabildim.

2.Püf noktası, elimde sadece tek sayılar olunca, 2.nin katlarını silmeye uğraşmadım, önce 3 ün katlarını sildim, sonraki tüm silme işlemlerinde 3’ün katlarına uğramadan çalışacak şekilde bir algoritma kurdum, böylece, %15, 20 civarı hızlandı.

3.Püf noktası, elimizdeki max sayısının kareköküne kadar olan sayıların katlarını silmek yeterli olduğuna kanaat ettim, bu müthiş hızlandırdı.

eğer meraklısı varsa, mesela 1.000.000.000 a kadar sayıların içinden asal olanların listesini, zipleyip filan yollayabilirim. (50 küsur milyon sayı var).

2 Beğeni
24

“Aklin yolu bir” diye bir sey var :slight_smile:

Ben de Eratosthenes kalburunu biliyordum, bir gun dusunurken daha az hafiza kullanan bir versiyonu geldi aklima (tum kompozit sayilari tutmaktansa her asalin son katini tutuyoruz, yeri geldikce guncelliyoruz). Bilinen, kullanilan varyantlarindan biriymis…

Su kod nasil calisiyor ayni makinede?

fn main() {
	const LIMIT: usize = 1_000_000_000;

	let mut prime_map = vec![false; LIMIT];
	prime_map[0] = true;
	prime_map[1] = true;

	let mut prime_count = 0;

	for candidate in 2..LIMIT {
		if prime_map[candidate] {
			continue;
		}

		prime_count += 1;

		let mut n = candidate;
		while n < LIMIT {
			prime_map[n] = true;
			n += candidate;
		}
	}

	println!("Primes < {}: {}", LIMIT, prime_count);
}

Herhalde olabilecek en duz Rust implementasyonu. Bende 19.5 saniye aldi. Sonra 4 kat daha hizlandirabildim.

2 Beğeni
26

mehmetk@fedora:~/Programlama/rust/asalYazBel/target/release$ time ./asalYazBel
Primes < 1000000000: 50847534

real 0m10,459s
user 0m10,005s
sys 0m0,391s

sayın aib , verdiğiniz kodu time ile çalıştırınca yukardaki gibi sonuç vardi, yaklaşık 10.5 sn sürdü. Aynı sayıda asal bulduk :slight_smile:

1 Beğeni
27

cargo build --release, degil mi?
O zaman bitmapli versiyonu 3 saniye filan tutar herhalde:

type BitmapUint = usize;
const BMPU_BITS: usize = BitmapUint::BITS as usize;

struct Bitmap {
	size: usize,
	map: Vec<BitmapUint>,
}

impl Bitmap {
	pub fn new(size: usize) -> Bitmap {
		let msize = (size + BMPU_BITS - 1) / BMPU_BITS;
		let map = vec![0; msize];
		Bitmap { size, map }
	}

	pub fn len(&self) -> usize { self.size }

	pub fn get(&self, i: usize) -> bool {
		self.map[i / BMPU_BITS] & (1 << (i % BMPU_BITS))
			!= 0
	}

	pub fn set(&mut self, i: usize) {
		self.map[i / BMPU_BITS] |= 1 << (i % BMPU_BITS);
	}
}

fn main() {
	type Num = u32;
	const LIMIT: Num = 1_000_000_000;

	fn num_to_index(n: Num) -> usize { ((n - 3) / 2) as usize }
	fn index_to_num(i: usize) -> Num { ((i * 2) + 3) as Num }
	let mut prime_map = Bitmap::new(num_to_index(LIMIT) + 1);

	let mut prime_count = 1;

	let mark_limit_index = num_to_index((LIMIT as f64).sqrt() as Num);

	for candidate_index in 0..prime_map.len() {
		if prime_map.get(candidate_index) {
			continue;
		}

		prime_count += 1;

		if candidate_index > mark_limit_index {
			continue;
		}

		for i in (candidate_index..prime_map.len())
			.step_by(index_to_num(candidate_index) as usize)
		{
			prime_map.set(i);
		}
	}

	println!("Primes < {}: {}", LIMIT, prime_count);
}

Haritayi isaretlemeye sayinin karesinden baslama optimizasyonu yok, cunku onu sonra Wikipedia’yi okurken kesfettim :slight_smile: Haritanin isminin composite_map olmamasi da benzer sebepten—farkina vardigimda uzerinden bir suru commit gecmisti.

Bu arada time programini (/usr/bin/time) da denemek isteyebilirsiniz:

cargo build --release && \time target/release/sieve
    Finished release [optimized] target(s) in 0.00s
Primes < 1000000000: 50847534
4.98user 0.01system 0:04.99elapsed 100%CPU (0avgtext+0avgdata 62804maxresident)k
0inputs+0outputs (0major+15343minor)pagefaults 0swaps

bool vektorunden bitmap’e geciste maxresident’in tam 1/8’ine dustugunu gormek mumkun mesela ^^

1 Beğeni
28

Merhaba öncelikle, geçen gün kodu paylaşamamıştım benim yazdığım c++ kodu, c++ kategorisinde paylaştım
Asal sayı hesaplamak için yazdığım kod

evet build release ile çalıştırdım.
yeni verdiğiniz kodlar için netice şu şekilde hem debug hem release sonucunu paylaşacağım:
mehmetk@fedora:~/Programlama/rust/aib_bitmap_asal/target/debug$ time ./aib_bitmap_asal
Primes < 1000000000: 50847534

real 0m21,006s
user 0m20,930s
sys 0m0,030s

mehmetk@fedora:~/Programlama/rust/aib_bitmap_asal/target/release$ time ./aib_bitmap_asal
Primes < 1000000000: 50847534

real 0m2,491s
user 0m2,454s
sys 0m0,029s

debug yaklaşık 21sn,
release ise yaklşık 2.5 sn de sonuca ulaştı.

benim paylaştığım c++ kod,release derlerseniz şöyle sonuç veriyor;
mehmetk@fedora:~/Programlama/c++/YeniAsal/bin/Release$ ./YeniAsal
YeniAsal(OOP))PROGRAMI
Kaça kadar?

çıktı istiyormusun ? (1=istiyorum , başka sayı=istemiyorum)
1 ile 1,000,000,000 arasındaki Asal sayıları arayacağım

1 ile 1,000,000,000 arasında. 50,847,534 tane asal sayı buldum,
Bulunan Asal sayı hesap özetini “asalSayilar.txt” dosyasına kaydettim.

bulunan en son asal sayı: 999,999,937

Hesaplama zamanları özeti:
477 elemanlı vektör aç : 0.086701sn.
Asal sayıların hesaplanması : 1.62178sn.
Asal ayıklama + dosyalara yazılması: 0.553144sn.
toplam geçen süre : 2.26163sn.

başarılar ve iyi çalışmalar dilerim.

1 Beğeni
29

Ben sizler kadar bu işlerin içinde değilim, daha ziyade amatör…
kurduğum vektörde çift sayıları da eleyip sadece tek sayılara 1’er bit ayırarak 1/16 ya düşürdüm…

sırf rust’da durum ne olacak diye algoritmamı rusta geçireceğim, ama henüz bilgim yetersiz, 1-2 haftadır rust çalışıyorum. belki biraz daha hızlanır…

cevaplarınız için teşekkürler…

30

C/C++'tan cok farkli olmuyor genelde. Aradaki rahatlik katmanlarini optimize etmek kolay olmadigi icin kimi yerlerde daha kotu sonuc verebiliyor, ama en kotu ihtimal C veya C++ yazar gibi bir takim isleri dusuk seviye yapmak sorunu cozuyor—sorun olursa.