Kopiowanie tablic
Ostatnio zmodyfikowano 2015-04-19 23:31
dek12 Temat założony przez niniejszego użytkownika |
Kopiowanie tablic » 2015-04-19 21:24:25 cześć eksperymentuje sobie troche i napotkalem pewien problem. mianowicie, zrobilem cos na wzor vectora. gdzie moge dodawac dowolna ilosc elementow. gdy tworze obiekt tego mojego vectora ustawiam mu rozmiar na 10. potem przy kazdym dodaniu elementu sprawdzam czy ilosc elementow nie jest wieksza od rozmiaru, jeśli tak to: -tworze tymczasowa tablice o rozmiarze o 10 wiekszym niz poprzednia. -kopiuje do niej elementy z oryginalnej tablicy -usuwam stara tablice -tworze nowa tablice o rozmiarze takim jak tymczasowa - kopiuje do nowej elementy z tymczasowej -usuwam tymczasowa
jak sie pewnie domyslacie, jest to "ciezka" operacja. dodanie 100000 elementow zajmuje okolo 14 sekund.
jak mozna to zoptymaizowac, przyspieszyc? jak to jest rozwiazane np w std::vector?
prosze tylko nie pisac, abym uzyl std::vector :D |
|
pekfos |
» 2015-04-19 21:47:48 1. Alokuj 2 razy tyle elementów co poprzednio, a nie o 10 więcej 2. Nie alokuj niepotrzebnej tablicy tymczasowej. |
|
dek12 Temat założony przez niniejszego użytkownika |
» 2015-04-19 22:03:52 prawie nic to nie zmieniło. zastanawia mnie jak to jest rozwiazane w std::vector, wie kots? |
|
pekfos |
» 2015-04-19 22:05:36 prawie nic to nie zmieniło. |
Więc niepoprawnie zastosowałeś się do wskazówek. Podaj kod. |
|
Fireho |
» 2015-04-19 22:09:46 W std::vector jest tak, że jest wskaźnik na tablicę, liczba elementów w tablicy i wielkość zarezerwowanej pamięci. Gdy zostaje dodany pierwszy element, to allokuje się tablicę o rozmiarze 1. Po dodaniu kolejnego 2, po dwóch kolejnych rozmiar zwiększa się do 4. Jak przekroczy się 4 to do 8, jak będzie więcej niż 8 to rozszerza do 16 itd.. Potęgi dwójki. Chyba że użyje się metod reserve lub shrink_to_fit , które odpowiednio rezerwują jakąś ilość lub zmniejszają ilość zaalokowanej tak, aby pasowała idealnie. |
|
dek12 Temat założony przez niniejszego użytkownika |
» 2015-04-19 22:27:20 void resize() { element < I >* newTab; int oldSize = size; int newSize = size * 2; newTab = new element < I >[ oldSize ]; for( int i = 0; i < oldSize; i++ ) { newTab[ i ].value = tab[ i ].value; } delete[] tab; tab = new element < I >[ newSize ]; for( int i = 0; i < oldSize; i++ ) { tab[ i ].value = newTab[ i ].value; } delete[] newTab; size = newSize; }
tab jest prywatnym polem (*element), konstruktor rezerwuje, a destruktor ja zwalnia. czy jak przepne tab na nowa tablice, to stara pamiec na ktora on wskazywal zostanie zwolniona? |
|
pekfos |
» 2015-04-19 23:02:10 Dalej robisz niepotrzebne alokacje. Rozróżniasz rozmiar od pojemności..? |
|
michal11 |
» 2015-04-19 23:11:25 Po co ci jakaś dodatkowa, tymczasowa tablica ? |
|
« 1 » 2 |