Tablice bardzo dynamiczne

2007-11-15 10:32

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(n2).
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 c1, …, cn, element opisany indeksami a1, …, an (liczonymi od zera) w wersji zlinearyzowanej znajdzie się na miejscu l:

Wzór na linearyzację tablicy wielowymiarowej

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 ;]

Tags: ,
Author: Xion, posted under Programming »


3 comments for post “Tablice bardzo dynamiczne”.
  1. Liosan:
    November 15th, 2007 o 12:09

    A… może być coś o potencjalnych zastosowaniach napisał…? Bo ja jakoś nic nie widzę… :)

    Swoją drogą, pewnie implementacja w OCamlu też jest prosta – używając typów wariantowych.

  2. Xion:
    November 15th, 2007 o 17:14

    Ja też nie widzę, poza byciem ciekawostką rzecz jasna :)

  3. io:
    November 16th, 2007 o 9:40

    Można tworzyć wirtualne przestrzenie wielowymiarowe i symulować podróże w tej przestrzeni… jeah :D

    pozdrawiam

Comments are disabled.
 


© 2019 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.