szybkość operacji.

Cześć, mam zadanie. Dość proste jednak wymagania czasowe są dość duże bo wymaga wykonania poniżej 1s

Napisz program, który:
• wczyta ze standardowego wejścia opisy budynków,
• wyznaczy minimalną liczbę plakatów potrzebnych do całkowitego pokrycia ich północnych
ścian,
• wypisze wynik na standardowe wyjście.

Plakaty się dotykają, mogą powtarzać.
I napisałem coś takiego:

Najpierw skanuje ilość budynków a potem ich wymiary x i h

#include <iostream>
#include <stdio.h>
#define MAXINT 2147483647
using namespace std;

int main()
{
	int size;
	int *psize = &size;
	scanf("%d",psize);

	int tablica[*psize+1];
	tablica[*psize] = -1;
	int *pointer = &tablica[0];
	int *pointerNaNajmniesza;
	int najmniejsza = MAXINT;
	pointerNaNajmniesza = &najmniejsza;
	int toLOST;

	for(int i = 0; i <*psize; i++)
	{
		scanf("%d %d",&toLOST,pointer);
			if(*pointerNaNajmniesza > *pointer)
				*pointerNaNajmniesza = *pointer;
			if(size-i==1)
				break;
		pointer++;
	}

	for(int i = 0; i <*psize; i++)
	{
		*pointer = *pointer-*pointerNaNajmniesza;
		if(*pointer == 0)
			*pointer = -1;
		if(size-i==1)
			break;
		pointer--;
	}

	toLOST = 1; // pierwszy plakat najniższy poziomy
	// teraz algorytm po powstałych grupach
	int stoper = 0;
	int *pointerStoper = &stoper;
	*pointerNaNajmniesza = MAXINT;

	for(int i = 0; i < *psize; i++)
	{
		while(true)
		{
			*pointerNaNajmniesza = MAXINT;
			*pointerStoper = 0;
			if(*pointer > 0)
			{
				while(true)
				{
					if(*pointer == -1)
						break;
					if(*pointerNaNajmniesza > *pointer)
						*pointerNaNajmniesza = *pointer;

					*pointerStoper+=1;
					pointer++;
				}
				for(int i = 0; i < *pointerStoper; i++)
				{
					pointer--;
					*pointer = *pointer-*pointerNaNajmniesza;
					if(*pointer == 0){
						*pointer = -1;
					}
				}
				toLOST++;
			}
			else
			{
				pointer++;
				break;
			}
		}
	}
	printf("%d",toLOST);
	return 0;
}

chodzi o to że w momencie wczytywania wykrywam najmniejszy.
Przesuwam się po tablicy pojedynczo wracając na początek i usuwam o najmniejszy i tam gdzie 0 ustawiam jako wielkość -1 - taki znacznik.
Potem już pętla for a w niej inne, i chodzę po tablicy do momentu znalezienia -1 co jest wyznacznikiem powstałej grupy. Stoper mi mówi ile przeszedłem do -1 czyli jak ta grupa jest duża i od razu skanuje najmniejszy. Wracając obniżam poziom o najmniejszy i inkrementuje ilość plakatów.
I przesuwam się dalej po wskaźnikach. Jeżeli wielkość jest większa od 0 to dalej ten sam algorytm.

I tutaj moje pytanie, czy sam ten proces jest czasochłonny sam z siebie czy może to pierwszy powrót na początek wraz z kasowaniem dużo zajmuje czasu?
przykładowe "in'y" mają po kilkaset tysięcy przykładowych budynków.
Dla nich proces trwa kilkanaście s, a wymóg to 1s max

Z góry dziękuję za jakąś radę jak to uefektywnić

1. Dla czystego sumienia bym sprawdził czas odczytu

2. O stylu tego kodu bym dyskutował (ewentualnie wypiłem jeszcze za mało kawy).

Moje oczy wolą notację tablicową niż wskaźnikową.
Masz straszny nadmiar wskaźników, np ZUPEŁNIE niepotrzebny i zaciemniający psize

AnyKtokolwiek napisał(a):

1. Dla czystego sumienia bym sprawdził czas odczytu

2. O stylu tego kodu bym dyskutował (ewentualnie wypiłem jeszcze za mało kawy).

Moje oczy wolą notację tablicową niż wskaźnikową.
Masz straszny nadmiar wskaźników, np ZUPEŁNIE niepotrzebny i zaciemniający psize

Może i faktycznie, w sumie tylko jeden wskaźnik tutaj na element tablicy jest potrzebny. Reszta zbędna. Narobiłem ich gdy kod okazał się za wolny.

Odczyt ? chodzi Ci ile czasu trwa zczytanie wszystkich rekordów z tym spacerem największy/najmniejszy ?

Maciej123321 napisał(a):

Cześć, mam zadanie. Dość proste jednak wymagania czasowe są dość duże bo wymaga wykonania poniżej 1s

Zacznij od użycia notacji tablicowej, na prawie wszystkich współczesnych komputerach będzie działać szybciej.
Zacznij używać operatorów +=, -=, *= itp
Podaj pełną treść zadania, bo nie koniecznie wybrałeś sensowny algorytm.

_13th_Dragon napisał(a):

Zacznij używać operatorów +=, -=, *= itp

Używanie lub nie tych operatorów nie ma znaczenia dla szybkości kodu.

_13th_Dragon napisał(a):

Podaj pełną treść zadania, bo nie koniecznie wybrałeś sensowny algorytm.

+1

Dodam do tego, lepiej nie pisać wszystkiego w main podziel kod na mniejsze części, żeby łatwiej było czytać i rozumieć kod.
Kod pisany w małych funkcjach, łatwiej się czyta i poprawia. Im szybciej się tego nauczysz tym lepiej.
Nie ma to wpływu na szybkość wykonywania kodu, ale na szybkość jego: czytania, analizowania i poprawiania; co jest równie ważne (a w pracy zespołowej nawet ważniejsze).

_13th_Dragon napisał(a):

Maciej123321 napisał(a):

Cześć, mam zadanie. Dość proste jednak wymagania czasowe są dość duże bo wymaga wykonania poniżej 1s

Zacznij od użycia notacji tablicowej, na prawie wszystkich współczesnych komputerach będzie działać szybciej.
Zacznij używać operatorów +=, -=, *= itp
Podaj pełną treść zadania, bo nie koniecznie wybrałeś sensowny algorytm.

Dobra zaraz przerobię na notację tablicową. Chociaż zawsze wydawało że wskaźniki są szybsze.

Treść:

Całość na stronie 63:
https://oi.edu.pl/static/attachment/20110704/oi15-b5.pdf

Zadanie
Napisz program, który:
• wczyta ze standardowego wejścia opisy budynków,
• wyznaczy minimalną liczbę plakatów potrzebnych do całkowitego pokrycia ich północnych
ścian,
• wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (1 6 n 6 250 000 ), oznaczającą
liczbę budynków stojących w rzędzie. Kolejne n wierszy zawiera po dwie liczby całkowite d i
i w i (1 6 d i , w i 6 1 000 000 000 ), oddzielone pojedynczym odstępem i oznaczające długość
i wysokość i-tego budynku w rzędzie.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą — minimalną liczbę
prostokątnych plakatów, którymi można całkowicie pokryć północne ściany budynków.

dokonałem modyfikacji na notacje tablicową.
Sprawdziłem też czas jak mnie proszono. No to samo pobieranie informacji (pierwsza pętla) trwa po nad 0.6s :/

następny algorytm wyszukiwania poda 100s
Wynik wypluwa poprawnie, ale 100 krotnie przekraczam czas.
Ale czy po 0.6s czasu trwania pobierania jest wgl szansa na to że dokona reszty operacji w 0.4s ?
W załączniku podaje przykładową zawartość danych wejściwych.
Dla tej paczki wynik to 155393 - poprawny

poniżej kod w notacji tablicowej (czytelniejszy chyba dla oka):

#include <iostream>
#include <stdio.h>
#define MAXINT 2147483647
using namespace std;
#include <cstdio>
#include <ctime>

int main()
{
    int size;
    scanf("%d",&size); // pierwszy wiersz z informacją ile jest budynków

    int tablica[size+1];
    tablica[size] = -1;
    int najmniejsza = MAXINT;
    int toLOST;

    clock_t start = clock();
    for(int i = 0; i <size; i++) // pierwsza pętla, pobieram informacje i od razu szukam najmnijeszej wartości
    {
        scanf("%d %d",&toLOST,&tablica[i]);
            if(najmniejsza > tablica[i])
            	najmniejsza = tablica[i];
    }
    clock_t stop = clock();
    double czas = (double)(stop-start)/CLOCKS_PER_SEC ;
    printf("%f\n",czas);

    for(int i = 0; i <size; i++) // pomniejszam o najmniejszą wartość 
    {
        tablica[i] -= najmniejsza;
        if(tablica[i] == 0)
        	tablica[i] = -1;
    }

    toLOST = 1; // pierwszy plakat najniższy poziomy
    // teraz algorytm po powstałych grupach
    int stoper = 0; // ta zmienna będzie mi mówiła jak duża grupa jest

    start = clock();

    for(int i = 0; i <size; i++) // petla po tablicy
    {
        while(true)
        {
            najmniejsza = MAXINT;
            stoper = 0;
            if(tablica[i] > 0)
            {
                while(true) // petla która szuka grupy i w niej najmniejszego
                {
                    if(tablica[i] == -1)
                        break;
                    if(najmniejsza > tablica[i])
                        najmniejsza = tablica[i];

                    stoper+=1; 
                    i++;
                }

                while(true) // jezeli jest grupa to pomniejsza w niej o najmniejsza wartosc.
                {
                	if(stoper == 0)
                		break;
                	i--;
                	tablica[i] -= najmniejsza;
					if(tablica[i] == 0)
						tablica[i] = -1;
					stoper -= 1;

                }
                toLOST++; // incrementuje ilosc plakatow
            }
            else // jezeli nie ma juz budynku w grupie wychodze z szukacza i ide dalej po tablicy (do fora)
            {
                break;
            }
        }
    }

    stop = clock();
    czas = (double)(stop-start)/CLOCKS_PER_SEC ;
    printf("%f\n",czas);
    printf("%d",toLOST);
    return 0;
}

IMO twój algorytm ma za dużą złożoność.
Mam pomysł na coś co ma złożoność O(n long n), ale go jeszcze nie dopracowałem, więc nie jestem pewien, czy tak się da.
Wygląda na to (nie mam pewności), że twój algorytm ma złożoność O(n^3) (czyli czas wykonania twojego kodu rośnie z proporcjonalnie do trzeciej potęgi rozmiaru danych wejściowych).

Po sprawdzeniu czasów też zacząłem myśleć nad tym i mam pomysł na kolejny algorytm.
Ale na razie pomysł.
Bo faktycznie nic tu nie wycisnę, czy tablicówka czy pointery. To i tak będzie za długo

Robisz tak:

1. sortujesz tablicę indeksów budynków, według wielkości budynków (jeśli budynki są równe to sortujesz po indeksie) O(n log n)
2. Iterujesz po posortowanych indeksach O(n)
   2.1. Jeśli wysokość się zmienia, naliczasz plakat O(1)
   2.2. Jeśli wysokość się nie zmienia, sprawdzasz czy pomiędzy tymi budynkami jest coś niższego (czy jest dolinka). Da się w czasie O(log n)
   2.3. Jeśli jest to dolinka naliczasz plakat O(1)
   2.4. Jeśli nie ma t dalej "rozklejasz" stary plakat O(1)
   2.5. Po drodze aktualizujesz dane od dolinkach O(log n)

Całość daje O(n log n)

1. Masz teraz już 3x while(true) - to się nie może dobrze skończyć.
2. Modyfikujesz licznik pętli wewnątrz pętli
3. Nie sprawdzasz wyniku scanf
4. Stąd do wieczności

else // jezeli nie ma juz budynku w grupie wychodze z szukacza i ide dalej po tablicy (do fora)
            {
                break;
            }

Fajnie że zastosowałeś klamerkę, szkoda tylko że tak daleko od miejsca gdzie mogło by to być.

5. Pętla w pętli:

for > while(true) > while(true)

Przy tego typu zadaniach raczej stosuje się ograniczone pętle, jeśli chcesz obliczyć złożoność asymptotyczną.
Faktyczna może być mniejsza (dzięki IFom), ale jak masz while(true) to generalnie można sobie dumać.

6. using namespace std;
   To C czy C++?

7. Algorytm jest zagmatwany i dlatego nie zagłębiałem się w niego, ale ten fragment zasługuje na szczególną uwagę:

    for(int i = 0; i <size; i++) // pomniejszam o najmniejszą wartość 
    {
        tablica[i] -= najmniejsza;
        if(tablica[i] == 0)
            tablica[i] = -1;
    }

Czyli po wykonaniu tej pętli dla rozmiarów:
na wejściu: 1,2,3
mamy: -1,1,2
Czyli różnica w stosunku do oryginału:
-2,-1,-1
Czy tak to miało wyglądać?

To powinno zadziałać, ale nadal nie jestem pewien że to jest optymalne rozwiązanie.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main()
{
	size_t size,add,count=0;
	cin>>size;
	vector<size_t> vec(size+1);
	while(size--) cin>>add>>vec[size];
	for(bool more=true;more;)
	{
		more=false;
		size_t pos=0,width=0,strip=INT_MAX;
		for(size_t pos=0;pos<vec.size();++pos)
		{
			add=vec[pos];
			if(add>0)
			{
				if(strip>add) strip=add;
				++width;
			}
			else
			{
				if(strip&&width) more=(++count);
				for(int i=1;i<=width;++i) if(vec[pos-i]) vec[pos-i]-=strip;
				width=0;
				strip=INT_MAX;
			}
		}		
	}
	cout<<count;
	return 0;
}

Ale jesteśmy durni.
Pod treścią zadania jest podane najlepsze rozwiązanie z liniową złożonością czasową, którego implementacja jest banalnie prosta:

template<typename T>
int findMinimuPosterCount(size_t n, T it)
{
    int count = 0;
    std::vector<int> stack;
    stack.reserve(n);

    for (size_t i = 0; i < n; ++i, ++it) {
        while (!stack.empty() && stack.back() > *it) 
            stack.pop_back();

        if (stack.empty() || stack.back() < *it)
        {
            stack.push_back(*it);
            ++count;
        }
    }
    return count;
}

Taki tip, w zadaniach algorytmicznych dobrze jest sobie policzyć liczbę iteracji (co mniej więcej koreluje ze złożonością) dla najgorszego przypadku. Jeśli wyjdzie coś poniżej 100 milionów to zwykle zmieści się poniżej 1 sekundy.

W ogóle to zadanie wyglądało znajomo, a jak zobaczyłem OI z rocznika 07/08 to mi się rozjaśniło, skąd to znam :D

_13th_Dragon napisał(a):

To powinno zadziałać, ale nadal nie jestem pewien że to jest optymalne rozwiązanie.

Dalej wolno, mimo wszystko.

MarekR22 napisał(a):

Ale jesteśmy durni.
Pod treścią zadania jest podane najlepsze rozwiązanie z liniową złożonością czasową, którego implementacja jest banalnie prosta:

no generalnie, to co dodałeś to niezła szkoła jazdy.
Na pocieszenie powiem że nie zauważyłem twojej wiadomości i po pracy usiadłem do twojego algorytmu który opisałeś słownie wcześniej ;)
i wykonuje się trzy razy szybciej od moich, ale dalej za wolno bo to jest czas rzędu 30s dla potwornych ilości danych przy moich 100s.
Ten kod co teraz wrzuciłeś wykonuje się najszybciej bo po zczytaniu to nie jest nawet 0.1s więc zasuwa w porównaniu ze wszystkim

Będę go gryzł cały jutrzejszy dzień ;)
Pewnie będę pytał.

Generalnie pojawił się tutaj problem też notacji w tym temacie (indeksowa vs wskaźnikowa)
I ich szybkości.
Sprawdziłem programy napisane w obu notacjach.
Wynik jest w przybliżeniu 25% lepszy na korzyść notacji wskaźnikowej.

Jednak ja tutaj wymyślałem skomplikowane algorytmy jak ktoś trafnie zauważył gdzie pętla poganiała jedną pętle.
Faktycznie to nie mogło działać szybko.
Jak jutro będę miał czas to porobię testy i najwyżej tutaj wrzucę jak się wszystko czasowo układa.

Pokaż te benchmarki, bo te wyniki są niewiarygodne.

Różnica była widoczna. Na tym moim kulawym kodzie.
Te najnowsze wersje sprawują się tak ostatecznie:

Notacja indeksowa dla 249089 danych wejściowych mamy 91s

Notacja wskaźnikowa te same dane, mamy 83s

Ponawiam prośbę. Pokaż benchmarki. Strzelam, że porównujesz jabłka do pomarańczy i nie optymalizujesz kodu. I pewnie UB na dokładkę.

Przydal by się kod aby zweryfikować czy na pewnno twoje porównanie wydajności ma sens.

Polecam także przeprowadzić benchmark przy pomocy jakiegoś frameworka (np. gbench) oraz odciąć strumień wyjścia lub całkowicie wyrzucić printy (musisz pamiętać wtedy aby zabezpieczyć się przed optymalizacją kompilatora aby nie pominął tego po prostu, gbench udostępnia do tego specjalną funkcje), tak aby mieć pewność że mierzysz wydajność pointer vs operator []

https://quick-bench.com/q/PLrpJEA6cWqqF-SnN60y-ttGdsI
https://quick-bench.com/q/eJd29yZNd2CtClP77A9pk6VP67w

MarekR22 napisał(a):

https://quick-bench.com/q/PLrpJEA6cWqqF-SnN60y-ttGdsI
https://quick-bench.com/q/eJd29yZNd2CtClP77A9pk6VP67w

I tak ma wyjść. O(n*max(h)) vs O(n) (Łączna ilość push i pop ze stosu jest nie większa od O(n), plus petla, które daje O(n), co po zsumowaniu dalej jest O(n)).

A to co mierzy OP i z jakim poziomem optymalizacji kompiluje, to ja nie wiem. Ale strzelam, że coś ma źle.