Ocena kodu.

0

Dzień dobry.

Dostałem zadanie:

Wprowadzić ciąg liczb, którego weilkości n. Wprowadzić dwie dodatkowe liczby a i b. We wprowadzonym ciągu wszystkie liczby, które są podzielone przez a i b , zamienić na zero. Wyprowadzić nowy ciąg.

Napisałem kod:

#include <stdio.h>
#include <stdlib.h>


void readInput(char*, void*);
void replace_int(int*, size_t, int, int, int);

int main(int argc, char** argv){
    size_t size=0;
    int a=0;
    int b=0;

    printf("Wprowadz ilosc liczb: ");
    readInput("%Iu", &size);

    printf("Wprowadz pierwsza liczbe do sprawdza podzielnosci: ");
    readInput("%d", &a);
    
    printf("Wprowadz druga liczbe do sprawdzania podzielnosci: ");
    readInput("%d", &b);

    int* numbers = (int*)calloc(size, sizeof(int));
    for(size_t i=0;i<size;++i){
        printf("Wprowadz %Iu/%Iu liczbe do tablicy: ", i+1, size);        
        readInput("%d", &numbers[i]);
    }    
   
    replace_int(numbers, size, a, b, 0);

    for(size_t i=0;i<size;++i){
        printf("%d ", numbers[i]);
    }

    free(numbers);
 
    return 0;
}

void replace_int(int* tab, size_t tab_size, int div_a, int div_b, int new_val){
    if(tab==NULL) return;
    
    for(size_t i=0;i<tab_size;++i){
       int mod = tab[i]%div_a + tab[i]%div_b;
       if(!mod)
           tab[i] = new_val;

    }
       
}

void readInput(char* format, void* variable){
     int isInputValid = scanf(format, variable);
     if(!isInputValid)         
        do{             
            fflush(stdin);             
            isInputValid = scanf(format, variable);
         }while(!isInputValid); 
}

Ogólnie to w C nie piszę, wiele rzeczy mi się myliło z C++, więc prosiłbym o wszelkie uwagi.

Dziękuję z góry.
Pozdrawiam.

1

Generalnie ładnie, nie ma za bardzo nadmiarowego kodu, duży plus. Mam jednak uwagi:

  1. Funkcja readInput wpadnie w nieskończoną pętlę jeśli strumień wyjścia zostanie zamknięty. Taka sytuacja zajdzie jeśli przekierujesz niepełny plik na wejście lub zamkniesz strumień w czasie czytania (ctrl+d w linuksowej konsoli). Aby uniknąć tego rozpatrz sytuację scanf()<0. Poza tym nie wiem po co tyle razy fflush(), zwykle nie powinien być potrzebny w ogóle.

  2. Używasz funkcji calloc(), nie jest to błąd, ale sam uzylbym tablicy o rozmiarze zmiennej (VLA) ze standardu C99. Wiem, że w takim programie raczej nie odczujesz kosztu czasowego, fragmentacji pamięci, ani innych problemow związanych z użyciem malloc, ale doświadczenie z C nauczyło mnie nie używać tego jeśli nie ma takiej potrzeby. Stos ma te zalety że automatycznie sprząta, jest szybszy i rzadziej generuje trudne do wykrycia błędy. Jak się przepełni stos to się posypie I debugger of razu napisze dlaczego, jak przekazujesz zmienne lokalne p przez wskaźnik możesz przypadkiem uszkodzić ramkę stosu, ale to łatwiejsze niż problem z napisanymi metadanymi sterty. Niby błąd podobny i do obu spotkałem się z ostrzeżeniami, ale w przypadku stosu przynajmniej wiesz w której funkcji szukać. No ale wiadomo że nie zawsze można użyć stosu...

  3. Nazwa funkcji replace_int nie wyraża w pełni tego co ona robi. Poza tym jej ciało jest mało czytelne.

  4. Brak konsekwencji w nazewnictwie funkcji, raz w stylu C raz wielbłąd.

Oczywiście nie sprawdzałem czy działa. Warto pisać testy...

0

Działać działa. //probably //1st bug to fix - negative numbers at input are passing

  1. fflush jest dlatego, że jak podam błędny input, to scanf nie chce już nic czytać
    Sugerujesz, żeby zamiast !isInputValid dać isInputValid<1 ?

  2. No właśnie. Pomyłka z C++. VLA. Skoro można ich użyć, to użyję, nie ma co.. Wygoda wygodą.

  3. Ok, zmienię na replace_if_divisible_int (trochę długie, ale co..). A ciało zrobiłem najbardziej czytelne jak tylko potrafiłem. Nie wiem co można tam zmienić.
    int mod = ... chyba rozumiesz

readInput - funckja
replace - funkcja _int - typ parametru
gdyby readInput przyjmował tylko int, to nazywałby się readInput_int

0

1. Ten fragment:

     if(!isInputValid)         
        do{             
            fflush(stdin);             
            isInputValid = scanf(format, variable);
         }while(!isInputValid); 

można uprościć, skoro pętla ma się wykonać tylko jeśli !isInputValid:

        while(!isInputValid)
        {
            fflush(stdin);             
            isInputValid = scanf(format, variable);
         }

Owszem, można scanf() umieścić w samym warunku pętli i uniknąć tworzenia zmiennej, ale zmienna przynajmniej fajnie określa co sprawdzamy.

2. Jak jeszcze w przypadku isInputValid zaprzeczenie w warunku nawet pasuje (ponieważ nazwa sugeruje/udaje wartość boolowską), to już stosowanie zaprzeczenia w tym fragmencie:

       int mod = tab[i]%div_a + tab[i]%div_b;
       if(!mod)

wymaga mimo wszystko chwilki by dojść do tego, co tutaj sprawdzasz. Moim zdaniem można pokusić się tutaj o zwyczajne porównanie:

       int mod = tab[i]%div_a + tab[i]%div_b;
       if(mod == 0)

Poza tym, całość wygląda OK (+ uwagi od kolegi wyżej).

0

Ok, dzięki. W takim razie kod wygląda teraz tak:

#include <stdio.h>
#include <stdlib.h>


void readInput_size_t(size_t*);
void readInput_int(int*);
void replaceIfDivisible_int(int*, size_t, int, int, int);
void insertToTable_int(int*, size_t);

int main(int argc, char** argv){
    size_t size=0;
    size_t a=0;
    size_t b=0;

    printf("Wprowadz ilosc liczb: ");
    readInput_size_t(&size);

    printf("Wprowadz pierwsza liczbe do sprawdzania podzielnosci: ");
    readInput_size_t(&a);

    printf("Wprowadz druga liczbe do sprawdzania podzielnosci: ");
    readInput_size_t(&b);

    int numbers[size];
    insertToTable_int(numbers, sizeof(numbers)/sizeof(int));

    replaceIfDivisible_int(numbers, size, a, b, 0);

    for(size_t i=0;i<size;++i){
        printf("%d ", numbers[i]);
    }

    free(numbers);

    return 0;
}

void replaceIfDivisible_int(int* tab, size_t tab_size, int div_a, int div_b, int new_val){
    if(tab==NULL) return;

    for(size_t i=0;i<tab_size;++i){
       int mod = tab[i]%div_a + tab[i]%div_b;
       if(mod==0)
           tab[i] = new_val;

    }

}

void readInput_int(int* variable){
    int isInputValid = scanf("%d", variable);
    while(isInputValid<=0){
        fflush(stdin);
        isInputValid = scanf("%d", variable);
    }
}
void readInput_size_t(size_t* variable){
    int input;
    int isInputValid = scanf("%d", &input);
    while(isInputValid<=0 || input<0){
        fflush(stdin);
        isInputValid = scanf("%d", &input);
    }
    *variable = (size_t)input;
}
void insertToTable_int(int* tab, size_t tab_size){
    for(size_t i=0;i<tab_size;++i){
        printf("Podaj %u/%u liczbe do tablicy: ", i+1, tab_size);
        readInput_int(&tab[i]);
    }
}

I w sumie wszystko działa, ale dalej nie jestem pewien czystości kodu. Doradzicie coś?.. Heh.
// Jeśli chodzi o readInput, to myślę, żeby zrobić enum INT/SIZE_T i w zależności od tego jakoś tą funkcję zmienić, ale może to wyjść pokracznie

0

Z punktu widzenia wydajności konstrukcja:

int mod = tab[i]%div_a + tab[i]%div_b;
if(!mod)
   tab[i] = new_val;

(choć wydaje się elegancka) nie jest optymalna.
Jeśli tab[i]%div_a nie jest spełniony, to i tak zostanie policzone tab[i]%div_b

0

To jak inaczej można by to zapisać?

0

Możliwości jest wiele

	if(!(tab[i]%div_a))
		if(!(tab[i]%div_b))
	        	   tab[i] = new_val;

	if(!(tab[i]%div_a) && !(tab[i]%div_b))
       	   tab[i] = new_val;

w powyższej wersji kompilator to zoptymalizuje i drugiego warunku nie policzy.
Ty użyłeś "+". To spowoduje, że kompilator policzy oba składniki i je doda. I dopiero wynik sprawdzi.
Musisz spowodować, że do pierwszego sprawdzenia doszło już po wyliczeniu pierwszego składnika.

0

Jak już optymalizujemy - to optymalizujmy dalej ;-).

Czemu wynik działania np. tej funkcji

void readInput_size_t(size_t* variable);

odbierasz przez wskaźnik?

Czemu nie zrobisz tak? (może są jakieś powody - uzasadnij)

size_t readInput_size_t(){
...
	return input;
}

A jeśli już masz przez wskaźnik, to po co tworzysz dodatkową zmienną input, którą na koniec przypisujesz do variable? W tym rozwiązaniu jedno tworzenie zmiennej i jedno przypisanie (dwie operacja) są nadmiarowe.

Dalej - cała ta konstrukcja while

while(isInputValid<=0 || input<0){
        fflush(stdin);
        isInputValid = scanf("%d", &input);
 }

jest taka sobie :-)

Ja już dawno nie programowałem dla konsoli, musiałem zajrzeć do dokumentacji :-), ale generalnie - w tym while sprawdzasz dwa warunki. Pytanie - po co? Czy nie da się jednym sprawdzeniem tego "załatwić". Kiedy input może być mniejsze od 0?
I w dwóch wierszach wykonujesz scanf. Czy nie możesz tego przerobić na do{}while, żeby scanf tylko raz występowało w tym kodzie?

Poza tym - w tej wersja jak masz teraz - to się nie skompiluje (masz int numbers[size];)
To nie przejdzie, w takim zapisie size musi być stałą.

2

optymalizacja optymalizacją ale
po

if(!(tab[i]%div_a))
        if(!(tab[i]%div_b))
                   tab[i] = new_val;

przed

int mod = tab[i]%div_a + tab[i]%div_b;
if(!mod)
   tab[i] = new_val;
  1. ile zyskuje sie na tej jednej linii kodu? Czy na pewno ma to takie znaczenie? Czy ten fragment kodu jest bottle neck? Cytujac Donalda Knuth'a

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

http://wiki.c2.com/?PrematureOptimization

  1. z punktu widzenia czytelnosci, kod zaczyna byc nieczytelny

  2. debugowanie tego to jest tragedia

0

Nie wiem teraz za bardzo, do którego fragmentu dyskusji się odnosisz.

  1. Którą "jedną" linię kodu masz na myśli?
  2. Który fragment masz na myśli?
  3. No jeśli dwa wyrażenia w jednym if-ie połączone && - to tragedia dla debugowania, to sorry :-).

Generalnie - jeśli chodzi o optymalizację, to grosz do grosza i pół kosza :-). I nie chodzi o to czy w danym momencie to ma znaczenie, czy nie, ale o nawyki.
Ten program nie robi niczego konkretnego, więc w zasadzie wszelkie dyskusje o jego optymalizacji są bez sensu. Ale autor prosił o ocenę.

0

Do Darkbit. Aż z ciekawości sprawdziłem :-)
Oba kompilatory (VC i Borland), na których na co dzień pracuję tego nie łykają. I wg mnie nie powinny. Ale wiesz - ja to starej daty programista jestem :-). Może teraz jest inaczej :-).

screenshot-20190219094531.png

2

@Stefan_3N bo użyłeś rozszerzenia cpp, a C++ nie ma w standardzie VLA, tymczasem C ma VLA, a jego kod jest właśnie w C.
Mało tego, z tego co widzę, to użyłeś C++ CLI

1

@Stefan_3N: edytowalem post ale jeszcze raz napisze tutaj

to

int mod = tab[i]%div_a + tab[i]%div_b;
if(!mod)
   tab[i] = new_val;

jest duzo bardziej czytelnie od tego

if(!(tab[i]%div_a) && !(tab[i]%div_b))
           tab[i] = new_val;

i na pewno jeszcze bardziej czytelne od tego

if(!(tab[i]%div_a))
        if(!(tab[i]%div_b))
                   tab[i] = new_val;

juz pomijam brakow {} bo tutaj sa zdania podzielone, ja nawet dla jednolinijkowcow zawsze daje {}

No jeśli dwa wyrażenia w jednym if-ie połączone && - to tragedia dla debugowania, to sorry :-).

tak, dwa wyrazenia w jedym ifie to tragedia. Do debuggowania to juz w ogole. Bo musisz recznie wpisywac wyrazenie do quickwatcha lub gdzie indziej zamiast po prostu wykonywac kod

Duzo lepiej bedzie miec dwie zmienne przed tym i wyrazenia w zmiennych. Ale wtedy ta "optymalizacja" nie bedzie wykonywana. Ja bym to napisal tak

int div_a_on_tab = tab[i]%div_a;
int div_b_on_tab = tab[i]%div_b;

int mod = div_a_on_tab + div_b_on_tab 
if(!mod)
{
   tab[i] = new_val;
}

drobne optymalizacje zostawil bym dla kompilatora

Oba kompilatory (VC i Borland), na których na co dzień pracuję tego nie łykają. I wg mnie nie powinny. Ale wiesz - ja to starej daty programista jestem :-). Może teraz jest inaczej :-).

to jest kod z C. w C VLA jest mozliwe, Ty natomiast tworzysz plik cpp czyli c++ a VLA dla c++ jest dostepne bodajze od C++17. Dodatkowo uzywasz C++ CLI co jest spora roznica od C++ a jeszcze wieksza od C

2
Stefan_3N napisał(a):

Z punktu widzenia wydajności konstrukcja:

int mod = tab[i]%div_a + tab[i]%div_b;
if(!mod)
   tab[i] = new_val;

(choć wydaje się elegancka) nie jest optymalna.
Jeśli tab[i]%div_a nie jest spełniony, to i tak zostanie policzone tab[i]%div_b

W C i C++ kompilator obowiązuje zasada "AS IF" ("Tak Jak"). Kompilator może dowolnie przekształcić kod, dopóki wynik działania będzie taki sam (a kompilator potrafi różne cuda: zamieniać pętlę na wzór, łączyć pętle, dzielić pętle, pomijać martwy kod, albo taki co jest bezsensu, bo ma UB).
Ergo twoje rozważania o optymalizacji są zupełnie bezsensu, bo dla kompilatora różnicy nie ma, kod wynikowy będzie taki sam.
Jeśli kompilator generuje taki sam kod, to lepiej pisać tak by było czytelniej dla człowieka.

1

Tu program:
screenshot-20190219120632.png

Tu wyniki (czasy w milisekundach):
screenshot-20190219120128.png

Jak zaczynałem programować, to liczył się każdy bajt. Każdą instrukcję oglądało się z trzech stron, gdzie by tu uszczknąć milisekundę.
I programy śmigały.
Teraz gigabjaty pamięci, super procesory i programy mulą :-).

Spójrz na zrzut i na wyniki. Nie wiem, może zrobiłem gdzieś błąd.
Ale wygląda na to, że jest o co powalczyć ;-)
Pewno znowu znajdziecie wytłumaczenie :-).
Ale z ciekawości sprawdźcie w swoich kompilatorach (nie wiem, czego używacie).
Jestem ciekaw wyników.

1

Dla takich opcji:
screenshot-20190219122249.png

Wyniki są takie:
screenshot-20190219122148.png

Może są jeszcze jakieś inne opcje (więcej czasu jednak spędzam w Borlandzie, tu robię to, czego tam nie mogę).

2

Ok. Myślałem, że tylko przekształciłeś kod, ale ty zmieniłeś logikę kodu i dlatego jest różnica.
Przyznaję, że się nie wczytałem w kod.
U niego jest dodawanie: tab[i] % div_a + tab[i] % div_b; i w takiej formie kompilator musi wykonać oba dzielenia, zwłaszcza że wynik dzielenia modulo nie musi być nieujemny.
Ty zamieniłeś to na logiczną koniunkcję, więc w wielu wypadkach wystarczy sprawdzić, że tab[i] % div_a != 0 i drugiego dzielenia nie trzeba robić, a dzielenie jest dużo dużo wolniejsze od innych operacji jak np mnożenie.
Z tego powodu tej różnicy w logice programu kodu, kompilator nie mógł zrobić optymalizacji do tego samego kodu (kody nie są równoważnie logicznie).

1

Porównałem sobie zbliżony przykład w Compiler Explorerze i ani gcc ani clang nie optymalizują tego przypadku. Dla typów całkowitych to nawet całkiem zrozumiałe (inna jest semantyka tych wyrażeń, np. -5 % 3 + 5 % 3 == 0), ale optymalizacji nie ma nawet dla unsigned.

Przy czym zgadzam się ze stwierdzeniem, że czytelność jest tu dużo ważniejsza, o ile to nie jest bottleneck w programie, z benchmarkami na dowód.

0

No właśnie o to dodawanie mi chodziło. Na końcu zwróciłem uwagę, że to jest dodawanie.

0

Mam projekt jeszcze nie zamknięty, więc sprawdziłem na ile wyciągnięcie int mod przed pętlę zmieni wynik.
(Opcje optymalizacji - jak ma zrzucie wyżej).

screenshot-20190219130858.png

Czyli wpływa dość mocno.

0

zgadzam sie z @Stefan_3N ze kod jest szybszy, ale nadal stoje przy swoim, ze takich optymalizacji nie warto robic bo zaciemniaja kod chyba ze jest to bottle neck aplikacji (wtedy komentarz dlaczego tak napisane, a najlepiej zamienic to na funkcje z komentarzem do funkcji)

dla miliarda (!) obliczen roznica jest widoczna bo roznica jest miedzy 3 sekundy a 6 sekund. Roznica jest dwukrotnie wieksza, poniewaz drugie modulo sie nie wykonuje. Dla takiego przypadku oczywiscie pominiecie jednego dzielenia ma sens

Teraz pytanie od strony biznesowej. Czy ma byc milion wejsc? Bylem w kilku(nastu) projektach, oprocz jednej sytuacji (liczenie animacji dla twarzy) nigdy sie nie spotkalem z takimi wymaganiami. Pracowalem w kilku branzach od gry, embedded, aplikacje dla przeplywu gazow na RESTach konczac (w tym REST ktory jest uzywany przez dziesiatki tysiecy ludzi)

Normalnie, bedzie to przelecenie raz (albo kilka razy) przez 1000 elementowa tablice zeby zrobic modulo. W takim przypadku, czy kod wykonuje sie 0,003 czy 0,006 na prawde nie ma znaczenia. Natomist czytelnosc kodu i jego utrzymanie spada. Juz duzo bardziej zastanowilbym sie, czy nie da sie jakies innej kolekcji dla takiego zadania wykonac, ktora przyspiesza kod ale zostawia czytelnosc na wysokim poziomie. Tutaj zapewne nie, ale chodzi o sama idee

Warto robic optymalizacje tam gdzie bedzie wiadomo, ze moze byc problem z wydajnoscia (bottle neck), a nie zawsze.

1

Przede wszystkim warto mieć świadomość jak to działa.
I potem - świadomie z tego korzystać.
A żeby mieć świadomość - trzeba o tym mówić. I dlatego zwróciłem na ten aspekt kodu uwagę.
Zawsze pod koniec prac sprawdzam, gdzie program spędza najwięcej czasu i rzecz jasna czepiam się tych miejsc w pierwszej kolejności. Ale - jak już wiemy gdzie jest wąskie gardło, to nadal potrzebna jest wiedza, jak to gardło udrożnić. I chyba to jest najważniejszy wniosek z tej dyskusji.
Nie "czy warto w tej konkretnej sytuacji", ale - "jak - jeśli zajdzie taka potrzeba".

1
PrezesiQ napisał(a):

Dostałem zadanie:

Wprowadzić ciąg liczb, którego weilkości n. Wprowadzić dwie dodatkowe liczby a i b. We wprowadzonym ciągu wszystkie liczby, które są podzielone przez a i b , zamienić na zero. Wyprowadzić nowy ciąg.

Żeby dobrze zrobić to zadanie trzeba nieco ruszyć głową (ledwo ledwo, bo nie jest to genialne odkrycie).
Zamiast sprawdzać podzielność przez a i b wystarczy sprawdzić podzielność przez lcm(a, b), które policzy się raz.
Wykona się wtedy jedno dzielenie, będzie jeden warunek do sprawdzenia, więc będzie szybciej.

0

Fasadin - prosiłeś pod clangiem - tylko tak: https://rextester.com/AVH19535
Dobry jest :-)
(nie wiem, czy z odczytem czasu czegoś nie pomieszałem).

0

Dobrze, że do tego wróciłeś, bo wbrew pozorom temat nie jest zamknięty i wymaga jeszcze przemyślenia.
Na razie jednak wracam do mojej starej zasady (zero automatycznych optymalizacji, jak chcesz mieć zoptymalizowane - to zoptymalizuj sam :-).
Nie ma darmowych obiadków :-).

Spójrzcie na to:
https://rextester.com/edit/FJT75634
Gdzie jest błąd? Czemu nie wykonuje tej konstrukcji?
(chyba wiem, ale nie będę Wam sugerował)

0

Bo jest tam do...while 0

0

Zrobiliśmy pewne niedopatrzenie na początku testów (ja zrobiłem, ale nie zwróciliście też na to uwagi)
Obie zmienne
int div_a = 100;
int div_b = 100;
są takie same. Kompilator chce być chytry, ale jest chyba za chytry. Oblicza pierwsze wyrażenie i drugiego już nie analizuje, tylko robi break. A powinien, bo w drugim warunku coś jednak dodatkowego (poza break) się dzieje.
Wystarczy zmienić jedną ze zmiennych - i zaczyna się wykonywać. Choć wyniki nie są prawidłowe.
Albo ja czegoś nie widzę, albo kompilator przesadza z optymalizacjami.
(zazwyczaj mówię, że kompilator się nie myli, tylko programista, ale - kto to wie :-))

0

Był błąd w logice.
Teraz liczy dobrze:
https://rextester.com/LOG13484
Nie tłumaczy to jednak tamtego zachowania.

1 użytkowników online, w tym zalogowanych: 0, gości: 1