Witam,
napisałem algorytm wyszukujący liczby zaprzyjaźnione w C. Jednak dla np. 10000000 wykonuje obliczenia w czasie 107s. Czy można bardziej zoptymalizować algorytm by wykonywał się szybciej oraz czy funkcję wyszukujące dzielniki poprawnie napisałem?
Z cacheować wyniki? Są tylko 42 takie pary liczb, mniejszych niż milion.
tzn.?
Tzn. liczysz sobie raz te 107 sekund, a następnie wynik zaszywasz w kodzie programu (dostęp w czasie stałym). Tych liczb jest mało. Tak się bardzo często robi z różnymi magicznymi liczbami pierwszymi w STL-u.
Takie rozwiązanie odpada 
(bo na lab …)
Nie rozumiem czemu odpada. Moim zdaniem jest to prosta obserwacja tego, że zbiór liczb spełniających warunki jest rzadki, a do tego jego rozwiązanie jest klasy NP-Hard. W celu optymalizacji stosujemy prosty hard-kod, bądź ujmując profesjonalnie metodę słownikowania.
Jedyna optymalizacja jaką widzę, to zmniejszenie liczby if-ów przy drugim odwołaniu do funkcji suma dzielników. Po jedno razowym jej przejściu
for(i=2; i<=where; i++)
if(liczba%i == 0)
jak już raz przejdziesz tego if-a, to możesz zapamiętywać w jakimś zbiorze, które liczby go spełniły i wtedy przy kolejnych wywołania po prostu pominąć (wykonać tylko dla liczb ze zbioru). Ale ponieważ wywołania są tylko 2 to może przyśpieszy sekundę, czy dwie.
Dzięki
Czym są liczby zaprzyjaźnione? Czy chodzi o liczby sprężone, a może o liczby zespolone?
https://pl.wikipedia.org/wiki/Liczby_zaprzyjaźnione
Liczby zaprzyjaźnione to para różnych liczb naturalnych, takich że suma dzielników każdej z tych liczb równa się drugiej (nie uwzględniając tych dwóch liczb jako dzielników).
Pierwszą parą takich liczb, która została podana już przez Pitagorasa, jest para liczb 220 i 284, ponieważ:
Nie wiadomo, czy istnieje nieskończenie wiele par liczb zaprzyjaźnionych i czy istnieje taka para liczb o różnej parzystości.
Niestety, chyba zbyt duże wykorzystanie pamięci, bo gdzieś po 430402 dostaję segfaulta.
⌁ [enedil:~/Desktop] 5s 139 $ cat MojaWersja.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
int sumaDzielnikow(int liczba);
int main()
{
int liczbaPierwsza=0;
int liczbaDruga=0;
int i=0;
int wprowadzona;
printf(": ");
scanf("%d",&wprowadzona);
clock_t t;
t=clock();
int *sumy;
sumy = malloc((wprowadzona + 1) * sizeof(int));
sumy[0] = 0;
sumy[1] = 1;
for(i = 2; i <= wprowadzona; i++) {
sumy[i] = sumaDzielnikow(i);
}
for(i = 1; i <= wprowadzona; i++){
liczbaPierwsza = i;
liczbaDruga = sumy[liczbaPierwsza];
if(liczbaDruga > liczbaPierwsza)
if(sumy[liczbaDruga] == liczbaPierwsza)
printf("%d\t\t\t%d\n\n", liczbaPierwsza, liczbaDruga);
}
t = clock()-t;
printf("\nCzas dzialania programu: %f\n",((float)t/CLOCKS_PER_SEC));
return 0;
}
int sumaDzielnikow(int liczba)
{
int sumaDz=1;
int i;
int where;
where=floor(sqrt(liczba));
for(i=2; i<=where; i++)
if(liczba%i == 0)
if((liczba/i) != i)
sumaDz+=i+liczba/i;
else
sumaDz+=i;
return sumaDz;
}
⌁ [enedil:~/Desktop] $ clang MojaWersja.c -o moja
MojaWersja.c:56:4: warning: add explicit braces to avoid dangling else [-Wdangling-else]
else
^
1 warning generated.
⌁ [enedil:~/Desktop] $ clang TwojaWersja.c -o twoja
TwojaWersja.c:47:4: warning: add explicit braces to avoid dangling else [-Wdangling-else]
else
^
1 warning generated.
⌁ [enedil:~/Desktop] $ ./moja
: 10000
220 284
1184 1210
2620 2924
5020 5564
6232 6368
Czas dzialania programu: 0.004872
⌁ [enedil:~/Desktop] 4s $ ./twoja
: 10000
220 284
1184 1210
2620 2924
5020 5564
6232 6368
Czas dzialania programu: 0.005998
⌁ [enedil:~/Desktop] 3s $ ./moja
: 1000000
220 284
1184 1210
2620 2924
5020 5564
6232 6368
10744 10856
12285 14595
17296 18416
63020 76084
66928 66992
67095 71145
69615 87633
79750 88730
100485 124155
122265 139815
122368 123152
141664 153176
142310 168730
171856 176336
176272 180848
185368 203432
196724 202444
280540 365084
308620 389924
319550 430402
Segmentation fault: 11
Dzięki enedil za propozycję, ale pamięć dynamiczna tutaj się nie sprawdzi bo nie wiem jaką liczbę wprowadzi na wejściu prowadzący (a będzie duża ). Faktem jest to, że tylko raz odwołujesz się do funkcji sumaDzielnkow() co wpływa bardzo na szybkość.
Czy jest inna możliwość ?
edit:
sumy = malloc((wprowadzona + 1) * sizeof(int));
nie powinno być:
sumy = (int*) malloc((wprowadzona + 1) * sizeof(int));
?
Nie dokońca rozumiem jak może to pomóc, ale dla liczb względznie pierwszych, funkcja ta jest łączna multiplikatywnie, czyli sumaDzielnkow(a*b) = sumaDzielnkow(a) * sumaDzielnkow(b).
Zaufane źródła twierdzą, że nie ma to znaczenia.
Takie rzeczy szybko zdiagnozujesz korzystając z debuggera, przykład:
/home/tomek/roboczy/prog/test$ clang -g -o a a.c -lm
a.c:59:4: warning: add explicit braces to avoid dangling else [-Wdangling-else]
else
^
1 warning generated.
/home/tomek/roboczy/prog/test$ ./a > /dev/null
1000000
Segmentation fault (core dumped)
/home/tomek/roboczy/prog/test$ gdb -q a a.core
/home/tomek/.gdbinit:1: Error in sourced command file:
Undefined command: "python". Try "help".
Core was generated by `a'.
Program terminated with signal 11, Segmentation fault.
Reading symbols from /lib/libm.so.5...done.
Loaded symbols for /lib/libm.so.5
Reading symbols from /lib/libc.so.7...done.
Loaded symbols for /lib/libc.so.7
Reading symbols from /libexec/ld-elf.so.1...done.
Loaded symbols for /libexec/ld-elf.so.1
#0 0x0000000000400985 in main () at a.c:36
36 if(sumy[liczbaDruga] == liczbaPierwsza)
(gdb) q
I już widzisz że wychodzisz poza tablicę ‘sumy’, dodaj warunek sprawdzający czy liczbaDruga nie jest większa niż rozmiar tablicy:
if(liczbaDruga > liczbaPierwsza && liczbaDruga < wprowadzona+1)
{
if(sumy[liczbaDruga] == liczbaPierwsza)
printf("%d\t\t\t%d\n\n", liczbaPierwsza, liczbaDruga);
}
ale jeśli algorytm ma być prawidłowy to musisz większy rozmiar tablicy zadać.
tomms i enedil DZIĘKI za pomoc !!! =D
Przy wejściu 10000000 tylko ~70s ! (33mb ram)
I co, to wszystko? Dostateczny z minusem 
Funkcja sumaDzielników jest nadal do kitu ;) Skoro masz tablice dlaczego nie liczysz sumy dzielników przy użyciu mnożeń tylko reszty z dzielenia? Raz że złożoność zamiast n*logn masz n^2, dwa, że wykorzystujesz dzielenia co zajmuje od 20 do 80 cykli procesora(zamiast 4). Poza tym zapotrzebowanie na RAM w stylu Chrome, bo dla zakresu 1mld liczb wyniesie aż 4-8GB. Ale w tej sprawie nie mam koncepcji.
Na moim kompie wykonanie tej niby lepszej wersji zajmuje aż 650s (Pentium M ULV 1.1GHz) myśle że można by to zbić do 200s (u Ciebie do 10-20s).
Poprawka na
int sumaDzielnikow(int liczba)
{
int sumaDz=1;
int i;
//int where;
//where=floor(sqrt(liczba));
for(i=2; /*i<=where*/ i*i<=liczba; i++)
if(liczba%i == 0)
if((liczba/i) != i)
sumaDz+=i+liczba/i;
else
sumaDz+=i;
return sumaDz;
}
Poprawiła czas 69s ;). Dzięki! Temat do zamknięcia, bo oddaje za 1h.
Taka optymalizacja to żadna optymalizacja, nie o to mi chodziło, okej za póxno na poprawki. Ale dlaczego temat do zamkniecia? Jesteś pewny zaliczenia? Jako jedyny miałeś i bedziesz mieć takie zadanie? Na temat problemu nie można dalej prowadzić dyskusji? Optymalizacje sprawdze we własnym zakresie, w swoim czasie dla własnej ciekawości skoro temat chcesz zamykać.
3.13 Zabrania się umieszczania próśb w celu odrobienia pracy domowej, zleceń (np. zrobienie strony WWW, napisanie kodu, i.t.p.), zaliczeń etc. jak i podawania rozwiązań w organizowanych quizach.
Kto tak powiedział ? 
,można spróbować podmienić funkcję sumy dzielników na Funkcje σ, ew podzielić zadanie na procesy