C#: Kan noen gi kommentarer på mitt nye (enkle) program?

[Deaktivert Konto]

Mitt første program som jeg har lagte selv i C# ble nettopp ferdig. Det viser nokk at det var en newb som programmerte det da... Har tidligere programmert et lignende program på en ti-83 kalkulator med rimelig bra resultat, men den var ganske treg.

 

I bunn og grunn er programmet bare en primtall-finner. Jeg tok tiden på hvor fort den kunne kalkulere tall:

 

Den kalkulerte de første 100 primtallene etter 10^15 (1,000,000,000,000,000) på 2 minutter.

Den kalkulerte det første primtallet etter 10^18 (1,000,000,000,000,000,000) på 34 sekunder.

 

Det eneste lille problemet er at programmet deler tallet på alle tall opptil sqrt(tallet) for å finne ut om det er et primtall..

 

Her er koden:

 

//C# kode

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace prime
{
   class Program
   {
       static void Main(string[] args
           /*Her skal programmet få inn en array av args
            * med [0] som primtallet det skal begynne fra,
            * og [1] som antall primtall etter [0] programmet skal finne*/)
       {
           ulong primeEnter = Convert.ToUInt64(args[0]) - 1; //(-1) pga at senere i programmet så må man legge til én
           ushort numberOfPrimes = Convert.ToUInt16(args[1]); //numberOfPrimes = nummer programmet skal finne.
           bool tester = false; //Hvis tester = true så er det et primtall.
           for (ushort i = 0; i < numberOfPrimes; i++) //egentlig hele programmet her. Det repeteres til du finner "numberOfPrimes" primtall.
           {
               while (tester == false) //mens det ikke er et primtall
               {
                   primeEnter++; //legg til én og prøv igjen. Dette er grunnen for at jeg la til (-1) i linje 17.
                   tester = FirstPrime(primeEnter); //denne returnerer true hvis den finner at det er et primtall
               }
               Console.WriteLine(primeEnter); //tester må være true her, altså er det et primtall.
               tester = false; //stiller tilbake boolen.
           }
       }

       static bool FirstPrime (ulong primeTester)
       {
           double squareRt = Math.Sqrt(primeTester); 
           uint i = 2; //denne skal primeTester deles på. Om det kommer ut at den deles uten noen desimalplasser, finner programmet ut at det ikke er et primtall.
           bool test = false;
           while (i <= squareRt) //hvis i er større enn squareRt er i et primtall.
           {
               if (primeTester % i == 0) //altså, primeTester er ikke et primtall
               {
                   i = 4290000000; //for å få i større en squareRt
                   test = true; //true betyr at det ikke er et primtall
               }
               i++; //ellers legger man til 1 og prøver igjen.
           }
           if (i != 4290000001) //primtall vil ha dette som verdi.
           {
               if (test != true) //primtall vil også ha dette som verdi
               {
                   return true; //dermed vet man at det er et primtall.
               }
               else
               {
                   return false; //det vil være et primtall om det kommer i denne kategorien.
               }
           }
           else
           {
               return false; //det vil være et primtall om det kommer i denne kategorien.
           }

       }
   }
}

 

 

Er det noen som kan gi tilbakemeldig?

 

På forhånd takk;

-DLA

[MailMan13]

Du lagrer kvradratroten i en double, som du så gjør fryktelig mange sammenligninger mot. Hvis du lagrer Ceil(Sqrt(primeTester)) i en uint eller long i stedet vil du spare litt tid. Hos meg går kjøretiden for de første 100 primtallene etter 10^15 ned fra 72 til 48 sekunder hvis jeg gjør det. Beregninger på heltaqllstyper er en god del raskere enn flyttall som double.

 

Det er en del redudante variabler og kodelinjer her. F.eks når du finner et tall som ikke er et primtall, kan du ikke bare returnere false med en gang? Da forsvinner 429000000[01] greiene, testvariabelen forsvinner og alle testene etter loopen forsvinner. Da blir den slik (jeg har renamet den til IsPrime, siden det er det den returnerer):

static bool IsPrime (this ulong primeTester)
{
   var squareRt = (uint)Math.Ceiling(Math.Sqrt(primeTester)); 
   uint i = 2; //denne skal primeTester deles på. Om det kommer ut at den deles uten noen desimalplasser, finner programmet ut at det ikke er et primtall.

   while (i <= squareRt) //hvis i er større enn squareRt er i et primtall.
   {
       if (primeTester % i == 0) //altså, ikke et primtall, returner false umiddelbart
           return false;

           i++; //ellers legger man til 1 og prøver igjen.
   }

   return true; // Ingen divisjoner gikk opp, det må være ett primtall
}

 

Det er litt støy i main metoden, det der +/- 1 greiene og nøsting av løkker. Vi kan utnytte et par Linq / IEnumerable features for å rulle det ut og få det på litt mer funksjonell form. Det gjør ikke noe hverken fra eller til med ytelsen, men intensjonen med koden kommer bedre frem for leseren uten at det koster noe, men en del flytkontroll og kommentarer faller bort:

static void Main(string[] args)
{
   ulong primeEnter = Convert.ToUInt64(args[0]); // start her, ingen -1 her lenger

   ushort numberOfPrimes = Convert.ToUInt16(args[1]); //antall programmet skal finne.

   var primes = NumbersFrom(primeEnter).Where(x => x.IsPrime()); // ingen løkke, angir at vi skal enumerere alle tall fra primeEnter som tilfredstiller funksjonen x => IsPrime(x)

   foreach(var prime in primes.Take(numberOfPrimes)) // så plukker vi numberOfPrimes første
       Console.WriteLine(prime);
}

//Hjelpemetode som enumererer tall oppover fra og med start til ulong.MaxValue
private static IEnumerable<ulong> NumbersFrom(ulong start)
{
   while(start <= ulong.MaxValue)
       yield return start++; 
}

Endret 27. november 2010 av MailMan13

[GeirGrusom]

Det er forresten ikke noe poeng å teste om partall er primtall, det er de aldri.

[MailMan13]

Forsåvidt, men det gir ikke noe observerbar effekt å optimalisere for det.

[GeirGrusom]

Overraskende... det burde bli vesentlig færre tall å sjekke imot...

[MailMan13]

Ja, bare halvparten så mange tall, men partall vil bli funnet i første iterasjon i IsPrime.

 

Det man sparer er en god del metodekall, men dem koster forsvinnende lite i forhold til tiden det tar å sjekke øvrige tall.

 

Mulig du vil kunne se effekt av det om du kjører med lavt startpunkt, svært mange tall og kjører med debugger tilkoblet. Debuggeren vil hindre JIT compileren i å inline / optimalisere IsPrime og MoveNext() fra iterator blokken, og lavt startpunkt minimerer kostnaden ved sjekk på ikke-partallene. Da får vi optimalisert effekten av optimaliseringen....

Endret 27. november 2010 av MailMan13

[Deaktivert Konto]

Tusen takk MailMan, men jeg skjønner ikke helt:

 

Kan du forklare dette litt bedre?

 var primes = NumbersFrom(primeEnter).Where(x => x.IsPrime()); // ingen løkke, angir at vi skal enumerere alle tall fra primeEnter som tilfredstiller funksjonen x => IsPrime(x)

   foreach(var prime in primes.Take(numberOfPrimes)) // så plukker vi numberOfPrimes første
       Console.WriteLine(prime);

[GeirGrusom]

Han lager først en enumerator for å hente ut primtall ved å be den om å hente ut alle tall fra 1 til PrimeEnter hvor tallet tilfredsstiller IsPrime. Deretter bruker han Take for å hente ut så mange primtall som oppgaven sier ifra denne enumeratoren.

 

x => x.IsPrime()

Dette er et lambdauttrykk. Den tar x som parameter, og returnerer om x er et primtall. Datatypene blir hentet utifra sammenheng.

Det er en kort måte å skrive anonyme funksjoner på. I tidligere C# versjoner kunne en skrevet dette istedet:

 

var primes = NumbersFrom(primeEnter).Where(delegate(ulong x) { return x.IsPrime(); });

 

Eller enda verre, dette:

 

private bool IsNumberPrime(ulong x) { return x.IsPrime() }
...
var primes = NumbersFrom(primeEnter).Where(new Funct<ulong,ulong>(IsNumberPrime));