Hey,
Ich möchte so effizient wie möglich alle Teiler eines gegebenen
Es gibt verschiedene Möglichkeiten dieses Problem zu lösen.
Um das ganze jedoch so performant und effizient wie möglich zu machen, war die Idee zuvor Primzahlen auszuschließen.
Man muss natürlich sagen der Begriff "effizient" ist hier nur relativ, da Primzahlfaktorisierung zu den NP-Vollständigen Problem gezählt wird.
Ich habe im Internet rechercheirt und ein Python Skript gefunden das ziemlich schnell alle Teiler einer Zahl findet.
Dieses Skript habe ich versucht soweit es mir möglich war in C# umzuschreiben.
Original Python Code:
Die Primezahl funktion
Daher habe ich diesen Schritt vorerst mal durch ein Sieb des Eratosthenes ersetzt was (in meinem Fall) irgendwie ziemlich langsam ist.
Mein C# Code:
Die Klasse lässt sich wie folgt verwenden:
Beispielsweise, für
Das Problem ist mein Code benötigt dafür
Wie kann ich meinen Code optimieren und wie bekomme ich die python-prime Funktion in C# umgeschrieben?
Zusätzlich stelle ich mir die Frage ob sich das ganze später noch weiter verbessern lässt indem bereits gefundene Primzahlen gecached werden und nicht neu generiert werden müssen ö.Ä?
Aber zuerst mal geht es darum das ganze an sich nahe an die Laufzeit des Pythonskripts zu bekommen.
Ich möchte so effizient wie möglich alle Teiler eines gegebenen
int
finden. (Eventuell mit dem Hintergedanken das später auf long zu erweitern).Es gibt verschiedene Möglichkeiten dieses Problem zu lösen.
Um das ganze jedoch so performant und effizient wie möglich zu machen, war die Idee zuvor Primzahlen auszuschließen.
Man muss natürlich sagen der Begriff "effizient" ist hier nur relativ, da Primzahlfaktorisierung zu den NP-Vollständigen Problem gezählt wird.
Ich habe im Internet rechercheirt und ein Python Skript gefunden das ziemlich schnell alle Teiler einer Zahl findet.
Dieses Skript habe ich versucht soweit es mir möglich war in C# umzuschreiben.
Original Python Code:
C#-Quellcode
- from itertools import compress
- def primes(n):
- """ Returns a list of primes < n for n > 2 """
- sieve = bytearray([True]) * (n//2)
- for i in range(3,int(n**0.5)+1,2):
- if sieve[i//2]:
- sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
- return [2,*compress(range(3,n,2), sieve[1:])]
- def factorization(n):
- """ Returns a list of the prime factorization of n """
- pf = []
- for p in primeslist:
- if p*p > n : break
- count = 0
- while not n % p:
- n //= p
- count += 1
- if count > 0: pf.append((p, count))
- if n > 1: pf.append((n, 1))
- return pf
- def divisors(n):
- """ Returns an unsorted list of the divisors of n """
- divs = [1]
- for p, e in factorization(n):
- divs += [x*p**k for k in range(1,e+1) for x in divs]
- return divs
- n = 2147483646
- primeslist = primes(int(n**0.5)+1)
- print(divisors(n))
Die Primezahl funktion
def primes(n)
habe ich nicht ganz verstanden.Daher habe ich diesen Schritt vorerst mal durch ein Sieb des Eratosthenes ersetzt was (in meinem Fall) irgendwie ziemlich langsam ist.
Mein C# Code:
C#-Quellcode
- public class DivisorFinder
- {
- private int _number;
- public DivisorFinder(int number)
- {
- _number = number;
- }
- private IEnumerable<int> FindPrimes(int upperLimit)
- {
- var composite = new BitArray(upperLimit);
- var sqrt = (int) Math.Sqrt(upperLimit);
- for (int p = 2; p < sqrt; ++p)
- {
- if (composite[p])
- continue;
- yield return p;
- for (int i = p * p; i < upperLimit; i += p)
- composite[i] = true;
- }
- for (int p = sqrt; p < upperLimit; ++p)
- if (!composite[p])
- yield return p;
- }
- private IEnumerable<(int, int)> FindPrimeFactors(IEnumerable<int> primesList)
- {
- var factors = new List<(int, int)>();
- foreach (var prime in primesList)
- {
- if (prime * prime > _number)
- break;
- int count = 0;
- while (_number % prime == 0)
- {
- _number = _number / prime;
- count++;
- }
- if (count > 0)
- factors.Add((prime, count));
- }
- if (_number > 1)
- factors.Add((_number, 1));
- return factors;
- }
- public IEnumerable<int> FindDivisors()
- {
- var primes = FindPrimes((int) (Math.Pow(_number, 0.5) + 1));
- var factors = FindPrimeFactors(primes);
- var divisors = new HashSet<int> {1};
- foreach (var factor in factors)
- {
- var stuff = new HashSet<int>();
- for (int i = 0; i < factor.Item2 + 1; i++)
- {
- foreach (int x in divisors)
- {
- stuff.Add((int) Math.Pow(x * factor.Item1, i));
- }
- }
- divisors.UnionWith(stuff);
- }
- Console.WriteLine($"Found {divisors.Count()} divisors.");
- return divisors;
- }
- }
Die Klasse lässt sich wie folgt verwenden:
C#-Quellcode
- private static void Main()
- {
- var number = 2147483637;
- var stopWatch = new Stopwatch();
- var divisorFinder = new DivisorFinder(number);
- Console.WriteLine($"Target value: {number}");
- stopWatch.Start();
- var divisors = divisorFinder.FindDivisors();
- stopWatch.Stop();
- var timeSpan = stopWatch.Elapsed;
- Console.WriteLine(string.Join(", ", divisors));
- Console.WriteLine($"Completed after {timeSpan.Seconds}:{timeSpan.Milliseconds}");
- Console.ReadKey();
- }
Beispielsweise, für
2147483637
bekomme ich folgendes Ergebnis, welches auch korrekt ist:Das Problem ist mein Code benötigt dafür
~18 Sekunden
, das Python Skript nur wenige Millisekunden.Wie kann ich meinen Code optimieren und wie bekomme ich die python-prime Funktion in C# umgeschrieben?
Zusätzlich stelle ich mir die Frage ob sich das ganze später noch weiter verbessern lässt indem bereits gefundene Primzahlen gecached werden und nicht neu generiert werden müssen ö.Ä?
Aber zuerst mal geht es darum das ganze an sich nahe an die Laufzeit des Pythonskripts zu bekommen.
C# Developer
Learning C++
Learning C++
Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „Rikudo“ ()