C++ - funkcja zwraca głupoty, jeśli w danym miejscu nie będzie instrukcji std::cout :)


(kijek) #1

Witam.

Jestem w trakcie tworzenia projektu na studia z budowy i analizy algorytmów. Uprzedzam więc, że algorytm mam gotowy, więc nie chodzi mi o pomoc przy wykonywaniu projektu. Mam za to dość ciekawy problem z kodem realizującym ten algorytm.

Otóż napisałem funkcję, która w zadanej tablicy jednowymiarowej odnajduje element o najwyższej wartości, a następnie zlicza ilość jego wystąpień. Funkcja prezentuje się następująco:

int maxCounter(int *table, unsigned int tableSize)
{
	int max, counter = 0;

	for(int n=0; n<tableSize; n++)
	{
		if(table[n]>max)
			max = table[n];

	}

	for(int n=0; n<tableSize; n++)
	{
		if(table[n]==max)
			counter++;
	}

	return counter;
}

Wywołuję więc funkcję i zadaję jej jakąś tablicę. W wyniku otrzymuję zero :slight_smile: Postanowiłem przeanalizować działanie algorytmu i w drugiej pętli wewnątrz instrukcji warunkowej, dodałem

std::cout << table[n] << "\n";

coby sprawdzić, czy instrukcja warunkowa w ogóle wykonuje się. Po skompilowaniu programu nagle okazało się, że wszystko działa. Tak więc moje pytanie - co jest przyczyną takiego egzotycznego działania programu? Czyżby kompilator coś namieszał (g++ 4.9.2), czy może zwyczajnie ja coś spierdzieliłem? :slight_smile: A jeśli tak, to co?


(ktoś tam) #2

Ostatnio miałem podobny problem. Kod oczywiście był zupełnie inny, ale program także wariował bez cout. Okazało się, że mam w tym samym pliku inną implementację tej funkcji (właściwie to była metoda, ale mniejsza o to), która była odpowiedzialna za owe wybryki. Ani kompilator ani debugger z jakiegoś powodu się tym nie przejmowały. Jeżeli było cout, to wybierał wersję z cout, jeżeli nie to tę bez. Mój kompilator to także g++ 4.9.x, więc sprawdź, czy nie masz czegoś podobnego. Zwróć także uwagę na edytor. Na początku nie mogłem znaleźć tej błędnej wersji, bo edytor (wbudowany w Eclipse Mars CDT) się bugował i nie pokazywał całego kodu. 

Swoją drogą także ciągle szukam błędów za pomocą cout :slight_smile:


(kijek) #3

Tutaj akurat problem okazał się być bardzo głupi. Otóż inicjując zmienne, miałem jakieś głupie przeświadczenie, iż w ten sposób obie zostaną wyzerowane. Problemem była więc zmienna max, która przyjmowała randomowe wartości :slight_smile:


(enedil) #4

Profesjonalna analiza…

Problem leży w Twoim kodzie. Jaką wartość ma zmienna max na samym początku, tuż po deklaracji?


(kijek) #5

Istotnie, głupie niedopatrzenie. Zresztą wyżej już wyjaśniłem :wink: Nie mniej dzięki za pomoc.


(enedil) #6

Wartości nie są całkowicie losowe.

Zauważ, że każde uruchomienie programu powinno dać tę samą liczbę w pierwszym wykonaniu tej funkcji.

 

Niemniej, zerowanie nie jest rozwiązaniem. W końcu wszystkie liczby w tablicy mogą być ujemne. Co wtedy?


(kijek) #7

To jest już dość duże niedopatrzenie, gdyż w takim przypadku powyższa implementacja jest nieskuteczna. W takim wypadku widzę tylko jedno sensowne rozwiązanie:

int max = std::numeric_limits<int>::min();

 


(enedil) #8

Ajj, zwyczajnie

int max = table[0];

I nie przejmujesz się resztą.


(mr-owl) #9

Witam,

A nie lepiej zrobić funkcję która ma mniejszą złożoność obliczeniową i przejść tablicę tylko raz? zaczynasz od table[0] i sprawdzasz czy twój max jest osiągnięty (dodajemy +1) lub znaleźliśmy wartość większą (ustawiamy max ma table[index] i resetujemy counter)?

Pozdrawiam,

mr-owl


(enedil) #10

O(2n) = O(n)

zresztą, Twoje rozwiąnie wymaga dodatkowej tablicy, co zwiększa złożoność miejscową z O(1) do O(n). 


(ktoś tam) #11

Cóż, na kod nie patrzałem. Przeczytałem opis i napisałem, że miałem coś o podobnych skutkach, więc napisałem, co u mnie było powodem.


(mr-owl) #12

“tóż napisałem funkcję, która w zadanej tablicy jednowymiarowej odnajduje element o najwyższej wartości, a następnie zlicza ilość jego wystąpień.” Do czego ma być tutaj ta druga tablica?

Albo ja tutaj czegoś nie rozumiem albo ty?

Pozdrawiam,

mr-owl


(kijek) #13

Słuszna uwaga, mr-owl. Funkcję można ograniczyć do jednej pętli, odpowiednio operując counterem. Dzięki :slight_smile:


(enedil) #14

Istotnie, teraz widzę dlaczego algorytm działa.