[C++] Implementacja kodu

Witam

Ostatnio wykonywałem śmieszne zadanie na jakiejś ze stron chyba SPOJ. Zadanie polegało na wczytaniu N liczb i odpowiedzeniu czy ona jest pierwsza czy też nie.

Zadanie rozwiązałem najprostszą metodą ( zakres był niewielki(chyba 10k) to tym bardziej idealnie się ten algorytm nadawał) sitem Eratostenesa na początku generowałem se tą tablice następnie po wczytaniu liczby odwoływałem się do tablicy np tab[liczba] i jeżeli true to TAK jest pierwsza w przeciwnym wypadku niet. czas był chyba koło 0,07 s no więc szukałem ulepszenia bo na 1 miejscu ktoś miał 0,00 s więc po krótkim namyśle wstawiłem cała tablice liczb pierwszych na sztywno do programu np.
bool tab[]={0,0,1,1,0,1,....}; więc generowanie tablicy miałem z głowy więc od razu można było praktycznie podawać odpowiedzi ku mojemu zaskoczeniu czas działania programu wyniósł 0,12 s (wysyłałem paro razy) może mi ktoś wytłumaczyć dlaczego?

Więc wnerwiony zrobiłem wydawało by się jeszcze prościej
Już nie sprawdzałem czy true czy false tylko w tablicy były wbite na sztywno odpowiedzi TAK / NIE
ale wtedy czas mnie już zdenerwował wyniósł 1,2 s i dlaczego? nie zmieniłem metody wczytywania / drukowania znaków (printf,scanf)

Bardzo bym był wdzięczny jak by mi mógł to ktoś wyjaśnić :)

Dzięki!

Zrobiłeś lokalną tablicę w main, na stosie, tak?

raz lokalnie a raz globalnie a właśnie lokalnie zmienne są na stosie przechowywane? i czy stos ma określoną pojemność? Bo myślałem ,że zmienne są przechowywane w Ramie tak jak np ta tablica. i Jak bym mógł prosić to czy może ktoś napisać jaka różnica między zmienną taką a taką nie chodzi mi o podstawy.

Zmienne lokalne są na stosie, dynamicznie tworzone są na stercie. Statyczne klamoty lądują jako część modułu. Zmienne lokalne mają to do siebie, że przy każdym wejściu do funkcji muszą zostać wypełnione, globlobalne/statyczne są wypełniane w czasie kompilacji lub inicjalizacji programu (to raczej w C++). Takie wypełnianie lokalne w wykonaniu GCC może nawet być wolniejsze niż wygenerowanie danych sitem, zależy jak to kompilator wygeneruje.

aha dzięki wielkie :) ale jak ktoś ma dodatkowe uwagi rady niech pisze :) a czy stos ma jakiś ustalony rozmiar gdzieś czytałem ,że zawsze ma 1 MB ale nie wiem czy to prawda.

Zależy od formatu plików wykonywalnych/systemu - część z nich ma zapisany rozmiar stosu w nagłówku (np. Windowsowe PE mają minimalny rozmiar stosu, maksymalny, który może być nawet na 0, nowsze systemy i tak powiększają do oporu). Generalnie każdy system raczej pozwala takie rzeczy ustawić, stara się powiększyć stos jeżeli program tego potrzebuje.

A teraz znów pytanko znalazłem to zadanie i napisałem taki kod (proszę się nie śmiać :D)

//bezbibliotek :P
bool tab[]={0,0,1,1..};//i tutaj ta tablica nie wkleje całej :P
char A1[2]={'N','T'};
char A2[2]={'I','A'};
char A3[2]={'E','K'};
int main()
{

    unsigned n;
    we(&n);//własna funkcja wczytywania szybsza od scanfa tak na moje potrzeby
    while(we(&n))
    {
        printf("%c%c%c\n",A1[tab[n]],A2[tab[n]],A3[tab[n]]);
    }
    return 0;
}

jak generowałem to sitem i sprawdzałem czy true/false czas miałem 0,07 a z kodem powyżej 0,13 chociaż nic nie jest liczone :D

po zamianie na scanfy czas 0,21... więc nie wina w mojej funkcji wczytywania

Przede wszystkim to użyj puts/fwrite bez takiego kombinowania z tablicami znaków, poza tym trzy razy indeksujesz tablicę, po jaką cholerę? Szczerze? Nie mam pojęcia co spaprałeś...

za bardzo nie wiem jak np string A[2]={"TAK","NIE"}; nie wiedziałem jak to wydrukowac printfem więc poszedłem na łatwizne :) i drukuje literki po kolei

Wypisując pojedyncze stringi szybciej niż tak się nie da:

fwrite(tab[n] ? "TAK\n" : "NIE\n", 1, 4, stdout);

Dobrym wyjściem jest złożyć całość wyjścia w tablicy i zapisać dopiero po sprawdzeniu wszystkiego jednym wywołaniem fwrite.

Gelldur napisał(a)

//bezbibliotek :P

Nie „bez bibliotek”, bo printf() jest w <stdio.h>. To że się kompiluje nie znaczy że tak jest dobrze. Najnowszy (ha! najnowszy... dziesięcioletni) standard C99 zresztą już nie pozwala na takie printf z kosmosu.

@up chodziło mi o to ,że bibliotek nie wkleiłem a nie ,że nie użyłem :)

Wypisując pojedyncze stringi szybciej niż tak się nie da:

fwrite(tab[n] ? "TAK\n" : "NIE\n", 1, 4, stdout);

Dobrym wyjściem jest złożyć całość wyjścia w tablicy i zapisać dopiero po sprawdzeniu wszystkiego jednym wywołaniem fw

Twoim sposobem miałem też czas 0,12 a co do tablicy ze stringami to nie mieszczą się w zadaniu zajmują koło 60k B a max jest 50k B