Tablice bardzo dynamiczne

W każdym poważnym języku programowania mamy do dyspozycji tablice o zmiennym rozmiarze, możliwym do ustalenia w czasie działania programu. Teoretycznie można by się bez nich obyć, jeżeli język posiada jakąś formę wskaźnika czy referencji, lecz konieczność ciągłego używania list na pewno nie byłaby przyjemna.
Z drugiej strony tablice mogą też być indeksowane więcej niż jednym indeksem, czyli być wielowymiarowe. Niekiedy wszystkie podtablice w danym wymiarze muszą mieć ten sam rozmiar (czyli całość być prostokątem, prostopadłościanem, itd.), ale np. C++ i C# pozwalają na dowolność i tworzenie chociażby macierzy trójkątnych zawierających tylko interesujące nas komórki.

To całkiem nieźle, lecz nie spotkałem jeszcze żadnego języka, który osiągnąłby zen w kwestii dynamicznych tablic, a mianowicie umożliwiał zmianę liczby wymiarów w trakcie działania programu. Być może powodem jest fakt, że w przypadku takich wybitnie elastycznych tablic nie da się już zapewnić dostępu do pojedynczego elementu w czasie stałym. Dla n wymiarów może on bowiem wynieść O(n²).
Jak więc można taką bardzo dynamiczną tablicę symulować? Ano trzeba samemu przeprowadzić jej linearyzację, czyli ponumerowanie wszystkich elementów tak, by można było obliczyć adres każdego w – liniowej przecież – pamięci operacyjnej. Przykładowo dla tablicy dwuwymiarowej element (x, y) będzie miał zlinearyzowany indeks równy zwykle x + y * width. Numerując z kolei trójwymiarową “kostkę”, otrzymalibyśmy formułę: x + y * width + z * height * width.

I tak dalej… W przypadku ogólnym aczkolwiek wzór może być trochę straszny :) Dla n-wymiarów o rozmiarach c₁, …, c_n, element opisany indeksami a₁, …, a_n (liczonymi od zera) w wersji zlinearyzowanej znajdzie się na miejscu l:

Formuła przekłada się oczywiście na dwie zagnieżdżone pętle – stąd więc jej oczekiwana złożoność. Można ją jednak łatwo zoptymalizować, przechowując wartość wewnętrznego iloczynu dla każdego z n wymiarów. Wtedy dostęp będzie już w czasie liniowym – oczywiście cały czas względem liczby wymiarów, a nie rozmiaru tablicy, więc nie jest aż tak źle :)
Taką dynamicznie wielowymiarową tablicę prawdopodobnie najłatwiej i najlepiej jest zaimplementować C++. I, co ciekawsze, nie będzie to wcale odkrywanie koła na nowo – czegoś takiego nie ma bowiem ani STL (daleko jej do tego), ani nawet boski boost ;]

Be Sociable, Share!

• 
• 

Be Sociable, Share!

• 
• 

• Tweet
•