Mam pewną funkcję, która otrzymuję jako parametr pewną liczbę. Musi ją zamienić na odpowiadającą wartość w tablicy. Elementów tablicy jest ponad 1700, typu int (przy czym nie wszystkie komórki są wykorzystywane).
bla[117] = 774;
bla[581] = 777;
bla[582] = 777;
bla[600] = 132;
Tu pojawia się moje pytanie. Czy to rozwiązanie jest mniej wydajne od case’ów albo if’ów? a może macie pomysł jak to lepiej rozwiązać?
Dodam, że piszę w C++ i z tego co wiem, oznaczona inicjalizacja tu nie działa 
Tak jak robisz jest wydajniej, jedynie zjada to sporo pamięci.
To jest część addona do pewnej gry (zamiana itemków przy ulepszaniu). Czy przy dużej ilości graczy nie spowoduje to zawieszenia się aplikacji?
Przy:
bla[2]=7;
bla[5]=3;
bla[9]=1;
Możesz zapisać:
bla[]={0,0,7,0,0,3,0,0,0,1};
Bardziej wydajnego sposobu nie istnieje.
Takie rozwiązanie jest bez sensu, będę musiał pisać setki zer i chyba nie wiele to zmieni.
Nie musisz je ręcznie pisać, jak już masz zapisane:
bla[117] = 774;
bla[581] = 777;
bla[582] = 777;
bla[600] = 132;
to zrób trzy wiersze kodu które to zamienia na {0,0,…};
Takie wpisanie po kolei trwa znacznie dłużej niż inicjalizacja którą zaproponowałem.
Zależy to od tego co robisz w swoim programie,najwydajniejsze są pojedyncze zmienne,bo w tablicy musisz obliczać offsety i przesunięcia,jeśli chce się dostać do i-tego elementu muszę wykonać działanie tablica[0+(i-ty-1)] bo w C i C++ zerowy jest pierwszym elementem.Dalej dochodzi algorytm,który będzie operował na tych tablicach,zwykłe przeszukiwanie ma złożoność O(n),ale już sortowanie przez wstawianie O(n^2)
@Up, bredzisz.
Przecież po to robi tablice, żeby dekodować w czasie O(1), po co ją przeszukiwać skoro “zamiana itemku” sugeruje nad wyraz oczywiste dekodowanie indeks->wartość. Po co ma coś sortować w tym w ogóle? Wtedy zaburzy tablice przekodowań…
@OP
Tak jak robisz jest ok, do czasu aż za indeks nie podstawisz czegoś dużego. Są jeszcze struktury, które mogą ci wyszukiwać elementy w czasie logarytmicznym (głównie drzewa). Da się ten problem rozwiązać aby wyszukiwać w czasie zamortyzowanym O(1). Tablice hashujące.
Masz jakąś funkcję F(in) = out, która dla danego elementu zwróci ten sam (nie koniecznie unikatowy) output. Czyli ważne żeby było to deterministyczne.
Najlepiej żeby to przekodowanie było bijekcją, wiadomo nierealne, bo w ogólnym przypadku liczb masz nieskończoność, a komórek pamięci ograniczoną liczbę. Ale im bardziej będzie zbliżona do bijekcji tym lepiej. Dzięki temu stała ilością operacji będziesz mógł wyliczyć sobie liczbę, która określi ci w który element tablicy wpadasz. Jeśli wpadniesz w element, w który ktoś wcześniej wpadł możesz albo zastosować rehashowanie (obliczasz hash inaczej - inny wynik, inna komórka, może tym razem pusta), albo tak naprawdę nie przejmować się tym i stwierdzić, że każda komórka to taka klasa abstrakcji. To co wpadnie umieścisz albo na liście O(n’), albo w drzewie O(logn’). Użyłem zapisu n’, bo oczywiście chodzi o to że nie będzie to nasz początkowe n ale maksimum z mocy zbiorów wszystkich tych klas. Stąd przy dość dobrym skrócie można przyjąć, że to n’ będzie bliskie 1. Nic nie stoi na przeszkodzie, żeby balansować tablicę hashującą techniką probabilistyczną. Powiedzmy połączymy rehashowanie z listą (mająca metodę size() - rozmiar, ilość elementów). Weźmy np. średnią arytmetyczną. Każy dodany element zwiększa licznik średniej o 1 (nie ważne do której listy zostanie dodany), a mianownik zwiększamy o 1 jeśli zostanie dodana do listy pustej. Teraz jeśli lista do której zamieramy dodać ma mniej elementów niż średnia to dodajemy element, w przeciwnym przypadku rehashujemy -> szukamy krótszej listy.
Tak czy siak, czy warto się nad tym zastanawiać? - może. Tablica jest ok jeśli największy indeks nie będzie duży.
Często spotyka się problemy w których trzeba poświęcić albo więcej pamięci, albo więcej mocy obliczeniowej, zależy jak duży jest problem i na jakich danych ma operować oraz jak często ta operacja będzie wykonywana i jaki jest stosunek do długości wykonywania tej operacji, co użytkownikowi będzie mniej przeszkadzać.
Dlatego wyróżnia się 2 typy optymalizacji czasowa - szybsza,ale bierze więcej pamięci i pamięciowa,wolniejsza ale nie zajmuje dużo pamięci tylko czasu procesora
Bo to są dwie sprzeczne zmienne optymalizacyjne. Optymalizacja oszczędzająca pamięć była kiedyś niezwykle istotna (16 bitowe systemy) teraz to niema co się tym przyjmować.
To zależy od tego jaka jest maksymalna wartość którą ma mapować funkcja, im większa wartość tym więcej będziesz musiał alokować pamięci, oraz od częstości wywołań takiej funkcji. Jeżeli maksymalna wartość będzie duża, albo ta tablica musi być często powielana to radze skorzystać z hash mapy. Boost posiada gotową implementacje więc nie napracujesz się zbyt wiele, wystarczy użyć.
http://www.boost.org/doc/libs/1_37_0/doc/html/unordered.html