Obliczanie czasu który zajnie operacja

Na początku zaznaczę że jest to problem czysto matematyczny. Mam pętlę w której wyliczam tyle liczb pierwszych ile zachce użytkownik. Liczę sobie czas obliczania wszystkich liczb. Jak mogę obliczyć przewidywany czas obliczania tych liczb? Wiem że mogę to zrobić tak: <ilość liczb do obliczenia> * <średni czas liczenia jednej liczby> = <przewidywany czas="czas" obliczania="obliczania">. Nie wiem jednak jak obliczyć średni czas obliczania liczby przed wykonaniem całego liczenia i poznania czasu wykonywania wszystkich obliczeń. Średnią mogę obliczyć tak: <czas wykonywania wszystkich obliczeń> / <ilość wykonanych obliczeń> = <średni czas obliczania jednej liczby>. Próbowałem zrobić tak, że przed właściwym liczeniem, przeprowadzałem takie skrócone liczenie. W sensie że np. do obliczenia mam 10000 liczb, ale zanim to zrobię, dzielę ilość liczb do obliczenia przez np. 100, co daje mi 100. Więc zrobiłem taką pętlę (MAX to ilość obliczeń do wykonania):

// rozpoczęcie mierzenia czasu
for (unsigned long long i = 0; i < MAX; i += MAX / 100)
{
    // to samo co we właściwej pętli w której wyznaczane są liczby pierwsze
}
// zakończenie mierzenia czasu

Następnie robiłem tak (czas jest w nanosekundach, NANOSECONDS_TO_MILLISECONDS to 1.0 / 1000000.0): <średni czas obliczania jednej liczby> = <czas obliczania="obliczania"> / <ilość iteracji w pętli>, <przewidywany czas="czas" obliczania="obliczania"> = <średni czas obliczania jednej liczby> * <ilość liczb do obliczenia>, <przewidywany czas="czas" obliczania="obliczania" w="w" milisekundach="milisekundach"> = <przewidywany czas="czas" obliczania="obliczania"> * NANOSECONDS_TO_MILLISECONDS. Z jakiegoś powodu program twierdzi że obliczanie zajmie ułamki sekundy, co jest nieprawdą. Jak mogę to zrobić aby obliczyć przewidywany czas?

Chyba problem jest już w koncepcji "średniej"
Tak by było, gdyby złożoność obliczeniowa była liniowa. A w nietrywialnych algorytmach (liczby pierwsze) nigdy taka nie jest - inaczej by nie były zdawane studentom.

https://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa

Mógłbyś zmierzyć jak dużo liczb jesteś w stanie wyliczyć np. w 5ms i potem wykorzystać https://en.wikipedia.org/wiki/Prime-counting_function - przy czym dokładność wyniku będzie zależała od wykorzystywanego przez Ciebie algorytmu do sprawdzania pierwszości.

Nadal nie wiem jak mogę obliczyć ten czas...

Kamil B napisał(a):

Z jakiegoś powodu program twierdzi że obliczanie zajmie ułamki sekundy, co jest nieprawdą.

Dlaczego nieprawdą?

Jak mogę to zrobić aby obliczyć przewidywany czas?

Generalnie nie możesz. Jak Ci napisano wcześniej, problem wyznaczania liczb pierwszych nie ma złożoności liniowej, co oznacza, że nie możesz w sposób który opisałeś ekstrapolować wyniku. Możesz sobie oczywiście coś tam wyliczać, ale estymacja nie będzie realistyczna. Musiałbyś przeanalizować sam algorytm i określić jak wzrasta złożoność obliczeniowa wraz z kolejnymi liczbami do wyznaczenia.

Wiem, że każda następna obliczana liczba obliczana jest dłużej (na początku leci szybko, a potem konkretnie zwalnia). Dlatego też jestem niezadowolony z mojego paska postępu który na początku leci bardzo szybko a potem tak zwalnia że 1% zajmuje jakieś 10 minut. Tą nieproporcjonalność też chciałem rozwiązać tym czasem, bo bym obliczał tak: 100 * <ilość już zajętego czasu> / <przewidywany czas="czas">. Czyli ogólnie nie mogę wyliczyć tego czasu?

Dlaczego nieprawdą?

Dlatego, że gdy rozpoczyna się właściwe liczenie, trwa ono prawie minutę.

Oszacować tempo wyliczania danej ilości liczb pierwszych możesz, jeśli generujesz je przy uzyciu Sita Erastotenesa.
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

@Kamil B: Postawiłeś bardzo ciekawy problem. Jak mając problem do rozwiązania parametryzowany parametrem n próbować przewidywać potencjalny czas wykonania w przyszłości. Wydaje mi się, że byłaby szansa zrobić taki estymator w taki (przybliżony) sposób:

1. Dla uprzednio zdefiniowanych klas złożoności (wybierz jakie chcesz, wartałoby mieć O(n),O(n*n), O(log n), O(n * log n) potencjalnie inne).
2. Dopasuj w/w funkcje do zmierzonych czasów dla kilku wybranych wartości n za pomocą chociażby metody najmniejszych kwadratów. Oblicz błąd dopasowania
3. Użyj funkcji, która miała najmniejszy błąd jako estymatora dla n o które pyta user i wylicz czas. Podaj ten czas zastrzegając błąd dopasowania z punktu 2.

Tak mi się teraz wymyśliło, ale proszę szanownych Czytelników o weryfikację i ew. inne pomysły.

Ja jeszcze dodam, że kiedyś zamieszczałem przykład jak można liczyć liczby pierwsze w czasie kompilacji.
Z tego co pamiętam działało nawet dla zakresu do 500000 dla gcc 10

Biorąc pod uwagę "objawy" liczysz to złym algorytmem, bo sito ma złożoność prawie liniową (cześć logarytmiczna daje bardzo słaby efekt).

kapojot napisał(a):

@Kamil B: Postawiłeś bardzo ciekawy problem. Jak mając problem do rozwiązania parametryzowany parametrem n próbować przewidywać potencjalny czas wykonania w przyszłości. Wydaje mi się, że byłaby szansa zrobić taki estymator w taki (przybliżony) sposób:

1. Dla uprzednio zdefiniowanych klas złożoności (wybierz jakie chcesz, wartałoby mieć O(n),O(n*n), O(log n), O(n * log n) potencjalnie inne).
2. Dopasuj w/w funkcje do zmierzonych czasów dla kilku wybranych wartości n za pomocą chociażby metody najmniejszych kwadratów. Oblicz błąd dopasowania
3. Użyj funkcji, która miała najmniejszy błąd jako estymatora dla n o które pyta user i wylicz czas. Podaj ten czas zastrzegając błąd dopasowania z punktu 2.

Tak mi się teraz wymyśliło, ale proszę szanownych Czytelników o weryfikację i ew. inne pomysły.

Ja bym zmienił ideę: w oparciu o TEORETYCZNĄ wiedzę o złożoności tego konkretnego algorytmu. Czyli konieczny jest w procesie świadomy inteligentny człowiek.
Mamy najlepsze połączenie teorii z praktyką. Teoria wyznacza charakter złożoności (a miga się w/s stałego współczynnika) a praktyka bdb dopasuje współczynnik (negując możliwość praktycznego wykrycia charakteru złożoności "black box")

Nie mam pewności, czy metoda najmniejszych kwadratów dopasuje coś mądrego, gdy czas szybko rośnie wykładniczo. To chyba metoda wielomianowa? Jak mocno przymusić, to "coś" dopasuje, ale to będzie pozbawione fundamentów