Optymalizacja programu C++

Witam! Mam na zadanie zmodyfikować kod programu, aby był szybciej wykonywany, ale niestety nie umiem tego zrobić. Byłbym wdzięczny, jeśli ktoś wskazałby co należy zmienić :)

#include <iostream>

using namespace std;

int main() {

	int i, j, DlugoscCiagu, LiczbaZapytan, Suma = 0;
	bool Znaleziono;
	cin >> DlugoscCiagu;
	int* Liczby1 = new int[DlugoscCiagu];

	for (i = 0; i < DlugoscCiagu; i++)
		cin >> Liczby1[i];

	cin >> LiczbaZapytan;
	int* Liczby2 = new int[LiczbaZapytan];

	for (i = 0; i < LiczbaZapytan; i++)
		cin >> Liczby2[i];

	for (i = 0; i < LiczbaZapytan; i++)
	{
		Znaleziono = false;
		for (j = 0; j < DlugoscCiagu; j++)
		{
			if (Liczby2[i] == Liczby1[j])
			{
				Suma += Liczby2[i];
				Znaleziono = true;
			}
		}
		if (Znaleziono == false)
			Suma -= Liczby2[i];
	}
	
	cout << Suma;
	return 0;
}

Jeżeli masz 2 takie pętle:

for (i = 0; i < LiczbaZapytan; i++)
	cin >> Liczby2[i];

for (i = 0; i < LiczbaZapytan; i++) { ... }

To możesz z nich zrobić 1.

atmal napisał(a):

Jeżeli masz 2 takie pętle:

for (i = 0; i < LiczbaZapytan; i++)
	cin >> Liczby2[i];

for (i = 0; i < LiczbaZapytan; i++) { ... }

To możesz z nich zrobić 1

No niby tak, ale to nieco zmienia logikę wpisywania danych. Poza tym jak czytamy ze std wejścia/wyjścia to wpływ na wydajność i tak bedzie taki sobie.

Ja mam uwagę, po co pisać if(x==true), nie lepiej if(x)?

@atmal Dzięki. Co do warunku if'a zmienienie tego na if (!Znaleziono) chyba niewiele da...

@C64 Zmieniłem na printf i scanf

Można by jeszcze jakoś te pętle przyspieszyć (bo chyba one najbardziej zamulają)?

Przecież tutaj problem stanowi idiotyczny naiwny algorytm ~O(n^2) a nie jakies problemy z dwiema pętlami zamiast jednej czy odwracanie warunków czy printf/scanf. Na oko ten algorytm sprawdza ile razy dana liczba wystąpiła w ciagu wejściowym i zlicza to na zasadzie liczba*ile_razy. No to przecież takie cos można zrobić w czasie O(n) a nie O(nk) ! Wczytując dane zrób sobie unordered_map gdzie kluczem jest dana liczba a wartością jest ile razy wystąpiła w ciagu wejściowym. Zbudowanie takiej mapy to O(n) bo po prostu budujemy czytając dane wejściowe.
Następnie odpowiedź na zadane pytanie to po prostu odczytanie z mapy czy dana liczba jest w mapie, a jeśli jest to ile razy wystąpiła, więc potrzeba nam już tylko O(k) odczytów z mapy które mają O(1)

@Shalom Dzięki wielkie, spróbuję :)

@Shalom nie wiem na jakiej podstawie twierdzisz co ten program ma robić, bo robi zupełnie coś innego i bezsensownego.
Nawet zakładając że masz rację to złożoność na pewno nie jest tu problemem.

Prawdopodobnie dane wejściowe są niezgodne z oczekiwaniami i przykładowo LiczbaZapytan ma nieustaloną wartość, więc program wisi bo akkurat LiczbaZapytan = 2012312355

@MarekR22 Jak dałeś taką liczbę to musiałbyś podać 2012312355 liczb :)

Bogaty Mleczarz napisał(a):

@MarekR22 Jak dałeś taką liczbę to musiałbyś podać 2012312355 liczb :)

Ja dobrze widzę, a patrze na telefonie to ogólnie nic nie widać ;], że dla dwóch takich samych różnowartościowych tablic na wyjściu jest 0?

Niech "Bogaty Mleczarz" dokładniej opisze w czym problem. Treść zadania, dane wejściowe, wyjściowe i na jakiej podstawie twierdzi, że problemem jest szybkość działania kodu.
Dla tak prostych danych wejściowych użycie unordered_map często jest dużą przesadą.

Jeśli to jest zadania ze SPOJ to najczęstrzą przyczyną czemu zdanie nie jest zaliczane z powodu przekroczenia czasu:

• nieprawidłowy odczyt danych wejściowych
• jakiś warunek brzegowy, który wiesza program (np z powodu UB).
• system("pause")
• zadanie, gdzie głównym wąskim gardłem są operacje IO (niestety wiele jest takich zadań, szczególnie jak problem jest tak prosty jak ten)
• za duża złożoność obliczeniowa algorytmu