Coś szybszego od mapy w algorytmie

0

Hej,
W algorytmie potrzebuję sprawdzać czy dany element, który wczytuję, jeśli się pojawił to zwiększyć jego ilość o jeden.
W tym przypadku muszę kolekcjonować inty więc pomyślałem, że mapa będzie świetnym rozwiązaniem ale czy na pewno?
Na ten moment wykorzystuje: map<int, int> liczby;
Chodzi o to, że mam tablicę dwuwymiarową i moje działanie polega na tym, że muszę wrzucić do kolekcji sumę elementu tab[x][y] + tab[x][y+1] itd. Gdy wynik się powtórzy to mam zwiększyć jego ilość o jeden. Następnie sprawdzić jaka liczba wystąpień była największa i zliczyć ile cyfr miało takie wystąpienie.
Zależy mi na czasie wykonania i tutaj pytanie do Was, czy mapa do takich działań jest najlepsza? Czy jest coś szybszego od mapy?

4

Jaki jest zakres wczytywanych liczb?

7

Z reguły hashmapa (unordered_map) jest szybsza dla przypadku ogólnego (amortized O(1) vs O(logn)). Jak trafnie zauważył @Patryk27, jeśli znasz zakres liczb (np. 0-255) to jeszcze efektywniejsze może być użycie zwykłej tablicy i indeksacja po niej - ale to może być niewydajne pamięciowo - inaczej mówiąc, to zależy od danych

0

Jeśli zakres licz, jest rozsądnie mały to tablica jest szybsza, przy okazji jeśli będziesz iterował najpierw po osi y a potem po x, i trzymał oś y w nawiasie drugiej "nawiasie", to przeglądanie tablicy będzie kilka razy szybsze.

0

Liczb może być min. 1000.

1

Możesz też podejść do sprawy inaczej. Zamiast robić mapę, zrób listę (w C++ to chyba bardziej std::vector), posortuj (chyba std::sort), a potem poszukaj najdłuższego ciągu takich samych liczb. Złożoność sortowania to niby O(n lg n), ale quicksort robi mało cache misses, przez co może być szybciej. Ewentualnie możesz użyć radix sorta, doskonale się nadaje do sortowania małych elementów (czyli np intów, bo mają tylko 4 bajty). Radix sort ma liniową złożoność i też robi mało cache misses.

0

Nie chodzi o ilość liczb, tylko ich zakres wartości.

0

Przepraszam, elementy macierzy sa ograniczone przez: -103 i 103.

1

Czyli w sumie tyle co 0..2000 - zakładając, że są to liczby całkowite, bez problemu upakujesz to w tablicy.

0

czyli 2000 elementów. Jak najbardziej możesz użyć tablicy.

0

Super Panowie tylko powiedzcie mi jedno, żebym dobrze zrozumiał.
Po kolei jade po tablicy dwuwymiarowej (macierz) i zliczam sobie każdy punkt jednocześnie ładując go do tablicy.
Tyle, że potem mam ją posortować tylko jak? Jeśli np będę miał tablicę po zapełnieniu taką:

1 2 2 5 3

To wtedy po sortowaniu będę miał tak:

5 3 2 2 1

I musiałbym z takiej tablicy wyciągnąć jedynkę, ponieważ maksymalna ilość powtórzeń to 2 i "podwojonych" wartości jest jedna.

Moglibyście podpowiedzieć jak do tego podejść?
Czy może zrobić coś na wzór mapy na tablicy dwuwymiarowej?

0

Nie, jeśli masz tak mało wartości (2000) to robisz sobie tablicę z 2000 elementów, ustawiasz wszystko na zero i np. jak obliczysz 666 to na pozycji [minimialna wartość​+obecna] zwiększasz ilość wyników o 1.

1
korleon napisał(a):

1 2 2 5 3
I musiałbym z takiej tablicy wyciągnąć jedynkę, ponieważ maksymalna ilość powtórzeń to 2 i "podwojonych" wartości jest jedna.

Dla prostoty załóżmy, że zakres liczb to [0..5]
Na początku masz tablicę

[0][0][0][0][0][0]

Modyfikujesz tablicę wraz z wczytaniem kolejnych liczb

1 -> [0][1][0][0][0][0]
2 -> [0][1][1][0][0][0]
2 -> [0][1][2][0][0][0]
5 -> [0][1][2][0][0][1]
3 -> [0][1][2][1][0][1]

Swoją drogą to się nazywa sortowanie przez zliczanie - counting sort.
Teraz patrzysz, gdzie jest największa wartość. Pod indeksem nr 2, czyli jest najwięcej dwójek. Potem patrzysz ile komórek ma taką samą wartość jak ta pod indeksem 2, no jest tylko jedna wartość -> zwracasz 1.

0

Napisałem taki kod na szybko, prosze o potwierdzenie czy dobrze zrozumiałem, wydaje mi się, że tak:

	int tab[2000];
	int index = 0;
	int aktualnaWartosc = 0;
	int powtorzenie = 0;
	
	for (int i = 0; i < 2000; i++) {
		if (tab[i] == aktualnaWartosc) {
			powtorzenie++;
		} else if (tab[i] > aktualnaWartosc) {
			aktualnaWartosc = tab[i];
			index = i;
			powtorzenie = 0;
		}
	}

Coś takiego?
A co jeśli chciałbym zliczyć ilość różnych elementów?
Wtedy musiałbym znowu przelecieć po uzupełnionej tablicy (już tej która ma jako wartości ilość wystąpień) i sprawdzić ile jest różnych od 0 tylko tutaj pytanko, co będzie szybsze? Ponowne przejechanie po tablicy czy dodanie ifa do podanego wyżej kodu?

1

Nie, zupełnie źle.

int tab[2000] = {};   // trzeba zerować, bo samo się nie zeruje
for (int i = 0; i < ile_liczb_na_wejsciu; ++i)
    ++tab[kolejna_liczba_na_wejsciu];
0

Dziękuję za odpowiedź.

Chyba w takim razie cos źle robie bo od razu rzuca mi Run Time error zaraz po wrzuceniu Twojej pętli, na tych większych liczbach, na mniejszych jest okej.

Mój kod wygląda następująco:

     int tab1[2000] = {};
    while (getline(cin, s)) {
    	if (licznik < rozmiarTablicy) {
	// uzupelnienie tablicy dwuwymiarowej wartosciami z pliku
        } else {
        	// obliczanie sumy w oparciu o 4 dane z pliku
        	suma = tab[x][x]....;
	        for (int a = 0; a < iloscSum; ++a) {
    			++tab1[suma];
    		}
        }
    }

Popróbowałem kilku rzeczy i doszedłem do tego, że "++tab1[suma]" w podanej wyżej pętli for wyrzuca podanym wyżej błędem.
Może to wina, że mogą trafić się minusowe sumy? Czy dobrym rozwiązaniem (przy ujemnych wartościach i zliczaniu ich wystąpień) jest dodanie do wartości 1000? Rozumiem, że zakres jest od -1000 do 1000 a Wy mówicie o 0 do 2000 czyli tak jakby przesuwamy o 1000?

Jeśli mogę prosić moderatora o doklejenie posta to byłoby super.

1

Tak, musisz dodać ten tysiąc do każdej wczytywanej liczby i odejmować przy wyświetlaniu.

0

Okazuje się, że źle zrozumiałem zadanie. Musiałem zmodyfikować dodawanie do tablicy i teraz wygląda to tak:

Elementy które wczytuje do tablicy 2 wymiarowej są ograniczone tak jak wcześniej mówiłem : -10 do 3 oraz 10 do 3.
Podczas wpisywania ich do tablicy muszę zadziałać na nich to znaczy:

tab[x][y] = aktualnaWartosc + tab[x-1][y] + tab[x][y-1] - tab[x-1][y-1]

.

Wtedy dopiero trafia to do tablicy dwu wymiarowej.

Następnie po uzupełnieniu kolejne cyfry to tak jak mówiłem dodanie konkretnych wartości z podanych indexów i wtedy wygląda to tak:

suma =
                    tab[x][y] +
                    tab[x - 1][y - 1] -
                    tab[x][y - 1] -
                    tab[x - 1][y];

Zakres wartości może być dużo większy na ten moment tj. po samym uzupełnieniu (jeśli dobrze rozumiem) każdy element w tablicy może być rzędu (4000 max gdy wszystko będzie dodatnie) a suma może być (16000 max gdy wszystko będzie dodatnie).

Przepraszam za zamieszanie ale czy teraz tablica jest również wskazana?
Sama iteracja później po tab1[32000] aby wyszukać ile jest różnych elementów już wyrzuca moje testy za zbyt długi czas..

Przez przypadek nacisnąłem Ctrl+V i samo wysłało, wybaczcie.

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