Üstteki yazıyı yazarken araştırmadım. Ama bir zamanlar araştırmıştım. Aklımda log2(n) diye kalmış.
Kaynağım sağlam bir kaynak değil.
Yanlış bilgi verdiğimi düşünüyorsanız beni bilgilendirerek hatalarımı düzeltebilirsiniz.
CPython’un math.sqrt'yi nasıl impleme ettiğini bilmiyorum. 5 dakikadır kaynak kodlarına bakıyorum ama sadece isqrt’yi bulabildim, o da tahmin ettiğim gibi 64bit sayılar için fast path kullanıyor (bu da implementasyondaki optimizasyonların karmaşıklığı nasıl etkilediğine bir örnek).
Ama günümüzde çoğu işlemcinin float’ların karekökünü almaya özel instruction’ları (talimat?) var. Yani kök alma işlemi yazılım değil donanım seviyesinde gerçekleşiyor. Bu da kök işlemini O(1) civarına indiriyor.
1 Beğeni
En kısa olanı değil en okunabilir olanı yazmalarını tavsiye etmelisiniz bence
2 Beğeni
Zaten onu anlatmak istemiştim. Nasıl gereksiz kod kullanıp uzattıklarını görseniz. Kısa, net anlamında kullandım.
1 Beğeni
[print(n)for n in range(2,999)if all([n%i!=0 for i in range(2,n)])]
3 Beğeni
Eratosthenes kalburu kadar zaman kazandırmasa da ilk koda göre daha hızlı bir yöntem.
asallar = [2]
for sayi in range(3,1000000):
for bolen in asallar:
if sayi%bolen==0:
break
else:
asallar.append(sayi)
print(asallar)
2 Beğeni
import re
asal_degil = re.compile(R"^1?$|^(11+?)\1+$")
kaca_kadar = 1_000
asallar = [sayi
for sayi in range(kaca_kadar)
if not re.search(asal_degil, "1"*sayi)]
1 Beğeni
Cok bariz bir seyi atlamisim:
[print(n)for n in range(2,999)if all([n%i for i in range(2,n)])]
Sonuca ulasamayan bir takim denemeler:
[print(n)for n in range(2,999)if all(map(lambda i:n%i,range(2,n)))]
print(list(filter(lambda n:all([n%i for i in range(2,n)]),range(2,999))))
print(list(filter(lambda n:all(map(lambda i:n%i,range(2,n))),range(2,999))))
list(map(lambda n:print(n)if all(map(lambda i:n%i,range(2,n)))else 0,range(2,999)))
print(reduce(lambda p,n:p+[n]*all([n%i for i in p]),range(2,999),[]))
print(list(map(lambda n:all(map(lambda i:n%i,range(2,n))),range(2,999))))
1 Beğeni
Konu eski ve çözülmüş bir durum ama üzerinde konuşmaya değer.
Özellikle bu kısım zaten hoşuma gidip üzerinde konuşmaya değer bulduğum kısım.
Farklı dillerin eski versiyonlarını bilen dil sınıflandırma yaklaşımlarının bir kaçına bakan biri için aslında anlaşılabilir bir durum.
C/C++, Pascal gibi dillerde kod satır şeklinde işlenmez. Bloklar halinde işlenir yanı bloğun başlangıcını ve bitişini koda ayrıca bildirmeliyiz.
Mesela bunu c de { } küme parantezleri ile yaparız. Blok nerede başlar bildirir sonra nerede biter onu da ayrıca bildiririz. Bu parantezler olmadığında kod çalışmaz kodun nerede başlayıp bittiğini anlayamaz. Bu da yetmez bir kaç bloktan oluşan kod da oluşturabilir bir de komple kodu bitireyim diye sonuna ; noktalı virgül bildirimi ister mesela if koşullu karşılaştırmasında hem bloğu hemde else bağlantılarını ayrıca bildirmek ve else lerin bittiğini de ayrıca noktalı virgülle bildirmek gerekir.
Pascal bu işe daha da ilginç yaklaşır. Madem başlangıç ve bitiş bildireceğim ve yüksek seviye dilim o zaman begin ve end bildirimleri arasında yazalım blokları buradan anlarız gibi yaklaşım getiriyor kodun yarısı begin end lerle dolu oluyor.
Basic ve python gibi yorumlanan diller önden bir compile edilmeyeceği için (aslında belleğe yerleştirirken bir precompile durumu var ama konumuz bu değil) satır satır alıp işler. Yani beklenti satırlar içerisindedir ve bir sonraki satırda olup biteceklerin icabına sonra bakarız yaklaşımı vardır. Tabi kapsam/scope durumu biraz yanıltıcı olabilir sadece o satıra indiğinde anlamlı olarak faydalanılır ama önden o scope için pek ön almaz (optimizasyon da konumuz dışı o konuda da istisnalar var)
Bu durumda pyrhon içinde anahtar kelimeleriniz bloklanmadığından kapsamı nereye bağladığınız biraz kendi sorumluluğunuzda kalıyor bu nedenle şaşırmamak gerekir.
Ha madem başlığa girdik biraz faydası olsun kod konusunda da bir iki çift kelam edelim.
Bu asal sayı kodları neden öğrencilere öğretiliyor diye merak ediyorum açıkcası. Yani hani kriptografide asal sayı içeren fonksiyonlar aranan özelliktir, ne kadar büyük ve iyi bir asal sayınız varsa kriptografiniz o kadar geri döndürülemez şekilde olur mantığını anlarım.
Ama zaten böyle bir şeyle uğraşan çok az kişi vardır ve zaten bunlar da ilk bin asal sayı ile ilgilenmezler bile. Onlar bulabildiikleri en büyük asalsayının peşindelerdir.
Konumuz öğrenci ise hadi çocuklar asal sayı nedir biliyorlardır. Madem bildikleri bir konu Bunun üzerinde uygulama yaptırırsak programlamanın ne faydası var yada nasıl yapılır güzel bir egzersiz olabilir diye düşünülüyor herhalde.
Sonuçta, for, if döngüsü çalıştırmak için bildikleri bir konunun kuralları üzerinden yürümek faydalı olabilir. Belki (?!)
Bir bilgisayarın en iyi yaptığı işin iterasyon olduğunu düşünürsek tekrarlayan işleri yaptırmaya çalışmak ve bunu koşullara göre tekrarlatmak evet mantlıklı.
Yani eğitim amaçlı bir enstrüman olmuş asal sayılar.
Bu nedenle insanlık için küçük ama öğrenciler için büyük bir konu olmuş.
Olaya yeni bir yaklaşım getirmek adına şunu söyleyebilirim, evet bilgisayarlara tekrarlanan işlemler yaptırmak iyidir ama bu demek değildir ki olaya matematiksel olarak da bakılmasın.
Öğretim amaçlı kısımda tamam onlar dümdüz devam etsinler ama normal bir programcı olarak her zaman sınırlar olmalıdır. Ekonomi gibi, sonsuz isteklerle sınırlı kaynakların denkleştirilmesi ekonominin tanımıdır (Üretim planlama hocamın da kulakları çınlasın.)
Bu durumda malın zaman faydası, malın yer faydası gibi konulara da giresim var da neyse.
Yani her zaman gerçek dünyada size yeterli bellek, yeterli zaman verilmiyor olabilir. Bu durumda bazan düşündüğünüz gibi dümdüz gidemeyebiliyorsunuz.
Koşulları değiştirelim. Bellek sıkıntımız yok, zaman sıkıntımız var ne yaparız? Algoritmamızın en az iterasyonla yada en az koşulla bu işi yapmasını istesek neler yapabiliriz?
Gerçi python kullanan birinin bellek ve zaman kaygısı olmalımıdır o da ayrı bir konu.
Ama oldu ya kafa yorduk diyelim.
Olaya bu yöndem bakmak istedim. Şöyle ufak bir internet taraması.
Ve farklı bir yaklaşım buldum.
Tabi ki daha iyileri de araştırlabilir konu bellek olduğunda farklı yaklaşım gerekebilir ama biz iterasyon azaltabilir miyiz diye bakıyoruz varsayalım.
Şimdi bunu da lambda tek satıra da yazarız da üzerinde konuşulabilsin diye insan kodu olarak bırakmaya karar verdim:
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Kaynak: How to Check if a Number is Prime in Python - Geekflare
Neden böyle bir şey yapmış?
Onu da kaynakta grafiklerle açıklamış.
Tabi sizin öğrenciler bununla uğraşsın diye yazmadım bunları ama bir kod varsa kodun amacı da olmalı. Öğrenciler için koşul ve iterasyon egzersizi, programcılar ve matematikçiler için de asal sayı ve matematik egzersizi olarak bakmak gerekir diye düşünüyorum.
Kolay gelsin.
Bu arada kod üzerinde tartışabiliriz. Sizce yaklaşım mantıklı ?
1 Beğeni
Asal sayılar klasik sorulardan birisi. Bölünebilme var, karşılaştırma var, döngü var, hatta iç içe döngü var. Burada amaç aslında basit ve anlaşılabilir bir şey üzerinden kodlama mantığını anlatmak.
Bu konularda klasik sorularım var belki diğer öğretmenler yapmıyordur bilemiyorum.
Mesela karşılaştırmalar (karar verme, if) konusundan sonra illa ki, üç sayı istetip bu sayıların üçgen olup olmadığını, üçgense ne tür bir üçgen olduğunu (eşkenar, ikizkenar, dik üçgen ve çeşit kenar gibi) yaptırırım.
Bir de fonksiyonlar konusundan sonra mutlaka mükemmel sayılar, zengin sayılar, arkadaş sayılar soruları da klasiklerimin arasındadır.
def is_prime(n):
for i in range(2,int(n**0.5)+1):
if (n%i) == 0:
return False
return True
Şu kod için de math kütüphanesini eklemeden daha iyi değil mi sanki bilemedim.
Tercih meselesi, burada önemli olan karekök alma yaklaşımının performansı. Bu karakökü çok farklı şekillerde alabilirsiniz, C gibi bir dilde bitshift yaparak bile alabilirsiniz o kısmı tercih.
Burada önemli olan matematiksel yaklaşım. Belki daha iyi yaklaşımlar da vardır. Literatürü taramak lazım.
Eğitimci değilim, yani en azından yetiişkin eğitimi dışında bir eğitim bilgim yok beni aşar yaklaşımınız. Sadece bakınca bir de bu işe reküsif/özyinelemeli fonksiyon soruları da geldi aklıma onu da çok sever eğitimciler.
1 Beğeni
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
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
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
“Aklin yolu bir” diye bir sey var 
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
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
1 Beğeni
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 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
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
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…
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.