Progblemet #5
Har sett en del frågor från personer som haft någon programmeringsuppgift som involverar primtal, så varför inte köra ett progblemet kring detta för att visa hur det ser ut i lite olika språk.
Primtal är ett positivt heltal som bara är jämt delbart med 1 och sig sjäv. De första tio primtalen är
2, 3, 5, 7, 11, 13, 17, 19, 23 och 29
En av de mer effektiva algoritmer för att beräkna primtal upp till ett par miljoner kallas sieve of eratosthenes. Denna algoritm kan implementeras väldigt effektivt i t.ex. C eller C++ genom att skapa en bit-array där varje bit representerar udda nummer (jämna nummer kan aldrig vara primtal då de är delbara med 2). En nackdel med denna algoritm är att den beräknar alla primtal upp till en given gräns.
Problemet som ska lösas denna gång är att beräkna det miljonte primtalet. Värdet på detta är 15,485,863.
Här kommer en lösning i ett språk jag verkligen börjar gilla skarpt, Go.
package main
import "fmt"
import "math"
func isPrime(n uint, primes []uint) bool {
limit := uint(math.Sqrt(float64(n)))
for i := 0; primes[i] <= limit; i++ {
if n % primes[i] == 0 {
return false
}
}
return true
}
func producePrimes(ch chan uint) {
primes := []uint{3}
ch<- 2
ch<- 3
for n := uint(5); ; n += 2 {
if isPrime(n, primes) {
ch<- n
primes = append(primes, n)
}
}
}
func main() {
primes := make(chan uint)
defer close(primes)
go producePrimes(primes)
for i := 1; i < 1000000; i++ {
<-primes
}
fmt.Println(<-primes)
}
Första raden i "main" skapar en kanal. En kanal i Go är en starkt typad enkelriktad kommunikationskanal, i detta fall är det en kanal av positiva heltal, uint.
Nästa är rent tekniskt onödig i detta program då alla resurser städas upp när main avslutas, men tar med den för att visa en väldigt trevlig finess i Go. defer är ett nyckelord som säger att den "closure" som följer måste köras när man avslutar nuvarande funktion, oavsett hur man avslutar funktionen. I detta fall stänger jag kommunikationskanalen, d.v.s close(primes) kommer inte köras vid rad 2 utan precis innan man avslutar main.
Sedan startas en asynkron "closure" m.h.a. nyckelordet go. I detta fall är det funktionen producePrime jag startar asynkront. Den funktion kan köras på en annan CPU-kärna på ett system som har flera CPU-kärnor.
<-primes läser ett värde som den andra änden, producePrime i detta fall, skriver. Resultatet är en värde av typen som kanalen har, uint i detta fall. De första 999,999 primtalen slängs bara bort och det 1,000,000:e skrivs ut.
Produce prime skapar en s.k. "slice" som innehåller alla udda primtal vi beräkat. En "slice" är väldigt lik en "array" i Python eller "vector<>" i C++, den kan alltså växa allt eftersom man lägger till element i slutet av den.
Första produceras primtalen 2 och 3. 5 är det första tal som testas om det är ett primtal och sedan testas vart annat tal efter det. Notera att producePrime inte kommer äta 100% CPU då kanalen jag skapat inte innehåller en buffer och således inte kan köa tal. Den som skriver till kanalen kommer i detta fall blocka om det inte finns någon som väntar på att läsa i andra änden, men det är möjligt att skapa kanaler som kan hålla ett eller flera tal i en intern buffer.
Detta fungerar alltså väldligt mycket som "lazy evaluation" som många funktionella språk har, d.v.s. ett värde beräknas inte innan man verkligen behöver det. Men man får även fördelen av att man potentiellt kan använda en separat CPU-tråd för beräkningen.
Att göra denna beräkning tog 2.5s på en 2760QM (2.4GHz Sandy Bridge) körandes Ubuntu 12.10.
Edit: och för att förtydliga idén kring "progblemet" trådarna. Tanken är att de som har kunskapen och orken ska posta sina egna lösningar till detta problem. Tanken är att det kommer visa interesserade personer hur man löser ett relativt enkelt problem på lite olika sätt och framförallt hur dessa lösningar kan gestalta sig i lite olika programmeringspråk!
Det är naturligtvis helt OK att posta flera lösningar i språk man själv eller andra redan postat en lösning i. Det finns ju ofta långt mer än ett sätt att lösa ett givet problem.
Att jag lagt in exikveringstiderna är att många verkar gilla att jämföra hastigheten på sina lösningar med andra
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
