Coś szybszego od mapy w algorytmie

Odpowiedz Nowy wątek
2016-12-07 13:59
korleon
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?

Pozostało 580 znaków

2016-12-07 14:01
Patryk27
4

Jaki jest zakres wczytywanych liczb?

Pozostało 580 znaków

2016-12-07 14:16
kq
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

edytowany 1x, ostatnio: kq, 2016-12-07 14:16

Pozostało 580 znaków

2016-12-07 14:17
topik92
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.

Pozostało 580 znaków

2016-12-07 15:15
korleon
0

Liczb może być min. 1000.

Pozostało 580 znaków

2016-12-07 15:43
Wibowit
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.

"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2016-12-07 15:44
lista na wskaznikach to bedzie std::list. lista na tablicach to bedzie std::vector - fasadin 2016-12-07 15:52

Pozostało 580 znaków

2016-12-07 15:52
Patryk27
0

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

Pozostało 580 znaków

2016-12-07 17:37
korleon
0

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

edytowany 1x, ostatnio: kq, 2016-12-13 18:26

Pozostało 580 znaków

2016-12-07 17:40
Patryk27
1

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

Pozostało 580 znaków

2016-12-07 17:40
kq
0

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

Pozostało 580 znaków

2016-12-07 18:46
korleon
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?

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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