Indeksowanie w Pythonie

Przeglądając jakiś rzeczywisty kod w języku Python można często natknąć się na nietypowe wykorzystanie operatora nawiasów kwadratowych. Tradycyjnie znaki te służą do indeksowania tablic, co w językach kompilowanych bezpośrednio do kodu maszynowego równa się prostej operacji na wskaźnikach:

Ponieważ jednak Python nie jest takim językiem, jego twórcy pozwolili sobie na to, by zawarte w nim kilogramy warstw abstrakcji oferowały dodatkową funkcjonalność również przy tak trywialnym zagadnieniu. W rezultacie indeksowanie tablic (a właściwie list, w tym i łańcuchów znaków) jest tu operacją, która często ukrywa w sobie znacznie bardziej skomplikowaną logikę niż to widać na pierwszy rzut oka.

Zacznijmy od tego, że w dopuszczalnymi indeksami są nie tylko dodatnie, ale i ujemne liczby całkowite. Oznaczają one dostęp do końcowych elementów tablicy: -1 do pierwszego od końca, -2 do drugiego, i tak dalej. Być może nie wydaje się logiczne to, że elementy tab[0] i tab[-1] są na przeciwnych krańcach listy podczas gdy ich indeksy różnią zaledwie o jeden. Uzasadnieniem jest tu odniesienie do indeksowania od końca w innych językach, czyli tab[tab.length() - i]. W Pythonie po prostu pomija się jawne zapisanie odwołania do długości tablicy.

Znacznie bardziej interesującym aspektem indeksowania jest użycie dwukropka (:). W zasadzie to zamienia on wówczas całą operację na “krojenie” (slice) tablicy, bo pozwala on na na wybór nie jednego elementu, a całego przedziału. Dokładniej mówiąc tab[i:j] oznacza fragment tablicy wyznaczony półotwartym zakresem indeksów . Kawałek ten zawiera więc tab[i], ale pomija tab[j]; jest to analogiczne chociażby do iteratorów begin() i end() w kontenerach STL.
To właśnie slicing jest tą nietypową operacją, która dla niewprawnego oka wygląda cokolwiek zagadkowo. Jest tak zwłaszcza wtedy, gdy wykorzystuje ona możliwość pominięcia jednego z krańców przedziału, który to jest wówczas “dociągany” do odpowiedniego krańca całej listy.

Łącząc wszystkie te zawiłości możemy już rozszyfrować większość często występujących przypadków użycia indeksowania w Pythonie:

Dwa ostatnie przykłady pokazują też, że tego rodzaju operacje są bardzo przydatne podczas przetwarzania łańcuchów znaków, które to “przypadkiem” są również swego rodzaju tablicami.

Co może udawać obiekt w C++

Możliwości przeciążania operatorów w C++ dla własnych typów obiektów sprawiają, że mogą one (tj. te obiekty) zachowywać się w bardzo różny sposób. Mogą na przykład “udawać” pewne wbudowane konstrukcje językowe, nierzadko wykonując ich zadania lepiej i wygodniej. Przykładów na to można podać co najmniej kilka – oto one:

• Obiekt może zachowywać się jak funkcja, czyli udostępniać możliwość “wywołania” siebie z określonymi parametrami. Takie twory często nazywa się funktorami i bywają używane podczas pracy ze standardową biblioteką STL.
  Działają one przy tym w bardzo prosty sposób, zwyczajnie przeciążając operator nawiasów okrągłych (). Jest on na tyle elastyczny, że może przyjmować dowolne parametry i zwracać dowolne rezultaty, co pozwala nawet na stworzenie więcej niż jednego sposobu “wywoływania” danego obiektu. Jednym z bardziej interesujących zastosowań dla tego operatora jest implementacja w C++ brakującego mechanizmu delegatów, czyli wskaźników na metody obiektów.
• Na podobnej zasadzie obiekt może udawać tablicę – wie o tym każdy, kto choć raz używał klas STL typu vector. Wymagane jest tu przeciążenie operatora indeksowania []. Daje ono wtedy dostęp do elementów obiektu-pojemnika, który zresztą nie musi być wcale indeksowany liczbami, jak w przypadku tablic wbudowanych (dowodem jest choćby kontener map). Ograniczeniem jest jedynie to, że indeks może być (naraz) tylko jeden, bo chociaż konstrukcja typu:
  1. v[3,4] = 5;

  jest składniowo najzupełniej poprawna, to działa zupełnie inaczej niż można by było się spodziewać :)

• Obiekty mogą też przypominać wskaźniki, które wtedy określa się mianem ‘sprytnych’ (smart pointers). Dzieje się tak głównie za sprawą przeciążenia operatorów * (w wersji jednoargumentowej) i ->. Normalnie te operatory nie mają zastosowania wobec obiektów, ale można nadać im znaczenie. Wtedy też mamy obiekt, który zachowuje się jak wskaźnik, czego przykładem jest choćby auto_ptr z STL-a czy shared_ptr z Boosta.
• Wreszcie, obiekt może też działać jako flaga boolowska i być używany jako część warunków ifów i pętli. Sprytne wskaźniki zwykle to robią, a innymi wartymi wspomnienia obiektami, które też takie zachowanie wykazują, są strumienie z biblioteki standardowej. Jest to spowodowane przeciążeniem operatora logicznej negacji ! oraz konwersji na bool lub void*.

Reasumując, w C++ dzięki przeciążaniu operatorów możemy nie tylko implementować takie “oczywiste” typy danych jak struktury matematyczne (wektory, macierze, itp.), ale też tworzyć własne, nowe (i lepsze) wersje konstrukcji obecnych w języku. Szkoda tylko, że często jest to wręcz niezbędne, by w sensowny sposób w nim programować ;)

Indeksowanie od tyłu

Pewna programistyczna mądrość ludowa uczy, że jedynymi liczbami bezpośrednio występującymi w kodzie powinny być tylko 0 lub 1. Brak lub nadmiar tej drugiej jest przy tym często pojawiającym się błędem, który zyskał swoją własną nazwę pomyłek o jedynkę (off-by-one errors).

Okazji do popełnienia tego rodzaju gaf jest sporo, a objawiają się one przede wszystkim wtedy, gdy mamy do czynienia z tablicami, łańcuchami znaków, kolekcjami, itd. – innymi słowy wszystkim, co da się indeksować. Jako rzecze C++ i większość innych “normalnych” języków, indeksy tablic rozpoczynają się od zera. Startowanie ich od jedynki ma aczkolwiek pewną zaletę: pętle przeglądające zawartość tablic mają wtedy prawie identyczne postaci niezależnie od kierunku przeglądania:

W przypadku indeksowania od zera pętla odliczająca wstecz jest wyraźnie różna:

Pisząc ją, trzeba więc zwrócić baczniejszą uwagę na to, co się robi.

Jednak nawet wtedy można potknąć się o pewien kruczek, gdy pod n podstawimy rzeczywiście używane wartości. Niech to będzie np. wielkość kolekcji STL czy długość łańcucha znaków std::string – a więc coś w stylu x.size(). Otóż takie wyrażenie zwraca liczbę typu równoważnego size_t, który z kolei jest równy ni mniej, ni więcej, jak tylko unsigned int. Jest to więc liczba bez znaku.
W zwykłej wersji pętli (liczonej do przodu) powoduje to ostrzeżenie kompilatora o niezgodności typów ze znakiem i bez znaku (signed/unsigned mismatch) w warunku i < x.size(), gdy i jest typu int. Jednym ze sposobów na pozbycie się tego warninga jest oczywiście zamiana typu licznika na size_t. Jeśli teraz mamy wystarczająco zły dzień, to przez analogię będziemy licznikiem tego typu indeksować również pętlę odwrotną:

I nieszczęście gotowe. Zauważmy bowiem, że odliczanie do tyłu tablicy/kolekcji indeksowanej od zera wymaga, by na koniec licznik przyjął na koniec wartość ujemną; inaczej warunek i >= 0 nigdy nie stanie się fałszywy. To się jednak nigdy nie stanie, gdy i jest liczbą bez znaku; zamiast tego nastąpi przekręcenie na maksymalną wartość dodatnią. Skutkiem będzie pętla nieskończona lub (częściej) access violation.

Co z tego wynika? Ano to, żeby… indeksowania generalnie unikać :) Po to bowiem zarówno STL, jak i każda inna biblioteka pojemników w każdym sensownym języku ma inne sposoby dostępu do elementów – choćby iteratory – aby z nich korzystać. I unikać takich “ciekawych” błędów jak powyższy :)

Dwa wymiary na dwa sposoby

W C++ dynamiczne tablice z więcej niż jednym wymiarem tworzy się zwykle w sposób dość złożony. Najpierw bowiem – w przypadku dwóch wymiarów – tworzymy tablicę wskaźników na jej wiersze, a następnie same wiersze:

Skądinąd wiadomo bowiem, że zapis tab[i] jest tylko cukierkiem składniowym zastępującym *(tab + i). Dlatego też w wyniku pierwszej dereferencji (indeksowania) musimy otrzymać wskaźnik (na wiersz tablicy), aby ponowną operację przeprowadzić drugi raz i dostać się do pojedynczego elementu.

Kiedy zaś tablica 2D jest umieszczona w jednym kawałku pamięci, wtedy element tab[i][j] powinien zostać obliczony inaczej – np. jako *(tab + j * width + i), jeśli elementy są układane w pamięci wierszami. Kompilator musiałby więc skądś wiedzieć, jaka jest szerokość (width) tablicy, a ponadto nie rozpatrywać każdej pary nawiasów kwadratowych osobno, lecz traktować je jako łączną operację indeksowania. Zwłaszcza pierwszy wymóg nie wydaje się rozsądny.

Warto jednak – jeśli zależy nam efektywności – używać drugiego sposobu przechowywania tablic dwuwymiarowych:

Dostęp do elementów jest wtedy szybszy, bo oszczędzamy sobie jednej dereferencji wskaźnika (która może być kosztowna, jeśli tablica jest porozrzucana po pamięci). Szczegóły indeksowania można zaś opakować w zgrabną klasę z przeciążonymi operatorami.
Albo po prostu użyć gotowego rozwiązania, np. klasy multi_array z Boosta :)

Kilka nawiasów kwadratowych

Gdy w C++ tworzymy typ wymagający indeksowania więcej niż jednym indeksem – a więc coś w stylu wielowymiarowej tablicy, np. macierzy – zazwyczaj używa się do tego celu operatora nawiasów okrągłych. Nie jest to specjalnie spójne z tablicami wbudowanymi język, gdzie do indeksowania stosuje się nawiasy kwadratowe, w tym przypadku nawet więcej niż jedną parę.
O ile jednak da się przeciążyć operator [], o tyle “operatorów” [][], [][][], itd. już nie. Można jednak zastosować inną technikę, jeśli chcemy by nasze własne typy były składniowo maksymalnie podobne do wbudowanych.

Trzeba mianowicie przygotować je tak, by dało się do nich stosować operator [] niejako więcej niż raz. Wymaga to wprowadzenia jakiejś klasy pośredniej; dla macierzy może ona reprezentować pojedynczy wiersz:

Dla tego wiersza piszemy naturalnie zwykły operator indeksowania, pozwalający nam dostać się do jego elementów. Trik leży w postaci operatora, którą umieszczamy w samej klasie macierzy:

Zwraca ona nasz wiersz, a właściwie jego opakowanie, które to zdefiniowaliśmy. W ten sposób osiągamy dla Matrix<T>zachowanie niemal dokładnie analogiczne do tablic typu T**: pierwsza para nawiasów daje nam T* (u nas MatrixRow<T>), zaś druga konkretną wartość typu T:

W tym rozwiązaniu oczywiście parę szczegółów do uwzględnienia (np. warianty const naszego operatora). Widać jednak, że jeśli bardzo chcemy, to przy odrobinie pomysłowości da się wszędzie używać “właściwych” nawiasów :)

Dynamicze tablice w C

Czasem życie zmusza do pisania w sławetnym i na szczęście zanikającym już języku C. A tam nie ma chociażby takich luksusów jak STL z niezastąpionymi pojemnikami. O wszelkie struktury danych trzeba zatroszczyć się samemu, co obejmuje także tak podstawowe jak dynamiczne tablice.
Jak wiadomo, takie tablice należy samodzielnie alokować, zmieniać ich rozmiar (z kopiowaniem zawartości) oraz zwalniać, gdy nie są już potrzebne. Najwyraźniej więc wybitnie przydatne są tu funkcje malloc i free, prawda? Otóż nieprawda :)

O wiele wygodniej jest bowiem używać funkcji realloc:

Jej nazwa wskazuje, że jej głównym przeznaczeniem jest zmiana rozmiaru już zaalokowanego kawałka pamięci. Zazwyczaj sprowadza się to zresztą do przydzielenia nowego, skopiowania tam zawartości starej porcji i zwolnienia jej. Jednakże w dwóch szczególnych przypadkach realloc zachowuje się inaczej – zależy to od parametrów, jakie jej podamy:

• jeżeli pierwszym parametrem będzie wskaźnik pusty (NULL), funkcja przydzieli pamięć w ilości bajtów wyrażonej drugim parametrem – czyli zachowa się jak malloc
• jeśli zaś drugim parametrem będzie zero, to funkcja spróbuje zwolnić kawałek pamięci, na który pokazuje wskaźnik będący pierwszym parametrem – czyli zachowa się jak free

To sprawia, że możemy używać funkcji realloc w postaci wywołania podobnego jak powyżej zawsze wtedy, gdy musimy zmienić rozmiar tablicy. Można na przykład dodać do niej element w taki oto sposób:

Nie musimy się martwić, czy tablica została wcześniej zaalokowana czy nie. Analogicznie wygląda usuwanie elementów z końca lub początku tablicy – wówczas nie trzeba przejmować się tym, czy z tablicy coś zostanie. Tak naprawdę opakowywanie obu tych operacji w funkcje nie jest nawet specjalnie potrzebne.

Jedynym warunkiem, aby to wszystko działało, jest odpowiednie zainicjowanie wskaźnika na tablicę oraz zmiennej przechowującej jej rozmiar – co jest aczkolwiek dość oczywiste:

I to właściwie wszystko. W sumie więc nie jest to może std::vector, ale w C nie ma co wybrzydzać :)

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