 |
Coders' city Nasza pasja to programowanie!
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
marcin_an
Dołączył: 26 Maj 2005 Posty: 18822
|
Wysłany: Sro Kwi 15, 2009 2:14 pm OP Temat postu: [C++] Tworzenie tablicy dwuwymiarowej (komentarz) |
|
|
Post dotyczy tego posta w CUO.
W po?cie jest napisane, ?e przy korzystaniu z metody z alokacj? ci?g?ego obszaru pami?ci trudniej jest tworzy? tablice dwuwymiarowe o nietypowych kszta?tach. Wbrew pozorom w wi?kszo?ci przypadków tak nie jest. Je?eli mamy kod alokuj?cy wiersze ró?nej d?ugo?ci metod? alokacji ka?dego wiersza oddzielnie, to bez problemu zwykle mo?na to prze?o?y? bezpo?rednio na wersj? z pojedyncz? alokacj?. Schemat jest prosty. Rozmiar wymaganego obszaru ci?g?ego jest równy sumie d?ugo?ci wszystkich wierszy. Oprócz tego musimy wiedzie?, gdzie zaczyna si? ka?dy z wierszy w zaalokowanym obszarze. Nietrudno si? domy?li?, ?e przesuni?cie jest sum? d?ugo?ci wszystkich poprzednich wierszy.
Dla osób lubi?cych wzorki: Przy za?o?eniu, ?e jest n oraz s(i) oznacza rozmiar i-tego wiersza: Rozmiar alokowanego obszaru
}) Przesuni?cie dla k-tego wiersza
=\sum_{i=1}^k{s(i)}) Przek?adaj?c te wzorki bezpo?rednio na kod: Kod: |  static unsigned int const n = 9;
 static unsigned int const s[n] = {1, 2, 3, 4, 5, 4, 3, 2, 1};
 T* data = new T[accumulate(s, s + n, 0)];
 vector<T*> rows(n);
 
 for (unsigned int i = 0; i < n; ++i)
 {
 rows[i] = data + accumulate(s, s + i, 0);
 }
|
Oczywi?cie jest to niewydajne (linia 8: ci?g?e przeliczanie tego samego) i mo?na to zapisa? przynajmniej tak: Kod: |   static unsigned int const n = 9;
  static unsigned int const s[n] = {1, 2, 3, 4, 5, 4, 3, 2, 1};
  T* data = new T[accumulate(s, s + n, 0)];
  vector<T*> rows(n);
  unsigned int currentOffset = 0;
  
  for (unsigned int i = 0; i < n; ++i)
  {
  rows[i] = data + currentOffset;
  currentOffset += s[n]; // Zwi?kszamy przesuni?cie o rozmiar wiersza
  }
|
W wi?kszo?ci przypadków mo?na (nawet wypada) napisa? to optymalniej, zast?puj?c wyra?enie s[n] lub sum? s[n] innymi, prostszymi wyra?eniami. Np. dla tablicy prostok?tnej suma s[n] to po prostu iloczyn d?ugo?ci wiersza i indeksu aktualnego wiersza: Kod: |  rows[i] = data + i * rowLength; // Czyli to, co wszyscy znaj?
|
Dla tablicy trójk?tnej s[i] mo?na zast?pi? po prostu i. D?ugo?ci wierszy tworz? ci?g arytmetyczny, wi?c nietrudno równie? zauwa?y?, jak policzy? sum? d?ugo?ci wierszy. Itd. _________________ Nieaktywny od 2017-04-01 |
|
Powrót do góry |
|
 |
|
|
|
Możesz pisać nowe tematy Możesz odpowiadać w tematach Nie możesz zmieniać swoich postów Nie możesz usuwać swoich postów Nie możesz głosować w ankietach Możesz dodawać załączniki na tym forum Możesz pobierać pliki z tego forum
|
 Debug: strone wygenerowano w 0.21920 sekund, zapytan = 11
|