Implementasi n-dimensional array (1)

N-dimensional array (atau selanjutnya disebut ndarray), atau yang oleh beberapa framework deep learning disebut tensor, adalah tulang punggung teknologi machine learning. Struktur data ini seringkali taken for granted: kita memakainya, namun kita tidak tahu mekanisme di baliknya.

Di tulisan ini kita akan coba membuat implementasi ndarray menggunakan python.

Saya sengaja menghindari penggunaan istilah tensor, karena di disiplin ilmu matematika murni tensor memiliki arti yang berbeda. Walau tensor bisa direpresentasikan dengan ndarray, ia memiliki karakteristik lain, lebih dari sekadar ndarray, atau "matrix dengan dimensi lebih dari dua".

Daftar isi

1. Pengantar

Ndarray adalah array yang merepresentasikan item-item dalam multidimensi, di mana jumlah item pada masing-masing dimensi berjumlah seragam. Mirip seperti nested array, yaitu array dalam array (dalam array (dalam array (...))). Beberapa perkakas machine learning dan deep learning menyebutnya sebagai tensor. Semuanya sama-sama mengacu pada bentuk umum dari skalar, vektor, dan matriks. Jika skalar memiliki 0 dimensi, vektor memiliki 1 dimensi dan matriks memiliki 2 dimensi, maka ndarray bisa saja memiliki sembarang dimensi, $N$, dengan $N\geq 0$. Bisa 3 dimensi, 4 dimensi, dst.

Di library ndarray modern (Numpy ndarray, tensorflow tensor, atau pytorch tensor), jumlah dimensi, urutan dimensi, elemen data, dan aspek lain suatu ndarray harus dapat dimanipulasi saat run-time. Ini berbeda dengan nested array yang dimensinya sudah harus ditetapkan saat deklarasi/inisialisasi dan tidak bisa diubah lagi saat runtime. Misalnya, pada c/c++ kita bisa membuat array 2 dimensi:

int[3][3] x;

namun hingga akhir program, x tetap 2 dimensi. Tidak berubah, dan tidak bisa diubah.

Ndarray array adalah komponen penting dalam perkembangan teknologi machine learning hingga deep learning. Biasanya ia digunakan untuk merepresentasikan data. Misal, data tabel dapat direpresentasikan dengan ndarray 2-dimensi berbentuk $n_{baris} \times n_{kolom}$. Data citra dapat direpresentasikan dengan ndarray 4-dimensi berbentuk $n_{sampel} \times n_{panjang} \times n_{lebar} \times n_{channel}$.

Di tulisan ini kita akan coba mengimplementasikan struktur data ndarray dengan bahasa pemrograman Python.

1.1. Beberapa fitur yang akan coba diimplementasikan

1.2. Batasan

2. Layout pada memori

Walau judulnya n-dimensional array, data numerik pada ndarray sebetulnya tidak tersusun berupa array dalam array (dalam array (dalam array (...))). Melainkan, data disimpan dalam format 1-D array di memori. Misalkan kita punya array berbentuk $3\times3$ seperti ini:

np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])

Output yang dihasilkan akan seperti ini:

array([[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]])

Namun, sebenarnya yang tersimpan di memori akan berupa array flat, kurang lebih akan seperti ini (jika dibayangkan).

Linear ndarray layout

Ilustrasi array di memori

Implementasi ndarray paling tidak memiliki dua komponen utama, yang memberinya karakteristik: shape dan strides.

2.1. Shape

Shape, seperti namanya, ia menentukan bentuk suatu ndarray. Shape dapat direpresentasikan sebagai tuple. Contoh: shape dari ndarray 2 dimensi (matrix) berbentuk $2 \times 2$ direpresentasikan dengan $(2,2)$. Secara formal, ndarray berdimensi $N$ memiliki shape berupa $(d_0, d_1, ..., d_{N-1})$.

2.2. Strides

Jumlah langkah yang dibutuhkan untuk menuju dimensi selanjutnya. Array pada ilustrasi di atas memiliki strides $(3, 1)$. Artinya, untuk menuju ke elemen selanjutnya di dimensi ke-2 (kolom), cukup lompat 1 saja. Namun, di dimensi pertama (baris), kita harus melompati 3 elemen untuk menuju kolom yang sama namun di baris selanjutnya.

Jumlah elemen pada strides selalu sama dengan jumlah elemen pada shape. Strides direpresentasikan sebagai tuple juga: $(s_0, s_1, ..., s_{N-1})$. Kita bisa menghitung masing-masing elemen di strides ($s_i$) berdasarkan shape dengan formula berikut ini.

\begin{equation} \label{eq:strides} s_i = \prod_{j+i+1}^{N-1} d_j \end{equation}

2.3. Mengakses elemen ndarray

Posisi (secara fisik) dari item pada data ndarray di memori kita sebut offset. Item pertama dari data tersebut bisa diakses pada offset 0. Bagaimana jika kita ingin memperoleh offset berdasarkan index? Misal, kita mempunyai ndarray berbentuk $(3, 3)$. Maka strides-nya adalah $(3, 1)$ Jika kita ingin menghitung offset dengan index $(n_0, n_1)$, di mana $n_0$ adalah index baris dan $n_1$ adalah index kolom, maka kalkulasinya adalah \begin{equation} offset = n_0 \times s_0 + n_1 \times s_1. \end{equation} Sama halnya dengan mengakses ndarray 3 dimensi dengan index $(n_0, n_1, n_2)$, dengan $n_2$ sebagai dimensi kedalaman. Pertama, peroleh strides-nya, kemudian hitung offset-nya: \begin{equation} offset = n_0 \times s_0 + n_1 \times s_1 + n_2 \times s_2. \end{equation}

Istilah teknis dari index $(n_0, n_1, ..., n_{N-1})$ pada ndarray berdimensi $N$ adalah multidimensional index. Secara umum, berdasarkan suatu multidimensional index $(n_0, n_1, ..., n_{N-1})$, offset dapat kita hitung dengan persamaan \ref{eq:offset}.

\begin{equation} \label{eq:offset} offset = \sum_{i=0}^{N-1} s_i n_i \end{equation}

3. Implementasi

3.1. Sketsa awal ndarray

Kita mulai dengan sebuah kelas NDArray, yaitu kelas utama untuk struktur data ndarray, dengan 3 properties utama: data, shape, dan strides. Selain itu, sertakan juga fungsi untuk membuat ndarray dari python list, ndarray_from_list(). Di fungsi ndarray_from_list(), argumen untuk parameter lst akan menjadi data bagi ndarray baru. Property shape akan mengikuti argument untuk parameter shape, dan kita cast menjadi list (untuk konsistensi).

class NDArray:
    def __init__(self):
        self.data = None
        self.shape = None
        self.strides = None


def ndarray_from_list(lst, *shape):
    if len(lst) != prod(shape):
        raise Exception(
            f"List dengan panjang {len(lst)} tidak bisa dijadikan ndarray berbentuk {shape}"
        )
    x = NDArray()
    x.data = lst
    x.shape = list(shape)
    x.strides = shape_to_strides(shape)
    return x

Saat inisialisasi ndarray, strides akan dihitung secara otomatis berdasarkan shape. Di bawah ini adalah implementasi dari fungsi shape_to_stride(). Fungsi ini berdasarkan persamaan \ref{eq:strides}.


...

def shape_to_strides(shape):
    strides = []
    for i in range(len(shape)):
        prod = 1
        for j in range(i + 1, len(shape)):
            prod *= shape[j]
        strides.append(prod)
    return strides

Di tahap ini kita bisa mencoba menggunakan ndarray. Misalnya:

x = ndarray_from_list([1, 2, 3, 4], 2, 2)

Kode di atas akan menghasilkan objek ndarray dengan data berisi [1, 2, 3, 4] dan shape dengan nilai (2, 2) (ekuivalen dengan matriks $2 \times 2$).

Kita masih belum akan mencetak ndarray sekarang, karena untuk dapat mencetak dengan benar (data berikut juga bentuknya), kita membutuhkan kalkulasi lebih lanjut. Namun, sementara ini kita akan menggunakan cara "curang" agar bisa mencetak ndarray dengan bentuk yang sesuai dengan memanfaatkan NumPy. Nanti kita akan ganti dengan implementasi kita sendiri.

Implementasikan 2 fungsi berikut ini. Yang pertama untuk mencetak dengan format tertentu (pretty print), yang kedua untuk mencetak atribut ndarray untuk mempermudah proses debugging.

import pprint

...

def print_ndarray(arr):
    # Walau menggunakan numpy, data dan shape tetap berdasarkan 
    # implementasi kita sendiri
    x = np.array([float(i) for i in arr.as_list()]).reshape(*arr.shape)
    print(x.__repr__())


def debug_print(arr):
    info = dict(
        actual_data=arr.data,
        intended_data=arr.as_list(),
        shape=arr.shape,
        strides=arr.strides,
    )
    pprint.pprint(info)

...

Jika digunakan sebagai berikut,

x = ndarray_from_list([1, 2, 3, 4], 2, 2)

print("Array:")
print_ndarray(x)

print()

print("Debug info:")
debug_print(x)

kita akan mendapatkan luaran seperti ini:

Array:
array([[1., 2.],
       [3., 4.]])

Debug info:
{'actual_data': [1, 2, 3, 4],
 'intended_data': [1, 2, 3, 4],
 'shape': [2, 2],
 'strides': [2, 1]}

Bagian actual_data adalah data dalam urutan sebenarnya pada memori. Bagian intended_data adalah data dalam urutan dengan versi yang dilihat oleh kita (user). Di contoh ini, keduanya masih sama, karena belum ada manipulasi apapun terhadap ndarray ini.

Selanjutnya, kita akan mengimplementasikan akses ke item pada ndarray dengan indeks tertentu (misal, berdasarkan baris $i$, kolom $j$). Tambah method get_item() pada kelas NDArray.

class NDArray:
    def __init__(self):
        self.data = None
        self.shape = None
        self.strides = None

    def get_item(self, *index):
        actual_offset = sum(i * s for i, s in zip(index, self.strides))
        return self.data[actual_offset]

Fungsi ini menerima input multidimensional index dari item yang akan kita akses, kemudian mengonversi index tersebut menjadi offset.

Contoh:

x = ndarray_from_list([1, 2, 3, 4], 2, 2)

# dengan multidimensional index, kita bisa mengakses item 3 
# sebagai berikut, karena 3 berada di baris 1, kolom 0
item = x.get_item(1, 0)

Method get_item akan mengonversi multidimensional index (1,0) menjadi offset (yaitu 2), kemudian mengakses item ke-2 pada x.data. Perhatikan bahwa actual_offset diperoleh berdasarkan persamaan \ref{eq:offset}.

Kita juga bisa melakukan indexing pada ndarray dengan dimensi lebih tinggi, misalnya ndarray 3 dimensi, dengan cara yang sama:

# Buat ndarray berbentuk 2x2x2
x = ndarray_from_list([1, 2, 3, 4, 5, 6, 7, 8], 2, 2, 2)

# koordinat ini mengacu ke item angka 6
item = x.get_item(1, 0, 1)

Seringkali kita akan membutuhkan akses data ndarray sebagai python list (flat/1-d list). Caranya adalah menampung semua elemen ndarray dari offset 0 hingga akhir. Pertama, implementasi method get_size() untuk membantu menghitung ukuran (atau panjang data seharusnya) dari data ndarray. Sederhana saja, ukuran ndarray merupakan hasil perkalian dari elemen pada shape. Sebagai contoh, ndarray 2 dimensi (matrix) berbentuk (3, 2) akan memiliki ukuran $3 \times 2 = 6$. Kedua, implementasi fungsi offset_to_index untuk mengonversi balik offset ke list berisi multidimensional index. ... ...

class NDArray:

    ...

    def get_size(self):
        return prod(self.shape)

    def as_list(self):
        result = []
        for i in range(self.get_size()):
            index = offset_to_index(self, i)
            value = self.get_item(*index)
            result.append(value)
        return result


...


def offset_to_index(arr, offset):
    index = [None for _ in range(len(arr.shape))]
    tmp_offset = offset
    for i in reversed(range(len(arr.shape))):
        index[i] = int(tmp_offset % arr.shape[i])
        tmp_offset /= arr.shape[i]
    return index

Pertanyaan yang mungkin muncul namun akan terjawab nanti:

mengapa untuk mencari ukuran ndarray tidak menggunakan len(self.data) saja?

3.2. Contoh kegunaan manipulasi stride

Sampai di titik ini, kita akan mulai bisa melihat "keajaiban" trik manipulasi strides dan shape. Ini juga alasan mengapa NumPy bisa sangat efisien.

3.2.1. Transpose

Saat melakukan transpose pada suatu ndarray x, berarti kita melakukan pertukaran antara elemen baris dan kolom dari x. Ini bisa saja kita lakukan dengan melakukan iterasi atas baris dan kolom, kemudian menukar x[i][j] dengan x[j][i].

Namun, sebetulnya kita tidak perlu melakukan iterasi yang mahal itu. Triknya adalah, kita cukup membalik x.shape dan x.strides. Misal, ndarray berbentuk (3, 2) dapat ditranspose menjadi berbentuk (2, 3) dengan elemen baris dan kolom yang ditukar, seperti ini:

### ndarray mula-mula
x = ndarray_from_list([1, 2, 3, 4, 5, 6], 3, 2)

print("SEBELUM TRANSPOSE:")
print("Array:")
print_ndarray(x)
print()
print("Debug info:")
debug_print(x)


### Dua baris di bawah ini adalah trik transpose kita
x.shape = list(reversed(x.shape))
x.strides = list(reversed(x.strides))

print()
print("SETELAH TRANSPOSE:")
print("Array:")
print_ndarray(x)
print()
print("Debug info:")
debug_print(x)

Output yang dihasilkan adalah

SEBELUM TRANSPOSE:
Array:
array([[1., 2.],
       [3., 4.],
       [5., 6.]])

Debug info:
{'actual_data': [1, 2, 3, 4, 5, 6],
 'intended_data': [1, 2, 3, 4, 5, 6],
 'shape': [3, 2],
 'strides': [2, 1]}

SETELAH TRANSPOSE:
Array:
array([[1., 3., 5.],
       [2., 4., 6.]])

Debug info:
{'actual_data': [1, 2, 3, 4, 5, 6],
 'intended_data': [1, 3, 5, 2, 4, 6],
 'shape': [2, 3],
 'strides': [1, 2]}

Setelah transpose, actual_data berbeda dengan intended_data karena strides dan shape, yang menentukan urutan iterasi per-elemen, telah berubah (dimanipulasi). Ternyata kita sama sekali tidak perlu mengubah urutan data sebenarnya di memori saat melakukan transpose. Yang perlu dilakukan adalah memanipulasi cara kita (user) dalam melihat urutan; dan cara yang bisa dilakukan untuk memanipulasi user dalam melihat urutan adalah dengan memanipulasi shape dan strides.

Jadi, jika ada ndaraay berbentuk (1000000, 1000000), kita tidak perlu melakukan iterasi sebanyak ratusan ribu kali untuk dalam melakukan transpose. Cukup mainkan saja shape dan stride-nya 😉.

3.2.2. Broadcasting

Library ndarray modern mengadopsi mekanisme broadcasting. Perhatikan contoh di bawah ini.

simple broadcasting illustration

Saat melakukan operasi aritmatika antara kedua ndarray dengan bentuk berbeda, ndarray yang lebih kecil seolah-olah diduplikat hingga kedua ndarray memiliki jumlah baris yang sama. Mekanisme ini disebut broadasting: salah satu atau kedua ndarray dengan ukuran berbeda di-broadcast satu sama lain, sehingga keduanya memiliki bentuk yang kompatibel (selama memenuhi syarat tertentu).

Dengan trik stride, kita tidak perlu membuat duplikat yang tidak perlu di memori.

B = mp.ndarray.ndarray_from_list([5, 5, 5], 3)

print("Mula-mula:")
mp.ndarray.print_ndarray(B)


# Dua baris berikut ini adalah proses broadcasting
# ndarray ukuran (3,) menjadi (3, 3)
B.shape = [3] + B.shape  # Prepend menambah dimensi berukuran 3 di depan
B.strides = [0] + B.strides  # Pepend stride untuk dimensi yang baru dengan 0

print()
print("Setelah broadcasting:")
mp.ndarray.print_ndarray(B)

Output:

Mula-mula:
array([3., 2., 1.])

Setelah broadcasting:
array([[3., 2., 1.],
       [3., 2., 1.],
       [3., 2., 1.]])

Mari bandingkan hasil debug_print() ndarray sebelum dan sesudah broadcasting.

SEBELUM BROADCASTING
{'actual_data': [3, 2, 1],
 'intended_data': [3, 2, 1],
 'shape': [3],
 'strides': [1]}

SETELAH BROADCASTING
{'actual_data': [3, 2, 1],
 'intended_data': [3, 2, 1, 3, 2, 1, 3, 2, 1],
 'shape': [3, 3],
 'strides': [0, 1]}

Lagi-lagi, yang berubah hanya shape dan strides, dan data di memori tidak berubah sama sekali. Dengan shape dan strides yang demikian, persepsi user akan dihadapkan dengan data ndarray yang (secara linear) seperti pada intended_data.

Ini juga menjawab pertanyaan mengapa kita tidak menggunakan len(self.data) di method get_size()untuk memperoleh ukuran ndarray. Untuk contoh di atas, ekspresi len(self.data) akan menghasilkan nilai 3, sementara yang kita harapkan adalah 9 (karena broadcasting). Maka, prod(self.shape) lebih tepat, karena ukuran ndarray selalu bergantung pada bentuknya.

Lebih banyak tentang broadcasting dan operasi aritmatika via universal function akan dibahas di bagian-bagian selanjutnya.


Next: fancy indexing, slicing, printing, ...

*** Bersambung ***